Hot answers tagged

16 votes

The death of isogeny-based cryptography?

It's early days to assess the full implications yet, but there is an excellent blog by Stephen Galbraith that seems to indicate that this does not currently apply to all isogeny-based schemes (in ...
Daniel S's user avatar
  • 23k
10 votes
Accepted

How to get an optimal strategy in computing isogenies for SIDH/SIKE

On page 67 of the same spec, Algorithm 42 does exactly what you are asking for. Here it is again in Python: ...
Luca De Feo's user avatar
8 votes
Accepted

SIKE: choice of n

I am the principal submitter for the SIKE proposal. The reference implementation uses 24, 32, and 40 bytes respectively for SIKEp503, SIKEp751, and SIKEp964 respectively. The motivation for these ...
djao's user avatar
  • 776
8 votes
Accepted

Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why?

Is SIDH actually insecure when keys are reused? If so, why? How can SIDH actually be broken? Can you demonstrate an attack? Yes it is. There is a well known adaptative attack, described here ...
Luca De Feo's user avatar
7 votes
Accepted

Has Burdges and De Feo's concept of Delayed Encryption ever been implemented?

There is PoC code for the De Feo-Masson-Petit-Sanso VDF here: https://github.com/isogenies-vdf/isogenies-vdf-sage. It's easily adapted to Delay Encryption.
Luca De Feo's user avatar
6 votes

How does the key size in supersingular isogeny schemes relate to their security level?

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$. To clarify, there are no complex numbers used at all. The elliptic curve is over a quadratic ...
Rino Sanchez's user avatar
6 votes
Accepted

SIKE/SIDH algorithm 6

Not a complete answer, just trying to shed some of your doubts. I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses ...
Luca De Feo's user avatar
5 votes

Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme

Block cipher is a concept from symmetric cryptography. Here we're talking about public key cryptography. SIKE is a public key encryption (PKE), and a key encapsulation mechanism (KEM). Of course ...
Luca De Feo's user avatar
5 votes
Accepted

Exactly what part of SIDH is proven to be NP-hard?

SIDH is believed to be quantum secure because the fastest known quantum attacks against it (which is based on claw finding algorithm) require exponential time with complexity $\mathcal{O}(p^{1/6})$.
Hamidreza's user avatar
  • 1,019
5 votes

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?

You are right that Vélu's formulas also work for any extension field, but then they require arithmetic in that field. Doing computations in $\mathbb F_p$ is simply much more efficient than in ...
yyyyyyy's user avatar
  • 12.1k
5 votes
Accepted

Why are computations (isogeny) in SIDH done in an extended prime field?

I am an inventor of SIDH. The computations take place in $\operatorname{GF}(p^2)$ just because all supersingular elliptic curves are defined over $\operatorname{GF}(p^2)$, up to isomorphism. It's just ...
djao's user avatar
  • 776
4 votes
Accepted

SIKE as Diffie-Hellman exchange

I am one of the inventors of SIKE. There is no actual Diffie-Hellman group in SIKE. If there were, then SIKE would be vulnerable to Shor's algorithm, as you said, largely defeating the purpose of a ...
djao's user avatar
  • 776
4 votes

SIDH: key agreement - why does it work?

I invented SIDH and can surely answer any technical questions about it. Proofs of $E_{ab} \cong E_{ba}$ are given in several places, though rarely in official Theorem / Proof form, because this result ...
djao's user avatar
  • 776
4 votes
Accepted

SIDH cryptosystem question

I invented SIDH. $E_0[\ell_A^{e_A}]$ has cardinality $(\ell_A^{e_A})^2$. Each of $P_A$, $Q_A$, and $R$ has order $\ell_A^{e_A}$ and they all generate different subgroups. This is possible because $E_0[...
djao's user avatar
  • 776
4 votes
Accepted

How to compute a smooth-degree isogeny given a generator point of its kernel?

The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree. ...
yyyyyyy's user avatar
  • 12.1k
4 votes
Accepted

Using Microsoft SIDH library for messages signing

SIDH is a key exchange algorithm, not a digital signature algorithm. The way SIDH works is each side generates a private, random value along with a corresponding public value. The public values are ...
forest's user avatar
  • 15.2k
4 votes
Accepted

What basic knowledge is required to understand SIKE?

Craig Costello has tried writing precisely what you're interested in, see SIKE for Beginners. It refers to numerous other surveys for isogeny-based crypto which may be useful (lecture notes by De Feo, ...
Mark's user avatar
  • 12.5k
4 votes
Accepted

CSIDH - l ideal generators

To answer your first question: it's as simple as that. Restating what you wrote, it's enough to check that $l$ divides all the four generators: $l^2$, $l(π-1)$, $l(π+1)$ and $π^2-1$. It's obvious for ...
Luca De Feo's user avatar
3 votes

Any Supersingular Isogeny-based Diffie-Hellman (SIDH) key exchange recommended Curve Domain Parameters?

All 'good' implementations so far have used the same curve, but there is now variation in the underlying finite field, which affects the other base parameters of the public points for each party and ...
Deirdre Connolly's user avatar
3 votes

Finding the subgroup in isogeny-based cryptography

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-...
Luiz Carvalho's user avatar
3 votes
Accepted

How are isogeny graphs made and how are they helpful to crypto?

Let an elliptic curve $E(F_p)$ have the Frobenius discriminant $D_\pi$, and $\left(\frac{D_\pi}{l}\right)$ be a Kronecker symbol for some $l$-degree isogeny. If $\left(\frac{D_\pi}{l}\right)=-1$, then ...
Meysam Ghahramani's user avatar
3 votes

How could you find the preimage of an isogeny function?

Isogenies are always surjective, but there's a nuance. They are surjective over the algebraic closure. The correct statement would be "for every $\mathbb{F}_{17}$-point on the green curve there are ...
Luca De Feo's user avatar
2 votes

SIKE as Diffie-Hellman exchange

what is the underlying group Isogenies do not form a group; one easy way to show that is that inverses do not exist. An isogeny is a mapping between two elliptic curves $A$ and $B$ that maps a ...
poncho's user avatar
  • 146k
2 votes
Accepted

How to Sample from Frobenius Eigenspace?

The Frobenius eigenspace of $-1$ is, by definition, the kernel of the map $π+1$. Typically, this is further restricted to some torsion group $E[ℓ]$, so we are really talking about $E[ℓ] ∩ E[π+1]$, i.e....
Luca De Feo's user avatar
2 votes

SIDH cryptosystem question

You appear to be under the impression that Elliptic Curve groups are always cyclic, and that there is only one subgroup of a given order. That is not the case, and it is most definitely not the case ...
poncho's user avatar
  • 146k
2 votes

Finding the subgroup in isogeny-based cryptography

There is a quantum sub-exponential time algorithm to extract the private keys from the system you cite. Another paper by Luca De Feo, David Jao, and Jerome Plut improves upon that system, addresses ...
Jeff Burdges's user avatar
  • 1,116
2 votes

DSSP reduction to DSSI

Suppose given a DSSP instance $\phi$, $(E_1,E_2,\phi')$ as defined in the paper. The goal is to use a DSSI oracle to decide if $\phi'$ is "parallel" to $\phi$ with "distance" $\ell_B^{e_B}$, that is, ...
yyyyyyy's user avatar
  • 12.1k
2 votes
Accepted

SIKE algorithm 2

result s is chosen randomly and is not known by the other party. That is correct; it is unpredictable to any other party; that's the point. What line 16 (and lines 11-13 as well) is there for is to ...
poncho's user avatar
  • 146k

Only top scored, non community-wiki answers of a minimum length are eligible