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, 2016 at 4:02
  • $\begingroup$ Yes. It likes Paillier. $\endgroup$
    – sam zhao
    Jan 11, 2016 at 5:48
  • $\begingroup$ BHHO (Crypto 2008) $\endgroup$
    – sam zhao
    Jan 11, 2016 at 6:30

1 Answer 1


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.

  • $\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, 2016 at 7:50
  • $\begingroup$ It's the same thing. To multiply by a matrix, you multiply by scalars and then add. $\endgroup$ Jan 11, 2016 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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