Giophantus distinguishing attack is a low dimensional learning with errors problem

Jintai Ding; Joshua Deaton; Kurt Schmidt

doi:10.3934/amc.2020014

Giophantus distinguishing attack is a low dimensional learning with errors problem

Jintai Ding^*, Joshua Deaton, Kurt Schmidt

^*Corresponding author for this work

University of Cincinnati

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	171-175
Number of pages	5
Journal	Advances in Mathematics of Communications
Volume	14
Issue number	1
DOIs	https://doi.org/10.3934/amc.2020014
Publication status	Published - Feb 2020
Externally published	Yes

Keywords

Cryptanalysis
Giophantus
Lattice
Learning with errors
NIST.
Post quantum cryptography

Access to Document

10.3934/amc.2020014

Cite this

@article{2fe5bdb4389848aab2a3e1dba22f6c5a,

title = "Giophantus distinguishing attack is a low dimensional learning with errors problem",

abstract = "In this paper, we attack the recent NIST submission Giophantus, a public key encryption scheme. We find that the complicated structure of Giophantus{\textquoteright}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 = "Cryptanalysis, Giophantus, Lattice, Learning with errors, NIST., Post quantum cryptography",

author = "Jintai Ding and Joshua Deaton and Kurt Schmidt",

note = "Publisher Copyright: {\textcopyright} 2020 AIMS.",

year = "2020",

month = feb,

doi = "10.3934/amc.2020014",

language = "English",

volume = "14",

pages = "171--175",

journal = "Advances in Mathematics of Communications",

issn = "1930-5346",

number = "1",

}

TY - JOUR

T1 - Giophantus distinguishing attack is a low dimensional learning with errors problem

AU - Ding, Jintai

AU - Deaton, Joshua

AU - Schmidt, Kurt

PY - 2020/2

Y1 - 2020/2

N2 - 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.

AB - 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.

KW - Cryptanalysis

KW - Giophantus

KW - Lattice

KW - Learning with errors

KW - NIST.

KW - Post quantum cryptography

UR - http://www.scopus.com/inward/record.url?scp=85073504551&partnerID=8YFLogxK

U2 - 10.3934/amc.2020014

DO - 10.3934/amc.2020014

M3 - Article

AN - SCOPUS:85073504551

SN - 1930-5346

VL - 14

SP - 171

EP - 175

JO - Advances in Mathematics of Communications

JF - Advances in Mathematics of Communications

IS - 1

ER -

Giophantus distinguishing attack is a low dimensional learning with errors problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this