{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T15:32:39Z","timestamp":1771515159494,"version":"3.50.1"},"reference-count":32,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181949","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T11:35:00Z","timestamp":1056627300000},"page":"261-270","source":"Crossref","is-referenced-by-count":112,"title":["Breaking the O(n\/sup 1\/(2k-1)\/) barrier for information-theoretic Private Information Retrieval"],"prefix":"10.1109","author":[{"given":"A.","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Y.","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"E.","family":"Kushilevitz","sequence":"additional","affiliation":[]},{"given":"J.-F.","family":"Raymond","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"19","first-page":"175","article-title":"Lower bounds for linear locally decodable codes and PIR","author":"goldreich","year":"2002","journal-title":"17th CCC"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1689"},{"key":"18","author":"goldreich","year":"2000"},{"key":"15","first-page":"927","article-title":"Secure multiparty computation of approximations","author":"feigenbaum","year":"2001","journal-title":"28th ICALP"},{"key":"16","first-page":"200","article-title":"A random server model for private information retrieval","author":"gertner","year":"1998","journal-title":"Random '98"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1007\/s001450010008"},{"key":"14","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/3-540-45539-6_10","article-title":"Single-database private information retrieval implies oblivious transfer","author":"di-crescenzo","year":"2000","journal-title":"Eurocrypt 2000"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004354"},{"key":"21","first-page":"11","article-title":"Efficient private information retrieval","volume":"e82 a","author":"itoh","year":"1999","journal-title":"IEICE Trans Fund of Electronics Commun and Comp Sci"},{"key":"20","first-page":"79","article-title":"Improved upper bounds on information theoretic private information retrieval","author":"ishai","year":"1999","journal-title":"31st STOC"},{"key":"22","first-page":"157","article-title":"On lower bounds for the communication complexity of private information retrieval","volume":"e84 a","author":"itoh","year":"2001","journal-title":"IEICE Trans Fund of Electronics Commun and Comp Sci"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"24","first-page":"939","article-title":"Secure games with polynomial expressions","author":"kiayias","year":"2001","journal-title":"28th ICALP"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646125"},{"key":"26","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/3-540-45539-6_9","article-title":"One-way trapdoor permutations are sufficient for single-database computationally-private information retrieval","volume":"1807","author":"kushilevitz","year":"2000","journal-title":"LNCS Eurocrypt 2000"},{"key":"27","article-title":"Private access to distributed information","author":"mann","year":"1998"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380855"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301312"},{"key":"3","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","article-title":"Hiding instances in multioracle queries","author":"beaver","year":"1990","journal-title":"STACS '90"},{"key":"2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/3-540-59042-0_88","article-title":"Simultaneous messages vs. communication","volume":"999","author":"babai","year":"1995","journal-title":"STACS 95 LNCS"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258609"},{"key":"1","first-page":"401","article-title":"Upper bound on the communication complexity of private information retrieval","volume":"1256","author":"ambainis","year":"1997","journal-title":"24th ICALP LNCS"},{"key":"30","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/258533.258606","article-title":"Private information storage","author":"ostrovsky","year":"1997","journal-title":"20th STOC"},{"key":"7","article-title":"Robust information-theoretic private information retrieval","author":"beimel","year":"0","journal-title":"3rd Conf on Security in Commun Networks 2002"},{"key":"6","first-page":"56","article-title":"Reducing the servers' computation in private information retrieval: PIR with preprocessing","author":"beimel","year":"2000","journal-title":"CRYPTO 2000"},{"key":"32","first-page":"357","article-title":"A new and efficient all-or-nothing disclosure of secrets protocol","author":"stern","year":"1998","journal-title":"Asiacrypt 98"},{"key":"5","first-page":"912","article-title":"Information-theoretic private information retrieval: A unified construction","author":"beimel","year":"2001","journal-title":"28th ICALP"},{"key":"31","article-title":"Private information retrieval: Improved upper bound, extension and applications","author":"raymond","year":"2000"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900017"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384047"},{"key":"8","first-page":"402","article-title":"Computationally private information retrieval with polylogarithmic communication","author":"cachin","year":"1999","journal-title":"Eurocrypt 99"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","location":"Vancouver, BC, Canada","acronym":"SFCS-02"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181949.pdf?arnumber=1181949","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T23:52:09Z","timestamp":1585007529000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181949\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":32,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181949","relation":{},"subject":[]}}