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 Answer 1

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$
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$ 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
    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$ 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$ Dec 21, 2015 at 13:46
  • 1
    $\begingroup$ Can applying some padding remedy the scheme? textbook RSA is not semantically secure either. $\endgroup$
    – Moonwalker
    Jan 18, 2016 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.