{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T02:42:29Z","timestamp":1792809749679,"version":"4.5.0"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n\/2$ in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient and noninteractive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.<\/jats:p>","DOI":"10.1137\/060651343","type":"journal-article","created":{"date-parts":[[2008,3,26]],"date-time":"2008-03-26T18:07:13Z","timestamp":1206554833000},"page":"1865-1890","source":"Crossref","is-referenced-by-count":98,"title":["Cryptography in the Bounded-Quantum-Storage Model"],"prefix":"10.1137","volume":"37","author":[{"given":"Ivan B.","family":"Damg\u00c5rd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Serge","family":"Fehr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louis","family":"Salvail","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Schaffner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,3,26]]},"reference":[{"key":"R1","unstructured":"M. A. Ballester, S. Wehner, and A. Winter,\n                      State Discrimination with Post-Measurement Information\n                      , http:\/\/arxiv.org\/abs\/quant-ph\/0608014 (2006)."},{"key":"R2","unstructured":"C. H. Bennett and G. Brassard,\n                      Quantum cryptography: Public key distribution and coin tossing\n                      , in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, 1984, pp. 175\u2013179."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/18.476316"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0217014"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Bhatia,\n                      Matrix Analysis\n                      , Grad. Texts in Math. 169, Springer, Berlin, 1997.","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01608825"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.1330"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. Brassard, N. L\u00fctkenhaus, T. Mor, and B. C. Sanders,\n                      Security aspects of practical quantum cryptography\n                      , in Advances in Cryptology\u2014EUROCRYPT '00, Lecture Notes in Comput. Sci. 1807, Springer, Berlin, 2000, pp. 289\u2013299.","DOI":"10.1007\/3-540-45539-6_20"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"G. Brassard and L. Salvail,\n                      Secret-key reconciliation by public discussion\n                      , in Advances in Cryptology\u2014EUROCRYPT '93, Lecture Notes in Comput. Sci. 765, Springer, Berlin, 1993, pp. 410\u2013423.","DOI":"10.1007\/3-540-48285-7_35"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"C. Cachin, C. Cr\u00e9peau, and J. Marcil,\n                      Oblivious transfer with a memory-bounded receiver\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1998, pp. 493\u2013502.","DOI":"10.1109\/SFCS.1998.743500"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. L. Carter and M. N. Wegman,\n                      Universal classes of hash functions\n                      , in Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), 1977, pp. 106\u2013112.","DOI":"10.1145\/800105.803400"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"C. Cr\u00e9peau,\n                      Efficient cryptographic protocols based on noisy channels\n                      , in Advances in Cryptology\u2014EUROCRYPT '97, Lecture Notes in Comput. Sci. 1233, Springer, Berlin, 1997, pp. 306\u2013317.","DOI":"10.1007\/3-540-69053-0_21"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"C. Cr\u00e9peau and J. Kilian,\n                      Achieving oblivious transfer using weakened security assumptions\n                      , in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1988, pp. 42\u201353.","DOI":"10.1109\/SFCS.1988.21920"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, J. Kilian, and L. Salvail,\n                      On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions\n                      , in Advances in Cryptology\u2014EUROCRYPT '99, Lecture Notes in Comput. Sci. 1592, Springer, Berlin, 1999, pp. 56\u201373.","DOI":"10.1007\/3-540-48910-X_5"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"I. B. Damg\u00e5rd, S. Fehr, K. Morozov, and L. Salvail,\n                      Unfair noisy channels and oblivious transfer\n                      , in Theory of Cryptography Conference (TCC), Lecture Notes in Comput. Sci. 2951, Springer, Berlin, 2004, pp. 355\u2013373.","DOI":"10.1007\/978-3-540-24638-1_20"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"I. B. Damg\u00e5rd, S. Fehr, R. Renner, L. Salvail, and C. Schaffner,\n                      A tight high-order entropic quantum uncertainty relation with applications\n                      , in Advances in Cryptology\u2014CRYPTO '07, Lecture Notes in Comput. Sci. 4622, Springer, Berlin, 2007, pp. 360\u2013378.","DOI":"10.1007\/978-3-540-74143-5_20"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"I. B. Damg\u00e5rd, S. Fehr, L. Salvail, and C. Schaffner,\n                      Cryptography in the bounded quantum-storage model\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 449\u2013458.","DOI":"10.1109\/SFCS.2005.30"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.50.631"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Y. Z. Ding, D. Harnik, A. Rosen, and R. Shaltiel,\n                      Constant-round oblivious transfer in the bounded storage model\n                      , in Theory of Cryptography Conference (TCC), Lecture Notes in Comput. Sci. 2951, Springer, Berlin, 2004, pp. 446\u2013472.","DOI":"10.1007\/978-3-540-24638-1_25"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Y. Dodis, L. Reyzin, and A. Smith,\n                      Fuzzy extractors: How to generate strong keys from biometrics and other noisy data\n                      , in Advances in Cryptology\u2014EUROCRYPT '04, Lecture Notes in Comput. Sci. 3027, Springer, Berlin, 2004, pp. 523\u2013540.","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"P. Dumais, D. Mayers, and L. Salvail,\n                      Perfectly concealing quantum bit commitment from any quantum one-way permutation\n                      , in Advances in Cryptology\u2014EUROCRYPT '00, Lecture Notes in Comput. Sci. 1807, Springer, Berlin, 2000, pp. 300\u2013315.","DOI":"10.1007\/3-540-45539-6_21"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"S. Dziembowski and U. M. Maurer,\n                      On generating the initial key in the bounded-storage model\n                      , in Advances in Cryptology\u2014EUROCRYPT '04, Lecture Notes in Comput. Sci. 3027, Springer, Berlin, 2004, pp. 126\u2013137.","DOI":"10.1007\/978-3-540-24676-3_8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.67.661"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/18.761271"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Hilgevood and J. B. M. Uffink,\n                      The mathematical expression of the uncertainty principle\n                      , in Microphysical Reality and Quantum Description, Kluwer Academic Publishers, Norwell, MA, 1988, pp. 91\u2013114.","DOI":"10.1007\/978-94-009-2925-8_8"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.51.1863"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. A. Levin, and M. Luby,\n                      Pseudorandom generation from one-way functions\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp. 12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1996.2957"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.35.3070"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/23\/7\/013"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3410"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.60.1103"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"U. M. Maurer,\n                      Perfect cryptographic security from partially independent channels\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), 1991, pp. 561\u2013572.","DOI":"10.1145\/103418.103476"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3414"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"T. Moran, R. Shaltiel, and A. Ta-Shma,\n                      Non-interactive timestamping in the bounded storage model\n                      , in Advances in Cryptology\u2014CRYPTO '04, Lecture Notes in Comput. Sci. 3152, Springer, Berlin, 2004, pp. 460\u2013476.","DOI":"10.1007\/978-3-540-28628-8_28"},{"key":"R36","unstructured":"R. Renner,\n                      Security of Quantum Key Distribution\n                      , Ph.D. thesis, ETH Z\u00fcrich, Z\u00fcrich, Switzerland, 2005; available online from http:\/\/arxiv.org\/abs\/quant-ph\/0512258."},{"key":"R37","doi-asserted-by":"crossref","unstructured":"R. Renner and R. K\u00f6nig,\n                      Universally composable privacy amplification against quantum adversaries\n                      , in Theory of Cryptography Conference (TCC), Lecture Notes in Comput. Sci. 3378, Springer, Berlin, 2005, pp. 407\u2013425.","DOI":"10.1007\/978-3-540-30576-7_22"},{"key":"R38","unstructured":"A. R\u00e9nyi,\n                      On measures of entropy and information\n                      , in Proceedings of the 4th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, University of California Press, Berkeley, CA, 1961, pp. 547\u2013561."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"L. Salvail,\n                      Quantum bit commitment from a physical assumption\n                      , in Advances in Cryptology\u2014CRYPTO '98, Lecture Notes in Comput. Sci. 1462, Springer, Berlin, 1998, pp. 338\u2013353.","DOI":"10.1007\/BFb0055740"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(95)00219-S"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.441"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. N. Wegman and J. L. Carter,\n                      New classes and applications of hash functions\n                      , in Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1979, pp. 175\u2013182.","DOI":"10.1109\/SFCS.1979.26"},{"key":"R43","unstructured":"S. Wehner and J. Wullschleger,\n                      Composable Security in the Bounded-Quantum-Storage Model\n                      , http:\/\/arxiv.org\/abs\/0709.0492 (2007)."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1145\/1008908.1008920"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060651343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:46Z","timestamp":1787336386000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060651343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060651343"],"URL":"https:\/\/doi.org\/10.1137\/060651343","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}