On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols
Nirattaya Khamsemanan, Rafail Ostrovsky, William E. Skeith III
Abstract:
In this work, we develop a methodology for determining the communication required to implement various two-party functionalities non interactively. In the particular setting on which we focus, the protocols are based upon somewhat homomorphic encryption and furthermore they treat the homomorphic properties as a black box. In this setting we develop lower bounds which give a smooth trade-off between the communication complexity and the "expressiveness" of the cryptosystem-- the latter being measured in terms of the depth of the arithmetic circuits that can be evaluated in ciphertext. Given the current state of the art in homomorphic encryption this trade-off may also be viewed as one between communication and computation since at present more expressive cryptosystems are markedly less efficient. We then apply this methodology to place lower bounds on number of cryptographic protocols including private information retrieval writing and private keyword search. Our work provides a useful "litmus test" of feasibility for use by other cryptographic researchers attempting to develop new protocols that use somewhat homomorphic encryption in a black-box way and require certain levels of communication efficiency. We also answer an open question from the thesis of Doerte K. Rappe[ Homomorphic Cryptosystems and Their Applications ,Universitat Dortmund, Germany, 2006] regarding the construction of fully homomorphic encryption from group homomorphic encryption.
message complexity.
The full version of this paper can be found at the Cryptology ePrint Archive[28].
comment: SIAM J. Discrete Math. 30(1): 266-295 (2016)
Fetch PDF file of the paper
| Back to Publications List |