What is an isogeny, and why is computing endomorphism rings hard?
Think about your answer, then reveal below.
Model answer: An isogeny is a morphism between elliptic curves preserving group structure. The endomorphism ring of an elliptic curve is the set of isogenies from the curve to itself. Computing endomorphism rings is hard because it requires finding lattice structures in very high-dimensional spaces (typically dimension 1000+). No polynomial-time algorithm is known for classical or quantum computers. This hardness is the cryptographic foundation: in SIKE/CSIDH, the private key encodes endomorphisms, the public key is the isogenized curve, and computing the private key from the public key requires solving the endomorphism ring problem.
Isogeny-based cryptography exploits a different hard problem than lattices or codes, providing diversity in post-quantum assumptions.
Question 2 True / False
Isogeny-based schemes have smaller keys/ciphertexts than lattice-based, but key generation is slow. Why?
TTrue
FFalse
Answer: True
Isogenies over elliptic curves are very structured objects. Computing them requires careful algebraic geometry (e.g., computing Hilbert class polynomials). This computational overhead during key generation is unavoidable. The trade-off is: small, elegant parameters (suitable for embedded devices, bandwidth-constrained networks) at the cost of slow key generation. For applications where keys are reused or generated infrequently, this trade-off is acceptable.