Paper 2024/1307
On Algebraic Homomorphic Encryption and its Applications to Doubly-Efficient PIR
Abstract
The Doubly-Efficient Private Information Retrieval (DEPIR) protocol of Lin, Mook, and Wichs (STOC'23) relies on a Homomorphic Encryption (HE) scheme that is algebraic, i.e., whose ciphertext space has a ring structure that matches the homomorphic operations. While early HE schemes had this property, modern schemes introduced techniques to manage noise growth. This made the resulting schemes much more efficient, but also destroyed the algebraic property. In this work, we study algebraic HE with the goal of improving its performance and thereby also the performance of DEPIR
We first prove a lower bound of
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Homomorphic EncryptionPrivate Information RetrievalPIRReduction
- Contact author(s)
- Simon Pohmann 2022 @ live rhul ac uk
- History
- 2024-08-23: approved
- 2024-08-21: received
- See all versions
- Short URL
- https://ia.cr/2024/1307
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1307, author = {Hiroki Okada and Rachel Player and Simon Pohmann and Christian Weinert}, title = {On Algebraic Homomorphic Encryption and its Applications to Doubly-Efficient {PIR}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1307}, year = {2024}, url = {https://eprint.iacr.org/2024/1307} }