SpringerLink
Log in

Code-based signatures from new proofs of knowledge for the syndrome decoding problem

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

In this paper, we study code-based signatures constructed from Proofs of Knowledge (PoK). This line of work can be traced back to Stern who introduced the first efficient PoK for the syndrome decoding problem in 1993 (Stern in A new identification scheme based on syndrome decoding. In: International cryptology conference (CRYPTO), 1993). Afterwards, different variations were proposed in order to reduce signature’s size. In practice, obtaining a smaller signature size relies on the interaction of two main considerations: (i) the underlying protocol and its soundness error and (ii) the types of optimizations which are compatible with a given protocol. In particular, optimizations related to the possibility of using random seeds instead of long vectors have a great impact on the final signature length. Over the years, different variations were proposed to improve the Stern scheme such as the Veron scheme (with public key as a noisy codeword rather than a syndrome) (Véron in Appl Algebra Eng Commun Comput 8(1):57-69, 1997), the AGS scheme which is a 5-pass protocol with soundness error asymptotically equal to 1/2 (Aguilar et al. in A new zero-knowledge code based identification scheme with reduced communication. In: IEEE information theory workshop, 2011) and more recently the FJR approach which permits to decrease the soundness probability to 1/N but induces a performance overhead (Feneuil et al. in Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature. Cryptology ePrint archive, report 2021/1576, 2021). Overall the length of the signature depends on a trade-off between: the scheme in itself, the possible optimizations and the cost of the implementation. For instance, depending on the application one may prefer a 30% shorter signature at the cost of a ten times slower implementation rather than a longer signature but a faster implementation. The recent approaches which increase the cost of the implementation open the door to many different types of trade-offs. In this paper we propose three new schemes and different trade-offs, which are all interesting in themselves, since depending on potential future optimizations a scheme may eventually become more efficient than another. All the schemes we propose use a trusted helper: the first scheme permits to get a soundness error of 1/2, the second scheme permits to decrease the soundness error to 1/N but with a different approach than the recent FJR scheme and at last the third scheme proposes a Veron-like adaptation of the FJR scheme in which the public key is a noisy codeword rather than a syndrome. We provide extensive comparison which lists various trade-offs between our schemes and previous ones. The table highlights the benefits of our constructions for certain types of trade-offs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. Proof of Knowledge systems with computational soundness are also called Arguments of Knowledge. Our PoK achieves computational ZK since the random masks \((\mathbf {u}, \mathbf {v})\) added to hide the secrets are generated from seeds with the help of pseudorandom objects such as XOF.

References

  1. Abdalla M., An J.H., Bellare M., Namprempre C.: From identification to signatures via the Fiat-Shamir transform: minimizing assumptions for security and forward-security. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2002).

  2. Aguilar C., Gaborit P., Schrek J.: A new zero-knowledge code based identification scheme with reduced communication. In: IEEE Information Theory Workshop (2011).

  3. Aguilar Melchor C., Aragon N., Barreto P., Bettaieb S., Bidoux L., Blazy O., Deneuville J.-C., Gaborit P., Ghosh S., Gueron S., Güneysu T., Misoczki R., Persichetti E., Sendrier N., Tillich J.-P., Vasseur V., Zémor G.: BIKE: Bit Flip** Key Encapsulation. NIST Post-Quantum Cryptography Standardization Project (Round 3). https://bikesuite.org (2020).

  4. Aguilar Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Bos J., Deneuville J.-C., Dion A., Gaborit P., Lacan J., Persichetti E., Robert J.-M., Véron P., Zémor G.: Hamming Quasi-Cyclic (HQC). NIST Post-Quantum Cryptography Standardization Project (Round 3). https://pqc-hqc.org (2020).

  5. Albrecht M.R., Bernstein D.J., Chou T., Cid C., Gilcher J., Lange T., Maram V., von Maurich I., Misoczki R., Niederhagen R., Patterson K.G., Persichetti E., Peters C., Schwabe P., Sendrier N., Szefer J., Tjhai C.J., Tomlinson M., Wang W.: Classic McEliece. NIST Post-Quantum Cryptography Standardization Project (Round 3). https://classic.mceliece.org (2020).

  6. Aragon N., Blazy O., Gaborit P., Hauteville A., Zémor G.: Durandal: a rank metric based signature scheme. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2019).

  7. Barenghi A., Biasse J.-F., Persichetti E., Santini P.: LESS-FM: fine-tuning signatures from a code-based cryptographic group action. In: International Workshop on Post-Quantum Cryptography (PQCrypto) (2021).

  8. Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in \(2^{n/20}\): how \(1+1=0\) improves information set decoding. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2012).

  9. Bellini E., Caullery F., Gaborit P., Manzano M., Mateu V.: Improved Véron identification and signature schemes in the rank metric. In: IEEE International Symposium on Information Theory (ISIT) (2019).

  10. Berlekamp E., McEliece R., Van Tilborg H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24, 3 (1978).

    Article  MathSciNet  MATH  Google Scholar 

  11. Bernhard D., Pereira O., Warinschi B.: How not to prove yourself: pitfalls of the fiat-shamir heuristic and applications to Helios. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2012).

  12. Bettaieb S., Bidoux L., Blazy O., Gaborit P.: Zero-knowledge reparation of the Véron and AGS code-based identification schemes. In: IEEE International Symposium on Information Theory (ISIT) (2021).

  13. Beullens W.: Sigma protocols for MQ, PKP and SIS, and fishy signature schemes. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2020).

  14. Biasse J.-F., Micheli G., Persichetti E., Santini P.: LESS is more: code-based signatures without syndromes. In: International Conference on Cryptology in Africa (AFRICACRYPT) (2020).

  15. Bidoux L., Gaborit P., Kulkarni M., Sendrier N.: Quasi-cyclic stern proof of knowledge. In: IEEE International Symposium on Information Theory (ISIT) (2022).

  16. Cayrel P.-L., Véron P., El Yousfi Alaoui S.M.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: International Conference on Selected Areas in Cryptography (SAC) (2011).

  17. Chen K.: A new identification algorithm. In: International Conference on Cryptography: Policy and Algorithms (CPA) (1995).

  18. Chen L., Jordan S., Liu Y.-K., Moody D., Peralta R., Perlner R., Smith-Tone D.: Report on post-quantum cryptography. In: US Department of Commerce, National Institute of Standards and Technology (2016).

  19. Courtois N., Finiasz M., Sendrier N.: How to achieve a McEliece-based digital signature scheme. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2001).

  20. Debris-Alazard T., Sendrier N., Tillich J.-P.: Wave: a new family of trapdoor one-way preimage sampleable functions based on codes. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2019).

  21. Don J., Fehr S., Majenz C.: The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and More. In: International Cryptology Conference (CRYPTO) (2020).

  22. Don J., Fehr S., Majenz C., Schaffner C.: Security of the Fiat-Shamir transformation in the quantum random-oracle model. In: International Cryptology Conference (CRYPTO) (2019).

  23. Feneuil T., Joux A., Rivain M.: Shared Permutation for Syndrome Decoding: New Zero-Knowledge Protocol and Code-Based Signature. Cryptology ePrint Archive, Report 2021/1576 (2021).

  24. Fiat A., Shamir A.: How to prove yourself: practical solutions to identification and signature problems. In: International Cryptology Conference (CRYPTO) (1986).

  25. Gaborit P., Schrek J., Zémor G.: Full cryptanalysis of the Chen identification protocol. In: International Workshop on Post-Quantum Cryptography (PQCrypto) (2011).

  26. Gueron S., Persichetti E., Santini P.: Designing a practical code-based signature scheme from zero-knowledge proofs with trusted setup. Cryptography 6(1), 5 (2022).

    Article  Google Scholar 

  27. Hamdaoui Y., Sendrier N.: A non asymptotic analysis of information set decoding. In: Cryptology ePrint Archive, Report 2013/162 (2013).

  28. Ishai Y., Kushilevitz E., Ostrovsky R., Sahai A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC) (2007), pp. 21–30.

  29. 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 (ASIACRYPT) (2012).

  30. Kales D., Zaverucha G.: An attack on some signature schemes constructed from five-pass identification schemes. In: International Conference on Cryptology and Network Security (CANS) (2020).

  31. Katz J., Kolesnikov V., Wang X.: Improved non-interactive zero knowledge with applications to post-quantum signatures. In: Proceedings of the 2018 ACM Conference on Computer and Communications Security (CCS) (2018).

  32. Kiltz E., Lyubashevsky V., Schaffner C.: A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2018).

  33. Liu Q., Zhandry M.: Revisiting post-quantum Fiat-Shamir. In: International Cryptology Conference (CRYPTO) (2019).

  34. Lyubashevsky V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2009).

  35. McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. Coding Thv 4244, 114–116 (1978).

    Google Scholar 

  36. Pointcheval D., Stern J.: Security proofs for signature schemes. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (1996).

  37. Pointcheval D., Stern J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000).

    Article  MATH  Google Scholar 

  38. Schnorr C.-P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161–174 (1991).

    Article  MathSciNet  MATH  Google Scholar 

  39. Sendrier N.: Decoding one out of many. In: International Workshop on Post-Quantum Cryptography (PQCrypto) (2011).

  40. Stern J.: A new identification scheme based on syndrome decoding. In: International Cryptology Conference (CRYPTO) (1993).

  41. Unruh D.: Quantum proofs of knowledge. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2012).

  42. Unruh D.: Computationally binding quantum commitments. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2016).

  43. Unruh D.: Post-quantum security of Fiat-Shamir. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2017).

  44. Véron P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1997).

    Article  MathSciNet  MATH  Google Scholar 

  45. Zhandry M.: How to construct quantum random functions. In: IEEE Symposium on Foundations of Computer Science FOCS (2012).

Download references

Author information

Authors and Affiliations

  1. Technology Innovation Institute, Abu Dhabi, UAE

    Loïc Bidoux, Mukul Kulkarni & Victor Mateu

  2. University of Limoges, Limoges, France

    Philippe Gaborit

Authors
  1. Loïc Bidoux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philippe Gaborit
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mukul Kulkarni
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Victor Mateu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Loïc Bidoux.

Additional information

Communicated by M. Albrecht.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix

PoK 1 (3-round, without optimization)

See Fig. 9.

Fig. 9
figure 9

3-round HVZK PoK for the \(\mathsf {SD}\) problem (without optimization)

Full size image

PoK 1 (3-round, with optimizations)

See Fig. 10.

Fig. 10
figure 10

3-round HVZK PoK for the \(\mathsf {SD}\) problem (with optimizations)

Full size image

Sig 1 (3-round)

See Figs. 11 and 12.

Fig. 11
figure 11

\(\mathsf {Keygen}\) and \(\mathsf {Sign}\) algorithms for Sig 1 (3-round)

Full size image
Fig. 12
figure 12

\(\mathsf {Verify}\) algorithm for Sig 1 (3-round)

Full size image

PoK 1 (5-round, without optimization)

See Fig. 13.

Fig. 13
figure 13

5-round HVZK PoK for the \(\mathsf {SD}\) problem (without optimization)

Full size image

PoK 1 (5-round, with optimizations)

See Fig. 14.

Fig. 14
figure 14

5-round HVZK PoK for the \(\mathsf {SD}\) problem (with optimizations)

Full size image

Sig 1 (5-round)

See Figs. 15 and 16.

Fig. 15
figure 15

\(\mathsf {Keygen}\) and \(\mathsf {Sign}\) algorithms for Sig 1 (5-round)

Full size image
Fig. 16
figure 16

\(\mathsf {Verify}\) algorithm for Sig 1 (5-round)

Full size image

PoK 2 (3-round, without optimization)

See Fig. 17.

Fig. 17
figure 17

3-round ZK PoK for the \(\mathsf {GD}\) problem (without optimization)

Full size image

PoK 2 (3-round, with optimizations)

See Fig. 18.

Fig. 18
figure 18

ZK PoK for the \(\mathsf {GD}\) problem over \(\mathbb {F}_2\) (with optimizations)

Full size image

Sig 2

See Figs. 19 and 20.

Fig. 19
figure 19

\(\mathsf {Keygen}\) and \(\mathsf {Sign}\) algorithms for Sig 2

Full size image
Fig. 20
figure 20

\(\mathsf {Verify}\) algorithm for Sig 2

Full size image

PoK 3 (3-round, without optimization)

See Fig. 21.

Fig. 21
figure 21

3-round HVZK PoK for the \(\mathsf {GD}\) problem (without optimization)

Full size image

PoK 3 (3-round, with optimizations)

See Fig. 22.

Fig. 22
figure 22

3-round HVZK PoK for the \(\mathsf {GD}\) problem (with optimizations)

Full size image

Sig 3

See Figs. 23 and 24.

Fig. 23
figure 23

\(\mathsf {Keygen}\) and \(\mathsf {Sign}\) algorithms for Sig 3

Full size image
Fig. 24
figure 24

\(\mathsf {Verify}\) algorithm for Sig 3

Full size image

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bidoux, L., Gaborit, P., Kulkarni, M. et al. Code-based signatures from new proofs of knowledge for the syndrome decoding problem. Des. Codes Cryptogr. 91, 497–544 (2023). https://doi.org/10.1007/s10623-022-01114-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-022-01114-3

Keywords

Mathematics Subject Classification

Search

Navigation