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:
Nonlinear Invariant Attack Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

From 5-Pass \(\mathcal {MQ}\)-Based Identification to \(\mathcal {MQ}\)-Based Signatures

verfasst von : Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, Peter Schwabe

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

This paper presents MQDSS, the first signature scheme with a security reduction based on the problem of solving a multivariate system of quadratic equations (\(\mathcal {MQ}\) problem). In order to construct this scheme we give a new security reduction for the Fiat-Shamir transform from a large class of 5-pass identification schemes and show that a previous attempt from the literature to obtain such a proof does not achieve the desired goal. We give concrete parameters for MQDSS and provide a detailed security analysis showing that the resulting instantiation MQDSS-31-64 achieves 128 bits of post-quantum security. Finally, we describe an optimized implementation of MQDSS-31-64 for recent Intel processors with full protection against timing attacks and report benchmarks of this implementation.

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 Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption
Nächstes Kapitel Collapse-Binding Quantum Commitments Without Random Oracles
Fußnoten
1
Sakumoto et al. [48] also sketched a proof that their 5-pass protocol is argument of knowledge when Com is computationally binding. Our security arguments rely on the weaker notion of soundness, therefore we include an appropriate proof.
 
2
Note that the concatenation of all \(\alpha _i\) was previously referred to as \(\mathsf {ch} _1\).
 
3
This follows from the fact that we combine 64 such monomials in two YMM registers.
 
4
A slight difference is introduced by cancellation of the monomials in the \(\mathbb {F}_2\) setting.
 
5
This follows from the fact that we need a total of \(\frac{64+64\cdot 65}{2 \cdot 32} = 67\) YMM registers worth of space to store the monomials and perform 4 reductions after accumulating 2 YMM monomials.
 
Literatur
1.
Akleylek, S., Bindel, N., Buchmann, J., Krämer, J., Marson, G.A.: An efficient lattice-based signature scheme with provably secure instantiation. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 44–60. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-31517-1_​3 CrossRef
2.
Alkim, E., Bindel, N., Buchmann, J., Dagdelen, O.: TESLA: tightly-secure efficient signatures from standard lattices. Cryptology ePrint Archive (2015)
3.
Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 28–47. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-04852-9_​2 CrossRef
4.
Bardet, M., Faugère, J., Salvy, B.: On the complexity of the F5 Gröbner basis algorithm. J. Symbolic Comput. 70, 49–70 (2015)MathSciNetCrossRefMATH
5.
Bernstein, D.J., Chou, T., Chuengsatiansup, C., Hülsing, A., Lange, T., Niederhagen, R., van Vredendaal, C.: How to manipulate curve standards: a white paper for the black hat. Cryptology ePrint Archive (2014)
6.
Bernstein, D.J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., Wilcox-O’Hearn, Z.: SPHINCS: Practical Stateless Hash-Based Signatures. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 368–397. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​15
7.
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak reference (2011)
8.
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G., Van Keer, R.: Keccak Code Package (2016)
9.
Bettale, L., Faugère, J., Perret, L.: Solving polynomial systems over finite fields: improved analysis of the hybrid approach. In: ISSAC 2012, pp. 67–74. ACM (2012)
10.
Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptology, pp. 177–197 (2009)
11.
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
12.
Chen, A.I.-T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H., Lee, F.Y.-S., Yang, B.-Y.: SSE implementation of multivariate PKCs on Modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04138-9_​3 CrossRef
13.
Chen, M.-S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: From 5-pass MQ-based identification to MQ-based signatures. Cryptology ePrint Archive (2016)
14.
Courtois, N., Goubin, L., Patarin, J.: SFLASH, a fast asymmetric signature scheme for low-cost smartcards - primitive specification and supporting documentation
15.
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000). doi:10.​1007/​3-540-45539-6_​27 CrossRef
16.
Courtois, N.T.: Efficient zero-knowledge authentication based on a linear algebra problem minrank. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 402–421. Springer, Heidelberg (2001). doi:10.​1007/​3-540-45682-1_​24 CrossRef
17.
Dagdelen, Ö., Bansarkhani, R., Göpfert, F., Güneysu, T., Oder, T., Pöppelmann, T., Sánchez, A.H., Schwabe, P.: High-speed signatures from standard lattices. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 84–103. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-16295-9_​5
18.
19.
Ding, J., Hu, L., Yang, B.-Y., Chen, J.-M.: Note on design criteria for rainbow-type multivariates. Cryptology ePrint Archive (2006)
20.
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). doi:10.​1007/​11496137_​12 CrossRef
21.
22.
Ducas, L.: Accelerating Bliss: the geometry of ternary polynomials. Cryptology ePrint Archive (2014)
23.
Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40041-4_​3 CrossRef
24.
Yousfi Alaoui, S.M., Dagdelen, Ö., Véron, P., Galindo, D., Cayrel, P.-L.: Extended security arguments for signature schemes. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 19–34. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-31410-0_​2 CrossRef
25.
26.
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: ISSAC 2002, 75–83. ACM (2002)
27.
Faugère, J.-C., Gligoroski, D., Perret, L., Samardjiska, S., Thomae, E.: A polynomial-time key-recovery attack on MQQ cryptosystems. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 150–174. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46447-2_​7
28.
29.
30.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)MATH
31.
Gligoroski, D., Ødegård, R.S., Jensen, R.E., Perret, L., Faugère, J.-C., Knapskog, S.J., Markovski, S.: MQQ-SIG. In: Chen, L., Yung, M., Zhu, L. (eds.) INTRUST 2011. LNCS, vol. 7222, pp. 184–203. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32298-3_​13 CrossRef
32.
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)MathSciNetCrossRefMATH
33.
Groot Bruinderink, L., Hülsing, A., Lange, T., Yarom, Y.: Flush, Gauss, and Reload - a cache attack on the BLISS lattice-based signature scheme. Cryptology ePrint Archive (2016)
34.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996, pp. 212–219. ACM (1996)
35.
Halevi, S., Krawczyk, H.: Strengthening digital signatures via randomized hashing. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 41–59. Springer, Heidelberg (2006). doi:10.​1007/​11818175_​3 CrossRef
36.
IBM. IBM makes quantum computing available on IBM cloud to accelerate innovation (2016)
37.
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48910-X_​15
38.
Gligoroski, D., Ødegård, R.S., Jensen, R.E., Perret, L., Faugère, J.-C., Knapskog, S.J., Markovski, S.: MQQ-SIG. In: Chen, L., Yung, M., Zhu, L. (eds.) INTRUST 2011. LNCS, vol. 7222, pp. 184–203. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32298-3_​13 CrossRef
39.
McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S.-L., Butin, D., Buchmann, J.: State management for hash based signatures. Cryptology ePrint Archive (2016)
40.
NIST. Post-quantum cryptography: NIST’s plan for the future (2016)
41.
42.
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68339-9_​4
43.
Patarin, J.: The Oil and Vinegar signature scheme. In: Dagstuhl Workshop on Cryptography (1997)
44.
45.
Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., Ding, J.: Design principles for HFEv- based multivariate signature schemes. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 311–334. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48797-6_​14 CrossRef
46.
Pointcheval, D., Poupard, G.: A new NP-complete problem and public-key identification. Des. Codes Crypt. 28(1), 5–31 (2003)MathSciNetCrossRefMATH
47.
Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68339-9_​33
48.
Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 706–723. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22792-9_​40 CrossRef
49.
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
50.
51.
Thomae, E.: About the Security of Multivariate Quadratic Public Key Schemes. Ph.D. thesis, Ruhr-University Bochum, Germany (2013)
52.
Thomae, E., Wolf, C.: Cryptanalysis of Enhanced TTS, STS and All Its Variants, or: why cross-terms are important. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 188–202. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-31410-0_​12 CrossRef
53.
Tsujii, S., Gotaishi, M., Tadaki, K., Fujita, R.: Proposal of a signature scheme based on STS trapdoor. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 201–217. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-12929-2_​15 CrossRef
54.
55.
Weiden, P., Hülsing, A., Cabarcas, D., Buchmann, J.: Instantiating treeless signature schemes. Cryptology ePrint Archive (2013)
56.
Yang, B.-Y., Chen, J.-M.: All in the XL Family: theory and practice. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 67–86. Springer, Heidelberg (2005). doi:10.​1007/​11496618_​7 CrossRef
57.
Yang, B.-Y., Chen, J.-M.: Building secure Tame-like multivariate public-key cryptosystems: the new TTS. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 518–531. Springer, Heidelberg (2005). doi:10.​1007/​11506157_​43 CrossRef
58.
Yang, B.-Y., Chen, J.-M., Chen, Y.-H.: TTS: high-speed signatures on a low-cost smart card. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 371–385. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-28632-5_​27 CrossRef
59.
Yeh, J.Y.-C., Cheng, C.-M., Yang, B.-Y.: Operating degrees for XL vs. F\(_4\)/F\(_5\) for generic \({\cal{MQ}}\) with number of equations linear in that of variables. In: Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography. LNCS, vol. 8260, pp. 19–33. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-42001-6_​3
Metadaten
Titel
From 5-Pass -Based Identification to -Based Signatures
verfasst von
Ming-Shing Chen
Andreas Hülsing
Joost Rijneveld
Simona Samardjiska
Peter Schwabe
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – ASIACRYPT 2016

Print ISBN: 978-3-662-53889-0

Electronic ISBN: 978-3-662-53890-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53890-6_5