A Zero-Knowledge Proof System with Algebraic Geometry Techniques
Source abstract
Abstract
Current requirements for ensuring data exchange over the internet to fight against security breaches have to consider new cryptographic attacks. The most recent advances in cryptanalysis are boosted by quantum computers, which are able to break common cryptographic primitives. This makes evident the need for developing further communication protocols to secure sensitive data. Zero-knowledge proof systems have been around for a while and have been considered for providing authentication and identification services, but it has only been in recent times that its popularity has risen due to novel applications in blockchain technology, Internet of Things, and cloud storage, among others. A new zero-knowledge proof system is presented, which bases its security in two main problems, known to be resistant, up to now, against quantum attacks: the graph isomorphism problem and the isomorphism of polynomials problem.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Polynomial and algebraic computation · Cryptographic Implementations and Security · Cryptography and Data Security
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science, CINVESTAV-IPN, Av. IPN 2508, Gustavo A. Madero, San Pedro Zacatenco, Mexico City 07360, Mexico
Department of Mathematics, CINVESTAV-IPN, Av. IPN 2508, Gustavo A. Madero, San Pedro Zacatenco, Mexico City 07360, Mexico
Funding
Consejo Nacional de Ciencia y Tecnología
References (30)
Show source-provided references
1. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems10.1145/359340.359342 ↗
2. National Institute of Standards and Technology (2013). Digital Signature Standard (DSS).
3. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer10.1137/S0097539795293172 ↗
4. Hopwood, D., Bowe, S., Hornby, T., and Wilcox, N. (2016). Zcash Protocol Specification, Zerocoin Electric Coin Company. Technical Report.
5. Identity-Based Remote Data Integrity Checking With Perfect Data Privacy Preserving for Cloud Storage10.1109/TIFS.2016.2615853 ↗
6. Beydemir, A., and Sogukpinar, I. (2017, January 5–8). Lightweight zero knowledge authentication for Internet of things. Proceedings of the 2017 International Conference on Computer Science and Engineering (UBMK), Antalya, Turkey.10.1109/UBMK.2017.8093410 ↗
7. Babai, L. (2016, January 18–21). Graph Isomorphism in Quasipolynomial Time. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA.10.1145/2897518.2897542 ↗
8. The Knowledge Complexity of Interactive Proof-systems10.1137/0218012 ↗
9. Bellare, M., Micali, S., and Ostrovsky, R. (1990, January 13–17). Perfect Zero-knowledge in Constant Rounds. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.10.1145/100216.100283 ↗
10. Practical graph isomorphism, II10.1016/j.jsc.2013.09.003 ↗
11. Codenotti, P., Katebi, H., Sakallah, K.A., and Markov, I.L. (2013, January 4–6). Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms. Proceedings of the International Conference on Tools with Artificial Intelligence of the IEEE, Herndon, VA, USA.10.1109/ICTAI.2013.139 ↗
12. Junttila, T., and Kaski, P. (2007, January 6). Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs. Proceedings of the Meeting on Algorithm Engineering & Experiments, New Orleans, LA, USA.10.1137/1.9781611972870.13 ↗
13. Authentication schemes from actions on graphs, groups, or rings10.1016/j.apal.2010.09.004 ↗
14. Patarin, J. (1996, January 12–16). Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain.10.1007/3-540-68339-9_4 ↗
15. Imai, H., and Matsumoto, T. (1985, January 15–19). Algebraic methods for constructing asymmetric cryptosystems. Proceedings of the 3rd International Conference on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Grenoble, France.
16. Matsumoto, T., and Imai, H. (1988, January 25–27). Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Davos, Switzerland.10.1007/3-540-45961-8_39 ↗
17. Ding, J., Gower, J.E., and Schmidt, D.S. (2006). Multivariate Public Key Cryptosystems, Springer.10.1090/conm/419/07997 ↗
18. Patarin, J. (1995, January 27–31). Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88. Proceedings of the 37th Annual International Cryptology Conference, Santa Barbara, CA, USA.10.1007/3-540-44750-4_20 ↗
19. Kipnis, A., Patarin, J., and Goubin, L. (1999, January 2–6). Unbalanced Oil and Vinegar Signature Schemes. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic.10.1007/3-540-48910-X_15 ↗
20. Ding, J., and Schmidt, D. (2005, January 7–10). Rainbow, a New Multivariable Polynomial Signature Scheme. Proceedings of the Third International Conference on Applied Cryptography and Network Security, New York, NY, USA.10.1007/11496137_12 ↗
21. (2019, November 04). National Institute of Standards and Technology.Candidate Quantum-Resistant Cryptographic Algorithms Publicly Available, Available online: https://www.nist.gov/news-events/news/2017/12/candidate-quantum-resistant-cryptographic-algorithms-publicly-available.
22. Buchberger, B. (1998). An Algorithmic Criterion for the Solvability of a System of Algebraic Equations. Gröbner Bases and Applications, Cambridge University Press. Number 251 in Lond Math S.10.1017/CBO9780511565847.034 ↗
23. Bernstein, D.J., Buchmann, J., and Dahmen, E. (2009). Post-Quantum Cryptography, Springer. [1st ed.].10.1007/978-3-540-88702-7 ↗
24. Linear Recurrence Equations on a Tree10.1007/s11006-005-0163-3 ↗
25. Combinatorial and asymptotic methods in algebra
26. Faugère, J.C., and Joux, A. (2003, January 17–21). Algebraic cryptanalysis of Hidden Field Equations (HFE) Using Gröbner Bases. Proceedings of the 23rd Annual International Cryptology Conference, Santa Barbara, CA, USA.10.1007/978-3-540-45146-4_3 ↗
27. Braeken, A., Wolf, C., and Preneel, B. (2005, January 14–18). A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes. Proceedings of the Cryptographers’ Track at the RSA Conference, San Francisco, CA, USA.10.1007/978-3-540-30574-3_4 ↗
28. Bard, G. (2009). Algebraic Cryptanalysis, Springer. [1st ed.].10.1007/978-0-387-88757-9 ↗
29. Goldreich, O. (2008). Computational Complexity: A Conceptual Perspective, Cambridge University Press.10.1017/CBO9780511804106 ↗
30. Nemhauser, G.L., and Wolsey, L.A. (1988). Integer and Combinatorial Optimization, Wiley-Interscience.10.1002/9781118627372 ↗