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

• ‘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 isogeny-based 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 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 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 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 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 isogeny-based PKE called SiGamal, a variant of CSIDH.

## References

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

2. “Pseudo-random generators and pseudo-random functions: cryptanalysis and complexity measures” by Thierry Mefenza Nountu. (2017).

3. “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

4. “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).

5. “SiGamal: A supersingular isogeny-based 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

6. “CSIDH: an efficient post-quantum 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).