Problems in the usage of a code hash function for a CFS signature scheme built on Goppa codes

Anastasiya Ilyukhina

Abstract


In 2001, a CFS signature scheme based on the Niederreiter cryptosystem was proposed. The signature algorithm is based on code cryptography, which makes the signature resistant to post-quantum attacks. However, there are certain difficulties in its implementation. One of them lies in the complexity of constructing a signature due to the low probability of receiving an acceptable syndrome that can be easily decoded. This article considers a known way of modifying the original signature scheme to solve this problem. The paper studies the use of a code hash function to quickly obtain a decodable syndrome. When considering the compression function of the hash function, an error was found in its construction and the insecurity of the signature scheme built on such a hash function was proved.

Full Text:

PDF (Russian)

References


W. Diffie and M. Hellman, «New directions in cryptography,» IEEE Transactions on Information Theory, vol. 22, No 6, pp. 644—654, 1976. doi: 10.1109/TIT.1976.1055638.

R. L. Rivest, A. Shamir and L. Adleman, «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,» Commun. ACM, vol. 21, No 2, pp. 120—126, Feb. 1978. doi: 10.1145/359340.359342. url: https://doi.org/10.1145/359340.359342.

M. O. Rabin, «DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION,» USA, tech report, 1979.

R. C. Merkle, «One Way Hash Functions and DES,» in Advances in Cryptology — CRYPTO’ 89 Proceedings, G. Brassard, ред., New York, NY: Springer New York, 1990, pp. 428—446.

H. M. Grumbling E., Quantum Computing: Progress and Prospects. 2019.

P. Shor, «Algorithms for quantum computation: discrete logarithms and factoring,» в Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124—134. doi: 10.1109/SFCS.1994. 365700.

N. I. of Standards и T. (NIST), «Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms,» 2016.

H. Singh, «Code based Cryptography: Classic McEliece,» CoRR, т. abs/1907.12754, 2019. url: http://arxiv.org/abs/1907.12754.

E. Berlekamp, R. McEliece and H. van Tilborg, «On the inherent intractability of certain coding problems (Corresp.),» IEEE Transactions on Information Theory, vol. 24, No 3, pp. 384—386, 1978. doi: 10.1109/TIT.1978.1055873.

R. J. McEliece, «A public-key cryptosystem based on algebraic,» vol. 4244, 1978, pp. 114—116.

D. J. Bernstein, «Introduction to post-quantum cryptography,» in Post-Quantum Cryptography, D. J. Bernstein, J. Buchmann и E. Dahmen, ред. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 1—14. doi: 10.1007/978- 3- 540- 88702- 7_1. url: https://doi.org/10.1007/978-3-540-88702-7_1.

N. T. Courtois, M. Finiasz and N. Sendrier, «How to Achieve a McEliece-Based Digital Signature Scheme,» in Advances in Cryptology — ASIACRYPT 2001, C. Boyd, ред., Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 157—174.

D. Augot, M. Finiasz and N. Sendrier, «A Family of Fast Syndrome Based Cryptographic Hash Functions,» in Progress in Cryptology – Mycrypt 2005, E. Dawson and S. Vaudenay, ed, Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 64—83.

I. B. Damgård, «A Design Principle for Hash Functions,» in Advances in Cryptology — CRYPTO’ 89 Proceedings, G. Brassard, ред., New York, NY:

Springer New York, 1990, pp. 416—427.

R. C. Merkle, «Secrecy, Authentication, and Public Key Systems.,» AAI8001972, diss., Stanford, CA, USA, 1979.

F. Ren, D. Zheng and W. Wang, «An Efficient Code Based Digital Signature Algorithm,» Int. J. Netw. Secur., vol. 19, pp. 1072—1079, 2017.

P.-L. Cayrel, A. Otmani and D. Vergnaud, «On Kabatianskii-Krouk-Smeets Signatures,» in Arithmetic of Finite Fields, C. Carlet and B. Sunar, ред., Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 237—251.

M. T. Banday, Cryptographic Security Solutions for the Internet of Things. Jan. 2019.

G. D’Alconzo, A. Meneghetti and P. Piasenti, «Security issues of CFS-like digital signature algorithms,» CoRR, vol. abs/2112.00429, 2021. url: https://arxiv.org/abs/2112.00429.

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Third Edition, 3rd. The MIT Press, 2009.

E. K. Alekseev, I. B. Oshkin, V. O. Popov and S. V. Smyshlyaev, «On the cryptographic properties of algorithms accompanying the applications of standards GOST R 34.11-2012 and GOST R 34.10-2012,» Mat. Vopr. Kriptogr., vol. 7, No 1, pp. 5—38, 2016.

S. Goldwasser, S. Micali and R. L. Rivest, «A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack,» в Discrete Algorithms and Complexity, D. S. Johnson, T. Nishizeki, A. Nozaki and H. S. Wilf, ред., Academic Press, 1987, pp. 287—310. doi: https://doi.org/10.1016/B978- 0- 12- 386870- 1. 50022-8. url: https://www.sciencedirect.com/science/article/pii/B9780123868701500228.

T. G. Tan, P. Szalachowski and J. Zhou, Challenges of Post-Quantum Digital Signing in Real-world Applications: A Survey, Cryptology ePrint Archive, Report 2019/1374, https://ia.cr/2019/1374, 2019.

L. Dallot, «Towards a Concrete Security Proof of Courtois, Finiasz and Sendrier Signature Scheme,» в Research in Cryptology, S. Lucks, A.-R. Sadeghi and C. Wolf, ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, с. 65—77.

J.-C. Faugère, V. Gauthier, A. Otmani, L. Perret and J.-P. Tillich, «A Distinguisher for High-Rate McEliece Cryptosystems,» IACR Cryptology ePrint Archive, vol. 2010, p. 331, July 2010. doi: 10.1109/ITW.2011.

K. Morozov, P. Roy, R. Steinwandt and R. Xu, «On the security of the Courtois-Finiasz-Sendrier signature,» Open Mathematics, vol. 16, pp. 161—167, March 2018. doi: 10.1515/math-2018-0011.

V. D. Goppa, «A New Class of Linear Correcting Codes,» Problems of Information Transmission, vol. 6, No 3, pp. 207—212, 1970.

P. Loidreau, «Codes Derived from Binary Goppa Codes,» Problems of Information Transmission - PROBL INF TRANSM, vol. 37, Apr. 2001. doi: 10.1023/A:1010406807141.

A. Canteaut and F. Chabaud, «A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511,» IEEE Transactions on Information Theory, vol. 44, No 1, pp. 367—378, 1998. doi: 10.1109/18.651067.

P. Loidreau and N. Sendrier, «Weak keys in the McEliece public-key cryptosystem,» IEEE Transactions on Information Theory, vol. 47, No 3,

pp. 1207—1211, 2001. doi: 10.1109/18.915687.

M. Finiasz and N. Sendrier, «Security Bounds for the Design of Code-Based Cryptosystems,» in Advances in Cryptology – ASIACRYPT 2009, M. Matsui, ред., Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 88—105.

S. Goldwasser and M. Bellare, Lecture Notes on Cryptography, 2001.

H. C. A. V. Tilborg, Fundamentals of Cryptology: A Professional Reference and Interactive Tutorial, 1st. USA: Kluwer Academic Publishers, 1999.

E. R. Berlekamp, «Goppa codes,» IEEE Trans. Inf. Theory, vol. 19, pp. 590—592, 1973.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162