A Class of Weak Keys for the QC-MDPC Cryptosystem

Nuh Aydin; Bahattin Yildiz; Suleyman Uludag

doi:10.1109/ACCT51235.2020.9383383

A Class of Weak Keys for the QC-MDPC Cryptosystem

Nuh Aydin, Bahattin Yildiz, Suleyman Uludag

Informatics, Computing, and Cyber Systems, School of

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

3 Scopus citations

Abstract

The quasi-cyclic moderate-density parity-check code (QC-MDPC) cryptosystem is one of the recent variants of the original McEliece code-based cryptosystem, that has also been part of the BIKE cryptosystem, which has been submitted to NIST as a post-Quantum cryptosystem candidate. We show that in certain cases the secret key can be recovered from the public key by means of a polynomial factorization. This leads to the concept of "weak keys"for the cryptosystem. Even though the probability of choosing a weak key at random is low, we are able to find weak keys quite easily. This suggests that avoiding weak keys may be introduced as a condition in the implementation of the cryptosystem.

Original language	English (US)
Title of host publication	Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	19-22
Number of pages	4
ISBN (Electronic)	9781665402873
DOIs	https://doi.org/10.1109/ACCT51235.2020.9383383
State	Published - Oct 11 2020
Event	17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020 - Vitual, Albena, Bulgaria Duration: Oct 11 2020 → Oct 17 2020

Publication series

Name	Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020

Conference

Conference	17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020
Country/Territory	Bulgaria
City	Vitual, Albena
Period	10/11/20 → 10/17/20

Keywords

McEliece cryptosystem
QC-MDPC
code-based cryptography
polynomial factorization
security

ASJC Scopus subject areas

Computational Theory and Mathematics
Software
Algebra and Number Theory
Discrete Mathematics and Combinatorics

Access to Document

10.1109/ACCT51235.2020.9383383

Cite this

Aydin, N., Yildiz, B., & Uludag, S. (2020). A Class of Weak Keys for the QC-MDPC Cryptosystem. In Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020 (pp. 19-22). Article 9383383 (Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACCT51235.2020.9383383

A Class of Weak Keys for the QC-MDPC Cryptosystem. / Aydin, Nuh; Yildiz, Bahattin; Uludag, Suleyman.
Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020. Institute of Electrical and Electronics Engineers Inc., 2020. p. 19-22 9383383 (Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020).

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

Aydin, N, Yildiz, B & Uludag, S 2020, A Class of Weak Keys for the QC-MDPC Cryptosystem. in Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020., 9383383, Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020, Institute of Electrical and Electronics Engineers Inc., pp. 19-22, 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020, Vitual, Albena, Bulgaria, 10/11/20. https://doi.org/10.1109/ACCT51235.2020.9383383

Aydin N, Yildiz B, Uludag S. A Class of Weak Keys for the QC-MDPC Cryptosystem. In Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020. Institute of Electrical and Electronics Engineers Inc. 2020. p. 19-22. 9383383. (Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020). doi: 10.1109/ACCT51235.2020.9383383

Aydin, Nuh ; Yildiz, Bahattin ; Uludag, Suleyman. / A Class of Weak Keys for the QC-MDPC Cryptosystem. Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 19-22 (Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020).

@inproceedings{26946c17bc0842a8b8e008398744679a,

title = "A Class of Weak Keys for the QC-MDPC Cryptosystem",

abstract = "The quasi-cyclic moderate-density parity-check code (QC-MDPC) cryptosystem is one of the recent variants of the original McEliece code-based cryptosystem, that has also been part of the BIKE cryptosystem, which has been submitted to NIST as a post-Quantum cryptosystem candidate. We show that in certain cases the secret key can be recovered from the public key by means of a polynomial factorization. This leads to the concept of {"}weak keys{"}for the cryptosystem. Even though the probability of choosing a weak key at random is low, we are able to find weak keys quite easily. This suggests that avoiding weak keys may be introduced as a condition in the implementation of the cryptosystem.",

keywords = "McEliece cryptosystem, QC-MDPC, code-based cryptography, polynomial factorization, security",

author = "Nuh Aydin and Bahattin Yildiz and Suleyman Uludag",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020 ; Conference date: 11-10-2020 Through 17-10-2020",

year = "2020",

month = oct,

day = "11",

doi = "10.1109/ACCT51235.2020.9383383",

language = "English (US)",

series = "Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "19--22",

booktitle = "Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020",

}

TY - GEN

T1 - A Class of Weak Keys for the QC-MDPC Cryptosystem

AU - Aydin, Nuh

AU - Yildiz, Bahattin

AU - Uludag, Suleyman

PY - 2020/10/11

Y1 - 2020/10/11

N2 - The quasi-cyclic moderate-density parity-check code (QC-MDPC) cryptosystem is one of the recent variants of the original McEliece code-based cryptosystem, that has also been part of the BIKE cryptosystem, which has been submitted to NIST as a post-Quantum cryptosystem candidate. We show that in certain cases the secret key can be recovered from the public key by means of a polynomial factorization. This leads to the concept of "weak keys"for the cryptosystem. Even though the probability of choosing a weak key at random is low, we are able to find weak keys quite easily. This suggests that avoiding weak keys may be introduced as a condition in the implementation of the cryptosystem.

AB - The quasi-cyclic moderate-density parity-check code (QC-MDPC) cryptosystem is one of the recent variants of the original McEliece code-based cryptosystem, that has also been part of the BIKE cryptosystem, which has been submitted to NIST as a post-Quantum cryptosystem candidate. We show that in certain cases the secret key can be recovered from the public key by means of a polynomial factorization. This leads to the concept of "weak keys"for the cryptosystem. Even though the probability of choosing a weak key at random is low, we are able to find weak keys quite easily. This suggests that avoiding weak keys may be introduced as a condition in the implementation of the cryptosystem.

KW - McEliece cryptosystem

KW - QC-MDPC

KW - code-based cryptography

KW - polynomial factorization

KW - security

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

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

U2 - 10.1109/ACCT51235.2020.9383383

DO - 10.1109/ACCT51235.2020.9383383

M3 - Conference contribution

AN - SCOPUS:85103964715

T3 - Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020

SP - 19

EP - 22

BT - Proceedings of the 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 17th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2020

Y2 - 11 October 2020 through 17 October 2020

ER -

A Class of Weak Keys for the QC-MDPC Cryptosystem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this