nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Ternary Syndrome Decoding with Large Weight

verfasst von : Rémi Bricout, André Chailloux, Thomas Debris-Alazard, Matthieu Lequesne

Erschienen in: Selected Areas in Cryptography – SAC 2019

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The Syndrome Decoding problem is at the core of many code-based cryptosystems. In this paper, we study ternary Syndrome Decoding in large weight. This problem has been introduced in the Wave signature scheme but has never been thoroughly studied. We perform an algorithmic study of this problem which results in an update of the Wave parameters. On a more fundamental level, we show that ternary Syndrome Decoding with large weight is a really harder problem than the binary Syndrome Decoding problem, which could have several applications for the design of code-based cryptosystems.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel An Improved Security Analysis on an Indeterminate Equation Public Key Cryptosystem by Evaluation Attacks

Nächstes Kapitel Exploring Trade-offs in Batch Bounded Distance Decoding

Nur mit Berechtigung zugänglich

[ABB+17]

Aragon, N., et al.: BIKE. NIST Round 1 submission for Post-Quantum Cryptography, December 2017

[ACP+17]

Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., Tomlinson, M.: NTS-KEM. First round submission to the NIST post-quantum cryptography call, December 2017

[AMAB+17]

Melchor, C.A., et al.: HQC. NIST Round 1 submission for Post-Quantum Cryptography, December 2017

[BBC+19]

Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Santini, P.: LEDAcrypt. Second round submission to the NIST post-quantum cryptography call, January 2019

[BCJ11]

Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364–385. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_21CrossRef

[BCL+17]

Bernstein, D.J., et al.: Classic McEliece: conservative code-based cryptography. First round submission to the NIST post-quantum cryptography call, November 2017. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/Classic_McEliece.zip

[BJMM12]

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: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520–536. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_31CrossRefMATH

[BMvT78]

Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)MathSciNetCrossRef

[CFG89]

Chaimovich, M., Freiman, G., Galil, Z.: Solving dense subset-sum problems by using analytical number theory. J. Complex. 5(3), 271–282 (1989)MathSciNetCrossRef

[CFS01]

Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_10CrossRef

[CG90]

Coffey, J.T., Goodman, R.M.: The complexity of information set decoding. IEEE Trans. Inf. Theory 36(5), 1031–1037 (1990)MathSciNetCrossRef

[CT17]

Torres, R.C.: Asymptotic analysis of ISD algorithms for the \(q-\)ary case. In: Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017, September 2017

[DST17]

Debris-Alazard, T., Sendrier, N., Tillich, J.-P.: Surf: a new code-based signature scheme. Preprint, September 2017. arXiv:1706.08065v3

[DST18]

Debris-Alazard, T., Sendrier, N., Tillich, J.-P.: Wave: a new code-based signature scheme. Cryptology ePrint Archive, Report 2018/996, October 2018. https://eprint.iacr.org/2018/996

[Dum91]

Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of the 5th Joint Soviet-Swedish International Workshop Information Theory, Moscow, pp. 50–52 (1991)

[FP05]

Flaxman, A.D., Przydatek, B.: Solving medium-density subset sum problems in expected polynomial time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 305–314. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31856-9_25CrossRef

[GKH17]

Gueye, C.T., Klamti, J.B., Hirose, S.: Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field \(\mathbb{F}_q\). In: El Hajji, S., Nitaj, A., Souidi, E.M. (eds.) C2SI 2017. LNCS, vol. 10194, pp. 96–109. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55589-8_7CrossRef

[GM91]

Galil, Z., Margalit, O.: An almost linear-time algorithm for the dense subset-sum problem. SIAM J. Comput. 20(6), 1157–1189 (1991)MathSciNetCrossRef

[GPV08]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008)

[Hir16]

Hirose, S.: May-Ozerov algorithm for nearest-neighbor problem over \({\mathbb{F}}_{q}\) and its application to information set decoding. In: Bica, I., Reyhanitabar, R. (eds.) SECITC 2016. LNCS, vol. 10006, pp. 115–126. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47238-6_8CrossRef

[HJ10]

Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235–256. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_12CrossRef

[IKR+18]

Interlando, C., Khathuria, K., Rohrer, N., Rosenthal, J., Weger, V.: Generalization of the ball-collision algorithm. arXiv preprint arXiv:1812.10955 (2018)

[JJ02]

Johansson, T., Jönsson, F.: On the complexity of some cryptographic problems based on the general decoding problem. IEEE Trans. Inf. Theory 48(10), 2669–2678 (2002)MathSciNetCrossRef

[Lyu05]

Lyubashevsky, V.: On random high density subset sums. Electronic Colloquium on Computational Complexity (ECCC), 1(007) (2005)

[McE78]

McEliece, R.J.: A public-key system based on algebraic coding theory, pp. 114–116. Jet Propulsion Lab, DSN Progress Report 44 (1978)

[Meu17]

Meurer, A.: A coding-theoretic approach to cryptanalysis. Ph.D. thesis, Ruhr University Bochum, November 2017

[MMT11]

May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_6CrossRefMATH

[MTSB12]

Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. IACR Cryptology ePrint Archive, Report 2012/409, 2012 (2012)

[Pet10]

Peters, C.: Information-set decoding for linear codes over F\(_{q}\). In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 81–94. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12929-2_7CrossRef

[Pra62]

Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962)MathSciNetCrossRef

[Sen11]

Sendrier, N.: Decoding one out of many. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 51–67. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_4CrossRef

[Ste93]

Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_2CrossRef

[Wag02]

Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_19CrossRef

Titel: Ternary Syndrome Decoding with Large Weight
verfasst von: Rémi Bricout
André Chailloux
Thomas Debris-Alazard
Matthieu Lequesne
Verlag: Springer International Publishing
Buch: Selected Areas in Cryptography – SAC 2019
Print ISBN: 978-3-030-38470-8

Electronic ISBN: 978-3-030-38471-5

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-38471-5_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"