Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Black-Box Separations for Non-interactive Classical Commitments in a Quantum World

  • Conference paper
  • First Online:

Abstract

Commitments are fundamental in cryptography. In the classical world, commitments are equivalent to the existence of one-way functions. It is also known that the most desired form of commitments in terms of their round complexity, i.e.,non-interactive commitments,cannot be built from one-way functions in a black-box way [Mahmoody-Pass, Crypto’12]. However, if one allows the parties to use quantum computationand communication, it is known that non-interactive commitments (to classical bits) are in fact possible [Koshiba-Odaira, Arxiv’11 and Bitansky-Brakerski, TCC’21].

We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation andclassical communication based on a black-box use of one-way functions. We prove that doing so is impossible unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto’22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC’21], as they only required a classical decommitment message. Because non-interactive commitments can be based on injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science’21] in which they only allowed thesecurity reduction to be quantum.

At a technical level, we prove that sampling oracles at random from “sufficiently large” sets (of oracles) will make them one-way against polynomial quantum-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al. [Asiacrypt’19] and Chung et al. [FOCS’20].

K.-M. Chung—Supported in part by the NSTC QC project, under Grant no. NSTC 111-2119-M-001-004- and the Air Force Office of Scientific Research under award number FA2386-20-1-4066.

Y.-T. Lin—Part of the work was done when working at Academia Sinica.

M. Mahmoody—Supported by NSF grants CCF-1910681 and CNS1936799.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    The PCC bears some similarities to a conjecture by Aaronson and Ambianis [AA09] that also deals with polynomials with a low degree and low influence and which is also proved for exponentially small influences. See [ACC+22] for more discussions and comparisons.

  2. 2.

    E.g., one can re-interpret the proofs of [IR89,BM09] to fall into this framework.

  3. 3.

    In the context of quantum information theory, purifying a quantum process means delaying all intermediate measurements to the end at the cost of introducing additional qubits. So that the whole computation remains a pure state until the final measurement.

  4. 4.

    Since\(\textsf{A}\) takesb as input, each\(V_i\) is defined to be a controlled-unitary with the control bitb.

  5. 5.

    As shown in [ACC+22], regardless of the image being\({\mathbb R}\) or\(\mathbb {C}\), the conjectures are equivalent up to a constant factor in\(\delta \). For convenience, we use the version with\(\mathbb {C}\).

  6. 6.

    Actually, the security loss here is at most\(\delta ^k\) instead of\(\delta \). We follow this convention for ease of the presentation.

  7. 7.

    Recall that by our convention, the security loss is at most\(\delta (k,T)^k\).

  8. 8.

    One can think of\((\textsf{com},\textsf{dec}_0,\textsf{dec}_1)\) as a cheating sender\(\textsf{Sen}^*\).

References

  1. Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. arXiv preprintarXiv:0911.0996 (2009)

  2. Austrin, P., Chung, H., Chung, K.M., Fu, S., Lin, Y.T., Mahmoody, M.: On the impossibility of key agreements from quantum random oracles. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 165–194. Springer, Cham (2022).https://doi.org/10.1007/978-3-031-15979-4_6

    Chapter  Google Scholar 

  3. Alagic, G., Childs, A.M., Grilo, A.B., Hung, S.-H.: Non-interactive classical verification of quantum computation. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 153–180. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-64381-2_6

    Chapter MATH  Google Scholar 

  4. Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13507, pp. 208–236. Springer, Cham (2022).https://doi.org/10.1007/978-3-031-15802-5_8

    Chapter  Google Scholar 

  5. Bartusek, J.: Secure quantum computation with classical communication. Cryptology ePrint Archive, Report 2021/964 (2021).https://ia.cr/2021/964

  6. 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_10

    Chapter  Google Scholar 

  7. Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput.26(5), 1510–1523 (1997)

    Article MathSciNet MATH  Google Scholar 

  8. Baecher, P., Brzuska, C., Fischlin, M.: Notions of black-box reductions, revisited. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 296–315. Springer, Heidelberg (2013).https://doi.org/10.1007/978-3-642-42033-7_16

    Chapter  Google Scholar 

  9. 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_17

    Chapter MATH  Google Scholar 

  10. Brakerski, Z., Canetti, R., Qian, L.: On the computational hardness needed for quantum cryptography. Cryptology ePrint Archive, Paper 2022/1181 (2022).https://eprint.iacr.org/2022/1181

  11. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-25385-0_3

    Chapter MATH  Google Scholar 

  12. Brakerski, Z., Koppula, V., Vazirani, U., Vidick, T.: Simpler proofs of quantumness. arXiv preprintarXiv:2005.04826 (2020)

  13. Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal — An\(O(n^2)\)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374–390. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-03356-8_22

    Chapter  Google Scholar 

  14. Barak, B., Ong, S.J., Vadhan, S.: Derandomization in cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 299–315. Springer, Heidelberg (2003).https://doi.org/10.1007/978-3-540-45146-4_18

    Chapter MATH  Google Scholar 

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

    Chapter  Google Scholar 

  16. Chia, N.-H., Chung, K.-M., Yamakawa, T.: Classical verification of quantum computations with efficient verifier. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 181–206. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-64381-2_7

    Chapter MATH  Google Scholar 

  17. 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).https://doi.org/10.1007/978-3-540-24638-1_21

    Chapter MATH  Google Scholar 

  18. Chung, K.M., Guo, S., Liu, Q., Qian, L.: Tight quantum time-space tradeoffs for function inversion. In: 61st Annual Symposium on Foundations of Computer Science, Durham, NC, USA, 16–19 November 2020, pp. 673–684. IEEE Computer Society Press (2020)

    Google Scholar 

  19. 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_5

    Chapter  Google Scholar 

  20. Cao, S., Xue, R.: Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives. Theor. Comput. Sci.855, 16–42 (2021)

    Article MathSciNet MATH  Google Scholar 

  21. Dupuis, F., Lamontagne, P., Salvail, L.: Fiat-shamir for proofs lacks a proof even in the presence of shared entanglement. Cryptology ePrint Archive, Report 2022/435 (2022).https://eprint.iacr.org/2022/435

  22. 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_21

    Chapter  Google Scholar 

  23. Donoho, D.L., Stark, P.B.: Uncertainty principles and signal recovery. SIAM J. Appl. Math.49(3), 906–931 (1989)

    Article MathSciNet MATH  Google Scholar 

  24. Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 15–17 May 1989, pp. 25–32. ACM Press (1989)

    Google Scholar 

  25. 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_18

    Chapter MATH  Google Scholar 

  26. Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, 12–14 November 2000, pp. 305–313. IEEE Computer Society Press (2000)

    Google Scholar 

  27. 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)

    Article MathSciNet MATH  Google Scholar 

  28. Hhan, M., Xagawa, K., Yamakawa, T.: Quantum random oracle model with auxiliary input. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 584–614. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-34578-5_21

    Chapter  Google Scholar 

  29. Hosoyamada, A., Yamakawa, T.: Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 3–32. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-64837-4_1

    Chapter MATH  Google Scholar 

  30. Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA, 30 October–1 November 1989, pp. 230–235. IEEE Computer Society Press (1989)

    Google Scholar 

  31. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 15–17 May 1989, pp. 44–61. ACM Press (1989)

    Google Scholar 

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

    Chapter  Google Scholar 

  33. 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_4

    Chapter MATH  Google Scholar 

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

  35. Kretschmer, W.: Quantum pseudorandomness and classical complexity. arXiv preprintarXiv:2103.09320 (2021)

  36. Hoi-Kwong Lo and Hoi Fung Chau: Is quantum bit commitment really possible? Phys. Rev. Lett.78(17), 3410 (1997)

    Article  Google Scholar 

  37. Lin, D., Quan, Y., Weng, J., Yan, J.: Quantum bit commitment with application in quantum zero-knowledge proof. Cryptology ePrint Archive, Report 2014/791 (2014).https://eprint.iacr.org/2014/791

  38. Lombardi, A., Schaeffer, L.: A note on key agreement and non-interactive commitments. Cryptology ePrint Archive, Report 2019/279 (2019).https://eprint.iacr.org/2019/279

  39. Mahadev, U.: Classical verification of quantum computations. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259–267. IEEE (2018)

    Google Scholar 

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

    Article  Google Scholar 

  41. Matsuda, T., Matsuura, K.: On black-box separations among injective one-way functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 597–614. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-19571-6_36

    Chapter  Google Scholar 

  42. Mahmoody, M., Pass, R.: The curious case of non-interactive commitments – on the power of black-box vs. non-black-box use of primitives. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 701–718. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-32009-5_41

    Chapter  Google Scholar 

  43. Morimae, T., Yamakawa, T.: Quantum commitments without one-way functions. In: International Cryptology Conference CRYPTO (2022)

    Google Scholar 

  44. Nayebi, A., Aaronson, S., Belovs, A., Trevisan, L.: Quantum lower bound for inverting a permutation with advice. Quant. Inf. Comput.15(11–12), 901–913 (2015)

    MathSciNet  Google Scholar 

  45. Naor, M.: Bit commitment using pseudo-randomness. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128–136. Springer, New York (1990).https://doi.org/10.1007/0-387-34805-0_13

    Chapter  Google Scholar 

  46. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)

    MATH  Google Scholar 

  47. Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci.49(2), 149–167 (1994)

    Article MathSciNet MATH  Google Scholar 

  48. Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004).https://doi.org/10.1007/978-3-540-24638-1_1

    Chapter MATH  Google Scholar 

  49. Unruh, D.: Quantum proofs of knowledge. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 135–152. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-29011-4_10

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  51. Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 497–527. Springer, Heidelberg (2016).https://doi.org/10.1007/978-3-662-49896-5_18

    Chapter  Google Scholar 

  52. Wigderson, A., Wigderson, Y.: The uncertainty principle: variations on a theme. Bull. Am. Math. Soc.58(2), 225–261 (2021)

    Article MathSciNet MATH  Google Scholar 

  53. Yan, J.: General properties of quantum bit commitments. Cryptology ePrint Archive, Paper 2020/1488 (2020).https://eprint.iacr.org/2020/1488

  54. Yao, A.C.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pages 80–91, Chicago, Illinois, 3–5 November 1982. IEEE Computer Society Press (1982)

    Google Scholar 

  55. 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_47

    Chapter  Google Scholar 

  56. Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 239–268. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-26951-7_9

    Chapter  Google Scholar 

  57. Zhang, J.: Succinct blind quantum computation using a random oracle. In STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 21–25 June 2021, pp. 1370–1383 (2021)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Academia Sinica, New Taipei, Taiwan

    Kai-Min Chung

  2. UCSB, Santa Barbara, USA

    Yao-Ting Lin

  3. University of Virginia, Charlottesville, USA

    Mohammad Mahmoody

Authors
  1. Kai-Min Chung

    You can also search for this author inPubMed Google Scholar

  2. Yao-Ting Lin

    You can also search for this author inPubMed Google Scholar

  3. Mohammad Mahmoody

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYao-Ting Lin.

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chung, KM., Lin, YT., Mahmoody, M. (2023). Black-Box Separations for Non-interactive Classical Commitments in a Quantum World. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14004. Springer, Cham. https://doi.org/10.1007/978-3-031-30545-0_6

Download citation

Publish with us

Societies and partnerships

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp