# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020021

## 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

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).

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
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
 $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] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [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] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492 [18] Fei Gao. Data encryption algorithm for e-commerce platform based on blockchain technology. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1457-1470. doi: 10.3934/dcdss.2019100 [19] Aiwan Fan, Qiming Wang, Joyati Debnath. A high precision data encryption algorithm in wireless network mobile communication. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1327-1340. doi: 10.3934/dcdss.2019091 [20] 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

2018 Impact Factor: 0.879

## Tools

Article outline

Figures and Tables