Additively homomorphic encryption ⇒ CRHF

Standard model · IKO05

Statement

A semantically secure additively homomorphic encryption scheme, with fixed-length ciphertexts closed under homomorphic addition, yields a collision-resistant hash function family — IKO05.

Notes

• Compression comes from the fixed ciphertext length, against which the parameters are chosen so that the hash output is shorter than its input — IKO05.
• Such schemes also give single-server PIR — Ste98 — and one-round sublinear PIR gives collision-resistant hashing as well (one-round sublinear cPIR ⇒ CRHF) — IKO05.