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

Collapse-Binding Quantum Commitments Without Random Oracles

verfasst von : Dominique Unruh

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

We construct collapse-binding commitments in the standard model. Collapse-binding commitments were introduced in (Unruh, Eurocrypt 2016) to model the computational-binding property of commitments against quantum adversaries, but only constructions in the random oracle model were known.
Furthermore, we show that collapse-binding commitments imply selected other security definitions for quantum commitments, answering an open question from (Unruh, Eurocrypt 2016).

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 From 5-Pass -Based Identification to -Based Signatures
Nächstes Kapitel Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
Fußnoten
1
This definition, called classical-style style binding in [16], roughly states, that it is computationally hard to find a commitment c, two messages \(m\ne m'\) and corresponding valid opening informations \(u,u'\).
 
2
We do not claim that they will work in every rewinding-based proof, but [16] showed their usefulness in the construction of arguments of knowledge. The proof of their construction did involve the quantum rewinding techniques from [14, 17].
 
3
The adversary can initialize a register M with the superposition of all messages, run the commit algorithm in superposition, and measure the resulting commitment c. Then M will still be in superposition between many different messages m which the adversary can open c to.
 
4
By unkeyed hash function, we mean a function that depends only on the security parameter. Such a function might be collision-resistant against uniform adversaries, but not against non-uniform ones.
 
5
To see that, let https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq77_HTML.gif be the distribution of the first output (i.e., discarding the trapdoor) of the injective key sampler https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq78_HTML.gif conditioned on outputting an injective key. Let https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq79_HTML.gif be the distribution of the first output of the lossy key sampler https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq80_HTML.gif conditioned on outputting a lossy key. Let \(S_F\) return the first output of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq82_HTML.gif (or https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq83_HTML.gif ). Let \(F_k(x):=F_\mathrm {ldtf}(k,x)\). For those choices, it is easy to see that \((S_F,F_k)\) satisfies Definition 2.
 
6
This is not explicitly mentioned in [13], but can be seen as follows: [13] constructs a matrix encryption scheme whose ciphertexts are pairs of matrices \((\mathbf A,\mathbf C')\) over https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq95_HTML.gif for a suitable prime q. We can see those ciphertexts as a tuple https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq96_HTML.gif for some n. The proof of Lemma 6.2 in [13, full version] shows that the matrix encryption scheme produces ciphertexts that are indistinguishable from uniformly random https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq97_HTML.gif .
The lattice-based lossy trapdoor function from [13] uses a ciphertext of that lossy encryption scheme as its key. Thus a key is indistinguishable from https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq98_HTML.gif . Hence we can choose \(S_F\) to simply return a uniformly random https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq100_HTML.gif .
To get an \(S_F\) that returns https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq102_HTML.gif instead, we let \(S_F\) choose \(s\in \{0,\dots ,2^\ell -1\}^n\) and set \(s_i':=s_i\bmod q\). For sufficiently large \(\ell \), this changes the distribution of \(s'\) only by a negligible amount. Then s can be encoded as an \(\ell _s\)-bitstring with \(\ell _s:=n\ell \). (Since this way of sampling \(s_i'\) is “oblivious”, i.e., given \(s_i'\) we can efficiently find randomness \(s_i\) that leads to that \(s_i'\), the security of the lossy function is not affected by outputting \(s_i\) as the key instead of \(s_i'\).).
 
7
We could simply analyze all schemes for adversaries that attack a single commitment at a time, and then invoke the parallel composition theorem from [16] to get the advantage when attacking t commitments. That theorem will then introduce a factor t in the advantage. ([16] states the theorem without concrete security bounds, but they are easily extracted from the proof.) In contrast, a direct analysis for t commitments may give better bounds, since the advantages we get in this paper do not depend on t.
 
8
In general, this can be computationally hard. However, should \(h_r\) be a universal hash function where this is hard, one can replace \(h_r\) by \(h'_{(r,t)}\) defined as \(h'_{(r,t)}(x):=t\oplus h_r(x)\). This function is still a universal hash function, and sampling r, t, u is easy.
 
9
Commonly, stronger conditions are placed on https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq260_HTML.gif , see, e.g., [8, Def. 8.7]. However, “suffix-code” and “injective” turns out to be sufficient. For example, the padding using in SHA-256 [12] is a Merkle-Damgård padding for https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_6/435239_1_En_6_IEq261_HTML.gif according to our definition.
 
10
We refer to [16] for the definition of “collapse-binding” for interactive commitments.
 
11
Namely, \(\Pr [u\text { invalid}]=1-p_0\), \(\Pr [u'\text { invalid}]=1-p_1\). Hence \(\Pr [u\text { invalid or} u'\text { invalid}]\le (1-p_0)+(1-p_1)\). Thus \(\Pr [u,u'\text { valid}]\ge 1-\bigl ((1-p_0)+(1-p_1)\bigr )=p_0+p_1-1\).
 
12
Collapse-binding commitments are rewinding-friendly, but this refers only to the case where we wish to measure the opened message m. Roughly, collapse-binding implies that measuring m does disturb the state more than measuring whether the commitment was opened correctly or not, and in that case, the rewinding technique from [14] applies. The [16] for example proofs using this technique.
 
Literatur
1.
Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems (the hardness of quantum rewinding). In: FOCS 2014, pp. 474–483. IEEE (2014). Preprint on IACR ePrint 2014/296
2.
Brassard, G., Crépeau, C., Jozsa, R., Langlois, D.: A quantum bit commitment scheme provably unbreakable by both parties. In: FOCS 1993, pp. 362–371. IEEE, Los Alamitos (1993)
3.
Crépeau, C., Dumais, P., Mayers, D., Salvail, L.: Computational collapse of quantum state with application to oblivious transfer. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 374–393. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24638-1_​21 CrossRef
4.
5.
Damgård, I., Fehr, S., Salvail, L.: Zero-knowledge proofs and string commitments withstanding quantum attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 254–272. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-28628-8_​16 CrossRef
6.
Damgård, I., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. J. Cryptology 10(3), 163–194 (1997)MathSciNetCrossRefMATH
7.
Dumais, P., Mayers, D., Salvail, L.: Perfectly concealing quantum bit commitment from any quantum one-way permutation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 300–315. Springer, Heidelberg (2000). doi:10.​1007/​3-540-45539-6_​21 CrossRef
8.
9.
Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68697-5_​16
10.
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRefMATH
11.
12.
13.
14.
15.
16.
17.
18.
Yan, J., Weng, J., Lin, D., Quan, Y.: Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract). In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 555–565. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48971-0_​47 CrossRef
19.
Mark Zhandry. How to construct quantum random functions. In: FOCS 2013, pages 679–687. IEEE Computer Society, Los Alamitos (2012). IACR ePrint2012/​182
Metadaten
Titel
Collapse-Binding Quantum Commitments Without Random Oracles
verfasst von
Dominique Unruh
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_6

Premium Partner

    Bildnachweise