Abstract:
Cryptography has a rich history, spanning thousands of years and evolving from ancient techniques such as the scytale and Caesar’s cipher to modern systems like RSA, DHKE, and ECDH. However, quantum computing poses a substantial threat to the security of these modern cryptosystems. To address this challenge, post-quantum cryptography
has emerged, with various branches including hash-based cryptography, code-based
cryptography, multivariate cryptography, lattice-based cryptography, and isogeny-based
cryptography.
Isogeny-based cryptography, a promising and relatively new area of research in postquantum
cryptography, employs algebraic mappings between elliptic curves to create
cryptographic systems. Despite recent advancements challenging the hardness of the
SIDH problem, an isogeny problem with additional information, several cryptosystems
remain secure and continue to flourish. Isogeny-based cryptography is a vibrant and active
research field.
This thesis delves into the fascinating world of advanced isogeny-based cryptosystems,
discussing their primitives, challenges, and innovative approaches to their development.
Topics covered include oblivious transfers, ring signatures, group signatures, blind signatures,
verifiable random functions, and the application of generic proof systems to
isogenies.
Concretely and first, we present the first efficient UC-secure oblivious transfer using
only a constant number of isogeny computations based on the group action inverse problem
(GAIP). To prove this, we propose a new assumption, the reciprocal CDH assumption, and
show the equivalence to the GAIP. Second, we present the first post-quantum accountable
ring signature, which immediately implies the first efficient isogeny-based group signature
with proof size logarithmic in the number of members. Here, we also show how to use the
Katz-Wang method to obtain a tight-secure variant, which is a less explored feature in the
post-quantum group/ring signature literature. Third, we present the first provably secure
blind signatures from isogenies based on the GAIP. Here, we present a novel approach
to optimize the result by proposing a new assumption, the ring-GAIP. We also give a
thorough analysis of it and show the equivalence to the GAIP for a few cases. Fourth, we
present the first provably secure verifiable random functions from isogenies based on the standard DDH assumption. To prove this, we propose a generalized DDH assumption,
the master DDH assumption, and show the equivalence to the DDH problem. Here, we
also give a new use of the quadratic twist and relax the assumption to optimize the
performance. Finally, we present the first practical application of generic proof systems
to the isogeny construction. Here, we consider the identification scheme for an isogeny
problem with a smooth degree.
All presented constructions have advantages over previously published schemes in
terms of the security notions achieved or the performance or both. By offering a thorough
analysis of these cryptosystems, this thesis lays a solid foundation for those new to the
subject. It equips readers with a comprehensive understanding of the principles and
potential applications of isogeny-based cryptosystems, fostering further research and
development in this exciting area of post-quantum cryptography.