Improving the CSIDH Protocol for Multi-party Cryptography: Rigorous Mathematical Analysis, Efficiency, and Security Comparison
Downloads
This paper introduces a novel Distributed Key Generation (DKG) protocol based on the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) framework for secure multi-party cryptography. Our proposed protocol is designed to address scalability and security concerns, particularly in post-quantum cryptographic systems. The main contributions include the introduction of Piecewise Verifiable Proofs (PVPs) for non-interactive zero-knowledge verification of secret shares, and the provision of rigorous security analysis, including resistance to quantum adversaries via Shor’s and Grover’s algorithms. We analyze the protocol’s efficiency, ensuring low computational overhead even in large-scale systems, and compare it with other distributed cryptographic protocols such as RSA-based and lattice-based schemes. Through mathematical proofs and complexity analysis, we demonstrate that our protocol offers enhanced security, efficiency, and scalability in a post-quantum environment. The results presented in this paper provide a strong foundation for implementing secure multi-party computations in quantum-resistant systems.
J. Silverman, The Arithmetic of Elliptic Curves. Springer, 2009.
D. Jao and L. De Feo, ”Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Post-Quantum Cryptography, 2011, pp. 19–34.
D. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, ”CSIDH: An efficient post-quantum commutative group action,” in Advances in Cryptology – ASIACRYPT 2018, pp. 395–427.
L. De Feo and D. Jao, ”Towards quantum-resistant cryptosystems: Supersingular isogeny graphs,” in
Post-Quantum Cryptography, 2011.
A. Shamir, ”How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979.
P. Shor, ”Algorithms for quantum computation: Discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
L. Grover, ”A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996.
D. Unruh, ”Post-quantum security of Fiat-Shamir,” in Advances in Cryptology - ASIACRYPT 2017, pp. 65–95.
D. Boneh and M. Franklin, ”Efficient generation of shared RSA keys,” in Proceedings of Advances in Cryptology - CRYPTO ’97, pp. 425–439.
C. Peikert, ”A decade of lattice cryptography,” Foundations and Trends in Theoretical Computer Sci- ence, vol. 10, no. 4, pp. 283–424, 2016.
V. Vaikuntanathan, ”Lattice cryptography,” in Advances in Cryptology – CRYPTO 2017, pp. 48–76.
C. Costello, ”A brief introduction to isogeny-based cryptography,” in Proceedings of Real World Crypto 2019.
L. De Feo, D. Jao, and J. Pluˆt, ”Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Journal of Mathematical Cryptology, 2014, vol. 8, no. 3, pp. 209–247.
S. Goldwasser, S. Micali, and C. Rackoff, ”The knowledge complexity of interactive proof systems,”
SIAM Journal on Computing, vol. 18, no. 1, pp. 186–208, 1989.
