{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:17:15Z","timestamp":1783009035558,"version":"3.54.5"},"reference-count":0,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2016,7,14]],"date-time":"2016-07-14T00:00:00Z","timestamp":1468454400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p> Private information retrieval (PIR) is a way for clients to query a remote database without the database holder learning the clients\u2019 query terms or the responses they generate. Compelling applications for PIR are abound in the cryptographic and privacy research literature, yet existing PIR techniques are notoriously inefficient. Consequently, no such PIRbased application to date has seen real-world at-scale deployment. This paper proposes new \u201cbatch coding\u201d techniques to help address PIR\u2019s efficiency problem. The new techniques exploit the connection between ramp secret sharing schemes and efficient information-theoretically secure PIR (IT-PIR) protocols. This connection was previously observed by Henry, Huang, and Goldberg (NDSS 2013), who used ramp schemes to construct efficient \u201cbatch queries\u201d with which clients can fetch several database records for the same cost as fetching a single record using a standard, non-batch query. The new techniques in this paper generalize and extend those of Henry et al. to construct \u201cbatch codes\u201d with which clients can fetch several records for only a fraction the cost of fetching a single record using a standard non-batch query over an unencoded database. The batch codes are highly tuneable, providing a means to trade off (i) lower server-side computation cost, (ii) lower server-side storage cost, and\/or (iii) lower uni- or bi-directional communication cost, in exchange for a comparatively modest decrease in resilience to Byzantine database servers.<\/jats:p>","DOI":"10.1515\/popets-2016-0036","type":"journal-article","created":{"date-parts":[[2016,7,18]],"date-time":"2016-07-18T08:14:59Z","timestamp":1468829699000},"page":"202-218","source":"Crossref","is-referenced-by-count":27,"title":["Polynomial Batch Codes for Efficient IT-PIR"],"prefix":"10.56553","volume":"2016","author":[{"given":"Ryan","family":"Henry","sequence":"first","affiliation":[{"name":"Indiana University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"35752","published-online":{"date-parts":[[2016,7,14]]},"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/content.sciendo.com\/view\/journals\/popets\/2016\/4\/article-p202.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2016-0036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:29:29Z","timestamp":1658334569000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2016\/popets-2016-0036.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,14]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,7,14]]},"published-print":{"date-parts":[[2016,10,1]]}},"alternative-id":["10.1515\/popets-2016-0036"],"URL":"https:\/\/doi.org\/10.1515\/popets-2016-0036","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,14]]}}}