access icon free PolarSig: An efficient digital signature based on polar codes

Code-based digital signatures suffer from two main drawbacks: large public key size and slow signature generation. Large public key size is inherent in almost all the code-based cryptosystems and other post-quantum alternatives; however, slow signature generation is due to their specific structure. Most of the current code-based signature schemes are constructed based on Courtois, Finiasz, and Sendrier (CFS) signature. CFS uses a counter to produce decodable syndromes or the complete decoding technique that imposes some extra computational cost to the signing algorithm for many choices of codes. In this study, the authors propose an efficient digital signature, PolarSig, which can reduce both public key size and signing time simultaneously. PolarSig uses some specific instances of polar codes that enable us to decode every random syndrome. Moreover, they apply puncturing and randomised omitting of frozen bits to protect the authors’ scheme from commonplace attacks targeting former cryptosystems based on polar codes. Besides, they prove that their signature is existentially unforgeable under a chosen message attack secure in the random oracle model.

Inspec keywords: decoding; public key cryptography; digital signatures; polar codes

Other keywords: code-based cryptosystems; PolarSig; polar codes; code-based digital signatures; decodable syndromes; Courtois Finiasz and Sendrier signature; post-quantum alternatives; public key size; current code-based signature schemes; random syndrome; signing algorithm; slow signature generation; complete decoding technique; random oracle model

Subjects: Data security; Cryptography theory; Codes; Cryptography

References

    1. 1)
      • 28. Finiasz, M., Sendrier, N.: ‘Security bounds for the design of code-based cryptosystems’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 2009, pp. 88105.
    2. 2)
      • 8. Finiasz, M.: ‘Parallel-CFS’. Int. Workshop on Selected Areas in Cryptography, Waterloo, Ontario, Canada, 2010, pp. 159170.
    3. 3)
      • 17. Sanitini, P., Baldi, M., Chiaraluce, F.: ‘Cryptanalysis of a one-time code-based digital signature scheme’. 2019 IEEE Int. Symp. on Information Theory (ISIT), Paris, France, 2019, pp. 25942598.
    4. 4)
      • 21. Wagner, D.: ‘A generalized birthday problem’. Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 2002, pp. 288304.
    5. 5)
      • 15. Debris-Alazard, T., Sendrier, N., Jean-Pierre, T.: ‘The problem with the SURF scheme’, 2017.
    6. 6)
      • 29. Sendrier, N.: ‘Decoding one out of many’. Int. Workshop on Post-Quantum Cryptography, Taipei, Taiwan, 2011, pp. 5167.
    7. 7)
      • 30. Stern, J.: ‘A method for finding codewords of small weight’. Int. Colloquium on Coding Theory and Applications, Toulon, France, 1988, pp. 106113.
    8. 8)
      • 7. Dallot, L.: ‘Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme’. Western European Workshop on Research in Cryptology, Bochum, Germany, 2007, pp. 6577.
    9. 9)
      • 9. Baldi, M., Bianchi, M., Chiaraluce, F., et al: ‘Using LDGM codes and sparse syndromes to achieve digital signatures’. Int. Workshop on Post-Quantum Cryptography, Limoges, France, 2013, pp. 115.
    10. 10)
      • 5. Canales-Martínez, I., Guo, Q., Johansson, T.: ‘A code-based signature scheme in the standard model’. 11th Int. Workshop on Coding and Cryptography (WCC), Saint-Jacut-de-la-Mer, France, 2019.
    11. 11)
      • 20. Korada, S.B., Urbanke, R.L.: ‘Polar codes are optimal for lossy source coding’, IEEE Trans. Inf. Theory, 2010, 56, (4), pp. 17511768.
    12. 12)
      • 10. Debris-Alazard, T., Sendrier, N., Tillich, J.-P.: ‘A new signature based on (U|U + V) codes’, 2017.
    13. 13)
      • 11. Lee, W., Kim, Y.-S., No, J.-S.: ‘A new signature scheme based on punctured reed--Muller code with random insertion’, arXiv preprint arXiv:1711.00159, 2017.
    14. 14)
      • 13. Debris-Alazard, T., Sendrier, N., Tillich, J.P.: ‘Wave: A new family of trapdoor one-way preimage sample able functions based on codes’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 2019, pp. 2151.
    15. 15)
      • 2. Kabatianskii, G., Krouk, E., Smeets, B.: ‘A digital signature scheme based on random error-correcting codes’. IMA Int. Conf. on Cryptography and Coding, Cirencester, UK, 1997, pp. 161167.
    16. 16)
      • 4. Cayrel, P.-L., Otmani, A., Vergnaud, D.: ‘On Kabatianskii-Krouk-Smeets signatures’. Int. Workshop on the Arithmetic of Finite Fields, Madrid, Spain, 2007, pp. 237251.
    17. 17)
      • 26. Prange, E.: ‘The use of information sets in decoding cyclic codes’, IRE Trans. Inf. Theory, 1962, 8, (5), pp. 59.
    18. 18)
      • 16. Terry Shue Chien Lau, C.H.T.: ‘Key recovery attack on rank quasi-cyclic code-based signature scheme’, arXiv preprint arXiv:1902.00241, 2019.
    19. 19)
      • 23. Shannon, C.E.: ‘Coding theorems for a discrete source with fidelity criterion’, IRE Nat. Conv. Rec., 1959, 27, pp. 142163.
    20. 20)
      • 1. Shor, P.: ‘Algorithms for quantum computation: discrete logarithms and factoring’. Proc. 35th Annual Symp. on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124134.
    21. 21)
      • 25. Goela, N., Korada, S.B., Gastpar, M.: ‘On LP decoding of polar codes’. Information Theory Workshop (ITW), Cairo, Egypt, 2010, pp. 15.
    22. 22)
      • 12. Song, Y., Huang, X., Mu, Y., et al: ‘A new code-based signature scheme with shorter public key’, IACR Cryptol. ePrint Arch., 2019, 2019, p. 53.
    23. 23)
      • 24. Hussami, N., Korada, S.B., Urbanke, R.: ‘Performance of polar codes for channel and source coding’. 2009 IEEE Int. Symp. on Information Theory, Seoul, Korea, 2009, pp. 14881492.
    24. 24)
      • 3. Courtois, N., Finiasz, M., Sendrier, N.: ‘How to achieve a McEliece-based digital signature scheme’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Gold Coast, QLD, Australia, 2001, pp. 157174.
    25. 25)
      • 33. Berlekamp, E., McEliece, R., van Tilborg, H.: ‘On the inherent intractability of certain coding problems (corresp.)’, IEEE Trans. Inf. Theory, 1978, 24, (3), pp. 384386.
    26. 26)
      • 18. Paulo, S.L.M., Barreto, E.P.: ‘Cryptanalysis of the wave signature scheme’, IACR Cryptol. ePrint Arch., 2018, 2018, p. 1111.
    27. 27)
      • 22. Arikan, E.: ‘Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels’, IEEE Trans. Inf. Theory, 2009, 55, (7), pp. 30513074.
    28. 28)
      • 14. Phesso, A., Tillich, J.-P.: ‘An efficient attack on a code-based signature scheme’. Post-Quantum Cryptography, Fukuoka, Japan, 2016, pp. 86103.
    29. 29)
      • 31. Minder, L., Shokrollahi, A.: ‘Cryptanalysis of the Sidelnikov cryptosystem’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Kuching, Malaysia, 2007, pp. 347360.
    30. 30)
      • 32. Bardet, M., Chaulet, J., Dragoi, V., et al: ‘Cryptanalysis of the McEliece public key cryptosystem based on polar codes’. Post-Quantum Cryptography, Fukuoka, Japan, 2016, pp. 118143.
    31. 31)
      • 6. Niederreiter, H.: ‘Knapsack-type cryptosystems and algebraic coding theory’, Prob. Control Inf. Theory, 1986, 15, (2), pp. 159166.
    32. 32)
      • 19. Korada, S.B.: ‘Polar Codes for Channel and Source Coding’. PhD thesis, EPFL, 2009.
    33. 33)
      • 27. Wieschebrink, C.: ‘Two NP-complete problems in coding theory with an application in code based cryptography’. 2006 IEEE Int. Symp. on Information Theory, Seattle, WA, USA, 2006, pp. 17331737.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2019.0578
Loading

Related content

content/journals/10.1049/iet-com.2019.0578
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading