Secure Computation over Lattices and Elliptic Curves.

Silvio M. Micali, Phillip Rogaway

Vijay S, S. Shanmuga Priya, C. N. Harshavardhana +1 more

With the rise of quantum computing, traditional cryptographic algorithms, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), face potential vulnerabilities. Quantum computers could efficiently solve problems that are currently computationally infeasible for classical computers, thus threatening the security of cryptographic systems. As a result, there is a pressing need to develop quantum- resistant cryptographic algorithms to ensure secure communication in a future where quantum computing is prevalent. ECDSA, widely used for securing digital communications, relies on elliptic curve cryptography to provide robust security through digital signatures. However, the advent of quantum computing poses a significant threat to ECDSA's security, as quantum algorithms such as Shor's algorithm could break the elliptic curve-based encryption by efficiently solving discrete logarithm problems. To address this issue, we propose a quantum-resistant cryptographic algorithm based on lattice-based cryptography. Our approach utilizes the Learning With Errors (LWE) problem, known for its resistance to quantum attacks. We implement the proposed algorithm and compare its performance with ECDSA in terms of key generation time, signing time, and verification time. The algorithm's security is analyzed against quantum attacks using theoretical and empirical methods. The experimental results demonstrate that the quantum-resistant algorithm provides a comparable level of security to ECDSA while offering significant advantages in the context of quantum resistance. Specifically, our quantum-resistant algorithm achieved key generation times of 120 ms, signing times of 150 ms, and verification times of 100 ms. In comparison, ECDSA showed key generation times of 80 ms, signing times of 90 ms, and verification times of 70 ms. Despite these performance trade-offs, the quantum resistance of the proposed algorithm ensures future-proof security for digital communications.

Jodie Eicher, Yaw Opoku

This article gives an introduction to Elliptic Curve Cryptography and Quantum Computing. It includes an analysis of Peter Shor's algorithm for the quantum computer breakdown of Discrete Log Cryptosystems and an analog to Shor's algorithm for Elliptic Curve Cryptosystems. An extended example is included which illustrates how this modified Shor's algorithm will work. # Thanks to Hewlett-Packard for their generous support 1 1. Introduction The goa of this study is to developa nunderstaGW]] of howa qua tum computer, when creaW5( will bea]X tobrea the present da y elliptic curve cryptosystems. Elliptic curvesa re di#cult to work witha nd very di#cult ot understaN5 According to Dr.RonaN L. Rivest, founder of RSA Da ta Security, ... the security of crypotosystemsbaos on elliptic curves is not well understood, due inla]] pa] to thea7M5MX[ naM5M of elliptic curves. Few cryptograWX)( understaW elliptic curves, so there is not the sa( widesprea understaX)( an consensus concerning the security...

Eike Kiltz

Belcy D Mathews, Lagishetty Pavan Kumar, Muddasani Santhosh Varma +1 more

Ronald Cramer