Dual-Ouroboros: An improvement of the McNie scheme

Philippe Gaborit; Lucky Galvez; Adrien Hauteville; Jon-Lark Kim; Myeong Jae Kim; Young-Sik Kim

doi:10.3934/amc.2020021

Article Contents

2020, Volume 14, Issue 2: 301-306. Doi: 10.3934/amc.2020021 open access

This issue Previous Article Multi-point codes from the GGS curves Next Article Algebraic dependence in generating functions and expansion complexity

Dual-Ouroboros: An improvement of the McNie scheme

1.
University of Limoges, Limoges, France
2.
Sogang University, Seoul, South Korea
3.
Chosun University, Gwangju, South Korea

^* Corresponding author: Jon-Lark Kim
^* Corresponding author: Jon-Lark Kim

Received: May 31, 2018

Revised: October 31, 2018

Early access: September 2019

Published: May 2020

The work of Jon-Lark Kim was supported by Samsung Science and Technology Foundation under Project Number SSTF-BA1602-01

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

McNie [8] is a code-based public key encryption scheme submitted to the NIST Post-Quantum Cryptography standardization [10] as a candidate. In this paper, we present Dual-Ouroboros, an improvement of McNie, which can be seen as a dual version of the Ouroboros-R protocol [1], another candidate to the NIST competition. This new improved protocol permits, first, to avoid an attack proposed by Gaborit [7] and second permits to benefit from a reduction security to a standard problem (as the original Ouroboros protocol).

Keywords:

Mathematics Subject Classification: Primary: 11T71, 14G50.

Citation:

FullText(HTML)

Table 1. Suggested parameters and key sizes in bytes for Dual-Ouroboros

$ n $	$ k $	$ l $	$ q $	$ m $	$ d $	$ r $	Failure	PK	SK	CT	Security
94	47	47	2	67	5	7	-28	788	1181	1181	128
142	71	71	2	91	5	6	-54	1616	2423	2423	128
194	97	97	2	91	5	7	-78	2207	3311	3311	128
106	53	53	2	101	5	8	-30	1339	2008	2008	192
158	79	79	2	101	5	8	-58	1995	2993	2993	192
194	97	97	2	101	5	8	-76	2450	3674	3674	192
134	67	67	2	107	6	9	-30	1793	2689	2689	256
158	79	79	2	131	6	8	-56	2588	3881	3881	256
202	101	101	2	131	6	8	-78	3308	4962	4962	256

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. C. Deneuville, P. Gaborit, A. Hauteville and G. Zémor, Ouroboros-R, http://pqc-ouroborosr.org/.
[2]	N. Aragon, P. Gaborit, A. Hauteville and J. P. Tillich, Improvement of the generic attacks for the rank syndrome decoding problem, 2017, < hal-01608464>.
[3]	L. Both and A. May, Decoding linear codes with high error rate and its impact for LPN security, in Post-Quantum Cryptography, PQCrypto 2018, (eds. T. Lange and R. Steinwandt), Lecture Notes in Computer Science, Springer, Cham., 10786 (2018), 25–46.
[4]	J.-C. Deneuville, P. Gaborit and G. Zémor, Ouroboros: A simple, secure and efficient key exchange protocol based on coding theory, International Workshop on Post-Quantum Cryptography, Springer, Cham, 10346 (2017), 18–34.
[5]	P. Gaborit, G. Murat, O. Ruatta and G. Zémor, Low rank parity check codes and their application to cryptography, In Proceedings of the Workshop on Coding and Cryptography WCC'2013, Bergen, Norway, 2013.
[6]	P. Gaborit, A. Hauteville, D. H. Phan and J.-P. Tillich, Identity-based encryption from rank metric, Advances in Cryptology—CRYPTO 2017. Part Ⅲ, Lecture Notes in Computer Science, Springer, 10403 (2017), 194–224.
[7]	Gaborit, Oficial comments on McNie, 2017, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions.
[8]	L. Galvez, J.-L. Kim, M. J. Kim, Y.-S. Kim and N. Lee, McNie, 2017, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions.
[9]	R. J. McEliece, A public key cryptosystem based on algebraic coding theory, DSN Progress Report, 42/44 (1978), 114-116.
[10]	Post-Quantum-Cryptography-Standardization, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization.