1515 lines
92 KiB
Plaintext
1515 lines
92 KiB
Plaintext
A Post-Quantum Oblivious PRF from Isogenies
|
||
|
||
Andrea Basso
|
||
|
||
University of Birmingham, United Kingdom
|
||
University of Bristol, United Kingdom
|
||
andrea.basso@bristol.ac.uk
|
||
|
||
|
||
|
||
|
||
Abstract. An oblivious pseudorandom function, or OPRF, is an im-
|
||
portant primitive that is used to build many advanced cryptographic
|
||
protocols. Despite its relevance, very few post-quantum solutions exist.
|
||
In this work, we propose a novel OPRF protocol that is post-quantum,
|
||
verifiable, round-optimal, and moderately compact.
|
||
Our protocol is based on a previous SIDH-based construction by Boneh,
|
||
Kogan, and Woo, which was later shown to be insecure due to an attack
|
||
on its one-more unpredictability.
|
||
We first propose an efficient countermeasure against this attack by re-
|
||
defining the PRF function to use irrational isogenies. This prevents a
|
||
malicious user from independently evaluating the PRF. The SIDH-based
|
||
construction by Boneh, Kogan, and Woo is also vulnerable to the recent
|
||
attacks on SIDH. We thus demonstrate how to efficiently incorporate the
|
||
countermeasures against such attacks to obtain a secure OPRF protocol.
|
||
To achieve this, we also propose the first proof of isogeny knowledge that
|
||
is compatible with masked torsion points, which may be of independent
|
||
interest.
|
||
Lastly, we design a novel non-interactive proof of knowledge of parallel
|
||
isogenies, which reduces the number of communication rounds of the
|
||
OPRF to the theoretically-optimal two.
|
||
Putting everything together, we obtain the most compact post-quantum
|
||
verifiable OPRF protocol.
|
||
|
||
Keywords: Oblivious Pseudorandom Functions · Isogenies · SIDH
|
||
|
||
|
||
|
||
1 Introduction
|
||
|
||
An oblivious pseudorandom function (OPRF) is a two-party protocol between a
|
||
user and a server. The two parties obliviously evaluate a PRF on a user-controlled
|
||
input with a secret key held by the server. After engaging in the protocol, the
|
||
user learns only the output of the PRF on their chosen input, while the server
|
||
does not learn anything, neither the user’s input nor the output of the function.
|
||
Oblivious PRFs can also satisfy a stronger property called verifiability: in a
|
||
verifiable OPRF (vOPRF), the server initially commits to its secret key, and
|
||
during the execution of the protocol it provides a proof that it has behaved
|
||
honestly and it has used the previously committed secret key.
|
||
2 Andrea Basso
|
||
|
||
Oblivious PRFs have widespread applications in privacy-preserving construc-
|
||
tions. For instance, the web browser Microsoft Edge uses an OPRF-based proto-
|
||
col to detect compromised passwords. Another practical use case of OPRFs is the
|
||
privacy-preserving authorisation mechanism known as Privacy Pass [11]. OPRFs
|
||
are also used within OPAQUE [22], a strong asymmetric password-authenticated
|
||
key exchange. Overall, OPRFs are a fundamental tool for developing privacy-
|
||
preserving solutions.
|
||
It is possible to build an OPRF using generic multi-party computation tech-
|
||
niques, but such solutions can be inefficient, and they require more rounds of
|
||
communication than what an ad-hoc construction can achieve. Indeed, highly-
|
||
efficient and round-optimal (i.e., with two rounds) constructions exist based on
|
||
Diffie-Hellman [20] or RSA blind signatures [9]. All such constructions are vulner-
|
||
able to quantum attacks, and very few quantum-resistant OPRFs are reported
|
||
in the literature. The first quantum-secure verifiable OPRF was proposed by
|
||
Albrecht, Davidson, Deo and Smart [1]. The protocol is based on the learning-
|
||
with-errors problem and the short-integer-solution problem in one dimension,
|
||
and it only requires two rounds of communication. However, the construction
|
||
can be characterized as a feasibility result, as a single OPRF execution requires
|
||
communicating hundreds of gigabytes of data. The only other post-quantum so-
|
||
lutions were proposed by Boneh, Kogan, and Woo [5]. The authors proposed two
|
||
moderately-compact OPRFs based on isogenies, one relying on SIDH and one on
|
||
CSIDH. The protocol based on CSIDH is a non-verifiable, three-round OPRF,
|
||
which is obtained by combining a Naor-Reingold PRF [27] with a CSIDH-based
|
||
oblivious transfer protocol [24] to make the PRF evaluation oblivious. The OPRF
|
||
based on SIDH is verifiable, but requires an even higher number of communi-
|
||
cation rounds, since the verifiability proof is highly interactive. A later work by
|
||
Basso, Kutas, Merz, Petit and Sanso [4] cryptanalyzed the SIDH-based OPRF by
|
||
demonstrating two attacks against the one-more unpredictability of the protocol,
|
||
i.e. it showed that a malicious user can recover sufficient information to indepen-
|
||
dently evaluate the PRF on any input. The first attack is polynomial-time, but
|
||
it can be easily prevented with a simple countermeasure; the second attack is
|
||
subexponential but still practical, and the authors argue that there is no simple
|
||
countermeasure against it. More recently, a series of works [7,25,28] developed
|
||
an efficient attack on SIDH that also extends to the SIDH-based OPRF.
|
||
|
||
Contributions. In this work, we propose an OPRF protocol that is post-
|
||
quantum secure, verifiable, round-optimal, and moderately compact (≈9 MB
|
||
per execution), with a security proof in the UC framework [6] in the random-
|
||
oracle model. To do so, we follow the same high-level approach as the SIDH-based
|
||
OPRF by Boneh, Kogan, Woo [5], but with the following changes:
|
||
– We propose an efficient countermeasure against the one-more unpredictabil-
|
||
ity attack by Basso, Kutas, Merz, Petit, and Sanso [4]. We modify the PRF
|
||
definition, and in particular we use irrational isogenies to map the user’s
|
||
input to an elliptic curve. In this way, the information that allowed an at-
|
||
tacker to independently evaluate the PRF is no longer defined over a field of
|
||
A Post-Quantum Oblivious PRF from Isogenies 3
|
||
|
||
small extension. A malicious user may still attempt to carry out the attack
|
||
from [4], but this would now require the attacker to work with points with
|
||
exponentially many coordinates over the base field, which makes the attack
|
||
infeasible. Besides preventing the attack, this change results in a smaller
|
||
prime and a more compact protocol.
|
||
– We discuss how to integrate MSIDH, a recently-proposed countermeasure [15]
|
||
against the SIDH attacks that relies on masked torsion, into the OPRF pro-
|
||
tocol. This requires using longer isogenies and a larger prime, but a series
|
||
of optimizations allow us to maintain a reasonable communication cost. To
|
||
integrate MSIDH, we also propose the first zero-knowledge proof of knowl-
|
||
edge that can guarantee the correctness of an MSIDH public key, which may
|
||
be of independent interest. The proof relies on splitting the masking value
|
||
into three multiplicative shares: this enables the prover to build a commu-
|
||
tative SIDH square and reveal a single edge, together with the torsion point
|
||
images, without leaking any information about the witness. Repeating the
|
||
process multiple times yields a proof with negligible soundness error.
|
||
– We propose a novel proof of knowledge that can guarantee that two isogenies
|
||
are parallel, i.e. they are computed by applying the same secret key to two
|
||
starting curves and torsion points. The protocol is obtained by evaluating two
|
||
proofs of isogeny knowledge in parallel with correlated randomness. The proof
|
||
can be proved zero-knowledge under a new yet mild assumption. Such a proof
|
||
can be used by the server to show that it has used a previously committed
|
||
secret key, which is the key ingredient to make the OPRF verifiable. Since
|
||
the proof is a proof of knowledge, it can be made non-interactive through
|
||
standard transformations; this makes the proposed OPRF the first isogeny-
|
||
based OPRF to be round-optimal.
|
||
|
||
|
||
Paper organization. In Section 2, we introduce the main constructions needed
|
||
for the rest of the paper. In Section 3, we present the OPRF ideal functionality,
|
||
together with the security notions and assumptions needed to implement it.
|
||
Section 4 presents novel countermeasures against the one-more unpredictability
|
||
attack by Basso, Kutas, Merz, Petit and Sanso, while Section 5 discusses how
|
||
to prevent the SIDH attacks, and Section 6 presents the new proof of parallel
|
||
isogeny used to achieve verifiability. In Section 7, we put everything together
|
||
to obtain the new OPRF protocol, estimate its communication complexity, and
|
||
compare it with the existing solutions.
|
||
|
||
|
||
2 Preliminaries
|
||
|
||
2.1 SIDH
|
||
|
||
The Supersingular Isogeny Diffie-Hellman (SIDH) [19] is a key-exchange pro-
|
||
tocol based on isogenies between supersingular elliptic curves. For informa-
|
||
tion on elliptic curves and isogenies, we refer the reader to [29]. The proto-
|
||
col parameters include a prime p of the form p = ABf − 1, where A and B
|
||
4 Andrea Basso
|
||
|
||
are smooth coprime integers and f a small cofactor, a supersingular curve E0
|
||
defined over Fp2 , and the basis PA , QA and PB , QB that span, respectively,
|
||
$
|
||
E0 [A] and E0 [B]. One party samples a secret key a ← − ZA , computes the
|
||
isogeny ϕA : E0 → EA := E0 /⟨PA + [a]QA ⟩, and publishes pkA = (EA , RA =
|
||
ϕA (PB ), SA = ϕA (QB )). The second party, proceeds similarly by sampling a se-
|
||
$
|
||
cret key b ←− ZB , computing ϕB : E0 → EB := E0 /⟨PB + [b]QB ⟩, and revealing
|
||
pkB = (EB , RB = ϕB (PA ), SB = ϕB (QA )). Then, both parties can agree on
|
||
a shared secret by translating their secret isogeny to the starting curve in the
|
||
other party’s public key using the revealed torsion information. In other words,
|
||
the first party computes ϕ′A : EB → EAB := EB /⟨RB + [a]SB ⟩, and the second
|
||
party computes ϕ′B : EA → EBA := EA /⟨RA + [b]SA ⟩. The codomain curves
|
||
EAB and EBA are isomorphic, and thus their j-invariant is the same and pro-
|
||
vides the shared secret of the key exchange. Note that it is possible to represent
|
||
the points in the public keys more compactly than two x-coordinates, which re-
|
||
quires 4 log p bits. If the points are expressed in terms of a canonical basis , i.e. a
|
||
basis deterministically computed from the curve, their coefficients only require
|
||
4 log A or 4 log B bits [10]. In the rest of the paper, we write P, Q = BN (E) for
|
||
a canonical basis of order N on E. We also refer to the setup described above
|
||
as the SIDH square (E0 , EA , EB , EAB ) with edges (ϕA , ϕB , ϕ′A , ϕ′B ). The Weil
|
||
pairing between points P, Q ∈ E[N ], for some curve E and integer N , is denoted
|
||
by eN (P, Q), and it satisfies the property eN (ϕ(P ), ϕ(Q)) = eN (P, Q)deg ϕ .
|
||
|
||
The SIDH attacks. The security of the SIDH protocol hinges on the hardness
|
||
of recomputing the secret isogenies given the public key. While the problem of
|
||
finding an isogeny between two curves is believed to be hard, the presence of
|
||
torsion point images in SIDH makes it easier since more information is revealed
|
||
about the secret isogeny. In a series of works by Castryck and Decru [7], Maino,
|
||
Martindale, Panny, Pope, and Wesolowski [25], and Robert [28], the authors
|
||
propose a polynomial-time algorithm that can compute an isogeny of smooth
|
||
degree d given the domain and codomain
|
||
√ curves, the degree d, and the image of
|
||
a torsion basis of order at least d. This fully breaks the SIDH key exchange
|
||
and all protocols based on it. Some countermeasures have been proposed [15],
|
||
based on either secret-degree isogenies or on masked torsion images. We discuss
|
||
these approaches in the context of the OPRF protocol in Section 5.
|
||
|
||
2.2 The OPRF construction by Boneh, Kogan, Woo
|
||
Boneh, Kogan, and Woo [5] introduced a verifiable OPRF protocol based on
|
||
SIDH, which uses a prime p of the form p = NM NB NK N1 N2 f − 1, where
|
||
the values Ni are coprime smooth integers and f is a small cofactor. Initially,
|
||
the server commits to its key k by publishing the curve EC obtained as the
|
||
codomain of the NK -isogeny starting from Ẽ with kernel ⟨P̃ + [k]Q̃⟩, where the
|
||
values Ẽ, P̃ , Q̃ are protocol parameters. The commitment also includes a zero-
|
||
knowledge proof πC of the correctness of the computation. Then, to evaluate the
|
||
PRF on input m ∈ M, where M defines the input space, the user computes an
|
||
A Post-Quantum Oblivious PRF from Isogenies 5
|
||
|
||
isogeny ϕm of degree NM by hashing the input with a function H and computing
|
||
ϕm : E0 → Em := E0 /⟨P + [H(m)]Q⟩, where the curve E0 and the points P, Q
|
||
are also protocol parameters. Then, the user blinds the curve Em by computing
|
||
a second isogeny ϕb : Em → Emb of degree NB . The user sends the curve Emb
|
||
and the torsion images RK = ϕb ◦ ϕm (PK ), SK = ϕb ◦ ϕm (QK ) to the server,
|
||
where the points PK , QK are also protocol parameters of order NK . The user
|
||
also provides a non-interactive zero-knowledge proof that torsion information
|
||
was honestly computed. The server validates the proof, computes the isogeny
|
||
ϕk : Emb → Embk := Emb /⟨RK + [k]SK ⟩ based on its secret key k, and sends
|
||
the curve Emrk , the image ϕk (Emb [NB ]), and a non-interactive zero-knowledge
|
||
proof of correctness to the user. Then, the server and the user engage in an in-
|
||
teractive protocol where the server proves that the isogeny ϕk has used the same
|
||
key k as the committed value. If the user is convinced, they use the provided
|
||
torsion information to undo the blinding isogeny, i.e. to compute the translation
|
||
of the dual of the blinding isogeny, to obtain the curve Emk . The output of the
|
||
OPRF is then the hash H m, j(Emk ), (EC , πC ) . The main exchange, without
|
||
the commitments and the proofs, is represented in Fig. 1.
|
||
|
||
ϕm
|
||
E0 Em
|
||
ϕb
|
||
|
||
|
||
ϕ′k Emb
|
||
|
||
ϕ′m
|
||
Ek Emk ϕk
|
||
|
||
|
||
ϕ̂′b
|
||
Embk
|
||
|
||
|
||
Fig. 1: The OPRF construction by Boneh, Kogan, and Woo. The protocol,
|
||
without the relevant zero-knowledge proofs, is represented by the solid lines: the
|
||
isogenies −→ (ϕm , ϕb , ϕ̂′b ) are computed by the client, while the isogeny −→
|
||
(ϕk ) is computed by the server. The isogenies ⇝ represent the PRF evaluation,
|
||
and the isogenies 99K are relevant to the attack presented in [4]. The figure is
|
||
based on Fig. 1 of [4].
|
||
|
||
|
||
|
||
|
||
2.3 The BKMPS attacks
|
||
Basso, Kutas, Merz, Petit, and Sanso [4] proposed two attacks against the one-
|
||
more unpredictability of the OPRF protocol by Boneh, Kogan, Woo [5] OPRF.
|
||
In the first attack, an attacker who acts as a malicious user engages in the
|
||
OPRF with a message isogeny ϕm with kernel generator a point M , of order ℓe .
|
||
The attacker repeats the process with message isogenies with kernel generators
|
||
[ℓ]M, [ℓ2 ]M, . . . , [ℓe ]M . The outputs of the PRF are the curves that lie on the
|
||
isogeny path of ϕ′m : Ek → Emk (see Fig. 1), which allows the attacker to
|
||
compute a generator of the kernel of such isogeny. The recomputed generator is
|
||
6 Andrea Basso
|
||
|
||
a scalar multiple ϕ′k (M ), where ϕ′k is the isogeny parallel to the server’s secret
|
||
isogeny, i.e. its kernel is generated by Pk + [k]Qk . By repeating this process three
|
||
times with points M1 , M2 and M3 := M1 + M2 (where M1 and M2 are linearly
|
||
independent), the attacker obtains
|
||
|
||
R := [α]ϕ′k (M0 ), S := [β]ϕ′k (M1 ),
|
||
T := [γ]ϕ′k (M3 ) = [γ/α]R + [γ/β]S,
|
||
|
||
for some unknown values α, β, γ. By expressing T in terms of R and S, the at-
|
||
tacker obtains the values γ/α and γ/β and the points R′ := [γ/α]R = [γ]ϕ′k (M0 )
|
||
and S ′ := [γ/β]S = [γ]ϕ′k (M1 ). Finally, the attacker can evaluate the PRF on
|
||
any input m by computing EK /⟨R′ + [H(m)]S ′ ⟩. The attack runs in polynomial
|
||
time, but it crucially relies on using message isogenies ϕm of varying degree. The
|
||
attack can be thwarted by server checking the order of the isogeny ϕm , which is
|
||
possible because of the proof of knowledge provided by user.
|
||
The authors of [4] also propose a second attack that cannot be easily pre-
|
||
vented. The attack proceeds in a similar way to the previous one, but the ma-
|
||
licious user uses only isogenies of full degree. To obtain the curves on the path
|
||
of ϕm , the attacker needs to find the middle curve between two PRF outputs.
|
||
This introduces a trade-off between the complexity of the attack and the number
|
||
of queries. Minimizing both yields a subexponential yet practical attack on the
|
||
one-more unpredictability of the protocol.
|
||
|
||
|
||
3 Oblivious pseudorandom functions
|
||
The security properties of an OPRF can be hard to define. Oblivious pseudoran-
|
||
dom functions were originally proposed by Naor and Reingold [27], who defined
|
||
an OPRF via an ideal functionality. Subsequent work [16,23] defined OPRFs
|
||
in terms of the two-party computation (k, x) 7→ (⊥, f (k, x)), but such a def-
|
||
inition has several drawbacks. On one side, it is hard to build protocols that
|
||
satisfy such a definition, because the security proof would require extracting the
|
||
user’s input, while at the same the definition is not secure enough, because it
|
||
does not guarantee any security under composability. Since OPRFs are mainly
|
||
used as building blocks in larger protocols, such a security guarantee is highly
|
||
needed. For these reasons, Jarecki et al. [20,22] proposed new definitions in the
|
||
UC framework [6]. To avoid extracting the user’s input, the ideal functionality
|
||
introduces a ticketing system that increases a counter when the PRF is evaluated
|
||
and decreases the counter when the user receives the PRF output. This captures
|
||
the idea that a malicious user should learn only the PRF output for one input
|
||
for each interaction. This results in the definition of Fig. 2, which is based on
|
||
the definitions by Jarecki et al. [20,21,22].
|
||
|
||
3.1 Security assumptions
|
||
To prove that the OPRF protocol we propose implements the functionality of
|
||
Fig. 2, we will make use of the properties listed in this section. Since our protocol
|
||
A Post-Quantum Oblivious PRF from Isogenies 7
|
||
|
||
|
||
Parameters: The PRF output ℓ, polynomial in the security parameter λ.
|
||
|
||
Convention: For every identifier S, the counter tx[S] is initially set to zero. For
|
||
every value π ∈ {0, 1}∗ and x ∈ {0, 1}∗ , the value F (π, x) is initially undefined,
|
||
and whenever such a value is referenced, the functionality assigns a random ℓ-bit
|
||
$
|
||
− {0, 1}ℓ .
|
||
string F (π, x) ←
|
||
|
||
Initialization
|
||
|
||
– On message init from party S, forward (init, S) to the adversary A.
|
||
– On message (Param, S, π) from adversary A, and if param[S] is undefined,
|
||
then set param[S] = π.
|
||
|
||
Evaluation
|
||
|
||
– On message (Eval, S, x) from P ∈ {U, A}, record ⟨P, x⟩ and forward the
|
||
message (Eval, P, S) to A.
|
||
– On message ServerComplete from server S, send (ServerComplete, S) to
|
||
A and increment tx[S].
|
||
– On message (UserComplete, P, π) from A, retrieve the record ⟨P, x⟩, delete
|
||
it from the list of records, and decrement tx[S] if there exists an honest server
|
||
S such that param[S] = π; abort if no such record exists or if tx[S] = 0. Then,
|
||
send (Eval, π, F (π, x)) to P .
|
||
|
||
|
||
|
||
|
||
Fig. 2: The FvOPRF functionality.
|
||
|
||
|
||
and security proof follows the same high-level structure as that of the OPRF
|
||
protocol by Boneh, Kogan, and Woo [5], these properties are also based on
|
||
those of the augmentable commitment framework proposed in [5]. Unlike [5],
|
||
we avoid the abstraction of augmentable commitments due to its restrictiveness
|
||
(the counteremasures of Section 4 would not be possible within that framework),
|
||
and we prefer an explicit description throughout this work.
|
||
|
||
Correctness. Firstly, we require the OPRF to be correct, i.e. the output of
|
||
the protocol is the output of function that deterministically depends only on the
|
||
user’s input and the server’s secret key. In other words, we want that the blinding
|
||
process that guarantees the obliviousness of the user’s input does not affect the
|
||
final output. In the context of our protocol, we want that the unblinding isogeny
|
||
undoes the effect of the blinding isogeny. This is contained in the following
|
||
lemma, whose proof follows from the correctness of the SIDH protocol [19].
|
||
Lemma 1 (Correctness). Let p be a prime of the form p = NB NK f − 1, where
|
||
NB , NK , f are smooth coprime integers. Let E0 be a supersingular elliptic curve
|
||
defined over Fp2 and let PB , QB and PK , QK be respectively a basis of E0 [NB ]
|
||
and E0 [NK ]. Let also b and k be two values in ZNB and ZNK . Then, consider the
|
||
8 Andrea Basso
|
||
|
||
isogenies
|
||
|
||
ϕB : E0 → EB := E0 /⟨PB + [b]QB ⟩,
|
||
ϕK : E0 → EK := E0 /⟨PK + [k]QK ⟩,
|
||
ϕ′k : EB → EBK := EB /⟨ϕB (PK ) + [k]ϕB (QK )⟩.
|
||
|
||
If RB , SB is a basis of EB [NB ] and the values b0 , b1 satisfy ker ϕ̂B = ⟨[b0 ]RB +
|
||
[b1 ]SB ⟩, then we have
|
||
|
||
j (EBK /⟨[b0 ]ϕ′k (RB ) + [b1 ]ϕ′k (SB )⟩) = j(EK ).
|
||
|
||
|
||
Input hiding. To ensure that the OPRF is oblivious, we want that the server
|
||
does not learn the user’s input. That holds in the strongest sense, i.e. the server
|
||
should not learn the user’s input even when the input is randomly chosen between
|
||
two inputs chosen by the server. In other words, the user must apply a blinding
|
||
step that fully hides the chosen input. In the context of isogenies, we want the
|
||
following problem to be hard.
|
||
|
||
Problem 1. Let p be a prime of the form p = NB NK f − 1, where NB NK , f are
|
||
smooth coprime integers. Let E0 and E1 be two supersingular elliptic curves
|
||
defined over Fp2 and chosen by the adversary, and let P0 , Q0 and P1 , Q1 be a
|
||
basis of E0 [NK ] and E1 [NK ], respectively, such that eNK (P0 , Q0 ) = eNK (P1 , Q1 ).
|
||
$
|
||
Let i be a random bit, i.e. i ← − {0, 1}, and B a random point in Ei [NB ], and
|
||
write ϕ : Ei → E ′ := Ei /⟨B⟩. Output i given E ′ and faux (ϕ(Pi ), ϕ(Qi )), where
|
||
the latter is some auxiliary torsion information.
|
||
|
||
The hardness of the problem clearly depends on the function faux ; if the tor-
|
||
sion images were directly revealed, Problem 1 would be easy due to the SIDH
|
||
attacks. We thus delay describing the function faux until Section 5, where we dis-
|
||
cuss the SIDH countermeasures and choose faux to reveal the values ϕ(Pi ), ϕ(Qi ),
|
||
both scaled by the same unknown value. In the section, we also state the variant
|
||
of the Decisional Isogeny problem that Problem 1 reduces to.
|
||
|
||
|
||
One-more unpredictability. A key property of an OPRF is that the user
|
||
learns the output of the PRF only on its input of choice. That means that a
|
||
malicious user should not learn the output on more inputs than the number of
|
||
OPRF executions. The BKMPS attack [4] on the OPRF by Boneh, Kogan, and
|
||
Woo [5] targets the one-more unpredictability, since it shows that a malicious
|
||
user can extract enough information to independently evaluate the OPRF on
|
||
any input of their choice. We propose an efficient countermeasure against the
|
||
one-more unpredictability attack in the next section; we thus delay until then
|
||
a formalization of the isogeny-related assumption (see Problem 4) we need to
|
||
guarantee the one-more unpredictability of the OPRF protocol.
|
||
A Post-Quantum Oblivious PRF from Isogenies 9
|
||
|
||
Commitment binding. At the beginning of the OPRF protocol, the server
|
||
commits to a secret key k, so that during each OPRF execution it can prove
|
||
that the same key was used. To guarantee verifiability, we want a commitment
|
||
scheme with an associated proof of input reuse. We propose to commit to a
|
||
key k by fixing a special curve Ẽ with a basis P̃ , Q̃ of Ẽ[NK ] and revealing
|
||
j(Ẽ/⟨P̃ + [k]Q̃⟩). The proof of input reuse, which in the context of isogenies
|
||
becomes a proof of parallel isogenies, is presented in Section 5.2. To guarantee
|
||
that the commitment is binding, we want that the following problem to be hard.
|
||
Problem 2 (Collision finding problem). Let E0 be a supersingular elliptic curve
|
||
of unknown endomorphism ring. Find two distinct isogenies ϕ0 : E0 → E and
|
||
ϕ1 : E0 → E ′ such that j(E0 ) = j(E1 ).
|
||
Problem 2 has been studied in the context of the CGL hash function [8], and
|
||
it has been shown to be heuristically equivalent to the following problem, which
|
||
underpins every isogeny-based protocol [13].
|
||
Problem 3 (Endomorphism Ring problem). Let E be a supersingular elliptic
|
||
curve. Find its endomorphism ring End(E).
|
||
|
||
|
||
4 Countermeasures against the one-more unpredictability
|
||
attack
|
||
The original protocol by Boneh, Kogan and Woo starts by mapping an input
|
||
m to an isogeny ϕm . If we denote with NM the torsion space dedicated to the
|
||
message, the protocol fixes a basis P, Q of E0 [NM ] and computes the isogeny ϕm
|
||
given by
|
||
ϕm : E0 → E0 /⟨P + [H(m)]Q⟩ =: Em , (1)
|
||
where H(·) maps the message m onto an element of ZNM .
|
||
The subexponential attack [4] recovers the image Pk , Qk of the torsion basis
|
||
P, Q, up to scalar multiplication, under the secret isogeny ϕ′k : E0 → Ek . With
|
||
such information, the attacker can evaluate the PRF on any input of their choice.
|
||
The output curve of the PRF is the curve computed as Ek /⟨Pk + [H(m)]k ⟩. The
|
||
attack is subexponential, and it is possible to obtain λ bits of security if the
|
||
2
|
||
isogeny ϕm has degree 2λ (this can be reduced if we limit the number of queries
|
||
the attacker can make). This would require using very long isogenies (the degree
|
||
would be 216,384 for λ = 128) and very large primes.
|
||
Instead, in this section we propose a novel and efficient countermeasure that
|
||
sidesteps these issues. Our main idea is to accept that an attacker may recover
|
||
the curve Ek and points Pk , Qk on it, but to prevent those points from being
|
||
sufficient to evaluate the desired isogeny. To do so, we require that the isogeny
|
||
ϕm has an irrational kernel, i.e. its kernel is defined over a sufficiently-large
|
||
extension field. Such an isogeny can be efficiently computed as a composition
|
||
of rational isogenies. More formally, assume that NM = ℓe , and e is the highest
|
||
power of ℓ that divides p + 1. Then, given an input m ∈ M, we compute the
|
||
isogeny ϕm in the following way:
|
||
10 Andrea Basso
|
||
|
||
1. We first map the message m to two elements in Zℓe through two hash func-
|
||
tions H0 , H1 that are collision resistant. We thus have m0 = H0 (m) and
|
||
m1 = H1 (m).
|
||
2. Given the starting curve E0 and two points P0 , Q0 spanning E0 [ℓe ], we com-
|
||
pute the isogeny ϕ0 : E0 → E1 := E0 /⟨P0 + [m0 ]Q0 ⟩.
|
||
3. We determine a canonical basis P1 , Q1 of E1 [ℓe ] and compute the isogeny
|
||
ϕ1 : E1 → Em := E1 /⟨P1 + [m1 ]Q1 ⟩,
|
||
4. The isogeny ϕm : E0 → Em is the composition ϕ1 ◦ ϕ0 .
|
||
|
||
An attacker may still try to apply the one-more unpredictability attack. In
|
||
the original case, the attacker recovers three isogenies from Ek to Emk and
|
||
they combine their kernel generators to obtain the image points Pk , Qk . In the
|
||
proposed construction, the attacker can still recover three (or more) isogenies
|
||
from Ek to Emk . However, the kernel generators of these isogenies are points of
|
||
order ℓ2e , and thus they are defined only over the extension field Fp2ℓe . This is an
|
||
exponentially large field, and even just representing such a point—let alone doing
|
||
any computation—would be exponential in the security parameter. To guarantee
|
||
security, it is important that the degree of ϕm is a prime power. If the degree
|
||
were a product of prime powers, it is possible to represent a large extension
|
||
by working over several smaller extensions because of the Chinese Remainder
|
||
Theorem. This can reduce the complexity of working over a large extension and
|
||
thus reduce the security of the proposed countermeasures.
|
||
|
||
|
||
ϕ0 ϕ1
|
||
E0 E1 Em
|
||
|
||
|
||
|
||
|
||
Ek ϕm0
|
||
Em0 k ϕm 1
|
||
Emk
|
||
|
||
Fig. 3: Summary of the proposed countermeasure (this does not depict the blind-
|
||
ing/unblinding phase). Isogenies in red are known or can be computed by the
|
||
attacker, isogenies in black are unknown to the attacker, and the dotted isogeny
|
||
represents the missing isogeny that the attacker needs to compute to succeed in
|
||
the attack.
|
||
|
||
|
||
The attacker can work with the kernel generators of only the first half of the
|
||
isogenies and obtain a basis Pk , Qk of order ℓe (see Fig. 3). This allows them
|
||
to evaluate the first isogeny ϕm0 to obtain the curve Em0 k for any message m.
|
||
However, the attacker has no way of computing the remaining isogeny ϕm1 . To
|
||
do so, the attacker would need to map the canonical basis on E1 to Em0 k , which
|
||
does not seem to be possible without knowing the server secret key. Alternatively,
|
||
the attacker could map the points P, Q and Pk , Qk under the isogenies ϕ0 and
|
||
ϕ′k . At least one of the image points on each curve has full order, and the point of
|
||
full order on Em0 k is the image of the point of full order on E1 . This suggest such
|
||
A Post-Quantum Oblivious PRF from Isogenies 11
|
||
|
||
an approach could be used to find a basis, but the second point on each curve is
|
||
always a scalar multiple of the first point1 . Hence, guessing the remaining point
|
||
has exponential complexity ℓe . Lastly, the attacker cannot use a similar strategy
|
||
as the one-more unpredictability attack to recover a basis on Em0 k because the
|
||
curve Em0 k depends on the message m. It thus changes at every interaction, and
|
||
it is hard for an attacker to find two messages that have the same first curve E1
|
||
and Em0 k since we assume that the hash function H0 is collision-resistant. Note
|
||
that we require H0 and H1 to be collision-resistant, but we conjecture that only
|
||
H0 needs to be. Overall, the knowledge of Em0 k does not help the attacker learn
|
||
any information on the curve Emk , which successfully prevents the the one-more
|
||
unpredictability attack.
|
||
|
||
|
||
Optimizations. We can extend this approach to obtain a more compact pro-
|
||
tocol. Rather than limiting ourselves to two isogenies, we can extend this to an
|
||
arbitrary number I. We obtain the optimal case when I is maximal, i.e. when
|
||
deg ϕm = ℓI .
|
||
Let Hi be I distinct random oracles for every i ∈ {1, . . . , I}. Then, given
|
||
an input m and a starting curve E0 , the isogeny ϕm and the curve Em by
|
||
computing an isogeny ϕi determined by Hi (m), generating a canonical basis on
|
||
the codomain curve, and repeating the process I times (see Algorithm 1). We
|
||
refer to this hashing as HI (x), and in the rest of the paper, we write (ϕm , Em ) =
|
||
HI (x) to refer to the function in Algorithm 1; we also write [P0 , P1 , . . . , PI−1 ]E,N
|
||
to denote a list points of order N where the point P0 belongs to E, and the point
|
||
Pi belongs to Ei := Ei1 /⟨Pi−1 ⟩. We refer to this as a sequence, whose associated
|
||
isogeny is the composition of the isogenies Ei → Ei /⟨Pi ⟩.
|
||
|
||
|
||
Algorithm 1 Function HI mapping the input m to the curve Em
|
||
1: for i ← 0 to I − 1 do
|
||
2: Set mi = Hi (m) and Pi , Qi = BM (E);
|
||
3: Compute ϕi : Ei → Ei+1 := Ei /⟨Pi + [mi ]Qi ⟩;
|
||
4: Set ϕm = ϕI−1 ◦ . . . ◦ ϕ0 and Em = EI−1 ;
|
||
5: return ϕm , Em ;
|
||
|
||
|
||
|
||
This technique to compute message isogenies results in a more compact
|
||
OPRF protocol because only the shorter isogenies ϕi need to be defined over
|
||
Fp2 ; thus, using more isogenies can result in a smaller prime p while maintaining
|
||
the same degree of the isogeny ϕm . However, this approach has also a security
|
||
advantage: an attacker can use the BKMPS attack to recover the image of basis
|
||
on Ek , which could potentially be used to recover the isogeny between E0 and
|
||
Ek using the SIDH attacks. While this could be avoided by picking a sufficiently
|
||
long isogeny ϕk , choosing I = e, i.e. setting parameters such that only isogenies
|
||
1
|
||
If ker ϕ = ⟨P + αQ⟩, it follows that ϕ(P ) = −αϕ(Q).
|
||
12 Andrea Basso
|
||
|
||
of degree ℓ have a kernel defined over Fp2 , ensures that an attacker obtains only
|
||
a basis of very small order, which prevents the attack altogether.
|
||
|
||
|
||
A new assumption. We proposed a modified protocol that prevents the ex-
|
||
isting one-more unpredictability attacks. As in the original construction, the
|
||
one-more unpredictability of the resulting protocol relies on the hardness of a
|
||
novel problem, which is the following.
|
||
|
||
Problem 4 (One-more unpredictability). Let p be a prime of the form p = NM NK f −
|
||
1, where NM and NK are smooth coprime integers, and f a cofactor. Let HI be
|
||
a function as in Algorithm 1. Let E0 be a supersingular curve defined over Fp2 ,
|
||
and let K be a point on E0 of order NK . Write ϕK for the isogeny ϕK : E0 →
|
||
EK := E0 /⟨K⟩. Given the curves E0 , EK and an oracle that responds to the
|
||
following queries:
|
||
|
||
– challenge: returns a random sequence [M0 , . . . , MI−1 ]E0 ,NM ,
|
||
– solve([V0 , . . . , VI−1 ]E0 ,NM ): returns j(EV /⟨ϕV (K)⟩), where ϕV is the isogeny
|
||
associated to the input sequence,
|
||
– decide(i, j): returns true if j is equal to the output of a solve query with input
|
||
the response of the i-th challenge query, and false otherwise,
|
||
|
||
For any value n, produce n pairs (i, j) such that decide(i, j) = true with less
|
||
than n solve queries.
|
||
|
||
The problem is based on Game 12 of [5], but compared to it, this game
|
||
involves multiple points during the challenge and solve query to abstract the
|
||
behavior described in the previous section. Moreover, the problem includes the
|
||
countermeasures against the polynomial time attack of [4], i.e. the attacker can
|
||
only query points of the correct order. This can be replicated in the OPRF set-
|
||
ting by checking the order of the isogenies in the proof of isogeny knowledge.
|
||
We included these countermeasures to prevent possible attacks since they are
|
||
inexpensive. However, we conjecture that the problem remains hard even if the
|
||
adversary is allowed to submit solve queries with points of arbitrary order. Fur-
|
||
thermore, the problem remains hard after the SIDH attacks since it does not
|
||
involve exchanging any torsion points.
|
||
|
||
|
||
Countermeasure costs. We briefly discuss the impact of the proposed coun-
|
||
termeasures on the performance of the OPRF protocol. Firstly, we need to de-
|
||
termine the parameters ℓ, e, and I. Keeping in mind the possible SIDH attacks
|
||
based on the recovered torsion on Ek , we choose I to be maximal. We require
|
||
that the degree of the message isogeny is about ≈ 25/2λ to prevent the attack
|
||
proposed in [26]. Hence, we set e = 1 and I = logℓ (25/2λ ).
|
||
The message component NM can then be chosen to be ℓ, to ensure that
|
||
isogenies of degree ℓ have kernel in Fp2 , or one, if torsion points of order ℓ are
|
||
defined over a small extension field. In the latter case, the prime p does not need
|
||
A Post-Quantum Oblivious PRF from Isogenies 13
|
||
|
||
to change to allow computations of the message isogeny. In both cases, not only
|
||
do the proposed countermeasures protect against existing attacks, but also they
|
||
reduce the prime size leading to a more compact and efficient protocol.
|
||
|
||
|
||
5 Countermeasures against the SIDH attacks
|
||
|
||
The recent series of attacks by Castryck and Decru [7], Maino, Martindale,
|
||
Panny, Pope, and Wesolowski [25], and Robert [28] exploits torsion-point infor-
|
||
mation to break SIDH. These attacks trivially translate to the OPRF, where
|
||
any third party can recover both the user’s hashed input (which breaks oblivi-
|
||
ousness) and the server’s secret key. In this section, we discuss how to adapt the
|
||
existing SIDH countermeasures to work in the OPRF setting. After modifying
|
||
the main exchange, we propose a novel proof of isogeny knowledge that works
|
||
together with the countermeasures, which may be of independent interest since
|
||
it is the first proof to prove the correctness of torsion point images in the SIDH-
|
||
with-countermeasure setting. This proof can be used together with the patched
|
||
SIDH to obtain a post-quantum non-interactive key-exchange.
|
||
Combining the countermeasures together with the novel proof of torsion point
|
||
correctness, we obtain an SIDH-based OPRF that is resistant against the SIDH
|
||
attacks. While the countermeasures impose larger parameters, the resulting pro-
|
||
tocol remains the most compact post-quantum vOPRF.
|
||
|
||
|
||
5.1 Protecting the exchange
|
||
|
||
Thus, to guarantee the security of the SIDH-based OPRF we need to rely on
|
||
the masked-torsion countermeasure, as in masked SIDH (MSIDH) [15]. Con-
|
||
sider an isogeny ϕ : E → E ′ of degree d, with a basis P, Q of E[n], for some
|
||
n coprime with d. Given the images P ′ = ϕ(P ), Q′ = ϕ(Q), a second party
|
||
can compute the pushforward of an isogeny with kernel ⟨P + [x]Q⟩ as the
|
||
isogeny with kernel ⟨P ′ + [x]Q′ ⟩. Thus, it is possible to reveal [α]P ′ , [α]Q′ , for
|
||
some random α coprime with the torsion order n, without affecting the correct-
|
||
ness of the protocol. However, this leaks the value α2 from the Weil pairing,
|
||
2
|
||
since en ([α]P ′ , [α]Q′ ) = en (P, Q)α deg ϕ . To ensure that the attacker cannot re-
|
||
cover the value α, MSIDH requires that any value has at least 2λ square roots
|
||
modulo n, hence n needs to be the product of at least λ prime powers. This,
|
||
however, is not enough to guarantee security, as an attacker can guess the correct
|
||
square root modulo some n′ | n with n′ > d1/2 in less than O(2λ ) guesses. It
|
||
is thus also needed that d > n′ , where n′ is the product of the powers of the λ
|
||
largest primes dividing n. From now on, we write n = fMSIDH (λ, d) to denote the
|
||
smallest value n that can guarantee λ bits of security when used in MSIDH with
|
||
an isogeny of degree d. Lastly, the countermeasure analysis in [15] shows that
|
||
MSIDH may be vulnerable when the starting curve has a small endomorphism.
|
||
In our case, such an attack does not apply even if the OPRF starting curve E0
|
||
has a known endomorphism ring with a small endomorphism ι. That is because
|
||
the attack would need a small endomorphism on Em x, but the composition of
|
||
14 Andrea Basso
|
||
|
||
the message and blinding isogeny ϕx ◦ ϕm is sufficiently long that the attack
|
||
does not apply. Even considering the attack on the starting curve Em (remem-
|
||
ber that in the security game the attacker can control the messages), does not
|
||
help: if the attacker can guess the input message, the smallest endomorphism
|
||
known on Em is ϕ̂m ◦ ι ◦ ϕm , which is too large for the attack to apply. Moreover,
|
||
the server computes its isogeny starting from a curve Emx that is sent by the
|
||
user, which generally could be an avenue for attack since MSIDH is insecure for
|
||
special starting curves. However, the user also submits a proof of knowledge of
|
||
an isogeny of long degree between E0 and Emx : this guarantees that the small-
|
||
est known endomorphism is again sufficiently large, which similarly prevents the
|
||
attack against the server’s isogeny.
|
||
We can now formulate the following problem, on whose hardness the input
|
||
hiding property of the OPRF is based.
|
||
|
||
Problem 5 (Decisional MSIDH isogeny problem). Let E0 be a supersingular el-
|
||
liptic curve, with a basis P, Q be of E0 [n]. Distinguish between the following
|
||
distributions:
|
||
|
||
– (E1 , R, S), where E1 is the codomain of a d-isogeny ϕ : E0 → E1 , where d
|
||
is coprime with n, and the points R, S are the masked images of P, Q, i.e.
|
||
$
|
||
R = [α]ϕ(P ) and S = [α]ϕ(Q) for some α ← − Z∗n ;
|
||
– (E1 , R, S), where E1 is a random supersingular elliptic curve and the points
|
||
2
|
||
R, S are a random basis of E1 [n] such that e(R, S) = e(P, Q)α d , for some
|
||
value α.
|
||
|
||
The hardness of the problem clearly depends on the choices of n and d; the
|
||
problem (conjecturally) requires O(2λ ) operations to solve when n > fMSIDH√(λ, d),
|
||
i.e. the product of the λ largest prime powers dividing n is smaller than d.
|
||
|
||
|
||
Concrete cost. We have shown it is possible to protect the OPRF protocol
|
||
from the SIDH attacks. Unfortunately, the proposed countermeasure do come at
|
||
a significant cost. The degrees of the blinding isogeny and the server’s isogeny
|
||
are the same as in SIDH with the same countermeasures. At security level λ =
|
||
128, that corresponds to isogenies of degree ≈ 22956 . More generally, we see
|
||
experimentally that the degree of the isogenies scales log-linearly in the security
|
||
parameter with a constant of ≈ 6.7. We thus have that the degree of the blinding
|
||
isogeny and the server’s isogeny must be ≈ 26.7λ log λ to guarantee the security
|
||
of the protocol.
|
||
|
||
|
||
5.2 Adapting the proof of isogeny knowledge
|
||
|
||
In the previous section, we showed how it is possible to protect the OPRF against
|
||
the SIDH attacks using masked torsion points. However, in the OPRF protocol
|
||
both parties need to prove the correctness of their torsion images to prevent
|
||
adaptive attacks and guarantee the verifiability of the execution. Thus, both
|
||
A Post-Quantum Oblivious PRF from Isogenies 15
|
||
|
||
parties want to prove that their revealed torsion points were honestly generated,
|
||
i.e. the two points are both scaled by the same value.
|
||
In this section, we propose a zero-knowledge proof of isogeny knowledge that
|
||
can guarantee the correctness of torsion points up to a scalar, i.e. a proof for the
|
||
following relation:
|
||
|
||
ϕ : E0 → E1 is a cyclic d-isogeny,
|
||
Riso = ((E0 , P0 , Q0 , E1 , P1 , Q1 ), (ϕ, α)) P1 = [α]ϕ(P0 ), .
|
||
Q1 = [α]ϕ(Q0 ).
|
||
|
||
|
||
In the literature, we can find two proofs of isogeny knowledge that also guar-
|
||
antee the correctness of torsion point images. The first proof constructs an SIDH
|
||
square and explicitly maps the torsion images through all the sides of the square.
|
||
This proof was proposed by Boneh, Kogan, and Woo [5] for the OPRF protocol,
|
||
based on a previous idea by Galbraith [17]. The second proof [12], instead, is an
|
||
extension of the simpler proof of isogeny knowledge by De Feo and Jao [19]. The
|
||
first proof requires a larger prime, but the torsion images are explicitly mapped,
|
||
which makes it well-suited to support masked torsion. We thus propose a new
|
||
proof based on the same approach as [5] and [17], although with some notable
|
||
differences. Building a more compact proof based on the second approach [12]
|
||
remains an open problem.
|
||
The main idea is that the masking constant α can be split into three shares
|
||
α = α1 α2 α3 . The prover can mask the torsion points with αi when computing
|
||
the i-th side of the SIDH square, so that the composition of the three isoge-
|
||
nies, together with their masking values, forms a commutative diagram with the
|
||
isogeny ϕ with masking value α. The proof remains zero-knowledge because each
|
||
single value αi is independent of α.
|
||
More formally, let E0 and E1 be supersingular elliptic curves with points
|
||
P0 , Q0 ∈ E0 [n] and P1 , Q1 ∈ E1 [n]. The prover wants to prove knowledge of
|
||
a d-isogeny ϕ : E0 → E1 and a value α ∈ Zn such that P1 = [α]ϕ(P0 ) and
|
||
Q1 = [α]ϕ(Q0 ). Let us assume n = fMSIDH (λ, d), so that the isogeny ϕ is hard
|
||
to extract from public information. The prover generates a random isogeny ψ :
|
||
E0 → E2 of degree s, where s ≈ n is a smooth number coprime with both n and
|
||
d, and generates the SIDH square (E0 , E1 , E2 , E3 ) with edges (ϕ, ψ, ϕ′ , ψ ′ ). To
|
||
guarantee soundness, the prover needs to show that ψ and ψ ′ are parallel: the
|
||
prover thus generates a s-basis R2 , S2 on E2 , maps it to E3 to obtain R3 , S3 ,
|
||
and expresses the kernels of ψ̂ and ψ̂ ′ in terms of R2 , S2 and R3 , S3 with the
|
||
same linear coefficients. The prover also splits α in three shares α = α1 α2 α3
|
||
and maps the points P0 , Q0 through ψ and ϕ′ with masking values α1 and α2 to
|
||
obtain the points
|
||
|
||
P2 = [α1 ]ψ(P0 ), Q2 = [α1 ]ψ(Q0 ),
|
||
P3 = [α2 ]ϕ′ (P2 ), Q3 = [α2 ]ϕ′ (Q2 ),
|
||
|
||
which implies that P3 and Q3 also satisfy the relation
|
||
|
||
[α3 ]P3 = ψ ′ (P1 ), [α3 ]Q3 = ψ ′ (Q1 ).
|
||
16 Andrea Basso
|
||
|
||
Hence, the SIDH square commutes with respect to the points Pi , Qi , i.e. if we
|
||
restrict ourselves to the n-torsion, we have
|
||
|
||
[α][s]ϕ = [α3 ]ψ̂ ′ ◦ [α2 ]ϕ′ ◦ [α1 ]ψ.
|
||
|
||
Thus, the witness can be split into three components, and hence we obtain a
|
||
proof with ternary challenges. The prover initially commits to the curves E2 , E3
|
||
and the relevant points on them with a commitment scheme C(·). Then, depend-
|
||
ing on the challenge, the prover responds with one edge of the SIDH square, the
|
||
relevant curves and points, and the corresponding commitment openings. The
|
||
proof is described in Fig. 4. Since each iteration has soundness error 2/3, the
|
||
proof must be repeated −λ log2/3 (2) ≈ 1.71 times to achieve a soundness error
|
||
of 2−λ .
|
||
|
||
Remark 1. If the kernel of the isogeny ϕ is not defined over a small extension
|
||
field, as in the case of the message isogeny, the proof can be computed by gluing
|
||
together multiple SIDH squares, as shown in [3].
|
||
|
||
|
||
P1 ((E0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α):
|
||
1: Sample a random cyclic isogeny ψ : E0 → E2 of degree s;
|
||
2: Construct the SIDH square (E0 , E1 , E2 , E3 , ϕ′ , ψ ′ ) on (ϕ, ψ);
|
||
3: Sample random units α1 , α2 mod n and set a3 := α/α1 α2 ;
|
||
4: Set P2 , Q2 := [α1 ]ψ(P1 ), [α1 ]ψ(Q1 ), and P3 , Q3 := [α2 ]ϕ′ (P2 ), [α2 ]ϕ′ (Q2 );
|
||
5: Let R2 , S2 be a basis of E2 [d] and set R3 , S3 := ϕ′ (R2 ), ϕ′ (S2 );
|
||
6: Write K = [a]R2 + [b]S2 for K a random generator of ker ψ̂
|
||
7: Sample random strings r1 , . . . , r7 ;
|
||
8: return st, C(E2 , R2 , S2 , P2 , Q2 ; r1 ), C(E3 , R3 , S3 , P3 , Q3 ; r2 ),
|
||
C(a, b; r3 ), C(ϕ′ ; r4 ), C(α1 ; r5 ), C(α2 ; r6 ), C(α3 ; r7 ) .
|
||
|
||
P2 (st, chall):
|
||
1: if chall == −1 then
|
||
2: return ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 ));
|
||
3: else if chall == 0 then
|
||
4: return ((E2 , R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 ));
|
||
5: else if chall == 1 then
|
||
6: return ((E3 , R3 , S3 , P3 , Q3 , r2 ), (a, b, r3 ), (α3 , r7 ));
|
||
|
||
V((E0 , P0 , Q0 ), (E1 , P1 , Q1 ), (com1 , . . . , com9 ), chall, resp):
|
||
1: if chall == −1 then
|
||
2: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 )) = resp;
|
||
3: Check com1 = C(E2 , R2 , S2 , P2 , Q2 ; r1 ),
|
||
com3 = C(a, b; r3 ), com5 = C(α1 ; r5 );
|
||
4: Let ψ̂ be the isogeny with kernel ⟨[a]R2 + [b]S2 ⟩;
|
||
5: Check ψ̂ is an s-isogeny from E2 to E0 ;
|
||
6: Check [α1 s]P0 = ψ̂(P2 ) and [α1 s]Q0 = ψ̂(Q2 );
|
||
7: else if chall == 0 then
|
||
8: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 )) = resp;
|
||
A Post-Quantum Oblivious PRF from Isogenies 17
|
||
|
||
|
||
|
||
9: Check com1 = C(E2 , R2 , S2 , P2 , Q2 ; r1 ),
|
||
com2 = C(E3 , R3 , S3 , P3 , Q3 ; r2 ),
|
||
com4 = C(ϕ′ ; r4 ), com6 = C(α2 ; r6 );
|
||
10: Check ϕ′ is a d-isogeny from E1 to E2 ;
|
||
11: Check R3 , S3 = ϕ′ (R2 ), ϕ′ (R3 );
|
||
12: Check P3 , Q3 = [α2 ]ϕ′ (P2 ), [α2 ]ϕ′ (Q2 );
|
||
13: else if chall == 1 then
|
||
14: ((E3 , R3 , S3 , P3 , Q3 , r2 ), (a, b, r3 ), (α3 , r7 )) = resp;
|
||
15: Check com2 = C(E3 , R3 , S3 , P3 , Q3 ; r2 ),
|
||
com3 = C(a, b; r3 ), com7 = C(α3 ; r7 );
|
||
16: Check ⟨R3 , S3 ⟩ = E3 [s];
|
||
17: Let ψ̂ ′ be the isogeny with kernel ⟨[a]R3 + [b]S3 ⟩;
|
||
18: Check ψ̂ is an s-isogeny from E3 to E1 ;
|
||
19: Check [α3 s]P1 = ψ̂ ′ (P3 ) and [α3 s]Q1 = ψ̂ ′ (Q3 );
|
||
|
||
|
||
|
||
Fig. 4: Interactive proof of knowledge for the relation Riso .
|
||
|
||
|
||
|
||
We now sketch the proofs of correctness, three-special soundness and zero-
|
||
knowledge. Given the similarity of the zero-knowledge proof with those in [5],
|
||
the proofs also follow a similar approach.
|
||
Correctness. A honest prover always generates proofs that are accepted by the
|
||
verifier. The verifier recomputes the same operations as the prover and checks
|
||
that the outputs match. The only difference is in the chall = ±1 cases, where
|
||
the verifier computes the dual of ψ and ψ ′ , which then introduces a factor s in
|
||
the point equality check.
|
||
Three-special soundness. The protocol is three-special sound because there
|
||
exists an extractor that extracts the witness given three accepting transcripts
|
||
with the same commitments and different challenges. The isogeny ϕ can be
|
||
computed by mapping the kernel of ϕ′ (from chall = 0) under the isogeny ψ̂ (from
|
||
chall = −1). Since the isogenies ψ and ψ ′ are parallel (from all the challenges
|
||
combined), this guarantees that ϕ is a d-isogeny from E0 to E1 . The masking
|
||
value α can be recomputed as the product of α1 , α2 , and α3 .
|
||
Zero-knowledge. We sketch a simulator that given a statement (E0 , P0 , Q0 ,
|
||
E1 , P1 , Q1 ) and a challenge chall can simulate a valid transcript without knowl-
|
||
edge of the witness. For the case chall = −1, the simulator behaves like an honest
|
||
prover. For chall = +1, the situation is similar: the simulator can compute a d-
|
||
isogeny ψ ′ , pick a random basis R3 , S3 of E3 [d] and a random value α3 ∈ Z∗n ,
|
||
and compute the values a, b and points P3 , Q3 that pass verification. Note that
|
||
the points R3 , S3 are uniformly random among the bases of E3 [d], and the value
|
||
α3 is uniformly random and independent of α; the simulated values are thus
|
||
distributed as the honestly-generated ones. The case of chall = 0 is more com-
|
||
plicated: the simulator can sample a random curve E2 , generate a random basis
|
||
18 Andrea Basso
|
||
|
||
2
|
||
P2 , Q2 of E2 [n] that satisfies e(P2 , Q2 ) = e(P0 , Q0 )x s for some random x, pick
|
||
a random d-isogeny ϕ′ : E2 → E3 , and compute the image points on E3 . In this
|
||
case, the indistinguishability of the simulator’s output is only computational.
|
||
It is thus based on the conjectured hardness of the following problem, which
|
||
is a modified version of the Decisional Supersingular Product (DSSP) problem
|
||
introduced in [19].
|
||
|
||
Problem 6 (DSSP with Torsion (DSSPwT) problem). Given an isogeny ϕ :
|
||
E0 → E1 and points P0 , Q0 ∈ E0 [n], where n = fMSIDH (λ, d), distinguish be-
|
||
tween the following distributions:
|
||
|
||
– D0 = {(E2 , P2 , Q2 , E3 , ϕ′ )}, where E2 is the codomain of an s-isogeny ψ :
|
||
E0 → E2 , the points P2 , Q2 satisfy P2 = [α]ψ(P0 ), Q2 = [α]ψ(Q0 ) for some
|
||
α ∈ Z∗n , and ϕ′ : E2 → E3 is a d-isogeny with kernel ker ϕ′ = ψ(ker ϕ).
|
||
– D1 = {(E2 , P2 , Q2 , E3 , ϕ′ )}, where E2 is a random supersingular curve with
|
||
the same cardinality as E0 , P2 and Q2 are two random points of order n
|
||
such that e(P2 , Q2 ) = e(P0 , Q0 )s , and the isogeny ϕ′ is a d-isogeny between
|
||
E2 and E3 .
|
||
|
||
Note that [5] argues that a similar proof can only reveal one torsion point (either
|
||
Pi or Qi ) at a time to prevent a distinguishing attack on the simulator. The
|
||
attack they present relies on computing the Weil pairing between two points
|
||
of coprime order, and thus their pairing is always one. The attack thus does
|
||
not apply, and the simulated transcript remains indistinguishable under Weil
|
||
pairing checks because the sampled points P2 , Q2 are guaranteed to have the
|
||
same pairing as the honestly-generated points. By revealing both points Pi and
|
||
Qi we obtain a significantly more efficient proof, since it has 1/3 soundness rather
|
||
than 1/6.
|
||
|
||
|
||
Optimizations. For simplicity, the proof in Fig. 4 contains a schematic descrip-
|
||
tion of the protocol, but the proof can be made more efficient through a series of
|
||
optimizations. In the commitment phase, the value α2 is only revealed together
|
||
with the isogeny ϕ′ , and thus they can be committed together. Note that we have
|
||
the prover commit to ϕ′ to make the proof online-extractable without recursion,
|
||
which is necessary to achieve a proof in the UC model. For applications of this
|
||
proof outside of the OPRF context, the prover can avoid committing to ϕ′ . The
|
||
masking values α1 and α3 are independent of α, even when considered together,
|
||
because α2 is uniformly random. They can then be committed together and re-
|
||
vealed both in the response to challenges chall = ±1. Since the commitment for
|
||
a, b is also revealed when chall = ±1, the values a, b, α1 , α3 can all be committed
|
||
together. When chall = −1, the curve E3 and the points P3 , Q3 are not revealed,
|
||
and thus learning α3 does not provide any information. The same applies to α1
|
||
when chall = +1. This allow us to reduce the number of commitments to four.
|
||
To further reduce the communication between prover and verifier, the basis
|
||
R2 , S2 on E2 can be chosen canonically, so that it can be recomputed from
|
||
E2 . Moreover, for the challenge chall = −1, the prover can avoid revealing the
|
||
A Post-Quantum Oblivious PRF from Isogenies 19
|
||
|
||
curve E2 , the points P2 , Q2 and the coefficients a, b by revealing instead a kernel
|
||
generator of ψ. The prover can recompute E2 , P2 , Q2 and obtain a, b by writing
|
||
a kernel generator of ψ̂ in terms of the canonical basis R2 , S2 . Normally, the
|
||
recomputed a, b would not be the same as those computed by the verifier since
|
||
they are not unique. The problem can be avoided by fixing a canonical way to
|
||
compute the coefficients, such as prescribing that one of the two coefficients must
|
||
be one, and that a must be one if both coefficients are invertible mod s. The
|
||
same approach holds for chall = +1, except that the points R3 , S3 have to be
|
||
revealed by the prover. In the case of the horizontal isogeny, the prover can avoid
|
||
revealing E3 and the points R3 , S3 and P3 , Q3 . They can all be recomputed from
|
||
the remaining values.
|
||
|
||
Concrete cost. Each repetition of the proof requires two commitments, which
|
||
are 2λ-bit long and use a λ-bit long opener. When chall = −1, the prover reveals
|
||
one s-isogeny, a masking value, and two commitment openers, which requires
|
||
log n + log s + 2λ bits. When chall = +1, the prover also reveals two torsion
|
||
points of order s: if they are compressed as in [2], the response requires 5 log s +
|
||
log n + 2λ bits. Lastly, for chall = 0, the prover reveals a curve, a d-isogeny, two
|
||
points of order n, a masking value, and three openers; thus, the answer requires
|
||
2 log p + log d + 5 log n + 3λ bits.√
|
||
Hence, if we assume d ≈ n ≈ s ≈ 3 n, an average proof where the three challenges
|
||
appear equally requires ≈ 1.71λ(20/9 log p + 7/3λ) bits, while a worst-case proof,
|
||
with only chall = 0 challenges, requires ≈ 1.71λ(4 log p + 3λ) bits.
|
||
|
||
|
||
6 Verifiability
|
||
Oblivious PRFs can satisfy a stronger security property called verifiability. In-
|
||
formally, this guarantees that the server behaves honestly and always uses the
|
||
same long-term static key. This is needed to guarantee the privacy of the user
|
||
in those instances where the user may later reveal the output of the OPRF. A
|
||
malicious server may behave “honestly” while also using different secret keys on
|
||
different interactions. After learning the OPRF output of the user, the server
|
||
can then test which secret key was used to produce that specific output and thus
|
||
link the user to a specific user-server interaction.
|
||
The OPRF protocol by Boneh, Kogan, and Woo achieves verifiability by intro-
|
||
ducing three components. First, the server initially commits to a secret key k.
|
||
The commitment is in the form of an elliptic curve EC := E/⟨P + [k]Q⟩, where
|
||
the curve E and the points P, Q are fixed parameters. Second, during the OPRF
|
||
execution, the server provides a zero-knowledge proof that its computations used
|
||
the same key as the one in the commitment. We refer to this proof as a proof
|
||
of parallel isogeny (PoPI). Lastly, the server also provides two proofs of isogeny
|
||
knowledge (PoIKs) that guarantee the correctness of the computations during
|
||
both the commitment stage and the OPRF execution. The proof of parallel
|
||
isogeny proposed by Boneh, Kogan, and Woo relies on the user and the server
|
||
engaging in an SIDH exchange, where one of the sides is either the commitment
|
||
20 Andrea Basso
|
||
|
||
isogeny or the the secret server isogeny in the OPRF protocol. However, this
|
||
proof is inherently interactive, and it requires five rounds of interaction. More-
|
||
over, the proof relies on multiple SIDH exchanges, and it is thus broken by the
|
||
attacks on SIDH [7,25,28].
|
||
We avoid these issues by introducing a novel public-coin proof protocol of parallel
|
||
isogeny. Since the proof does not rely on private randomness, we obtain a proof of
|
||
knowledge that can be made non-interactive via the Fiat-Shamir transform [14]
|
||
or the Unruh transform [30]. In the OPRF setting, we will rely on the latter
|
||
to achieve the online-extractability without rewinding needed to get a proof in
|
||
the UC model. Our main approach relies on executing two proofs of isogeny
|
||
knowledge in parallel with correlated randomness. Since part of the randomness
|
||
used is shared, we can obtain a proof of parallelness without needing additional
|
||
computations.
|
||
Firstly, we formalize the notion of parallelness. We say that two d-isogenies ϕ :
|
||
E0 → E1 and ϕ̃ : Ẽ0 → Ẽ1 are parallel with respect to the bases T0 , V0 ∈ E0 [d]
|
||
and T̃0 , Ṽ0 ∈ E0′ [d] if there exists coefficients a, b ∈ Zd such that ker ϕ = ⟨[a]T0 +
|
||
[b]V0 ⟩ and ker ϕ̃ = ⟨[a]T̃0 + [b]Ṽ0 ⟩. This suggests that the parallelness relation
|
||
that we are proving is the following:
|
||
E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩ ∼
|
||
|
||
= E1 ,
|
||
Rpar = ((E0 , T0 , V0 , E1 , Ẽ0 , T̃0 , Ṽ0 , Ẽ1 ), (k0 , k1 ))
|
||
Ẽ0 /⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩ ∼
|
||
= Ẽ1
|
||
However, as discussed before, we are combining several proofs together to ob-
|
||
tain a larger proof that simultaneously proves knowledge of two isogenies and
|
||
guarantees the two isogenies are parallel. We thus obtain a proof for the follow-
|
||
ing relation, where we consider the case of a secret key with two coefficients for
|
||
completeness. For practical reasons, the OPRF will fix k0 = 1 without any loss
|
||
of security.
|
||
|
||
ker ϕ = ⟨[k0 ]T0 + [k1 ]V0 ⟩,
|
||
|
||
0 0 0 0 0 1 1 1
|
||
((E , T , V , P , Q , E , P , Q , ′
|
||
|
||
|
||
ker ϕ = ⟨[k ]T̃ + [k ] Ṽ ⟩,
|
||
|
||
∗ 0 0 1 0
|
||
Rpar = Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ),
|
||
(E0 , P0 , Q0 , E1 , P1 , Q1 ), (ϕ, α) ∈ Riso ,
|
||
(k0 , k1 , α, α′ ))
|
||
|
||
|
||
(Ẽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), (ϕ′ , α′ ) ∈ Riso
|
||
|
||
|
||
Now, let the curve Ẽ0 with a d-basis T̃0 , Ṽ0 be fixed protocol parameters. Using
|
||
the same notation as before, assume that server has committed to its key (k0 , k1 )
|
||
by publishing the codomain of the d-isogeny ϕ̃ that has kernel ⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩.
|
||
The server may also reveal some torsion information in its commitment, but as
|
||
we will discuss later, this is not strictly needed. During the OPRF execution,
|
||
the server receives a curve E0 with a d-basis T0 , V0 on it, and it computes ϕ :
|
||
E0 → E1 := E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩. The server then wants to prove that it knows
|
||
the isogenies ϕ and ϕ̃ and that they are parallel.
|
||
If the server simply ran two instances of the PoIK from Fig. 4 in parallel, there
|
||
would be no way to convince the prover that the isogenies are indeed parallel. If
|
||
the proofs share the same challenges, i.e. the verifier sends the same challenges to
|
||
both proofs, the server would respond with both ϕ′ and ϕ̃′ when chall = 0. How-
|
||
ever, the isogenies ϕ′ and ϕ̃′ are parallel with respect to the bases ψ(T0 ), ψ(V0 )
|
||
A Post-Quantum Oblivious PRF from Isogenies 21
|
||
|
||
and ψ̃(T̃0 ), ψ̃(Ṽ0 ) (where ψ is the vertical isogeny used in the proof of knowl-
|
||
edge), which are not revealed in the proof. If we were to reveal them, the proof
|
||
would not be zero-knowledge, because when chall = 0, the verifier could recom-
|
||
pute the secret isogeny ψ and ψ̃ through the SIDH attacks. Instead, we want
|
||
to modify the proof to reveal different bases T2 , V2 ∈ E2 [d] and T̃2 , Ṽ2 ∈ Ẽ2 [d]
|
||
such that ϕ′ and ϕ̃′ are parallel with regards to them, but also such that they do
|
||
not reveal much information about ψ and ψ̃. We thus propose that the prover
|
||
generates four random coefficients w, x, y, z ∈ Zd such that wz − xy ̸= 0 mod d,
|
||
and computes T2 and V2 as the solution of
|
||
|
||
ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 ,
|
||
|
||
and similarly for T̃2 and Ṽ2 . This is then secure, because the basis T2 , V2 is
|
||
uniformly random. Thus, for a single proof, this change only does not affect the
|
||
security of the proof since no additional information is revealed. The rest of the
|
||
proof needs to be modified to ensure that the process is followed correctly, i.e.
|
||
we want the prover to reveal the values w, x, y, z together with ψ so that the
|
||
verifier can verify the correctness of T2 and V2 . The modified proof is denoted
|
||
∗
|
||
by Piso , and it is represented explicitly in Fig. 5.
|
||
|
||
|
||
|
||
P∗1
|
||
|
||
(E0 , T0 , V0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α , (w, x, y, z) :
|
||
1-4: Same as P1 in Fig. 4.
|
||
5: Set T2 , V2 to satisfy ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 ;
|
||
6-8: Same as P1 in Fig. 4.
|
||
|
||
P∗2 (st, chall):
|
||
1: if chall == −1 then
|
||
2: return ((E2 , T2 , V2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 ), (w, x, y, z));
|
||
3: else if chall == 0 then
|
||
4: return ((E2 , T2 , V2 ,R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 ));
|
||
5: else if chall == 1 then
|
||
6: Same as P2 in Fig. 4.
|
||
|
||
V∗ ( (E0 , T0 , V0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α , com, chall, resp :
|
||
|
||
|
||
1: if chall == −1 then
|
||
2: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 ), (w, x, y, z)) = resp;
|
||
3-6: Same as V in Fig. 4.
|
||
7: Check ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 ;
|
||
8: else
|
||
9: Same as V in Fig. 4.
|
||
|
||
|
||
|
||
Fig. 5: Modified proof of knowledge for the relation Riso where the basis ran-
|
||
domness is explicit. The expressions in magenta denote the changes from Fig. 4.
|
||
22 Andrea Basso
|
||
|
||
Now, if the prover executes the modified proof of isogeny knowledge for ϕ and
|
||
ϕ̃ in parallel, with the same challenges, and with the same values x, w, y, z, the
|
||
isogenies ϕ′ , ϕ̃′ revealed when chall = 0 are parallel when the isogenies ϕ, ϕ̃ are
|
||
also parallel, as shown in the following lemma.
|
||
Lemma 2. Let notation be as above. The isogenies ϕ, ϕ̃ are parallel if and only
|
||
if the isogenies ϕ′ , ϕ̃′ are also parallel.
|
||
Proof. Assume the isogeny ϕ has kernel ⟨[k0 ]T0 + [k1 ]V0 ⟩ and the isogeny ϕ̃ has
|
||
kernel ⟨[k̃0 ]T̃0 + [k̃1 ]Ṽ0 ⟩. The kernel of ϕ′ is the image of the kernel of ϕ under ψ,
|
||
i.e. ker ϕ′ = ψ(ker ϕ). Since ker ϕ = ⟨[k0 ]T0 + [k1 ]V0 ⟩, it follows that
|
||
ker ϕ′ = ⟨[k0 ]ψ(T0 ) + [k1 ]ψ(V0 )⟩ = ⟨[wk0 + yk1 ]T2 + [xk0 + zk1 ]V2 ⟩.
|
||
Similarly, we obtain
|
||
ker ϕ̃′ = ⟨[wk̃0 + y k̃1 ]T̃2 + [xk̃0 + z k̃1 ]Ṽ2 ⟩.
|
||
Since the coefficients w, x, y, z were chosen such that the matrix ( wy xz ) is invert-
|
||
ible, we obtain that
|
||
(k0 = k̃0 ) ∧ (k1 = k̃1 ) ⇐⇒ (wk0 + yk1 = wk̃0 + y k̃1 ) ∧ (xk0 + zk1 = xk̃0 + z k̃1 ).
|
||
|
||
|
||
∗
|
||
We can now use the proof Piso from Fig. 5 to construct our proof of parallel
|
||
isogeny knowledge. The prover runs two such proofs in parallel, with the same
|
||
randomness (w, x, y, z), and responds to the verifier’s challenges with the re-
|
||
sponses of the individual proofs. The resulting proof is represented explicitly in
|
||
Fig. 6. The security proofs follow closely those of the PoIK Piso in Section 5.2:
|
||
correctness of Piso implies correctness of Ppar , while the soundness of Ppar follows
|
||
from the soundness of Piso and Lemma 2. The argument for zero-knowledge is
|
||
also similar, but it is based on the hardness of the following problem, which
|
||
takes into consideration that the two parallel instance partially share the same
|
||
randomness.
|
||
Problem 7 (Double DSSP with Torsion (DDSSPwT) problem). Let D0 and D1
|
||
be as in Problem 6. Given:
|
||
1. two d-isogenies ϕ : E0 → E1 , ϕ̃ : Ẽ0 → Ẽ1 ,
|
||
2. the points T0 , V0 ∈ E0 [d] and T̃0 , Ṽ0 ∈ Ẽ0 [d],
|
||
3. the points P0 , Q0 ∈ E0 [n] and P̃0 , Q̃0 ∈ Ẽ0 [n], where n = fMSIDH (λ, d),
|
||
distinguish between the following distributions:
|
||
(E2 , T2 , V2 , P2 , Q2 , E3 , ϕ′ ),
|
||
|
||
∗
|
||
– D0 = , where the curves and the n-torsion
|
||
(Ẽ2 , T̃2 , Ṽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ )
|
||
points follow the D0 -distribution, i.e. we have (E2 , P2 , Q2 , E3 , ϕ′ ) ← D0 , and
|
||
(Ẽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) ← D0 , and moreover
|
||
|
||
T2 ψ(T0 ) T̃2 ψ̃(T̃0 )
|
||
=B , and =B ,
|
||
V2 ψ(V0 ) Ṽ2 ψ̃(Ṽ0 )
|
||
A Post-Quantum Oblivious PRF from Isogenies 23
|
||
|
||
|
||
P1 ((E0 , T0 , V0 , P0 , Q0 , E1 , P1 , Q1 ), (Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), k0 , k1 , α, α′ ):
|
||
1: Sample random coefficients w, x, y, z such that wz − xy ̸= 0 mod d;
|
||
2: Compute ϕ : E0 → E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩ ∼ = E1
|
||
3: Compute ϕ′ : Ẽ0 → Ẽ0 /⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩ ∼ = Ẽ1
|
||
4: Run P∗1 ((E0 , P0 , Q0 , E1 , P1 , Q1 ), ϕ, α, (w, x, y, z)) to get st, com;
|
||
5: Run P∗1 ((Ẽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 ,Q̃1 ), ϕ̃′ , α̃′ , (w, x, y, z)) to get st, ˜ com;˜
|
||
6: return (st, st), ˜ (com, com) ˜ ;
|
||
˜ chall):
|
||
P2 ((st, st),
|
||
1: return (P∗2 (st, chall), P∗2 (st,
|
||
˜ chall));
|
||
|
||
V((E0 , T0 , V0 , P0 , Q0 , E1 , P1 , Q1 ), (Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ),
|
||
˜ chall, (resp, resp)):
|
||
(com, com), ˜
|
||
1: Set v := V∗ ((E0 , R, S, P0 , Q0 , E1 , P1 , Q1 ), com, chall, resp);
|
||
2: Set ṽ := V∗ ((Ẽ0 , T̃ , Ṽ , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), com,
|
||
˜ chall, resp); ˜
|
||
3: if chall == 0 and ϕ′ , ϕ̃′ are not parallel wrt T2 , V2 and T̃2 , Ṽ 2 then
|
||
4: return ⊥;
|
||
5: return v ∧ ṽ;
|
||
|
||
|
||
|
||
Fig. 6: Interactive proof of knowledge for the relation R∗par .
|
||
|
||
|
||
for some B ∈ GL2 (Zn ), and ψ and ψ̃ being respectively the s-isogenies
|
||
between E0 and E2 and Ẽ0 and Ẽ2 that are guaranteed to exist because of
|
||
the D0 distribution;
|
||
(E2 , T2 , V2 , P2 , Q2 , E3 , ϕ′ ),
|
||
|
||
∗
|
||
– D1 = , where the curves and the n-torsion
|
||
(Ẽ2 , T̃2 , Ṽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ )
|
||
points follow the D1 -distribution, i.e. we have (E2 , P2 , Q2 , E3 , ϕ′ ) ← D1 , and
|
||
(Ẽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) ← D1 , and moreover the points T2 , V2 and T̃2 , Ṽ2 form a
|
||
random basis of E2 [d] and Ẽ2 [d], respectively.
|
||
|
||
The proof Ppar is a proof of knowledge, and it can be made non-interactive
|
||
with standards transformations, such as the Fiat-Shamir [14] or the Unruh [30]
|
||
transform. This is the first non-interactive proof of parallelness.
|
||
|
||
|
||
Optimizations. For simplicity, the presentation of the proof R∗par preferred
|
||
a schematic description, but it is possible to improve the protocol to make it
|
||
more compact. Besides the optimizations applicable to the proof Piso described
|
||
in Section 5.2, we remark that parallelness is independent of torsion images.
|
||
Thus, the proofs of isogeny knowledge do not need to guarantee the correctness
|
||
of torsion images to prove parallelness. However, in the OPRF context, the
|
||
correctness of the torsion images revealed by the server is needed to guarantee
|
||
verifiability: a malicious server might otherwise reveal incorrect torsion points
|
||
to different users and use that information to match OPRF outputs to specific
|
||
24 Andrea Basso
|
||
|
||
interactions. Hence, the proof can be made more efficient by avoiding proving
|
||
the correctness of torsion images for the commitment isogeny.
|
||
|
||
|
||
Concrete cost. The proof described in Fig. 5 adds the communication of the
|
||
values w, x, y, z when chall = −1. In that case, the prover’s response requires
|
||
log n + log s + 4 log d + 2λ bits; when chall = 0, the response is also larger because
|
||
the points R2 , S2 need to be communicated explicitly. The answers to the other
|
||
challenge remains unchanged.
|
||
The same proof, when used for the commitment isogeny, can avoid proving cor-
|
||
rectness of the torsion images, resulting in a smaller proof. In particular, no
|
||
masking values are ever revealed, and when chall = 0 the√response does not con-
|
||
tain the points P2 , Q2 on E2 . Setting d ≈ n ≈ s ≈ 3 n, we obtain that an
|
||
average proof Ppar requires ≈ 1.71λ(49/9 log p + 14/3λ) bits, while a worst-case
|
||
proof would require ≈ 1.71λ(9 log p + 6λ) bits.
|
||
|
||
|
||
7 A new OPRF protocol
|
||
|
||
In this section, we combine the countermeasures presented in Section 4, the SIDH
|
||
countermeasures and the novel proof of isogeny knowledge discussed in Section 5,
|
||
and the non-interactive proof of parallel isogeny introduced in Section 6 to obtain
|
||
a verifiable OPRF protocol that is post-quantum secure, round-optimal, and
|
||
moderately compact.
|
||
The OPRF protocol is a two-party protocol between a user U and a server S.
|
||
Let NM , NB , NK be coprime numbers representing the degrees of the message
|
||
isogeny, the blinding isogeny, and the server’s isogeny, respectively. Let p be a
|
||
prime of the form p = NM NB NK f − 1, for some cofactor f , and let E0 , Ẽ be
|
||
two supersingular elliptic curves defined over Fp2 . Moreover, let P, Q be a fixed
|
||
basis of E0 [NM ] and let P̃ , Q̃ be a fixed basis of Ẽ[NK ]. The first curve is used
|
||
to compute the PRF, while the second is used within the server’s commitment.
|
||
At a high-level, to evaluate the OPRF on an input x, the user maps the input
|
||
to a curve Em according to Algorithm 1 and computes a blinding isogeny ϕb :
|
||
Em → Emb . The user then sends the codomain curve, together with torsion
|
||
images and a proof of their correctness, to the server, which computes a second
|
||
isogeny ϕk : Emb → Embk . The torsion information is appropriately masked to
|
||
avoid the SIDH attacks. The server then responds with the curve Embk , some
|
||
torsion information, a proof of their correctness, and a proof that it has used the
|
||
previously-committed secret key. The user then concludes by using the torsion
|
||
information provided by the server to undo the blinding isogeny and compute
|
||
the curve Emk . Its j-invariant is then hashed together with the input and the
|
||
server’s public key to form the PRF output. The protocol is described in Fig. 7,
|
||
and it realizes the OPRF ideal functionality of Fig. 2, which allows us to state
|
||
the following theorem.
|
||
Theorem 1. The protocol described in Fig. 7 realizes the ideal functionality
|
||
FvOPRF of Fig. 2 in the random oracle model.
|
||
A Post-Quantum Oblivious PRF from Isogenies 25
|
||
|
||
The proof follows the same line as the security proof of the OPRF protocol
|
||
by Boneh, Kogan, and Woo [5, Theorem 20], since the hardness assumption
|
||
of Problem 4 and the proof Piso are a drop-in replacement for the Auxiliary
|
||
One-More SIDH assumption and the NIZKPK proof used in [5], respectively.
|
||
At a high level, the case of an honest user and malicious server in the proof is
|
||
simple because the server only interacts with the user through their first query,
|
||
and in that case the user’s security corresponds to the input hiding property,
|
||
guaranteed by the hardness of Problem 1. The case of a malicious user is more
|
||
complicated, because the user has output. The server can be simulated as a
|
||
honest server, but to ensure that the malicious user output is indistinguishable
|
||
from the ideal-world, the random oracle H̄ can be programmed to output the
|
||
ideal-world output. This would create a problem with the ticketing system of
|
||
the ideal functionality if the adversary could produce more OPRF outputs than
|
||
the number of interactions, but the one-more unpredictability property prevents
|
||
that. The main difference between this proof and that of [5] is the use of a non-
|
||
interactive proof of parallel isogeny, which results in a simpler proof since the
|
||
proof of knowledge can be simulated. Note that the proof in [5] is written in terms
|
||
of the augmentable commitment abstraction, which we preferred avoiding; since
|
||
the same security properties can be directly expressed in terms of the OPRF
|
||
protocol, as shown in Section 3, the difference is purely syntactical.
|
||
|
||
Parameters. A prime p of the form p = NM NB NK f − 1, where NM , NB , NK are
|
||
smooth coprime integers and f a smooth cofactor. E0 and Ẽ are supersingular
|
||
elliptic curves defined over Fp2 , where End Ẽ is unknown, and P, Q ∈ E0 [NM ] and
|
||
P̃ , Q̃ ∈ E[NK ] are fixed bases. The protocol also relies on the following functions:
|
||
|
||
– Hi : {0, 1}∗ → ZM for i ∈ {1, . . . , I}, where I is such that NM
|
||
I
|
||
> 24λ
|
||
∗ λ
|
||
– H̄ : {0, 1} → {0, 1} , to hash the final PRF output,
|
||
|
||
and two non-interactive proofs of knowledge: Piso , for the user to prove correctness
|
||
of torsion images, and Ppar , for the server to prove it computed honestly with the
|
||
committed key.
|
||
|
||
Initialization. On input init from the environment, the server S:
|
||
|
||
– sample k ← ZK and stores it,
|
||
– computes the curve ẼC = Ẽ/⟨P̃ + [k]Q̃⟩,
|
||
– stores pk = (j(EC )) and outputs (init, pk).
|
||
|
||
Evaluation. On input init from the environment, the server S:
|
||
|
||
– On input (Eval, S, x), the user U proceeds as follows:
|
||
1. Sample α ← Z∗N and b ← ZB ,
|
||
2. Compute (ϕm , Em ) = HI (x);
|
||
3. Compute ϕb : Em → Emb := Em /⟨Pm + [b]Qm ⟩, where Pm , Qm =
|
||
BB (Em ),
|
||
4. Set ϕmb = ϕb ◦ ϕ1 ◦ ϕ0 , R = [α]ϕmb (P ), S = [α]ϕmb (Q),
|
||
5. Compute πc ← Piso (E0 , P, Q, Emb , R, S, ϕmb , α),
|
||
26 Andrea Basso
|
||
|
||
|
||
|
||
6. Send message (Emb , R, S, πc ) to the server and store ϕb .
|
||
– On input ServerComplete from the environment and message
|
||
(Emb , R, S, πc ) from the user U , the server S proceeds as follows:
|
||
1. Verify the proof πc and sample αk ← Z∗n ,
|
||
2. Compute ϕk : Emb → Embk := Emb /⟨R + [k]S⟩,
|
||
3. Compute Rk = [αk ]ϕk (Pb ), Sk = [αk ]ϕk (Qb ), where Pb , Qb = BB (Emb ),
|
||
4. Compute πk ← Ppar ((Emb , Pb , Qb , Embk , Rk , Sk ), (Ẽ, P̃ , Q̃, ẼC ), k, αk )2 ,
|
||
5. Send (pk, Embk , Rk , Sk , πk ) to the user U .
|
||
– On input (pk = j(Ec ), Embk , Rk , Sk , πk ) from the server S, the user U proceeds
|
||
as follows:
|
||
1. Verify the proof πk ,
|
||
2. Compute b0 , b1 such that ⟨[b0 ]Pb + [b1 ]Qb ⟩ = ker ϕ̂b , where Pb , Qb =
|
||
Bd (Emb ),
|
||
3. Compute ϕu : Embk → Emk := Embk /⟨[b0 ]Rk + [b1 ]Sk ⟩,
|
||
4. Compute y = H̄(x, pk, j(Em k)) and output (Eval, pk, y).
|
||
|
||
|
||
|
||
|
||
Fig. 7: The verifiable OPRF protocol.
|
||
|
||
|
||
Parameter selection. Firstly, we discuss how to select the starting curves E0
|
||
and Ẽ. As mentioned in Section 5, the cryptanalysis on masked-torsion SIDH
|
||
with a starting curve with small endomorphism [15, Section 4.2] does not apply
|
||
here, since the message isogeny removes this property from the starting curve
|
||
of the blinding isogeny. Hence, the curve E0 does not need to have unknown
|
||
endomorphism ring. However, the situation is different for Ẽ: as observed in [4],
|
||
knowledge of End Ẽ allows to find collisions in the server’s commitment. Thus,
|
||
knowing End Ẽ would allow the server to break verifiability, since it could prove
|
||
parallelness to two distinct isogenies. It is thus necessary that the curve Ẽ is
|
||
generated by a trusted party or through a multiparty trusted setup ceremony,
|
||
such as the one presented in [3].
|
||
The main parameter of the OPRF protocol is the prime p. Firstly, if the message
|
||
isogeny is the composition of many isogenies whose kernel is defined over Fp4 , the
|
||
value p + 1 does not need have a dedicated factor. Then, for the main exchange,
|
||
i.e. the blinding, server’s isogeny, unblinding part, we need to smooth coprime
|
||
integers NB and NK that are highly composite to prevent the SIDH attacks.
|
||
Following the analysis of Section 5, we have NB ≈ NK ≈ 22956 . Lastly, the proofs
|
||
of knowledge Piso and Ppar require a third cofactor NS that is coprime with both
|
||
NB and NK . To guarantee the hardness of Problems 6 and 7, the integer NS needs
|
||
to be of the same length as NB and NK . However, since torsion points of order
|
||
NS do not need to be masked, the value NS can be a prime power. Putting this
|
||
2
|
||
The proof algorithm does not receive torsion points because, as discussed in Section 6,
|
||
they are not necessary to prove parallelness.
|
||
A Post-Quantum Oblivious PRF from Isogenies 27
|
||
|
||
together, we obtain that the prime p needs to be of the form p = NB NS NK f − 1
|
||
and be at least 8868-bit long to guarantee λ = 128 bits of security. Note that
|
||
the new computation of the message isogeny and the new proofs of knowledge
|
||
has significantly reduced the size of the prime; compared to the OPRF protocol
|
||
by Boneh, Kogan, and Woo, we use a prime that is 5.8× larger, while relying on
|
||
an SIDH protocol with isogenies that are 9.2× longer.
|
||
|
||
Efficiency. We now estimate the communication cost of the OPRF proto-
|
||
col. The largest components are the non-interactive proofs of knowledge: given
|
||
the analysis of the previous sections, they are less than 1.7λ(35 log p + 51λ)-
|
||
bit long. Since log p ≈ 10λ log λ, we obtain that one OPRF execution requires
|
||
1.7λ2 (350 log λ + 51) bits of communication. For λ = 128, this corresponds to a
|
||
transcript of 8.7 MB. We remark that the size of the proofs is particularly large
|
||
due to the Unruh transform needed to prove security in the UC framework. If
|
||
the proofs were made non-interactive via the Fiat-Shamir transform, a single
|
||
execution of the verifiable OPRF with λ = 128 would require 1.9 MB of com-
|
||
munication on average and 3.8 MB in the worst case. Such an OPRF may be
|
||
used in instances where security in the UC framework is not necessary.
|
||
A direct comparison with the protocol by Boneh, Kogan, and Woo [5] is not sim-
|
||
ple since their bandwidth estimate does not appear to include the Unruh trans-
|
||
form overhead. We estimate that one execution of the OPRF from [5] requires at
|
||
least 10.9 MB3 . Our protocol is thus more compact than that in [5], despite be-
|
||
ing round-optimal and secure against both the one-more unpredictability attack
|
||
and the SIDH attacks. This is made possible by the fact that the sigma protocols
|
||
are highly optimized and have ternary challenges, which significantly reduces the
|
||
overhead introduced in the Unruh transform. Indeed, if we compare a version
|
||
of the two protocols with the Fiat-Shamir transform, our OPRF uses 31% more
|
||
bandwidth than the one in [5]. We summarize the state of post-quantum OPRF
|
||
protocols in Table 1.
|
||
|
||
8 Conclusion
|
||
In this work, we presented a post-quantum verifiable oblivious PRF protocol
|
||
that is moderately compact and round-optimal. The protocol is the first round-
|
||
3
|
||
In [5, Section 5], the authors estimate that the largest response in the sigma protocol
|
||
Rcom requires 6 log p + 5λ bits. The protocol has a challenge space of size 6, and
|
||
it needs to be repeated 3.8λ times to obtain a negligible soundness error. Without
|
||
considering the size of the committments, the Unruh-based NIZKP contains 6 hashed
|
||
values that are as long as the largest response, per each iteration. The transcript of
|
||
an Rcom proof thus requires at least 3.8λ × 6(6 log p + 5λ) bits. The entire OPRF
|
||
hence requires three times as much (three such proofs are used), plus 5λ log p bits
|
||
for the proof of parallel isogenies.
|
||
4
|
||
The number of communication rounds depends on the underlying OT construction.
|
||
An update to [24] suggests four rounds may be necessary.
|
||
5
|
||
Recent work by Heimberger, Meisingseth, and Rechberger [18] suggests such con-
|
||
struction may be insecure.
|
||
28 Andrea Basso
|
||
|
||
|
||
Table 1: Post-quantum OPRF protocols secure against malicious clients.
|
||
Protocol Rounds Bandwidth (avg.) Verifiable Secure
|
||
[1] (LWE) 2 >128 GB ✓ ✓
|
||
[5] (CSIDH) 34 424 kB ✗ ✓5
|
||
[5] (SIDH)FO 6 1.4 MB ✓ ✗
|
||
[5] (SIDH)Unruh 6 >10.9 MB ✓ ✗
|
||
[This work]FO 2 1.9 MB ✓ ✓
|
||
[This work]Unruh 2 8.7 MB ✓ ✓
|
||
|
||
|
||
|
||
optimal OPRF based on isogenies, and it is several orders of magnitude more
|
||
compact than the existing round-optimal protocol. To obtain this protocol, we
|
||
started from an insecure protocol by Boneh, Kogan, and Woo, and we proposed
|
||
an efficient countermeasure against the one-more unpredictability attack, in-
|
||
tegrated the existing SIDH countermeasures, developed a new zero-knowledge
|
||
proof of isogeny that works with the SIDH countermeasures, and proposed a
|
||
novel non-interactive proof of parallel isogeny that reduced the number of rounds
|
||
to two.
|
||
The protocol is an important stepping stone towards fully practical post-
|
||
quantum OPRFs, but its performance is hindered by the inefficiency of the SIDH
|
||
countermeasures. In future work, we aim at developing more efficient solutions:
|
||
a moderate reduction in the degree of the isogenies would significantly improve
|
||
the efficiency of the protocol. It is also interesting to improve the proof of parallel
|
||
isogeny by avoiding validating the commitment isogeny at every interaction.
|
||
|
||
Acknowledgements. The author thanks Christophe Petit and Luca de Feo
|
||
for various suggestions, and Tako Boris Fouotsa, Christophe Petit, Chloe Mar-
|
||
tindale, and the anonymous reviewers of Crypto and the PQCifris workshop for
|
||
feedback on earlier versions of this work. The author would also like to thank
|
||
Luca de Feo, Antonin Leroux, and Benjamin Wesolowski for fruitful discussions
|
||
on isogeny-based zero-knowledge proofs at the Banff International Research Sta-
|
||
tion workshop “Supersingular Isogeny Graphs in Cryptography”.
|
||
This work has been supported in part by EPSRC via grant EP/R012288/1,
|
||
under the RISE (http://www.ukrise.org) programme.
|
||
|
||
|
||
References
|
||
1. Albrecht, M.R., Davidson, A., Deo, A., Smart, N.P.: Round-optimal verifiable
|
||
oblivious pseudorandom functions from ideal lattices. In: Garay, J. (ed.) PKC 2021,
|
||
Part II. LNCS, vol. 12711, pp. 261–289. Springer, Heidelberg (May 2021). https:
|
||
//doi.org/10.1007/978-3-030-75248-4 10
|
||
2. Azarderakhsh, R., Jao, D., Kalach, K., Koziel, B., Leonardi, C.: Key compression
|
||
for isogeny-based cryptosystems. In: Proceedings of the 3rd ACM International
|
||
Workshop on ASIA Public-Key Cryptography. pp. 1–10. ACM (2016)
|
||
A Post-Quantum Oblivious PRF from Isogenies 29
|
||
|
||
3. Basso, A., Codogni, G., Connolly, D., De Feo, L., Fouotsa, T.B., Lido, G.M., Mor-
|
||
rison, T., Panny, L., Patranabis, S., Wesolowski, B.: Supersingular curves you can
|
||
trust. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part II. LNCS, vol.
|
||
14005, pp. 405–437. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-
|
||
3-031-30617-4 14
|
||
4. Basso, A., Kutas, P., Merz, S.P., Petit, C., Sanso, A.: Cryptanalysis of an obliv-
|
||
ious PRF from supersingular isogenies. In: Tibouchi, M., Wang, H. (eds.) ASI-
|
||
ACRYPT 2021, Part I. LNCS, vol. 13090, pp. 160–184. Springer, Heidelberg (Dec
|
||
2021). https://doi.org/10.1007/978-3-030-92062-3 6
|
||
5. Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies.
|
||
In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492,
|
||
pp. 520–550. Springer, Heidelberg (Dec 2020). https://doi.org/10.1007/978-3-030-
|
||
64834-3 18
|
||
6. Canetti, R.: Universally composable security: A new paradigm for cryptographic
|
||
protocols. In: 42nd FOCS. pp. 136–145. IEEE Computer Society Press (Oct 2001).
|
||
https://doi.org/10.1109/SFCS.2001.959888
|
||
7. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay,
|
||
C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423–447.
|
||
Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4 15
|
||
8. Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from ex-
|
||
pander graphs. Journal of Cryptology 22(1), 93–113 (Jan 2009). https://doi.org/
|
||
10.1007/s00145-007-9002-x
|
||
9. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest,
|
||
R.L., Sherman, A.T. (eds.) CRYPTO’82. pp. 199–203. Plenum Press, New York,
|
||
USA (1982)
|
||
10. Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny
|
||
Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS,
|
||
vol. 9814, pp. 572–601. Springer, Heidelberg (Aug 2016). https://doi.org/10.1007/
|
||
978-3-662-53018-4 21
|
||
11. Davidson, A., Goldberg, I., Sullivan, N., Tankersley, G., Valsorda, F.: Privacy
|
||
Pass: Bypassing internet challenges anonymously. Proc. Priv. Enhancing Technol.
|
||
2018(3), 164–180 (2018). https://doi.org/10.1515/popets-2018-0026
|
||
12. De Feo, L., Dobson, S., Galbraith, S.D., Zobernig, L.: SIDH proof of knowledge. In:
|
||
Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part II. LNCS, vol. 13792, pp. 310–
|
||
339. Springer, Heidelberg (Dec 2022). https://doi.org/10.1007/978-3-031-22966-
|
||
4 11
|
||
13. Eisenträger, K., Hallgren, S., Lauter, K.E., Morrison, T., Petit, C.: Supersingular
|
||
isogeny graphs and endomorphism rings: Reductions and solutions. In: Nielsen,
|
||
J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 329–
|
||
368. Springer, Heidelberg (Apr / May 2018). https://doi.org/10.1007/978-3-319-
|
||
78372-7 11
|
||
14. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and
|
||
signature problems. In: Odlyzko, A.M. (ed.) CRYPTO’86. LNCS, vol. 263, pp. 186–
|
||
194. Springer, Heidelberg (Aug 1987). https://doi.org/10.1007/3-540-47721-7 12
|
||
15. Fouotsa, T.B., Moriya, T., Petit, C.: M-SIDH and MD-SIDH: Countering SIDH at-
|
||
tacks by masking information. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023,
|
||
Part V. LNCS, vol. 14008, pp. 282–309. Springer, Heidelberg (Apr 2023). https:
|
||
//doi.org/10.1007/978-3-031-30589-4 10
|
||
16. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious
|
||
pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–
|
||
30 Andrea Basso
|
||
|
||
324. Springer, Heidelberg (Feb 2005). https://doi.org/10.1007/978-3-540-30576-
|
||
7 17
|
||
17. Galbraith, S.D.: Authenticated key exchange for SIDH. Cryptology ePrint Archive,
|
||
Report 2018/266 (2018), https://eprint.iacr.org/2018/266
|
||
18. Heimberger, L., Meisingseth, F., Rechberger, C.: Oprfs from isogenies: Designs and
|
||
analysis. Cryptology ePrint Archive, Paper 2023/639 (2023), https://eprint.iacr.
|
||
org/2023/639
|
||
19. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular
|
||
elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th In-
|
||
ternational Workshop, PQCrypto 2011. pp. 19–34. Springer, Heidelberg (Nov / Dec
|
||
2011). https://doi.org/10.1007/978-3-642-25405-5 2
|
||
20. Jarecki, S., Kiayias, A., Krawczyk, H.: Round-optimal password-protected secret
|
||
sharing and T-PAKE in the password-only model. In: Sarkar, P., Iwata, T. (eds.)
|
||
ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 233–253. Springer, Heidelberg
|
||
(Dec 2014). https://doi.org/10.1007/978-3-662-45608-8 13
|
||
21. Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: TOPPSS: Cost-minimal password-
|
||
protected secret sharing based on threshold OPRF. In: Gollmann, D., Miyaji, A.,
|
||
Kikuchi, H. (eds.) ACNS 17. LNCS, vol. 10355, pp. 39–58. Springer, Heidelberg
|
||
(Jul 2017). https://doi.org/10.1007/978-3-319-61204-1 3
|
||
22. Jarecki, S., Krawczyk, H., Xu, J.: OPAQUE: An asymmetric PAKE protocol se-
|
||
cure against pre-computation attacks. In: Nielsen, J.B., Rijmen, V. (eds.) EU-
|
||
ROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 456–486. Springer, Heidelberg
|
||
(Apr / May 2018). https://doi.org/10.1007/978-3-319-78372-7 15
|
||
23. Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications
|
||
to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.)
|
||
TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (Mar 2009). https:
|
||
//doi.org/10.1007/978-3-642-00457-5 34
|
||
24. Lai, Y.F., Galbraith, S.D., Delpech de Saint Guilhem, C.: Compact, efficient
|
||
and UC-secure isogeny-based oblivious transfer. In: Canteaut, A., Standaert, F.X.
|
||
(eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 213–241. Springer, Hei-
|
||
delberg (Oct 2021). https://doi.org/10.1007/978-3-030-77870-5 8
|
||
25. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key
|
||
recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023,
|
||
Part V. LNCS, vol. 14008, pp. 448–471. Springer, Heidelberg (Apr 2023). https:
|
||
//doi.org/10.1007/978-3-031-30589-4 16
|
||
26. Merz, S.P., Minko, R., Petit, C.: Another look at some isogeny hardness assump-
|
||
tions. In: Topics in Cryptology - CT-RSA 2020 - the Cryptographers’ Track at the
|
||
RSA Conference 2020, San Francisco, CA, USA, February 24-28, 2020, Proceed-
|
||
ings. pp. 496–511 (2020)
|
||
27. Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random
|
||
functions. In: 38th FOCS. pp. 458–467. IEEE Computer Society Press (Oct 1997).
|
||
https://doi.org/10.1109/SFCS.1997.646134
|
||
28. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.)
|
||
EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472–503. Springer, Heidelberg
|
||
(Apr 2023). https://doi.org/10.1007/978-3-031-30589-4 17
|
||
29. Silverman, J.H.: The Arithmetic of Elliptic Curves, vol. 106. Springer Science &
|
||
Business Media (2009)
|
||
30. Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle
|
||
model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS,
|
||
vol. 9057, pp. 755–784. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/
|
||
978-3-662-46803-6 25
|
||
|