Giophantus distinguishing attack is a low dimensional learning with errors problem

Jintai Ding; Joshua Deaton; Kurt Schmidt

doi:10.3934/amc.2020030

Article Contents

2020, Volume 14, Issue 4: 573-577. Doi: 10.3934/amc.2020030

This issue Previous Article Some results on

$ \mathbb{Z}_p\mathbb{Z}_p[v] $

-additive cyclic codes Next Article New classes of strictly optimal low hit zone frequency hopping sequence sets

Giophantus distinguishing attack is a low dimensional learning with errors problem

University of Cincinnati, Cincinnati, OH 45219, USA

^* Corresponding author: Kurt Schmidt
^* Corresponding author: Kurt Schmidt

Received: February 1, 2019

Revised: March 1, 2019

Early access: September 11, 2019

Published online: September 11, 2019

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

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60, 68P25; Secondary: 81P94.

Citation:

Full Text(HTML)

Related Papers

Cited by

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, 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.
[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.
[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, STOC'05: Proceedings of the Annual ACM Symposium on Theory of Computing, (2005), 84–93. doi: 10.1145/1060590.1060603.