3

Rivest et al. proposed the concept of privacy homomorphisms, but did not distinguish between partial versus fully homomorphic encryption. Gentry seems to take for granted the idea that fully homomorphic encryption must preserve both addition and multiplication.

Clearly, someone in the intervening three decades made the distinction and gave a definition, but who, and in what paper? I'm having trouble finding a source.

Improve this question
4
  • I conjecture that at first a number of scientists found schemes that are only partially homomorphic and hence Gentry's scheme obtained that distinguishing qualification.
    – Mok-Kong Shen
    Dec 11, 2014 at 10:12
  • In his dissertation, Gentry seems to assume that the term "fully homomorphic encryption" is already known to his audience. That suggests that the term was coined well before 2009.
    – user2752467
    Jan 3, 2015 at 23:23
  • I think I remember gentry coining that term in a paper related to his dissertation. I will have a look into my masters thesis and come back :)
    – Tobi Nary
    Mar 28, 2016 at 14:57
  • "A guide to fully homomorphic encryption by Armknecht et al" may be of help here.
    – SEJPM
    Mar 28, 2016 at 18:51

1 Answer 1

Reset to default
1

Also in 2009, Gentry published Fully Homomorphic Encryption Using Ideal Lattices, defining fully homomorphic encryption like so:

Definition 2 (Fully Homomorphic Encryption). E is fully homomorphic if it is homomorphic for all circuits.

Yet, he hints at Rivest et al for the term:

Rivest et al. [54] asked a natural question: What can one do with an encryption scheme that is fully homomorphic: a scheme E with an effi- cient algorithm Evaluate E that, for any valid public key pk, any circuit C (not just a circuit consisting of multiplication gates), and any ciphertexts ψ i ← Encrypt E (pk ,π i ), outputs ψ ← Evaluate E (pk ,C,ψ 1 ,...,ψ t ) , a valid encryption of C ( π 1 ,...,π t ) under pk?

citing "On Data banks and privacy homomorphisms" which, as you noticed, does not use the term.

Another publication by Boneh et al, "Evaluating 2-DNF Formulas on Ciphertexts" from 2005 does not use the phrase. Neither does "Evaluating Branching Programs on Encrypted Data" by Ishai et Paskin from 2007.

Also, as the term is self-explanatory to a fair degree, as the previous models were merely partially homomorphic, Gentry might use the term as-is without explanation, but instead chooses to clarify:

We propose a solution to the old open problem of con- structing a fully homomorphic encryption scheme . This no- tion, originally called a privacy homomorphism , was intro-duced by Rivest, Adleman and Dertouzos [54] shortly af- ter the invention of RSA by Rivest, Adleman and Shamir [55].

Given that the term was not used in papers relevant to the subject before Gentry's publication and that the definition he gives has no source, it is likely that Gentry coined the term.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .