A key exchange based on the short integer solution problem and the learning with errors problem

Jintai Ding; Kevin Schmitt; Zheng Zhang

doi:10.1007/978-3-030-16458-4_8

A key exchange based on the short integer solution problem and the learning with errors problem

Jintai Ding, Kevin Schmitt, Zheng Zhang^*

^*Corresponding author for this work

University of Cincinnati

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

7 Citations (Scopus)

Abstract

Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.

Original language	English
Title of host publication	Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding
Editors	Claude Carlet, El Mamoun Souidi, Sylvain Guilley, Abderrahmane Nitaj
Publisher	Springer Verlag
Pages	105-117
Number of pages	13
ISBN (Print)	9783030164577
DOIs	https://doi.org/10.1007/978-3-030-16458-4_8
Publication status	Published - 2019
Externally published	Yes
Event	3rd International Conference on Codes, Cryptology and Information Security, C2SI 2019 - Rabat, Morocco Duration: 22 Apr 2019 → 24 Apr 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11445 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Codes, Cryptology and Information Security, C2SI 2019
Country/Territory	Morocco
City	Rabat
Period	22/04/19 → 24/04/19

Keywords

Attack
Key exchange
Lattice
LWE
SIS

Access to Document

10.1007/978-3-030-16458-4_8

Cite this

Ding, J., Schmitt, K., & Zhang, Z. (2019). A key exchange based on the short integer solution problem and the learning with errors problem. In C. Carlet, E. M. Souidi, S. Guilley, & A. Nitaj (Eds.), Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding (pp. 105-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11445 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-16458-4_8

Ding, Jintai ; Schmitt, Kevin ; Zhang, Zheng. / A key exchange based on the short integer solution problem and the learning with errors problem. Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding. editor / Claude Carlet ; El Mamoun Souidi ; Sylvain Guilley ; Abderrahmane Nitaj. Springer Verlag, 2019. pp. 105-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c7dd53fc32964aed9e26de1d25fb93fd,

title = "A key exchange based on the short integer solution problem and the learning with errors problem",

abstract = "Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang{\textquoteright}s key exchange and then we will construct a key exchange based on SIS and LWE problems.",

keywords = "Attack, Key exchange, Lattice, LWE, SIS",

author = "Jintai Ding and Kevin Schmitt and Zheng Zhang",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 3rd International Conference on Codes, Cryptology and Information Security, C2SI 2019 ; Conference date: 22-04-2019 Through 24-04-2019",

year = "2019",

doi = "10.1007/978-3-030-16458-4_8",

language = "English",

isbn = "9783030164577",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "105--117",

editor = "Claude Carlet and Souidi, {El Mamoun} and Sylvain Guilley and Abderrahmane Nitaj",

booktitle = "Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding",

}

Ding, J, Schmitt, K & Zhang, Z 2019, A key exchange based on the short integer solution problem and the learning with errors problem. in C Carlet, EM Souidi, S Guilley & A Nitaj (eds), Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11445 LNCS, Springer Verlag, pp. 105-117, 3rd International Conference on Codes, Cryptology and Information Security, C2SI 2019, Rabat, Morocco, 22/04/19. https://doi.org/10.1007/978-3-030-16458-4_8

A key exchange based on the short integer solution problem and the learning with errors problem. / Ding, Jintai; Schmitt, Kevin; Zhang, Zheng.
Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding. ed. / Claude Carlet; El Mamoun Souidi; Sylvain Guilley; Abderrahmane Nitaj. Springer Verlag, 2019. p. 105-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11445 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - A key exchange based on the short integer solution problem and the learning with errors problem

AU - Ding, Jintai

AU - Schmitt, Kevin

AU - Zhang, Zheng

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

N2 - Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.

AB - Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.

KW - Attack

KW - Key exchange

KW - Lattice

KW - LWE

KW - SIS

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

U2 - 10.1007/978-3-030-16458-4_8

DO - 10.1007/978-3-030-16458-4_8

M3 - Conference Proceeding

AN - SCOPUS:85065499669

SN - 9783030164577

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 105

EP - 117

BT - Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding

A2 - Carlet, Claude

A2 - Souidi, El Mamoun

A2 - Guilley, Sylvain

A2 - Nitaj, Abderrahmane

PB - Springer Verlag

T2 - 3rd International Conference on Codes, Cryptology and Information Security, C2SI 2019

Y2 - 22 April 2019 through 24 April 2019

ER -

Ding J, Schmitt K, Zhang Z. A key exchange based on the short integer solution problem and the learning with errors problem. In Carlet C, Souidi EM, Guilley S, Nitaj A, editors, Codes, Cryptology and Information Security - 3rd International Conference, C2SI 2019, Proceeding. Springer Verlag. 2019. p. 105-117. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-16458-4_8

A key exchange based on the short integer solution problem and the learning with errors problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this