February  2020, 14(1): 171-175. doi: 10.3934/amc.2020014

Giophantus distinguishing attack is a low dimensional learning with errors problem

University of Cincinnati, Cincinnati, OH 45219, USA

*Corresponding author: Jintai Ding

Received  February 2019 Revised  May 2019 Published  August 2019

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.

Citation: 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
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]

Jayashree Dey, Ratna Dutta. Post-quantum secure fully-dynamic logarithmic-size deniable group signature in code-based setting. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022077

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Alessandro Barenghi, Jean-François Biasse, Edoardo Persichetti, Paolo Santini. On the computational hardness of the code equivalence problem in cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022064

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (343)
  • HTML views (377)
  • Cited by (0)

Other articles
by authors

[Back to Top]