American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020030

Giophantus distinguishing attack is a low dimensional learning with errors problem

Jintai Ding , Joshua Deaton and  Kurt Schmidt ,

University of Cincinnati, Cincinnati, OH 45219, USA

* Corresponding author: Kurt Schmidt

Received  February 2019 Revised  March 2019 Published  September 2019

Fund Project: J. Ding and K. Schmidt are partially supported by US Air Force.

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.

Keywords: Lattice, post quantum cryptography, learning with errors, Giophantus, cryptanalysis, NIST..
Mathematics Subject Classification: Primary: 94A60, 68P25; Secondary: 81P94.
Citation: Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, doi: 10.3934/amc.2020030
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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  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]

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
[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]

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]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020089
[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]

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
[17]

Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492
[18]

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
[19]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117
[20]

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

2019 Impact Factor: 0.734

Tools

Article outline

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences