Cryptanalysis of GiophantusTM Schemes against Hybrid Attack

Yuntao Wang; Yasuhiko Ikematsu; Koichiro Akiyama; Tsuyoshi Takagi

doi:10.1145/3384940.3388958

Cryptanalysis of GiophantusTM Schemes against Hybrid Attack

Yuntao Wang, Yasuhiko Ikematsu, Koichiro Akiyama, Tsuyoshi Takagi

Laboratory of Mathematical Design for Advanced Cryptography

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The hybrid attack was proposed by Howgrave-Graham in CRYPTO2007, which was originally designed for the cryptanalysis of NTRU cryptosystems. In this paper, based on Howgrave-Graham's attack model, we propose a simulator of hybrid attack to evaluate the hardness of the unique shortest vector problem. By a dynamical computation, our algorithm can trade off the cost between reduction and MitM, while both of them run in exponential time. Further, we adapt our simulator to Giophantus™, Giophantus+ and Giophantus-cryptosystems, proposed by Akiyama et al. in SAC2017, SCIS2019 and SCIS2020, respectively. Our analysis shows that by the hybrid attack, the security levels can be reduced by at most 19 bits for Giophantus' parameters proposed in NIST Post Quantum Cryptography (PQC) standardization 1st round submission. Meanwhile, the parameter sets of Giophantus+ and Giophantus-are secure against the hybrid attack.

Original language	English
Title of host publication	APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020
Publisher	Association for Computing Machinery, Inc
Pages	28-35
Number of pages	8
ISBN (Electronic)	9781450376075
DOIs	https://doi.org/10.1145/3384940.3388958
Publication status	Published - Oct 5 2020
Event	7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020 - Taipei, Taiwan, Province of China Duration: Oct 6 2020 → …

Publication series

Name	APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020

Conference

Conference	7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020
Country/Territory	Taiwan, Province of China
City	Taipei
Period	10/6/20 → …

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Computer Science Applications
Information Systems
Software

Access to Document

10.1145/3384940.3388958

Cite this

Wang, Y., Ikematsu, Y., Akiyama, K., & Takagi, T. (2020). Cryptanalysis of GiophantusTM Schemes against Hybrid Attack. In APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020 (pp. 28-35). (APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020). Association for Computing Machinery, Inc. https://doi.org/10.1145/3384940.3388958

Cryptanalysis of GiophantusTM Schemes against Hybrid Attack. / Wang, Yuntao; Ikematsu, Yasuhiko; Akiyama, Koichiro et al.
APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020. Association for Computing Machinery, Inc, 2020. p. 28-35 (APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Wang, Y, Ikematsu, Y, Akiyama, K & Takagi, T 2020, Cryptanalysis of GiophantusTM Schemes against Hybrid Attack. in APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020. APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020, Association for Computing Machinery, Inc, pp. 28-35, 7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020, Taipei, Taiwan, Province of China, 10/6/20. https://doi.org/10.1145/3384940.3388958

Wang Y, Ikematsu Y, Akiyama K, Takagi T. Cryptanalysis of GiophantusTM Schemes against Hybrid Attack. In APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020. Association for Computing Machinery, Inc. 2020. p. 28-35. (APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020). doi: 10.1145/3384940.3388958

Wang, Yuntao ; Ikematsu, Yasuhiko ; Akiyama, Koichiro et al. / Cryptanalysis of GiophantusTM Schemes against Hybrid Attack. APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020. Association for Computing Machinery, Inc, 2020. pp. 28-35 (APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020).

@inproceedings{b84293e633f24999a5e7aa8713a0f00b,

title = "Cryptanalysis of GiophantusTM Schemes against Hybrid Attack",

abstract = "The hybrid attack was proposed by Howgrave-Graham in CRYPTO2007, which was originally designed for the cryptanalysis of NTRU cryptosystems. In this paper, based on Howgrave-Graham's attack model, we propose a simulator of hybrid attack to evaluate the hardness of the unique shortest vector problem. By a dynamical computation, our algorithm can trade off the cost between reduction and MitM, while both of them run in exponential time. Further, we adapt our simulator to Giophantus{\texttrademark}, Giophantus+ and Giophantus-cryptosystems, proposed by Akiyama et al. in SAC2017, SCIS2019 and SCIS2020, respectively. Our analysis shows that by the hybrid attack, the security levels can be reduced by at most 19 bits for Giophantus' parameters proposed in NIST Post Quantum Cryptography (PQC) standardization 1st round submission. Meanwhile, the parameter sets of Giophantus+ and Giophantus-are secure against the hybrid attack.",

author = "Yuntao Wang and Yasuhiko Ikematsu and Koichiro Akiyama and Tsuyoshi Takagi",

note = "Funding Information: This work was supported by JSPS KAKENHI Grant Number 19F19378, 19K20266, JST CREST Grant Number JPMJCR14D6, Japan. Publisher Copyright: {\textcopyright} 2020 ACM.; 7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020 ; Conference date: 06-10-2020",

year = "2020",

month = oct,

day = "5",

doi = "10.1145/3384940.3388958",

language = "English",

series = "APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020",

publisher = "Association for Computing Machinery, Inc",

pages = "28--35",

booktitle = "APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020",

}

TY - GEN

T1 - Cryptanalysis of GiophantusTM Schemes against Hybrid Attack

AU - Wang, Yuntao

AU - Ikematsu, Yasuhiko

AU - Akiyama, Koichiro

AU - Takagi, Tsuyoshi

PY - 2020/10/5

Y1 - 2020/10/5

N2 - The hybrid attack was proposed by Howgrave-Graham in CRYPTO2007, which was originally designed for the cryptanalysis of NTRU cryptosystems. In this paper, based on Howgrave-Graham's attack model, we propose a simulator of hybrid attack to evaluate the hardness of the unique shortest vector problem. By a dynamical computation, our algorithm can trade off the cost between reduction and MitM, while both of them run in exponential time. Further, we adapt our simulator to Giophantus™, Giophantus+ and Giophantus-cryptosystems, proposed by Akiyama et al. in SAC2017, SCIS2019 and SCIS2020, respectively. Our analysis shows that by the hybrid attack, the security levels can be reduced by at most 19 bits for Giophantus' parameters proposed in NIST Post Quantum Cryptography (PQC) standardization 1st round submission. Meanwhile, the parameter sets of Giophantus+ and Giophantus-are secure against the hybrid attack.

AB - The hybrid attack was proposed by Howgrave-Graham in CRYPTO2007, which was originally designed for the cryptanalysis of NTRU cryptosystems. In this paper, based on Howgrave-Graham's attack model, we propose a simulator of hybrid attack to evaluate the hardness of the unique shortest vector problem. By a dynamical computation, our algorithm can trade off the cost between reduction and MitM, while both of them run in exponential time. Further, we adapt our simulator to Giophantus™, Giophantus+ and Giophantus-cryptosystems, proposed by Akiyama et al. in SAC2017, SCIS2019 and SCIS2020, respectively. Our analysis shows that by the hybrid attack, the security levels can be reduced by at most 19 bits for Giophantus' parameters proposed in NIST Post Quantum Cryptography (PQC) standardization 1st round submission. Meanwhile, the parameter sets of Giophantus+ and Giophantus-are secure against the hybrid attack.

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

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

U2 - 10.1145/3384940.3388958

DO - 10.1145/3384940.3388958

M3 - Conference contribution

AN - SCOPUS:85095602443

T3 - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020

SP - 28

EP - 35

BT - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020

PB - Association for Computing Machinery, Inc

T2 - 7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020

Y2 - 6 October 2020

ER -

Cryptanalysis of GiophantusTM Schemes against Hybrid Attack

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this