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]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[2]

José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020376
[3]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (178)
  • HTML views (562)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences