nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Quantum Commitments and Signatures Without One-Way Functions

verfasst von : Tomoyuki Morimae, Takashi Yamakawa

Erschienen in: Advances in Cryptology – CRYPTO 2022

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In the classical world, the existence of commitments is equivalent to the existence of one-way functions. In the quantum setting, on the other hand, commitments are not known to imply one-way functions, but all known constructions of quantum commitments use at least one-way functions. Are one-way functions really necessary for commitments in the quantum world? In this work, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but their polynomially many copies are computationally indistinguishable from the same number of copies of Haar random states [Ji, Liu, and Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if \(\textbf{BQP}=\textbf{QMA}\) (relative to a quantum oracle) [Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. In this work, we also consider digital signatures, which are other fundamental primitives in cryptography. We show that one-time secure digital signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of digital signatures is equivalent to the existence of one-way functions. Our result, on the other hand, shows that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.

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 Certified Everlasting Zero-Knowledge Proof for QMA

Nächstes Kapitel Semi-quantum Tokenized Signatures

Nur mit Berechtigung zugänglich

If a commitment scheme is statistically binding, there exists at most one message to which a commitment can be opened except for a negligible probability. This unique message can be found by a brute-force search, which means that the scheme is not statistically hiding.

[IR90] showed the impossibility of relativizing constructions of key exchange from one-way functions, and oblivious transfer is stronger than key exchange. Since most cryptographic constructions are relativizing, this gives a strong negative result on constructing oblivious transfer from one-way functions in the classical setting.

Our construction of commitments also satisfies perfect correctness, i.e., the probability that the honest receiver opens the correct bit committed by the honest sender is 1.

It actually shows stronger things, because \(\textbf{BQP}=\textbf{QMA}\) also excludes the existence of some quantum-secure quantum cryptographic primitives where honest algorithms are quantum.

Indeed, [BCKM21] states as follows: “Moreover if in the future, new constructions of statistically binding, quantum computationally hiding commitments involving quantum communication are discovered based on assumptions weaker than quantum-hard one-way functions, it would be possible to plug those into our protocol compilers to obtain QOT.”.

Again, it also excludes some quantum-secure quantum cryptographic primitives.

It is not necessarily a PRSG. Any OWSG (Definition 4.1) is enough. For details, see Sect. 4.

Let us consider an adversary \(\mathcal {A}\) that runs the SWAP test on two copies of the received state and outputs the result of the SWAP test. When \(\rho _k^{\otimes t}\) is sent with uniformly random k, the probability that \(\mathcal {A}\) outputs 1 is \((1+\frac{1}{2^n}\sum _k\text{ Tr }(\rho _k^2))/2\). When the t copies of Haar random states \(|\psi \rangle ^{\otimes t}\) is sent, the probability that \(\mathcal {A}\) outputs 1 is 1. For the security, \(|(1+\frac{1}{2^n}\sum _k\text{ Tr }(\rho _k^2))/2-1|\le {\textsf{negl}}(\lambda )\) has to be satisfied, which means the expected purity of \(\rho _k\), \(\frac{1}{2^n}\sum _k\text{ Tr }(\rho _k^2)\), has to be negligibly close to 1.

Another example of constructions is \(|\psi _0\rangle =\sum _{k\in \{0,1\}^n}|k\rangle |\phi _k\rangle \) and \(|\psi _1\rangle =\sum _{r\in \{0,1\}^m}|r\rangle |r\rangle \). We have chosen the one we have explained, because the analogy to Naor’s commitment scheme is clearer.

We remark that it is also noted in [AQY21, Remark 6.2] that they are “probably equivalent”.

[AQY21]

Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. IACR Cryptol. ePrint Arch. 2021, 1663 (2021)

[BB84]

Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: IEEE International Conference on Computers Systems and Signal Processing, pp. 175–179. IEEE (1984)

[BB21]

Bitansky, N., Brakerski, Z.: Classical binding for quantum commitments. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 273–298. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_10CrossRef

[BBCS92]

Bennett, C.H., Brassard, G., Crépeau, C., Skubiszewska, M.-H.: Practical quantum oblivious transfer. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 351–366. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_29CrossRef

[BCKM21]

Bartusek, J., Coladangelo, A., Khurana, D., Ma, F.: One-way functions imply secure computation in a quantum world. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 467–496. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_17CrossRefMATH

[Blu81]

Blum, M.: Coin flipping by telephone. In: CRYPTO 1981, volume ECE Report 82–04, pp. 11–15 (1981)

[BS19]

Brakerski, Z., Shmueli, O.: (Pseudo) random quantum states with binary phase. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part I. LNCS, vol. 11891, pp. 229–250. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36030-6_10CrossRef

[BS20]

Brakerski, Z., Shmueli, O.: Scalable pseudorandom quantum states. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 417–440. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_15CrossRef

[CK88]

Crépeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions (extended abstract). In: 29th FOCS, pp. 42–52 (1988)

[CLS01]

Crépeau, C., Légaré, F., Salvail, L.: How to convert the flavor of a quantum bit commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 60–77. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_5CrossRef

[DFL+09]

Damgård, I., Fehr, S., Lunemann, C., Salvail, L., Schaffner, C.: Improving the security of quantum protocols via commit-and-open. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 408–427. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_24CrossRef

[DH76]

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)MathSciNetCrossRef

[DMS00]

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). https://doi.org/10.1007/3-540-45539-6_21CrossRef

[Dol21]

Doliskani, J.: Efficient quantum public-key encryption from learning with errors. arXiv:2105.12790 (2021)

[FUYZ20]

Fang, J., Unruh, D., Yan, J., Zhou, D.: How to base security on the perfect/statistical binding property of quantum bit commitment? Cryptology ePrint Archive: Report 2020/621 (2020)

[GC01]

Gottesman, D., Chuang, I.L.: Quantum digital signatures. arXiv:quant-ph/0105032 (2001)

[GLSV21]

Grilo, A.B., Lin, H., Song, F., Vaikuntanathan, V.: Oblivious transfer is in MiniQCrypt. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 531–561. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_18CrossRefMATH

[HILL99]

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)MathSciNetCrossRef

[IL89]

Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: 30th FOCS, pp. 230–235 (1989)

[ILL89]

Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: 21st ACM STOC, pp. 12–24 (1989)

[IR90]

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_2CrossRef

[JLS18]

Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom quantum states. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 126–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_5CrossRef

[KKNY12]

Kawachi, A., Koshiba, T., Nishimura, H., Yamakami, T.: Computational indistinguishability between quantum states and its cryptographic application. J. Cryptol. 25(3), 528–555 (2011). https://doi.org/10.1007/s00145-011-9103-4MathSciNetCrossRefMATH

[KO09]

Koshiba, T., Odaira, T.: Statistically-hiding quantum bit commitment from approximable-preimage-size quantum one-way function. In: Childs, A., Mosca, M. (eds.) TQC 2009. LNCS, vol. 5906, pp. 33–46. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10698-9_4CrossRefMATH

[KO11]

Koshiba, T., Odaira, T.: Non-interactive statistically-hiding quantum bit commitment from any quantum one-way function. arXiv:1102.3441 (2011)

[Kre21]

Kretschmer, W.: Quantum pseudorandomness and classical complexity. In: TQC 2021 (2021)

[LC97]

Lo, H.-K., Chau, H.F.: Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410–3413 (1997)CrossRef

[LR86]

Luby, M., Rackoff, C.: Pseudo-random permutation generators and cryptographic composition. In: 18th ACM STOC, pp. 356–363 (1986)

[May97]

Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 3414–3417 (1997)CrossRef

[Mer90]

Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_21CrossRef

[MP12]

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41CrossRef

[MS94]

Mayers, D., Salvail, L.: Quantum oblivious transfer is secure against all individual measurements. In: Proceedings Workshop on Physics and Computation, PhysComp 1994, pp. 69–77. IEEE (1994)

[Nao91]

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991). https://doi.org/10.1007/BF00196774CrossRefMATH

[NS03]

Nayak, A., Shor, P.: Bit-commitment-based quantum coin flipping. Phys. Rev. A 67, 012304 (2003)CrossRef

[Unr16]

Unruh, D.: Collapse-binding quantum commitments without random oracles. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 166–195. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_6CrossRef

[Yan20]

Yan, J.: General properties of quantum bit commitments. Cryptology ePrint Archive: Report 2020/1488 (2020)

[Yao95]

Yao, A.C.-C.: Security of quantum protocols against coherent measurements. In: 27th ACM STOC, pp. 67–75 (1995)

[YWLQ15]

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). https://doi.org/10.1007/978-3-662-48971-0_47CrossRef

Titel: Quantum Commitments and Signatures Without One-Way Functions
verfasst von: Tomoyuki Morimae
Takashi Yamakawa
Verlag: Springer Nature Switzerland
Buch: Advances in Cryptology – CRYPTO 2022
Print ISBN: 978-3-031-15801-8

Electronic ISBN: 978-3-031-15802-5

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-15802-5_10

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"

Premium Partner