Homomorphic Cryptography

Informally, a cryptographic function C(x)C(x) is homomorphic if it allows to peform computations on its input xx without inverting CC. The most studied homomorphic cryptography problem in the area of lattice cryptography is that of Fully Homomorphic Encryption, i.e., the construction of secure encryption schemes EE such that, given the encryption of a message E(m)E(m) and the description of a function ff, one can compute the encryption E(f(m))E(f(m)) of the result of applying ff to the message, without knowing the decryption key. There is so much work on fully homomorphic encryption that we list it on a separate page. Here are some additional homomorphic cryptography problems that have been solved using lattices.

Homomorphic signature schemes are digital signature schemes that allow some limited form of forgery, e.g., given a signature S(m)S(m) on a message mm, one should be able to derive a signagure S(f(m))S(f(m)) on a related message. Notice that homomorphic signature schemes are not secure digital signatures because they allow some form of forgery.

  1. Homomorphic signatures for polynomial functions
    (Boneh & Freeman - Eurocrypt 2010)

  2. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures
    (Boneh & Freeman - PKC 2011)

Key-homomorphic encryption differs from (fully) homomorphic encryption in that it allows to operate homomorphically on encryption key rather than the encrypted message.

  1. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits
    (Boneh, Gentry, Gorbunov, Halevi, Nikolaenko, Segev, Vaikuntanathan & Vinayagamurthy - EuroCrypt 2014)