Assume Alice encrypts messages $m_1$,...,$m_n$ using secret keys $k_1$,...,$k_n$ on a homomorphic encryption scheme (BHHO), so she would get $c_1=Enc_{k_1}(m_1)$,...,$c_n=Enc_{k_n}(m_n)$. Then Alice sends a constant a , some random numbers $a_1$,...,$a_n$ and these ciphertexts to Bob. Can Bob do the following homomorphic operations? (The homomorphic encryption scheme requires that the ciphertext is multiplied by a random number) $$d_1=Enc_{k_1}(m_1)*{a_1}*a=Enc_{k_1}(m_1*{a_1}*a)$$ ... $$d_n=Enc_{k_n}(m_n)*{a_n}*a=Enc_{k_n}(m_n*{a_n}*a)$$

  • $\begingroup$ What kind of homomorphic cryptosystem are we talking? Something like Paillier? $\endgroup$ – mikeazo Jan 11 '16 at 4:02
  • $\begingroup$ Yes. It likes Paillier. $\endgroup$ – sam zhao Jan 11 '16 at 5:48
  • $\begingroup$ BHHO (Crypto 2008) $\endgroup$ – sam zhao Jan 11 '16 at 6:30

Yes. Additive homomorphic encryption can also be used to obtain multiplication by a scalar. The way that this is done is by repeated addition, in exactly the same way as you do efficient exponentiation.

Recursively, define:

  • If $a$ equals 1 then $mult(a,Enc_k(m)) = Enc_k(m)$

  • If $a$ is even then $mult(a,Enc_k(m)) = mult\left(\frac{a}{2},Enc_k(m)\right)+mult\left(\frac{a}{2},Enc_k(m)\right)$

  • If $a$ is odd then $mult(a,Enc_k(m)) = mult\left(\frac{a-1}{2},Enc_k(m)\right)+mult\left(\frac{a-1}{2},Enc_k(m)\right)+Enc_k(m)$

Thus, you only need addition.

| improve this answer | |
  • $\begingroup$ The ciphertext is multiplied by a random matrix(not a random number) on BHHO homomorphic encryption scheme(i.e. a additive homomorphic encryption).If we have a lot of ciphertexts, which need to be done homomorphic operations, can all the ciphertexts be multiplied by the same random matrix? $\endgroup$ – sam zhao Jan 11 '16 at 7:50
  • $\begingroup$ It's the same thing. To multiply by a matrix, you multiply by scalars and then add. $\endgroup$ – Yehuda Lindell Jan 11 '16 at 7:58

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.