Abstract:
Cryptography plays a vital role in the modern age of computing and security. Of the many branches of cryptography, we primarily focus on two in this thesis. The first is post-quantum secure key exchange from isogenies. Key exchange protocols are critical for setting up secure communication over the internet. We construct a new initial key agreement protocol to replace the classical extended triple Diffie-Hellman (X3DH) scheme in the Signal Protocol, using Supersingular Isogeny Diffie–Hellman (SIDH) for post-quantum security. As part of this work, we introduce a new model capturing the security properties of Signal X3DH, and within this model prove security of our new scheme (SI-X3DH). The SI-X3DH protocol requires a way of proving knowledge of SIDH secret keys. This brings us to the second primary focus of this thesis: zero-knowledge proofs. As suggested by the name, such schemes allow a statement to be proved without leaking any information other than the validity of the statement. We propose a zero-knowledge proof protocol that fixes a flaw in the security proof of the De Feo–Jao–Plût identification scheme from 2014. We then propose a second protocol that additionally proves correctness of the torsion points in SIDH public keys. These schemes admit the first secure, non-interactive Proofs of Knowledge for SIDH secret keys. Still in the line of zero-knowledge proofs, we study a primitive used in various classical constructions: unknown-order groups. Our contributions here are threefold. We study the security of recommended parameter sizes for ideal class groups as groups of unknown order, and show that these do not meet their claimed level of security when accounting for Sutherland’s primorial steps algorithm in generic groups. In response, we propose new parameters for various levels of security. Secondly, we give a new method of compressing elements of ideal class groups, requiring only 3/4 of their uncompressed size. Finally, we concretely propose a new method of generating groups of unknown order using Jacobians of genus-3 hyperelliptic curves-including an analysis of their security. We show that Jacobians may provide a more efficient choice for unknown-ordergroups than ideal class groups of imaginary quadratic fields.