{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T12:18:34Z","timestamp":1764332314457},"reference-count":0,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"2","license":[{"start":{"date-parts":[[2015,6,1]],"date-time":"2015-06-01T00:00:00Z","timestamp":1433116800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-<jats:italic>n<\/jats:italic> computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for <jats:italic>large-output<\/jats:italic> polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter <jats:italic>s<\/jats:italic> is set equal to the only positive root of a degree-(<jats:italic>m<\/jats:italic> + 1) polynomial, where <jats:italic>m<\/jats:italic> is the length of the branching program. We show, by using Galois theory, that even when <jats:italic>m<\/jats:italic> = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for <jats:italic>s<\/jats:italic>, and based on this, propose a \u0398 (log<jats:italic>m<\/jats:italic>)-time algorithm to find an integer approximation to <jats:italic>s<\/jats:italic>.<\/jats:p>","DOI":"10.1515\/popets-2015-0016","type":"journal-article","created":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T17:02:48Z","timestamp":1435165368000},"page":"222-243","source":"Crossref","is-referenced-by-count":24,"title":["Optimal Rate Private Information Retrieval from Homomorphic Encryption"],"prefix":"10.56553","volume":"2015","author":[{"given":"Aggelos","family":"Kiayias","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, Greece"}]},{"given":"Nikos","family":"Leonardos","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Diderot \u2013 Paris 7, France"}]},{"given":"Helger","family":"Lipmaa","sequence":"additional","affiliation":[{"name":"University of Tartu, Estonia"}]},{"given":"Kateryna","family":"Pavlyk","sequence":"additional","affiliation":[{"name":"University of Tartu, Estonia"}]},{"given":"Qiang","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Connecticut, USA"}]}],"member":"35752","published-online":{"date-parts":[[2015,6,22]]},"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2015\/2\/article-p222.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2015-0016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:29:11Z","timestamp":1658334551000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2015\/popets-2015-0016.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,1]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2015,6,22]]},"published-print":{"date-parts":[[2015,6,1]]}},"alternative-id":["10.1515\/popets-2015-0016"],"URL":"https:\/\/doi.org\/10.1515\/popets-2015-0016","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,1]]}}}