- Previous Article
- AMC Home
- This Issue
-
Next Article
New mission and opportunity for mathematics researchers: Cryptography in the quantum era
Giophantus distinguishing attack is a low dimensional learning with errors problem
University of Cincinnati, Cincinnati, OH 45219, USA |
In this paper, we attack the recent NIST submission Giophantus, a public key encryption scheme. We find that the complicated structure of Giophantus's ciphertexts leaks information via a correspondence from a low dimensional lattice. This allows us to distinguish encrypted data from random data by the LLL algorithm. This is a more efficient attack than previous proposed attacks.
References:
| [1] |
K. Akiyama, Y. Goto, S. Okumura, T. Takagi, K. Nuida, G. Hanaoka, H. Shimizu and Y. Ikematsu, A public-key encryption scheme based on non-linear indeterminate equations (Giophantus), Cryptology ePrint Archive, Report 2017/1241, (2017), Available from: https://eprint.iacr.org/2017/1241. |
| [2] |
K. Akiyama, Indeterminate equation public-key cryptosystem "$Giophantus$", First PQC Standardization Conference, Fort Lauderdale FL. USA, (2018), Available from: https://csrc.nist.gov/CSRC/media/Presentations/Giophantus/images-media/Giophantus-April2018.pdf. |
| [3] |
M. R. Albrecht, R. Fitzpatrick and F. Göpfert, On the efficacy of solving LWE by reduction to unique-SVP, International Conference on Information Security and Cryptology, Cryptology ePrint Archive, Report 2013/602, 8565 (2013), 293–310, Available from: https://eprint.iacr.org/2013/602.
doi: 10.1007/978-3-319-12160-4_18. |
| [4] |
W. Beullens, W. Castryck and F. Vercauteren, IND-CPA attack on Giophantus, (2018), Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Giophantus-official-comment.pdf. |
| [5] |
J. T. Ding, S. Alsayigh, R. V. Saraswathy, S. Fluhrer and X. D. Lin, Leakage of Signal function with reused keys in RLWE key exchange, 2017 IEEE International Conference on Communications (ICC), (2017), Available from: https://eprint.iacr.org/2016/1176.
doi: 10.1109/ICC.2017.7996806. |
| [6] |
S. Fluhrer, Cryptanalysis of ring-LWE based key exchange with key share reuse, Cryptology ePrint Archive: Report 2016/085, (2016), Available from: https://eprint.iacr.org/2016/085. |
| [7] |
P. Nguyen, Giophantus and *LWR-based submissions, (2018), Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Giophantus-official-comment.pdf. |
| [8] |
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the Annual ACM Symposium on Theory of Computing, (2005), 84–93.
doi: 10.1145/1060590.1060603. |
show all references
References:
| [1] |
K. Akiyama, Y. Goto, S. Okumura, T. Takagi, K. Nuida, G. Hanaoka, H. Shimizu and Y. Ikematsu, A public-key encryption scheme based on non-linear indeterminate equations (Giophantus), Cryptology ePrint Archive, Report 2017/1241, (2017), Available from: https://eprint.iacr.org/2017/1241. |
| [2] |
K. Akiyama, Indeterminate equation public-key cryptosystem "$Giophantus$", First PQC Standardization Conference, Fort Lauderdale FL. USA, (2018), Available from: https://csrc.nist.gov/CSRC/media/Presentations/Giophantus/images-media/Giophantus-April2018.pdf. |
| [3] |
M. R. Albrecht, R. Fitzpatrick and F. Göpfert, On the efficacy of solving LWE by reduction to unique-SVP, International Conference on Information Security and Cryptology, Cryptology ePrint Archive, Report 2013/602, 8565 (2013), 293–310, Available from: https://eprint.iacr.org/2013/602.
doi: 10.1007/978-3-319-12160-4_18. |
| [4] |
W. Beullens, W. Castryck and F. Vercauteren, IND-CPA attack on Giophantus, (2018), Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Giophantus-official-comment.pdf. |
| [5] |
J. T. Ding, S. Alsayigh, R. V. Saraswathy, S. Fluhrer and X. D. Lin, Leakage of Signal function with reused keys in RLWE key exchange, 2017 IEEE International Conference on Communications (ICC), (2017), Available from: https://eprint.iacr.org/2016/1176.
doi: 10.1109/ICC.2017.7996806. |
| [6] |
S. Fluhrer, Cryptanalysis of ring-LWE based key exchange with key share reuse, Cryptology ePrint Archive: Report 2016/085, (2016), Available from: https://eprint.iacr.org/2016/085. |
| [7] |
P. Nguyen, Giophantus and *LWR-based submissions, (2018), Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Giophantus-official-comment.pdf. |
| [8] |
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the Annual ACM Symposium on Theory of Computing, (2005), 84–93.
doi: 10.1145/1060590.1060603. |
| [1] |
Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012 |
| [2] |
Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (4) : 573-577. doi: 10.3934/amc.2020030 |
| [3] |
Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013 |
| [4] |
Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022026 |
| [5] |
Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046 |
| [6] |
Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1 |
| [7] |
Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247 |
| [8] |
Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377 |
| [9] |
Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 |
| [10] |
Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040 |
| [11] |
Janne M.J. Huttunen, J. P. Kaipio. Approximation errors in nonstationary inverse problems. Inverse Problems and Imaging, 2007, 1 (1) : 77-93. doi: 10.3934/ipi.2007.1.77 |
| [12] |
Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 |
| [13] |
Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249 |
| [14] |
Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281 |
| [15] |
Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 |
| [16] |
Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089 |
| [17] |
Christophe Prieur. Control of systems of conservation laws with boundary errors. Networks and Heterogeneous Media, 2009, 4 (2) : 393-407. doi: 10.3934/nhm.2009.4.393 |
| [18] |
Negin Karimi, Ahmad Yousefian Darani, Marcus Greferath. Correcting adversarial errors with generalized regenerating codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022005 |
| [19] |
Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87 |
| [20] |
Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]