-
Previous Article
Locally recoverable codes from algebraic curves with separated variables
- AMC Home
- This Issue
-
Next Article
Dual-Ouroboros: An improvement of the McNie scheme
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. Google Scholar |
[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. Google Scholar |
[3] |
M. R. Albrecht, R. Fitzpatrick and F. Göpfert, On the efficacy of solving LWE by reduction to unique-SVP, Information Security and Cryptology – ICISC, (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. Google Scholar |
[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, 2016, Available from: https://eprint.iacr.org/2016/085. Google Scholar |
[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. Google Scholar |
[8] |
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC'05: 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. Google Scholar |
[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. Google Scholar |
[3] |
M. R. Albrecht, R. Fitzpatrick and F. Göpfert, On the efficacy of solving LWE by reduction to unique-SVP, Information Security and Cryptology – ICISC, (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. Google Scholar |
[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, 2016, Available from: https://eprint.iacr.org/2016/085. Google Scholar |
[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. Google Scholar |
[8] |
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC'05: 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 (1) : 171-175. doi: 10.3934/amc.2020014 |
[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] |
Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046 |
[5] |
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 |
[6] |
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 |
[7] |
Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377 |
[8] |
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 |
[9] |
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 |
[10] |
Janne M.J. Huttunen, J. P. Kaipio. Approximation errors in nonstationary inverse problems. Inverse Problems & Imaging, 2007, 1 (1) : 77-93. doi: 10.3934/ipi.2007.1.77 |
[11] |
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 |
[12] |
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 |
[13] |
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 |
[14] |
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 |
[15] |
Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492 |
[16] |
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 |
[17] |
Christophe Prieur. Control of systems of conservation laws with boundary errors. Networks & Heterogeneous Media, 2009, 4 (2) : 393-407. doi: 10.3934/nhm.2009.4.393 |
[18] |
Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117 |
[19] |
Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901 |
[20] |
Nicolás M. Crisosto, Christopher M. Kribs-Zaleta, Carlos Castillo-Chávez, Stephen Wirkus. Community resilience in collaborative learning. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 17-40. doi: 10.3934/dcdsb.2010.14.17 |
2018 Impact Factor: 0.879
Tools
Article outline
[Back to Top]