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 the properties of algebraic HE and try to make progress in solving this problem. We first prove a lower bound of
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2025
- Keywords
- Homomorphic EncryptionPrivate Information RetrievalPIRReduction
- Contact author(s)
- Simon Pohmann 2022 @ live rhul ac uk
- History
- 2025-02-19: last of 2 revisions
- 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} }