Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Some Results on the Known Classes of Quadratic APN Functions Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography

verfasst von : Thierry P. Berger, Cheikh Thiécoumba Gueye, Jean Belo Klamti

Erschienen in: Codes, Cryptology and Information Security

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

It is easy to determine if a given code \(\mathcal {C}\) is a subcode of another known code \(\mathcal {D}\). For most of occurrences, it is easy to determine if two codes \(\mathcal {C}\) and \(\mathcal {D}\) are equivalent by permutation. In this paper, we show that determining if a code \(\mathcal {C}\) is equivalent to a subcode of \(\mathcal {D}\) is a NP-complete problem. We give also some arguments to show why this problem seems much harder to solve in practice than the Equivalence Punctured Code problem or the Punctured Code problem proposed by Wieschebrink [21]. For one application of this problem we propose an improvement of the three-pass identification scheme of Girault and discuss on its performance.

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 The Weight Distribution for an Extended Family of Reducible Cyclic Codes
Nächstes Kapitel Spectral Approach for Correlation Power Analysis
Literatur
1.
Barg, A.: Some new NP-complete coding problems. Problemy Peredachi Informatsii 30(3), 23–28 (1994). English translation in Probl. Inform. Trans. 30, 209–214, July–September 1994
2.
Berger, T.P.: New perspectives for code-based public key cryptography. In: Codes and Lattices in Cryptography, CLC 2006, Darmstadt (2006)
3.
Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-02384-2_​6 CrossRef
4.
5.
Berlekamp, E., McEliece, R.J., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theor. 24(3), 384–386 (1978)MathSciNetCrossRefMATH
6.
Cayrel, P.L., Diagne, M.K., Gueye, C.T.: NP-completeness of the Coset weight problem for Quasi-dyadic codes. In: International Conference on Coding theory and Cryptography ICCC 2015, Alger, Algeria (2015)
7.
Cayrel, P.-L., Véron, P., Yousfi Alaoui, S.M.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 171–186. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19574-7_​12 CrossRef
8.
Garey, E., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)MATH
9.
Girault, M.: A (non-practical) three-pass identification protocol using coding theory. In: Seberry, J., Pieprzyk, J. (eds.) AUSCRYPT 1990. LNCS, vol. 453, pp. 265–272. Springer, Heidelberg (1990). doi:10.​1007/​BFb0030367 CrossRef
10.
Gaborit, P., Girault, M.: Lightweight code-based authentication and signature. In: ISIT (2007)
11.
Harari, S.: A new authentication algorithm. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 91–105. Springer, Heidelberg (1989). doi:10.​1007/​BFb0019849 CrossRef
12.
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Jet Propulsion Lab. DSN Progress Report, Technical report (1978)
13.
Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05445-7_​24 CrossRef
14.
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theor. 15(2), 159–166 (1986)MathSciNetMATH
15.
16.
Sendrier, N.: Finding the permutation between equivalent codes: the support splitting algorithm. IEEE Trans. Inf. Theor. 46(4), 1193–1203 (2000)MathSciNetCrossRefMATH
17.
Sendrier, N., Simos, D.E.: The hardness of code equivalence over \(\mathbb{F}_q\) and its application to code-based cryptography. In: Proceeding of Post-Quantum Cryptography, 5th International Workshop PQcrupto 2013, Limoges, France (2013)
18.
Sidel’nikov, V.M., Shestakov, S.O.: On cryptosystems based on generalized Reed-Solomon codes. Discrete Math. 4(3), 57–63 (1992)MATH
19.
20.
21.
Wieschebrink, C.: Two NP-complete problems in coding theory with an application in code based cryptography. In: Proceedings of IEEE ISIT 2006, Seattle, USA, pp. 1733–1737 (2006)
22.
Wieschebrink, C.: An attack on a modified niederreiter encryption scheme. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 14–26. Springer, Heidelberg (2006). doi:10.​1007/​11745853_​2 CrossRef
23.
Stern, J.: An alternative to the Fiat-Shamir protocol. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 173–180. Springer, Heidelberg (1990). doi:10.​1007/​3-540-46885-4_​19
24.
Véron, P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1996)MathSciNetCrossRefMATH
25.
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). doi:10.​1007/​3-540-48329-2_​2
Metadaten
Titel
A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography
verfasst von
Thierry P. Berger
Cheikh Thiécoumba Gueye
Jean Belo Klamti
Copyright-Jahr
2017
Buch
Codes, Cryptology and Information Security

Print ISBN: 978-3-319-55588-1

Electronic ISBN: 978-3-319-55589-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-55589-8_15