American Institute of Mathematical Sciences

Advanced
May  2020, 14(2): 301-306. 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, 2020, 14 (2) : 301-306. 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  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]

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
[11]

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

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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

Julien Arino, Chris Bauch, Fred Brauer, S. Michelle Driedger, Amy L. Greer, S.M. Moghadas, Nick J. Pizzi, Beate Sander, Ashleigh Tuite, P. van den Driessche, James Watmough, Jianhong Wu, Ping Yan. Pandemic influenza: Modelling and public health perspectives. Mathematical Biosciences & Engineering, 2011, 8 (1) : 1-20. doi: 10.3934/mbe.2011.8.1
[20]

Lianju Sun, Ziyou Gao, Yiju Wang. A Stackelberg game management model of the urban public transport. Journal of Industrial & Management Optimization, 2012, 8 (2) : 507-520. doi: 10.3934/jimo.2012.8.507

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (118)
  • HTML views (484)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences