Pseudorandom Functions from Isogenies

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 key-exchange and message authentication codes (let $\text{MAC}_k(m) = F_k(m)$).

Naor-Reingold 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 Naor-Reingold 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 Diffie-Hellman (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 ¹.

Efficiency

The evaluation of $F_{\textbf{a}}$ consists of ²:

• $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 isogeny-based cryptography, which are conjecturally post-quantum:

• ‘Cryptographic Group Actions and Applications’ by Alamati, De Feo, Montgomery and Patranabis. ³
• ‘Oblivious Pseudorandom Functions from Isogenies’ by Boneh, Kogan and Woo. ⁴
• ‘SiGamal: A supersingular isogeny-based PKE and its application to a PRF’ by Moriya, Onuki and Takagi. ⁵

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 Naor-Reingold-like 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 group-action 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 ⁶. 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 Group-Action 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 ³ explore other cryptographic primitives that can be built from group actions, whilst Moriya, Onuki and Takagi ⁵ implement and evaluate their constriction based on the supersingular isogeny-based PKE called SiGamal, a variant of CSIDH.

References