Skip to main content
Tweeted twitter.com/StackCrypto/status/678972724128165889
Changed s to be not prime
Source Link

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) primesprime $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)

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) primes $n$, $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)

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)

edited title
Link

Is that simple additive-homomorphic homomorphic scheme secure?

Source Link

Is that additive-homomorphic scheme secure?

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) primes $n$, $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)