Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Applicable Algebra in Engineering, Communication and Computing 6/2021

27-02-2020 | Original Paper

On the security of the modified Dual-ouroboros PKE using Gabidulin codes

Authors: Terry Shue Chien Lau, Chik How Tan, Theo Fanuela Prabowo

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 6/2021

Login to get access
share
SHARE

Abstract

Recently, Kim et al. proposed a modified Dual-Ouroboros public-key encryption (\({\textsf{PKE}}\)) using Gabidulin codes to overcome the limitation of having decryption failure in the original Dual-Ouroboros using low rank parity check codes. This modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes is proved to be INDCPA secure, with very compact public key size of 738 bytes achieving 128-bit security level. However, they did not specify on their choice of the secret key S used in their \({\textsf{PKE}}\). In this paper, we analyze different possible choices for S in the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes. More specifically, we show that if S is invertible over \({\mathbb{F}}_{q^m}\) without any restriction, then the decryption algorithm will fail. Furthermore, we show that Kim et al.’s proposal of the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes has secret key S over \({\mathbb{F}}_q\) for its decryption algorithm to be correct. Then, we proposed two attacks: key recovery attack and plaintext recovery attack on their \({\textsf{PKE}}\) with S over \({\mathbb{F}}_q\). We are able to recover the secret key for all the proposed parameters within 235 seconds. Moreover, we show that the public key matrix in their proposal generates a subcode of Gabidulin code. As a consequence, we can apply the Frobenius weak attack on their proposal and recover the plaintext for all the proposed paramters within 0.614 second. Finally, we give a proposal for the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes such that it is correct and secure, by considering certain restrictions on S over \({\mathbb{F}}_{q^m}\).

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Literature
1.
go back to reference Aguilar-Melchor, C., Aragon, A., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Zémor, G.: Ouroboros-R. http://​pqc-ouroborosr.​org (2017). Accessed 8 Dec 2019 Aguilar-Melchor, C., Aragon, A., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Zémor, G.: Ouroboros-R. http://​pqc-ouroborosr.​org (2017). Accessed 8 Dec 2019
2.
go back to reference Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2018), pp. 2421–2425 (2018) Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2018), pp. 2421–2425 (2018)
3.
go back to reference Berlekamp, E., McEliece, R., Tilborg, H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978) MathSciNetCrossRef Berlekamp, E., McEliece, R., Tilborg, H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978) MathSciNetCrossRef
4.
go back to reference Bardet, M., Briaud, P., Brox, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.-P.: An Algebraic Attack on Rank Metric Code-based Cryptosystems. CoRR abs/1910.00810 (2019) Bardet, M., Briaud, P., Brox, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.-P.: An Algebraic Attack on Rank Metric Code-based Cryptosystems. CoRR abs/1910.00810 (2019)
5.
go back to reference Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Peredachi Inf. 21(1), 3–16 (1985) MathSciNetMATH Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Peredachi Inf. 21(1), 3–16 (1985) MathSciNetMATH
8.
go back to reference Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016) MathSciNetCrossRef Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016) MathSciNetCrossRef
9.
go back to reference Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: New results for rank-based cryptography. In: Proceedings of Progress in Cryptology (AFRICACRYPT 2014), pp. 1–12 (2014) Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: New results for rank-based cryptography. In: Proceedings of Progress in Cryptology (AFRICACRYPT 2014), pp. 1–12 (2014)
11.
go back to reference Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016) MathSciNetCrossRef Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016) MathSciNetCrossRef
12.
go back to reference Horlemann-Trautmann, A., Marshall, K., Rosenthal, J.: Considerations for rank-based cryptosystems. In: Proceedings of IEEE International Symposium on Information (ISIT 2016), pp. 2544–2548 (2016) Horlemann-Trautmann, A., Marshall, K., Rosenthal, J.: Considerations for rank-based cryptosystems. In: Proceedings of IEEE International Symposium on Information (ISIT 2016), pp. 2544–2548 (2016)
13.
go back to reference Horlemann-Trautmann, A., Marshall, K., Rosenthal, J.: Extension of overbeck’s attack for Gabidulin based cryptosystems. Des. Codes Cryptogr. 86(2), 319–340 (2018) MathSciNetCrossRef Horlemann-Trautmann, A., Marshall, K., Rosenthal, J.: Extension of overbeck’s attack for Gabidulin based cryptosystems. Des. Codes Cryptogr. 86(2), 319–340 (2018) MathSciNetCrossRef
15.
go back to reference Marshall, K.: A study of cryptographic systems based on Rank metric codes. Ph.D. Dissertation, University of Zurich (2016) Marshall, K.: A study of cryptographic systems based on Rank metric codes. Ph.D. Dissertation, University of Zurich (2016)
16.
go back to reference Loidreau, P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Proceedings of the International Workshop on Coding and Cryptography (WCC 2005), pp. 36–45 (2005) Loidreau, P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Proceedings of the International Workshop on Coding and Cryptography (WCC 2005), pp. 36–45 (2005)
17.
go back to reference Loidreau, P.: A new rank metric codes based encryption scheme. In: Proceedings of the 8th International Conference on Post-Quantum Cryptography (PQCrypto 2017), pp. 3–17 (2017) Loidreau, P.: A new rank metric codes based encryption scheme. In: Proceedings of the 8th International Conference on Post-Quantum Cryptography (PQCrypto 2017), pp. 3–17 (2017)
18.
go back to reference Lau, T.S.C., Tan, C.H.: Key recovery attack on McNie based on low rank parity check codes and its reparation. In: Proceedings of Advances in Information and Computer Security (IWSEC 2018), pp. 19–34 (2018) Lau, T.S.C., Tan, C.H.: Key recovery attack on McNie based on low rank parity check codes and its reparation. In: Proceedings of Advances in Information and Computer Security (IWSEC 2018), pp. 19–34 (2018)
19.
go back to reference Lau, T.S.C., Tan, C.H.: New rank codes based encryption scheme using partial circulant matrices. Des. Codes Cryptogr. 87(12), 2979–2999 (2019) MathSciNetCrossRef Lau, T.S.C., Tan, C.H.: New rank codes based encryption scheme using partial circulant matrices. Des. Codes Cryptogr. 87(12), 2979–2999 (2019) MathSciNetCrossRef
20.
go back to reference Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008) MathSciNetCrossRef Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008) MathSciNetCrossRef
Metadata
Title
On the security of the modified Dual-ouroboros PKE using Gabidulin codes
Authors
Terry Shue Chien Lau
Chik How Tan
Theo Fanuela Prabowo
Publication date
27-02-2020
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 6/2021
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00419-x

Other articles of this Issue 6/2021

Applicable Algebra in Engineering, Communication and Computing 6/2021 Go to the issue

Premium Partner