Staff Research Scientist, Visa Research
A Practical Approach to Effective Cryptography in a Post-Quantum Computing World
Cryptography trapdoors, implying mathematical functions that are easy to calculate but hard to reverse, are the foundation of modern cryptography. The schoolbook example is how multiplying two extremely large prime numbers is easy from a computational perspective, while factorizing the result of the multiplication back to its original two prime numbers is considered difficult. In his talk at Upgrade 2020, the recent NTT Research Summit, Yilei Chen from Visa Research talks about hard elliptic curve isogeny problems over RSA moduli and groups with infeasible inversion. Chen’s work expands upon work initiated by Molnar and Hohenberg in 2003 and further continued by Irrer et al in 2004.
In their work, Molnar and Hohenberg proved how infeasible inversion would have huge implications for the ability to create directed transitive cryptographic signatures, in addition to making it easy to implement broadcast encryption without much overhead. (The latter was shown by Irrer et al in 2004.) In such a way the work is arguably related to Proxy Re-Encryption, in that it provides transitive cryptography mechanisms and new cryptography primitives, with the possibility of having important real-world applications.
An elliptic curve isogeny is a mapping from one elliptic curve to another. Chen’s work is easily visualized by imagining an elliptic curve isogeny as a volcano and using the intersections in the isogeny graph as cryptography primitives. Chen’s work illustrates how to create cryptography primitives using his approach and elliptic curve isogenies over RSA moduli that are easy to compose and calculate, but very hard to reversely calculate – implying a simple composition, yet infeasible inversion.
In his talk, Chen discusses most of the elements required to understand his approach, and provides references for further reading where necessary.
For the full transcript of Yilei Chen’s presentation, click here.
Watch Yilei Chen’s full presentation below.
Hard Problems on Isogeny Graphs over RSA Moduli and Groups with Infeasible Inversion