Limits of provable security for homomorphic encryption
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractWe show that public-key bit encryption schemes which support weak (i.e., compact) homomorphic evaluation of any sufficiently "sensitive" collection of functions cannot be proved message indistinguishable beyond AM ∩ coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity. Examples of sensitive collections include parities, majorities, and the class consisting of all AND and OR functions. We also give a method for converting a strong (i.e., distribution-preserving) homomorphic evaluator for essentially any boolean function (except the trivial ones, the NOT function, and the AND and OR functions) into a rerandomization algorithm: This is a procedure that converts a ciphertext into another ciphertext which is statistically close to being independent and identically distributed with the original one. Our transformation preserves negligible statistical error. © 2013 International Association for Cryptologic Research.
All Author(s) ListBogdanov A., Lee C.H.
Name of Conference33rd Annual International Cryptology Conference, CRYPTO 2013
Start Date of Conference18/08/2013
End Date of Conference22/08/2013
Place of ConferenceSanta Barbara, CA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by International Association for Cryptologic Research,
Volume Number8042 LNCS
Issue NumberPART 1
PublisherSpringer Verlag
Place of PublicationGermany
Pages111 - 128
LanguagesEnglish-United Kingdom

Last updated on 2020-30-10 at 23:41