# American Institute of Mathematical Sciences

May  2020, 14(2): 301-306. 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  May 2020 Early access  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, 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/. [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.

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/. [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.
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] Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021053 [5] Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031 [6] Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046 [7] Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026 [8] 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 [9] 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 [10] 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 [11] 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 [12] Carla Mascia, Massimiliano Sala, Irene Villa. A survey on functional encryption. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021049 [13] Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377 [14] 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 [15] 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 [16] Debrup Chakraborty, Sebati Ghosh, Cuauhtemoc Mancillas López, Palash Sarkar. ${\sf {FAST}}$: Disk encryption and beyond. Advances in Mathematics of Communications, 2022, 16 (1) : 185-230. doi: 10.3934/amc.2020108 [17] Christoph Hauert, Nina Haiden, Karl Sigmund. The dynamics of public goods. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 575-587. doi: 10.3934/dcdsb.2004.4.575 [18] 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 [19] 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 [20] Ernan Haruvy, Ashutosh Prasad, Suresh Sethi, Rong Zhang. Competition with open source as a public good. Journal of Industrial and Management Optimization, 2008, 4 (1) : 199-211. doi: 10.3934/jimo.2008.4.199

2021 Impact Factor: 1.015

## Tools

Article outline

Figures and Tables