American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020021

Dual-Ouroboros: An improvement of the McNie scheme

Philippe Gaborit 1, , Lucky Galvez 2, , Adrien Hauteville 1, , Jon-Lark Kim 2,, , Myeong Jae Kim 2, and  Young-Sik Kim 3,

1. 

University of Limoges, Limoges, France
2. 

Sogang University, Seoul, South Korea
3. 

Chosun University, Gwangju, South Korea

* Corresponding author: Jon-Lark Kim

Received  June 2018 Revised  November 2018 Published  September 2019

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

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: McNie, post-quantum cryptography, public key encryption.
Mathematics Subject Classification: Primary: 11T71, 14G50.
Citation: Philippe Gaborit, Lucky Galvez, Adrien Hauteville, Jon-Lark Kim, Myeong Jae Kim, Young-Sik Kim. Dual-Ouroboros: An improvement of the McNie scheme. Advances in Mathematics of Communications, doi: 10.3934/amc.2020021
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/. Google Scholar

[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>. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

Gaborit, Oficial comments on McNie, 2017, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions. Google Scholar

[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. Google Scholar

[9]

R. J. McEliece, A public key cryptosystem based on algebraic coding theory, DSN Progress Report, 42/44 (1978), 114-116.   Google Scholar

[10]

Post-Quantum-Cryptography-Standardization, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization. Google Scholar

show all references

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/. Google Scholar

[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>. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

Gaborit, Oficial comments on McNie, 2017, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions. Google Scholar

[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. Google Scholar

[9]

R. J. McEliece, A public key cryptosystem based on algebraic coding theory, DSN Progress Report, 42/44 (1978), 114-116.   Google Scholar

[10]

Post-Quantum-Cryptography-Standardization, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization. Google Scholar

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
Table Options

Download as excel

$ 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
[1]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012
[2]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[3]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[4]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046
[5]

Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[6]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[7]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
[8]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[9]

Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377
[10]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[11]

Angsuman Das, Avishek Adhikari, Kouichi Sakurai. Plaintext checkable encryption with designated checker. Advances in Mathematics of Communications, 2015, 9 (1) : 37-53. doi: 10.3934/amc.2015.9.37
[12]

Christoph Hauert, Nina Haiden, Karl Sigmund. The dynamics of public goods. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 575-587. doi: 10.3934/dcdsb.2004.4.575
[13]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[14]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249
[15]

Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273
[16]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[17]

Ernan Haruvy, Ashutosh Prasad, Suresh Sethi, Rong Zhang. Competition with open source as a public good. Journal of Industrial & Management Optimization, 2008, 4 (1) : 199-211. doi: 10.3934/jimo.2008.4.199
[18]

Lejun Shi, Shaocui Guo, Xu Yang. Encryption service protocol based on matrix norm algorithm. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020255
[19]

Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492
[20]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (67)
  • HTML views (336)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences