Skip to main content

2020 | OriginalPaper | Buchkapitel

Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric

verfasst von : Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, Victor Mateu

Erschienen in: Cryptology and Network Security

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et al. in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 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

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
A C++ implementation of the schemes described in this work can be found at https://​github.​com/​ahasikos/​rank_​commitments.
 
2
In the full distance decoding, the attacker receives an arbitrary point and aims at decoding the closest codeword. In the half distance decoding, the attacker knows that the error vector is within the error correction distance, i.e. \(\mathsf {w_H}(e) \le \left\lfloor (d-1)/2\right\rfloor \). In this case the decoding complexity is \(2^{0.0473n}\).
 
Literatur
1.
Zurück zum Zitat Aguilar, C., Blazy, O., Deneuville, J.C., Gaborit, P., Zémor, G.: Efficient encryption from random quasi-cyclic codes. arXiv preprint arXiv:1612.05572 (2016) Aguilar, C., Blazy, O., Deneuville, J.C., Gaborit, P., Zémor, G.: Efficient encryption from random quasi-cyclic codes. arXiv preprint arXiv:​1612.​05572 (2016)
2.
Zurück zum Zitat Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop (ITW), pp. 648–652. IEEE (2011) Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop (ITW), pp. 648–652. IEEE (2011)
6.
10.
Zurück zum Zitat Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384–386 (1978)CrossRefMATH Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384–386 (1978)CrossRefMATH
11.
Zurück zum Zitat Cayrel, P.L., Lindner, R., Rückert, M., Silva, R.: Improved zero-knowledge identification with lattices. Tatra Mountains Math. Publ. 53(1), 33–63 (2012)MathSciNetCrossRefMATH Cayrel, P.L., Lindner, R., Rückert, M., Silva, R.: Improved zero-knowledge identification with lattices. Tatra Mountains Math. Publ. 53(1), 33–63 (2012)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Cayrel, P.L., Véron, P., Alaoui, S.M.E.Y.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: International Workshop on Selected Areas in Cryptography, pp. 171–186 (2010) Cayrel, P.L., Véron, P., Alaoui, S.M.E.Y.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: International Workshop on Selected Areas in Cryptography, pp. 171–186 (2010)
14.
Zurück zum Zitat Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Conference on the Theory and Application of Cryptographic Techniques, pp. 186–194 (1986) Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Conference on the Theory and Application of Cryptographic Techniques, pp. 186–194 (1986)
15.
Zurück zum Zitat Gabidulin, E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985)MathSciNetMATH Gabidulin, E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985)MathSciNetMATH
16.
Zurück zum Zitat Gaborit, P., Girault, M.: Lightweight code-based identification and signature. In: 2007 IEEE International Symposium on Information Theory, pp. 191–195. IEEE (2007) Gaborit, P., Girault, M.: Lightweight code-based identification and signature. In: 2007 IEEE International Symposium on Information Theory, pp. 191–195. IEEE (2007)
17.
Zurück zum Zitat Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016)MathSciNetCrossRefMATH Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016)MathSciNetCrossRefMATH
18.
Zurück zum Zitat Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In: International Workshop on Post-Quantum Cryptography, pp. 35–50 (2011) Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In: International Workshop on Post-Quantum Cryptography, pp. 35–50 (2011)
19.
Zurück zum Zitat Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)MathSciNetCrossRefMATH Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH
21.
Zurück zum Zitat Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, pp. 212–219. ACM (1996) Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, pp. 212–219. ACM (1996)
23.
Zurück zum Zitat Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 663–680 (2012) Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 663–680 (2012)
27.
Zurück zum Zitat Loidreau, P.: Properties of codes in rank metric. arXiv preprint cs/0610057 (2006) Loidreau, P.: Properties of codes in rank metric. arXiv preprint cs/0610057 (2006)
30.
Zurück zum Zitat May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 203–228 (2015) May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 203–228 (2015)
32.
Zurück zum Zitat Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Probl. Inf. Transm. 38(3), 237–246 (2002)MathSciNetCrossRefMATH Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Probl. Inf. Transm. 38(3), 237–246 (2002)MathSciNetCrossRefMATH
33.
Zurück zum Zitat Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
38.
Zurück zum Zitat Véron, P.: Improved identification schemes based on error-correcting codes. Commun. Comput. Appl. Algebra Eng. 8(1), 57–69 (1997)MathSciNetCrossRefMATH Véron, P.: Improved identification schemes based on error-correcting codes. Commun. Comput. Appl. Algebra Eng. 8(1), 57–69 (1997)MathSciNetCrossRefMATH
39.
Zurück zum Zitat Wachter-Zeh, A.: Decoding of block and convolutional codes in rank metric. Ph.D. thesis, Universität Ulm (2013) Wachter-Zeh, A.: Decoding of block and convolutional codes in rank metric. Ph.D. thesis, Universität Ulm (2013)
Metadaten
Titel
Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric
verfasst von
Emanuele Bellini
Philippe Gaborit
Alexandros Hasikos
Victor Mateu
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-65411-5_28