Questions tagged [isogeny]
Elliptic curve isogenies are structure-preserving maps between elliptic curves which have been proposed as a foundation of post-quantum cryptosystems.
47
questions
1
vote
0
answers
24
views
Is there a curve that supports both pairing checks and Montgomery ladders?
Is there a curve that supports both?
Or are there two curves that can be mapped between using a 2-isogeny that support pairing checks on one and Montgomery ladders on the other?
Is there a paper on it?...
- 11
0
votes
1
answer
60
views
Is it possible to map points from curve BN254 to C25519 and back using a 2-isogeny?
If it is could you give me a paper that states it is possible?
Thank you
- 3
3
votes
2
answers
149
views
CSIDH - The inverse problem
I started studying CSIDH a few weeks ago and, seeing these papers [1] [2], I was wondering:
Given $[a]E$ and $E$, find $[a]^{-1}E$.
I read that is easy to find $[a]^{-1}E_0$ knowing $[a]E_0$ by ...
15
votes
1
answer
4k
views
The death of isogeny-based cryptography?
Wouter Castryck and Thomas Decru recently broke SIDH.
From the abstract:
We present an efficient key recovery attack on the Supersingular
Isogeny Diffie-Hellman protocol (SIDH), based on a "glue-...
- 151
2
votes
0
answers
57
views
Generating pairs of elliptic $\mathbb{F}_q$-curves isogenous over $\mathbb{F}_q$ such that nobody knows an $\mathbb{F}_q$-isogeny between them
Let $\mathbb{F}_q$ be a large finite field. What if I invent how to efficiently construct pairs of elliptic "cryptographically strong" $\mathbb{F}_q$-curves $E_1$, $E_2$ isogenous over $\...
- 395
1
vote
0
answers
48
views
What is an advantage of the Charles--Lauter--Goren hash function?
What is an advantage of the Charles--Lauter--Goren hash function (based on isogenies of elliptic curves) among other provably secure collision-resistance hash functions ? I heard that it is slower.
- 395
7
votes
1
answer
256
views
CSIDH - l ideal generators
I am trying to study the CSIDH algorithm. I have some beginner background in elliptic curves and I have been following Andrew Sutherland's lectures (https://math.mit.edu/classes/18.783/2019/lectures....
- 392
2
votes
0
answers
87
views
Cryptographic invariant maps
In [BGK+18] in section 4, Boneh et al. write that:
For any choice of ideal classes
$\mathfrak{a}_1,\dots,\mathfrak{a}_n,\mathfrak{a}_1',\dots,\mathfrak{a}_n'$
in ${Cl}(\mathcal{O})$, the abelian ...
- 173
0
votes
1
answer
126
views
Theorem of the dual isogeny in SIDH Zk proof
In the proof of soundness for the SIDH ZK proof protocol (section 6.2 in DJP11) the authors refer to the "Theorem of the dual isogeny". What do they mean by this?
In particular, I don't ...
- 173
3
votes
2
answers
146
views
Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary?
In the original SIDH paper by De Feo, Jao and Plût, the basis points $P_A$ and $Q_A$ are supposed to be independent points in $E(\mathbb{F}_{p^2})$ of order $\ell_A^{e_A}$ for some small prime $\ell_A$...
- 33
2
votes
0
answers
91
views
Question about using isogenies to mask elliptic pair
For this question I'm referring to the ed25519 algorithm
In blockchain one project (Monero) shot itself in the foot a while back by having senders derive public keys from an ed25519 pair, by ...
- 135
1
vote
1
answer
166
views
Has Burdges and De Feo's concept of Delayed Encryption ever been implemented?
In mid 2020 Jeffrey Burdges and Luca De Feo published a paper proposing a trapdoor-less time-lock puzzle called Delay Encryption. Has a prototype of this ever been made?
- 498
0
votes
1
answer
134
views
CSIDH Squaring Fixing the Base Curve
Consider the following variants of the CSIDH squaring problem.
P1. Given $sE, E$ where $s$ is a random ideal class and $E$ is a random curve (reachable from initial $E_0$), find $s^2E$
P2. Given $sE_0$...
- 133
1
vote
1
answer
428
views
What basic knowledge is required to understand SIKE?
I'm interested in learning about Supersingular Isogeny based Key Encapsulation mechanism.
Currently, I only know all the basic knowledge about how standard Elliptic Curve Cryptography, works, using ...
- 1,000
0
votes
1
answer
125
views
Characteristics of an isogeny between super-singular elliptic curves
I believe I've read this before, but I can't find it despite hours of searching on Google.
I've know the common definition of isogeny in elliptic curves, as $\phi:E_1 \rightarrow E_2$ a nonconstant ...
- 1,374
1
vote
2
answers
156
views
SIKE as Diffie-Hellman exchange
SIKE involves a Diffie-Hellman like construction using isogenies between elliptic curves. Is it possible to express it as an instance of Diffie-Hellman? I.e. what is the underlying group if so, and ...
- 113
1
vote
0
answers
84
views
How to Reduce a Quaternion Ideal into Power Smoothness?
(TL;DR) How exactly do we reduce a quaternion ideal into another powersmooth one?
Given a supersingular elliptic curve, it is known that its endomorphism ring is non-commutative. Specifically, there ...
- 133
2
votes
1
answer
191
views
How to Sample from Frobenius Eigenspace?
So I was implementing the $2$-point method described here[1], which requires to samples two points $P_0, P_1$ in the Frobenius eigenspace initially. It uses a method called Elligator, which seems to ...
- 133
2
votes
1
answer
315
views
How to find kernel of isogeny from the dual isogeny
Let $E$ be a supersingular elliptic curve over $\mathbb{F}_{p^2}$, where $p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$ for some primes $\ell_A, \ell_B$.
Let $R \in E[\ell_A^{e_A}]$ be a point of order $\...
- 23
0
votes
1
answer
81
views
Public points in SIDH
I was going through a presentation titled "SIKE in Hardware" by professor Reza Azarderakhsh. On the page $10$ of the presentation he introduces a variable $w$. Could you please explain what the ...
- 53
3
votes
1
answer
189
views
SIDH: key agreement - why does it work?
In SIDH both parties agree on the key in following way:
Alice calculates a kernel $R = mPB + nQB$
Thanks to Velu formulas (and further improvements), she can now compute isogeny $\phi_a$
She uses $\...
- 365
1
vote
2
answers
179
views
SIDH cryptosystem question
I'm trying to understand the SIDH cryptosystem and got confused at this point:
Alice fixes base $\{P_A,Q_A\}$ so that it generates $E_0[l_A^{e_A}]$. Then she chooses secret parameters $m_A,n_A$ and ...
- 173
2
votes
1
answer
250
views
CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?
I am trying to understand the action of the CSIDH protocol.
Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{...
- 151
3
votes
1
answer
153
views
Why are computations (isogeny) in SIDH done in an extended prime field?
While reading the SIDH key exchange protocol, I noticed that all the isogeny computations and curves are defined over the extended prime field $\mathbb{F}_{p^2}$. Does it make the problem ...
- 53
1
vote
0
answers
67
views
What does the absence of Abelian group actions on supersingular isogenies implicate?
There are no Abelian group actions on supersingular isogenies. Why does this make them secure? - motivated by De Feo's Paper on mathematics of IBS
- 115
3
votes
1
answer
243
views
How are isogeny graphs made and how are they helpful to crypto?
I don't understand how the shapes of isogeny graphs are determined. While Alice and Bob do walk on it and don't backtrack, are they actually relevant to crypto?
Also, I was told that supersingular ...
- 115
1
vote
1
answer
300
views
Exactly what part of SIDH is proven to be NP-hard?
SIDH is quantum secure, why is it quantum secure? Exactly which part of the algorithm is proven to be NP-hard? Computing the isogeny function?
- 115
2
votes
1
answer
197
views
How could you find the preimage of an isogeny function?
How do you know if an isogeny is surjective or not, and how do you tell how many points on E maps to E'? Does the answer lie in the degree of the isogeny function?
- 115
0
votes
1
answer
210
views
Using Microsoft SIDH library for messages signing
SIDH library looks good but lacks documentation and samples.
The only signature-related code was found at http://github.com/yhyoo93/isogenysignature/blob/master/tests/kex_tests.c appeared not able to ...
- 13
2
votes
1
answer
387
views
SIKE/SIDH algorithm 6
I was recently reading this paper on SIKE and I'm trying to understand the details of the implementation.
I've noticed the point tripling algorithm (algorithm 6) was already described in a different ...
- 365
5
votes
1
answer
199
views
SIKE: choice of n
The "Supersingular Isogeny Key Encapsulation" proposal submited to PQC-NIST (PDF) defines the value $n$ to be from set $\{192,256,320\}$ (see point 1.4). Does anybody have an idea to what it ...
- 365
0
votes
1
answer
139
views
SIKE algorithm 2
I was recently reading this paper on SIKE and there on page 20 I encountered algorithm 2. I understanding line 14 of algorithm 2 in sike but I don't understanding line 17 of algorithm 2. $h (s || (c_0,...
- 3
6
votes
2
answers
484
views
How to get an optimal strategy in computing isogenies for SIDH/SIKE
How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec?
If possible, can anyone give me an example?
And why do we need to compute all leaf point? I though we just need ...
- 107
1
vote
1
answer
306
views
Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme
I'm a newbie in studying and learning how SIDH works.
I have a simple doubt.
So my question is in the SIKE submission present in this link (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/...
- 31
2
votes
2
answers
685
views
How to compute a smooth-degree isogeny given a generator point of its kernel?
I need to compute an isogeny from $E: y^2 = x^3 + ax + b$, given a generator point for its kernel subgroup, using Python.
The point has smooth order.
I need both the parameters for the curve and ...
- 107
2
votes
1
answer
173
views
Supersingular isogeny Diffie–Hellman key exchange (SIDH) Library Support AES-256?
In the version 3.0 of the SIDH library, it implements SIDH/SIKEp503 (AES-128) and SIDH/SIKEp751 (AES-192) only.
Are there plans to incorporate AES-256?
Nathan Aw
- 2,257
5
votes
1
answer
312
views
Any Supersingular Isogeny-based Diffie-Hellman (SIDH) key exchange recommended Curve Domain Parameters?
For existing ECDH, I understand that there are recommended Elliptic Curve Domain Parameters. May I know if there are such similar considerations in SIDH? Any recommended Curve Domain Parameters?
- 2,257
5
votes
1
answer
928
views
Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why?
I was considering using Microsoft's SIDH implementation for post-quantum public-key encryption because of its relatively small key size. I realized however, thanks to Issue #4, that it might not be as ...
- 120
4
votes
0
answers
392
views
How can I calculate the security level provided by a supersingular Elliptic Curve?
I want to know what security level is provided by an elliptic curve used in Supersingular isogeny Diffie–Hellman key exchange (SIDH). Is there any mathematical convention to follow or by looking at ...
- 83
4
votes
2
answers
844
views
Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation
In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states:
Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-...
- 41
4
votes
2
answers
293
views
How does the key size in supersingular isogeny schemes relate to their security level?
I'm looking at the De Feo, Jao, and Plût 2014 paper:
Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.
My understanding of section 3.2 Key Exchange, is that Alice'...
- 3,577
6
votes
2
answers
479
views
Finding the subgroup in isogeny-based cryptography
Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem:
Elliptic curves are ...
- 2,323
6
votes
3
answers
703
views
Supersingular Isogeny Key Exchange broken?
Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves.
https://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf
with the quote "...
- 461
3
votes
1
answer
152
views
DSSP reduction to DSSI
In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional ...
- 502
5
votes
1
answer
221
views
Parameter choice Supersingular Isogeny DH
In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies” by DeFeo, Jao and Plut (PDF), the public parameters are defined as:
Supersingular curve $E$, and
bases $P, Q$ ...
- 502
3
votes
1
answer
1k
views
Supersingular Isogeny Key Exchange Software [closed]
Are there any optimised implementations of the Supersingular Isogeny Key Exchange by Defeo, Jao, and Plut. It seems like this would be a great drop-in replacement for Diffie-Hellman in both OpenSSL ...
- 31
3
votes
2
answers
502
views
PQ Key Exchange based on Elliptic Curve Isogenies
I was reading the Wikipedia article on Post Quantum Cryptography and was interested in opinions as to whether the Supersingular Elliptic Curve Isogeny Diffie-Hellman listed there would be a good Post ...
- 31