CryptoDB
Sometimes-Decryptable Homomorphic Encryption from Sub-exponential DDH
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Homomorphic encryption (HE) is a popular cryptographic primitive with wide ranging applications. While many HE schemes have been proposed over the years, schemes that support general or even more than degree-two homomorphism are known only from lattice-based assumptions or program obfuscation. In particular, constructions based solely on group-based assumptions remain elusive. We propose the notion of sometimes-decryptable homomorphic encryption s-HE --- a relaxation of HE that allows very high decryption error for homomorphically evaluated ciphertexts. We present a construction of s-HE for constant-depth (resp., logarithmic depth) threshold circuits based on the sub-exponential (resp., exponential) Decisional Diffie-Hellman (DDH) assumption. We demonstrate several applications of s-HE: - We construct SNARGs for all NP languages that have a TC0-Frege proof of non-membership. Namely, for every instance that is not in the language, we require that there exists a polynomial-size proof in propositional logic proving the non-membership of the instance. Moreover, each line of the proof is a TC0 formula. Our SNARG proof size is a fixed polynomial in the security parameter, and the CRS size grows polynomially in the size of the propositional proof. Previously, such a result was known either from FHE [Jin et al, STOC'24], or using indistinguishability obfuscation [Jain-Jin, FOCS'22]. - We construct predicate extractable hash for bit-fixing functions and monotone-policy batch arguments [Brakerski et al, CRYPTO 2023] from s-HE. Previously, these primitives were only known from FHE. - Finally, we demonstrate a simple construction of correlation-intractable hash (CIH) functions from s-HE, subsuming the previous result of [Jain-Jin, EUROCRYPT 2021]. |
BibTeX
@inproceedings{crypto-2025-35744,
title={Sometimes-Decryptable Homomorphic Encryption from Sub-exponential DDH},
publisher={Springer-Verlag},
author={Abhishek Jain and Zhengzhong Jin},
year=2025
}