5
$\begingroup$

I am doing a little cryptography research and stuck with question.

Suppose $\bar m$ is a vector of 64-bit numbers. And i want to have an additive homomorphic encryption over them. I choose large (2048 bit) prime $n$, large not prime $s$ and vector $\bar r$ of large random numbers, with size of vector equal to vector $\bar m$. Finaly, encryption function $Enc$ looks like that: $$Enc(m_i) = (r_i,m_i+r_i\cdot s\mod n)$$ where $Enc$ yields an ordered pair of numbers. So the number $n$ with encrypted vector $c=Enc(m)$ goes to the opponent, but $s$ keeps secret.

Sum of an encrypted values is just sum of pairs (all operations are modulo $n$): $$Sum(c_i,c_j) = (c_i.first+c_j.first,c_i.second+c_j.second)$$ $$or$$ $$(a,b)+(c,d)=(a+c,b+d)$$ where $c_i.first$ is the first element of pair $c_i$ and $c_i.second$ is the second.

Decryption looks like that: $$Dec(c_i) = c_i.second - c_i.first\cdot s$$

Intuitively, i think, that this scheme is vulnerable, but i can't see why. I will be glad to have a hint to understanding this problem.

Many thanks in advance to your great community!
(sorry for any grammar mistakes, English is not my native language)

$\endgroup$
1
$\begingroup$

It is not semantically secure. If the adversary asks for the encryption of message $0$ then it gets $r_i,r_i*s$, so it recovers the secret key $s$ and breaks the security game.

$\endgroup$
  • $\begingroup$ Ok, i understand it. The scheme is not secure even against Known Plaintext Attack. But what if adversary can't ask for encryption and s is random in every session? $\endgroup$ – cvzakharchenko Dec 21 '15 at 8:44
  • $\begingroup$ that is very weak. The attacker always can ask for encryptions. In its weakest form a security game for confidentiality provides ciphers to the attacker at its will $\endgroup$ – curious Dec 21 '15 at 9:27
  • $\begingroup$ But homomorphic encryption scheme can be used, when user encrypts his own data and sends to untrusted party. Untrusted party do some computations over encrypted data and returns to user. Isn't this secure with new session key each time? As i see, attacker can "search" for predictable values in data just trying to treat each encrypted value as 0, 1, 2 or any other frequently occured numbers. But i wonder, is there some algebraic or just more clever attacks? $\endgroup$ – cvzakharchenko Dec 21 '15 at 13:28
  • $\begingroup$ Oh, and in case of two equal messages, the secret key reveals easily, as i can see. $\endgroup$ – cvzakharchenko Dec 21 '15 at 13:46
  • 1
    $\begingroup$ Can applying some padding remedy the scheme? textbook RSA is not semantically secure either. $\endgroup$ – Moonwalker Jan 18 '16 at 22:16

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.