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.

  • 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 '14 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. – Justin Lardinois Jan 3 '15 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 '16 at 14:57
  • "A guide to fully homomorphic encryption by Armknecht et al" may be of help here. – SEJPM Mar 28 '16 at 18:51
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.