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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Dec 21, 2015 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
    Commented Dec 21, 2015 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
    Commented Dec 21, 2015 at 13:28
  • $\begingroup$ Oh, and in case of two equal messages, the secret key reveals easily, as i can see. $\endgroup$
    – cvzakharchenko
    Commented Dec 21, 2015 at 13:46
  • 1
    $\begingroup$ Can applying some padding remedy the scheme? textbook RSA is not semantically secure either. $\endgroup$
    – Moonwalker
    Commented Jan 18, 2016 at 22:16

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.