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.