{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T03:14:11Z","timestamp":1770434051924,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540259107","type":"print"},{"value":"9783540320555","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11426639_16","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T15:02:36Z","timestamp":1279119756000},"page":"268-284","source":"Crossref","is-referenced-by-count":23,"title":["Computational Indistinguishability Between Quantum States and Its Cryptographic Application"],"prefix":"10.1007","author":[{"given":"Akinori","family":"Kawachi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Koshiba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"Yamakami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/3-540-45841-7_26","volume-title":"STACS 2002","author":"M. Adcock","year":"2002","unstructured":"Adcock, M., Cleve, R.: A quantum Goldreich-Levin theorem with cryptographic applications. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 323\u2013334. Springer, Heidelberg (2002)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: Proc. 35th ACM Symp. Theory of Computing, pp. 20\u201329 (2003)","DOI":"10.1145\/780542.780546"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. In: Proc. 28th ACM Symp. Theory of Computing, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proc. 29th ACM Symp. Theory of Computing, pp. 284\u2013293 (1997)","DOI":"10.1145\/258533.258604"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. In: Proc. 43rd IEEE Symp. Foundations of Computer Science, pp. 743\u2013750 (2002)","DOI":"10.1109\/SFCS.2002.1181999"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/BFb0055718","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 26\u201345. Springer, Heidelberg (1998)"},{"key":"16_CR7","unstructured":"Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proc. IEEE International Conf. Computers, Systems, and Signal Processing, pp. 175\u2013179 (1984)"},{"issue":"4","key":"16_CR8","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput.\u00a013(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: Proc. 44th IEEE Symp. Foundations of Computer Science, pp. 308\u2013317 (2004)","DOI":"10.1109\/SFCS.2003.1238205"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/3-540-44750-4_34","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"D. Boneh","year":"1995","unstructured":"Boneh, D., Lipton, R.J.: Quantum cryptanalysis of hidden linear functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 424\u2013437. Springer, Heidelberg (1995)"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/978-3-540-28629-5_51","volume-title":"Mathematical Foundations of Computer Science 2004","author":"M. Cr\u00e2smaru","year":"2004","unstructured":"Cr\u00e2smaru, M., Gla\u00dfer, C., Regan, K.W., Sengupta, S.: A protocol for serializing unique strategies. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 660\u2013672. Springer, Heidelberg (2004)"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-540-24638-1_21","volume-title":"Theory of Cryptography","author":"C. Cr\u00e9peau","year":"2004","unstructured":"Cr\u00e9peau, 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.\u00a02951, pp. 374\u2013393. Springer, Heidelberg (2004)"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-44987-6_5","volume-title":"Advances in Cryptology - EUROCRYPT 2001","author":"C. Cr\u00e9peau","year":"2001","unstructured":"Cr\u00e9peau, C., L\u00e9gar\u00e9, F., Salvail, L.: How to convert the flavor of a quantum bit commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol.\u00a02045, pp. 60\u201377. Springer, Heidelberg (2001)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/978-3-540-28628-8_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"I. Damg\u00e5rd","year":"2004","unstructured":"Damg\u00e5rd, I., Fehr, S., Salvail, L.: Zero-knowledge proofs and string commitments withstanding quantum attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 254\u2013272. Springer, Heidelberg (2004)"},{"issue":"6","key":"16_CR15","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Information Theory\u00a022(6), 644\u2013654 (1976)","journal-title":"IEEE Trans. Information Theory"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/3-540-45539-6_21","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"P. Dumais","year":"2000","unstructured":"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.\u00a01807, pp. 300\u2013315. Springer, Heidelberg (2000)"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/aama.2000.0699","volume":"25","author":"M. Ettinger","year":"2000","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics\u00a025, 239\u2013251 (2000)","journal-title":"Advances in Applied Mathematics"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. System Sci.\u00a028(2), 270\u2013299 (1984)","journal-title":"J. Comput. System Sci."},{"key":"16_CR19","series-title":"Randomness and Computation","first-page":"73","volume-title":"Advances in Computing Research","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof system. In: Advances in Computing Research. Randomness and Computation, vol.\u00a05, pp. 73\u201390. JAI Press, Greenwich (1989)"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Grigni, M., Schulman, L.J., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In: Proc. 33rd ACM Symp. Theory of Computing, pp. 68\u201374 (2001)","DOI":"10.1145\/380752.380769"},{"issue":"2","key":"16_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.L.: Complexity measures for public-key cryptosystems. SIAM J. Comput.\u00a017(2), 309\u2013335 (1988)","journal-title":"SIAM J. Comput."},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Hallgren, S.: Polynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem. In: Proc. 34th ACM Symp. Theory of Computing, pp. 653\u2013658 (2002)","DOI":"10.1145\/509907.510001"},{"issue":"4","key":"16_CR23","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1137\/S009753970139450X","volume":"32","author":"S. Hallgren","year":"2003","unstructured":"Hallgren, S., Russell, A., Ta-Shma, A.: The hidden subgroup problem and quantum computation using group representations. SIAM J. Comput.\u00a032(4), 916\u2013934 (2003)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"16_CR24","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology\u00a09(4), 199\u2013216 (1996)","journal-title":"J. Cryptology"},{"key":"16_CR25","unstructured":"Kempe, J., Shalev, A.: The hidden subgroup problem and permutation group theory. In: Proc. 16th ACM-SIAM Symp. Discrete Algorithms (2005)"},{"key":"16_CR26","unstructured":"Kitaev, A.: Quantum measurements and the Abelian stabilizer problem. quant-ph\/9511026 (1995)"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-540-24587-2_20","volume-title":"Algorithms and Computation","author":"H. Kobayashi","year":"2003","unstructured":"Kobayashi, H.: Non-interactive quantum perfect and statistical zero-knowledge. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 178\u2013188. Springer, Heidelberg (2003)"},{"key":"16_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user Boston Inc., Basel (1993)"},{"key":"16_CR29","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. quant-ph\/0302112 (2003)"},{"issue":"17","key":"16_CR30","doi-asserted-by":"publisher","first-page":"3410","DOI":"10.1103\/PhysRevLett.78.3410","volume":"78","author":"H.-K. Lo","year":"1997","unstructured":"Lo, H.-K., Chau, H.F.: Is quantum bit commitment really possible? Physical Review Letters\u00a078(17), 3410\u20133413 (1997)","journal-title":"Physical Review Letters"},{"key":"16_CR31","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/dimacs\/011\/11","volume":"11","author":"E.M. Luks","year":"1993","unstructured":"Luks, E.M.: Permutation groups and polynomial-time computation. Groups and Computation\u00a011, 139\u2013175 (1993)","journal-title":"Groups and Computation"},{"issue":"17","key":"16_CR32","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1103\/PhysRevLett.78.3414","volume":"78","author":"D. Mayers","year":"1997","unstructured":"Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Physical Review Letters\u00a078(17), 3414\u20133417 (1997)","journal-title":"Physical Review Letters"},{"issue":"3","key":"16_CR33","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/382780.382781","volume":"48","author":"D. Mayers","year":"2001","unstructured":"Mayers, D.: Unconditional security in quantum cryptography. J. ACM\u00a048(3), 351\u2013406 (2001)","journal-title":"J. ACM"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measure. In: Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 372\u2013381 (2004)","DOI":"10.1109\/FOCS.2004.72"},{"key":"16_CR35","unstructured":"Moore, C., Rockmore, D., Russell, A., Schulman, L.J.: The hidden subgroup problem in affine groups: basis selection in Fourier sampling. In: Proc. 15th ACM-SIAM Symp. Discrete Algorithms, pp. 1106\u20131115 (2004)"},{"key":"16_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/3-540-44598-6_9","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"T. Okamoto","year":"2000","unstructured":"Okamoto, T., Tanaka, K., Uchiyama, S.: Quantum public-key cryptosystems. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol.\u00a01880, pp. 147\u2013165. Springer, Heidelberg (2000)"},{"key":"16_CR37","doi-asserted-by":"crossref","unstructured":"Regev, O.: Quantum computation and lattice problems. In: Proc. 43rd IEEE Symp. Foundations of Computer Science, pp. 520\u2013529 (2002)","DOI":"10.1109\/SFCS.2002.1181976"},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"Regev, O.: New lattice-based cryptographic constructions. In: Proc. 35th ACM Symp. Theory of Computing, pp. 407\u2013416 (2003)","DOI":"10.1145\/780542.780603"},{"key":"16_CR39","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J. Comput. System Sci.\u00a037, 312\u2013323 (1988)","journal-title":"J. Comput. System Sci."},{"key":"16_CR40","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.\u00a026, 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"16_CR41","doi-asserted-by":"crossref","unstructured":"Tompa, M., Woll, H.: Random self-reducibility and zero knowledge interactive proofs of possession of information. In: Proc. 28th IEEE Symp. Foundations of Computer Science, pp. 472\u2013482 (1987)","DOI":"10.1109\/SFCS.1987.49"},{"key":"16_CR42","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Limits on the power of quantum statistical zero-knowledge. In: Proc. 43rd IEEE Symp. Foundations of Computer Science, pp. 459\u2013468 (2002)","DOI":"10.1109\/SFCS.2002.1181970"},{"key":"16_CR43","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions. In: Proc. 23rd IEEE Symp. Foundations of Computer Science, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11426639_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T22:22:31Z","timestamp":1740262951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11426639_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540259107","9783540320555"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/11426639_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}