In this blogpost we will assume knowledge of CSIDH (see previous blogpost). Basic knowledge of pseudorandom functions will be useful.
What is a Pseudorandom Function?
Intuitively, a pseudorandom function (PRF) is a function that “looks like” a random function. We now define it more formally.
Firstly, we let $F: ${$0,1$}$^* \times ${$0,1$}$^* \rightarrow ${$0,1$}$^*$. We then define $F_k(x) = F(k,x)$, and the first input is called the key. For simplicitly of notation we assume $F$ is length preserving, meaning that F(k, x) is only defined if $\vert k \vert = \vert x \vert$, in which case $\vert F(k, x) \vert = \vert k \vert = \vert x \vert$. It is important to note that choosing a uniform $k \in ${$0,1$}$^n$ is equivalent to choosing the function $F_k: ${$0,1$}$^n \rightarrow ${$0,1$}$^n$.
Let $\text{Func}_n$ be the set of all functions mapping {$0,1$}$^n$ to {$0,1$}$^n$.
Definition: $F = ${$F_k$} is a pseudorandom function if $F_k$, for uniform key $k \in ${$0,1$}$^n$ is indistinguishable from a uniform function $f \in \text{Func}_n$
Formally, $F$ is a pseudorandom function if, for all polynomial time $\mathcal{D}$
\[\vert \mathbb{P}_{f \leftarrow \{0,1\}^n}[\mathcal{D}^{F_k}=1]  \mathbb{P}_{f \leftarrow \text{Func}_n}[\mathcal{D}^{f(\cdot)}=1] \vert < \epsilon(n)\]where $\epsilon$ is a negligible function. Here $\mathcal{D}^{F_k}$ means $\mathcal{D}$ is given ‘oracle access’ to $F_k$ where $k$ is chosen uniformly. This means that $\mathcal{D}$ is allowed to give inputs to the fucntion and get back the corresponding outputs. $\mathcal{D}$ cannot, however, look ‘inside’ the funtion and cannot see anything about the value $k$ being used, apart from what it learns from the inputs and outputs it sees. We define $\mathcal{D}^{f(\cdot)}$ similarly.
We also want this function family to be efficiently computable, meaning that given $k$ and $x$, $F_k(x)$ can be evaluated efficietly.
Application of PRFs
PRFs can be used for encryption. Indeed, let $F_k$ be a PRF where $k$ is the private key and let $r$ be random string in the domain of $F_k$. For a message $m$, we define the ciphertext to be $(F_k(r) \oplus m, r)$. If {$F_k$} is a pseudorandom function family then this encryption scheme is semantically secure, meaning that if an adversary is allowed to choose between two plaintexts $m_0$ and $m_1$, and they receive an encryption of either plaintext, they cannot guess if it was $m_0$ or $m_1$ with probability better than $1/2$.
Other applications include keyexchange and message authentication codes (let $\text{MAC}_k(m) = F_k(m)$).
NaorReingold PRF
In 1997, Naor and Reingold construsted a family of pseudorandom functions [1], which take as input {$0, 1$}$^n$ (for some parameter $n$) and output an element in a multiplicative group $\mathbb{G}$ of prime order $l$, generated by $g \in \mathcal{G}$.
The construction is as follows.
Set the secret key to be the vector $\textbf{a} = (a_1, \dots, a_n) \in ((\mathbb{Z}/l\mathbb{Z})^*)^n$. The NaorReingold function $F_{\textbf{a}}:${$0,1$}$^n \rightarrow \mathbb{G}$ is defined by
\[F_{\textbf{a}}(x_1, \dots, x_n) = g^{\prod_{i=1}^n a_i^{x_i} \mod l}\]This defines a family of functions {$F_{\textbf{a}}$}.
To lighten notation we often use an integer $x \in ${$0, 1, \dots, 2^n  1$}, which implicitly defines $(x_1, \dots, x_n) \in ${$0, 1$}$^n$, the bit representation of $x$ with extra leading zeros if necessary.
Security
Naor and Reingold showed this function is a pseudorandom function assuming the hardness of the Decisional DiffieHellman (DDH) problem. This assumption states that given a cyclic group $\mathbb{G} = \langle g \rangle$ and elements $g$, $g^x$ and $g^y$, no efficient algorithm can distinguish between $g^{xy}$ and an element picked uniformly at random in $\mathbb{G}$. This assumption has been used in proving the security of other cryptographic schemes, such as the ElGamal encryption scheme ^{1}.
Efficiency
The evaluation of $F_{\textbf{a}}$ consists of ^{2}:
 $n$ modular multiplications in $\mathbb{Z}/l\mathbb{Z}$, from calculating $\prod_{i=1}^n a_i^{x_i} \mod l$ in the exponent;
 1 modular exponentiation in $\mathbb{G}$, from calculating $g^P$ where $P = \prod_{i=1}^n a_i^{x_i} \mod l$.
These can be efficiently calculated, and therefore the evaluation of $F_{\textbf{a}}$ is efficient for all $\textbf{a} \in ((\mathbb{Z}/l\mathbb{Z})^*)$.
PRFs from Isogenies
At Asiacrypt 2020 there were three papers that proposed PRFs using isogenybased cryptography, which are conjecturally postquantum:
 ‘Cryptographic Group Actions and Applications’ by Alamati, De Feo, Montgomery and Patranabis. ^{3}
 ‘Oblivious Pseudorandom Functions from Isogenies’ by Boneh, Kogan and Woo. ^{4}
 ‘SiGamal: A supersingular isogenybased PKE and its application to a PRF’ by Moriya, Onuki and Takagi. ^{5}
Here we will present the construction by Boneh, Kogan and Woo.
We recall the definition of a group action: $G$ acts on a set $S$ is there is a map $\star: G \times S \rightarrow S$ such that for all $s \in S$ and $g, h \in G$, we have:
 $g \star (h \star s)) =(gh) \star s$
 $1 \star s = s$, where 1 is the identity in $G$.
We say $\star$ is transitive if, for all $s, s’ \in S$, there exists $g \in G$ such that $g \star s = s’$.
We say $\star$ is faithful if $g \star s = s$ if and only if $g = 1$.
Boneh, Kogan and Woo showed how to build a NaorReingoldlike PRF using group actions. Let $G$ be an abelian finite group that acts on $S$ transitively and faithfully. Let $s_0 \in S$ be a fixed element. Then, we define $F_k$, where $k = (k_0, \dots, k_n)$ is our secret key, with input space is {$0, 1$}$^n$ as:
\[F_k(x_1, \dots, x_n) = (k_0k_1^{x_1}k_2^{x_2}\cdots k_n^{x_n}) \star s_0\]This construction defines a secure PRF provided that the groupaction variant of the DDH assumption holds in $G$. Namely, with $G$, $S$ as above and $s \in S$, if $a, b, c$ are sampled randomly from $G$ then the following two tuples are computationally indistinguishable:
 $(a \star s, b \star s, (ab) \star s)$
 $(a \star s, b \star s, c \star s)$
We can then instantiate this using isogenies via the CSIDH group action ^{6}. More precisely, let $p = 4l_1 \cdots l_n  1$ be prime with $l_i$ small distinct odd primes and $p \cong 3 \mod 8$. Fix a supersingular elliptic curve $E_0: y^2 = x^3 + x$ over $\mathbb{F}_p$. This will be our fixed element ‘$s_0$’. Let End$_{\mathbb{F}_p}(E_0)$ be the $\mathbb{F}_p$rational endomorphisms of $E_0$. We will denote this as $\mathcal{O}$. Then the class group $Cl(\mathcal{O})$ is a finite abelian group that acts transitively and faithfully on $S$, the set of supersingular elliptic curves over $\mathbb{F}_p$.
We will set our key ‘$k$’ to be $([\mathfrak{a}_0], …, [\mathfrak{a}_n])$, for $[\mathfrak{a}_i] \in Cl(\mathcal{O})$. We, therefore, have
\[F_k(x_1, ..., x_n) = j([\mathfrak{a}_n]^{x_n}\cdots [\mathfrak{a}_1]^{x_1} [\mathfrak{a}_0] \cdot E_0)\]where $j(\cdot)$ means we are taking the $j$invariant of the resulting elliptic curve.
Assuming that the GroupAction DDH is hard in the CSIDH setting, this construction gives us a PRF.
Boneh, Kogan and Woo use this PRF to build an oblivious pseudorandom function, which informally means that information is concealed from two parties involved in a PRF.
Alamati, De Feo, Montgomery and Patranabis ^{3} explore other cryptographic primitives that can be built from group actions, whilst Moriya, Onuki and Takagi ^{5} implement and evaluate their constriction based on the supersingular isogenybased PKE called SiGamal, a variant of CSIDH.
References

“A public key cryptosystem and a signature scheme based on discrete logarithms” by Taher ElGamal. IEEE transactions on information theory (1985). ↩

“Pseudorandom generators and pseudorandom functions: cryptanalysis and complexity measures” by Thierry Mefenza Nountu. (2017). ↩

“Cryptographic Group Actions and Applications” by Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis. International Conference on the Theory and Application of Cryptology and Information Security (2020). ↩ ↩^{2}

“Oblivious Pseudorandom Functions from Isogenies” by Dan Boneh, Dmitry Kogan, and Katharine Woo. International Conference on the Theory and Application of Cryptology and Information Security (2020). ↩

“SiGamal: A supersingular isogenybased PKE and its application to a PRF” by Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi. International Conference on the Theory and Application of Cryptology and Information Security (2020). ↩ ↩^{2}

“CSIDH: an efficient postquantum commutative group action” by Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. International Conference on the Theory and Application of Cryptology and Information Security (2018). ↩