0
$\begingroup$

Recently I read about homomorphic cryptosystem. They might solve a problem. To do this there need to be some modifications from standard version.

Using Paillier here but a solution for other also fine.

E.g. given two cipher text $c_1,c_2$ with generator $g$ and factors $r_i$:
$c_i = g^{m_i} r_i^n \mod n^2$
$n=p\cdot q$, with $p,q$ primes

Now if they get multiplied
$c_1 \cdot c_2 \equiv g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1r_2)^n \equiv g^{m_1+m_2} r^n \mod n$
The factors $m_1, m_2$ get added. If they get $n$ or larger they start over again. In normal use case that is prohibit by selecting a larger $n$.

Now I'm looking for a way to get this overflow for a special kind of $m$. Image an election with 3 candidates and their votes counted in one exponent.
E.g. candidate 1 has 5 votes, 2 has 6 and 3rd 42 votes, exponent of $g$ could be ${005006042}$. In another region it's ${133700123}$. If ciphers multiplied those exponents get added and sum up all votes for each single candidate. This exponent form only allows up to $999$ total votes for each candidate (assuming the total exponent number is $<n$).

In my use case there will always be some exponent overflow, no matter how big $n$ is. But instead the whole exponent it should be one for each candidate.
E.g. $700.800.900$ and $400.100.200$ should add up to $100.900.100$ instead of $1100.901.100$.
Is there a way to have multiple overflows in exponent? Or an alternative way for multiple counters?

Elements also get subtracted, so there need to be an underflow as well.


As far as I understood each cipher can(should?) have its own $r$. For my use case it need to be associative in some way. It need to be the same cipher independent of order and direction. E.g. adding 5 votes to a cipher should result in same ciphertext as adding 5 times one vote to the same cipher. That should work if there is only one $r$ (for each candidate)(+$r^{-1}$ for subtraction). But a single $r$ works against security, or?
You know another way to achieve this? Some way to check if two different $c_1\not= c_2$ have the same exponent without encrypting it would also work.

$\endgroup$
  • $\begingroup$ 1. Use 3 ciphertexts for each candidate, no problem since semantical security. 2. $r$ guarantees semantic security. If you remove you will ECB!. $\endgroup$ – kelalaka May 8 at 18:32
  • $\begingroup$ "For my use case it need to be associative in some way"; what do you mean by that? Do you really mean deterministic (that is, one particular $m$ always maps to the same $c$) - that's not good for security. If you mean something else, what precisely do you mean? $\endgroup$ – poncho May 8 at 19:11
  • $\begingroup$ @kelalaka: 3 ciphertexts for each (total 9, why that?) or 1 for each candidate? If used together with 2nd question it won't work. ECB? Electronic Code Book? $\endgroup$ – J. Doe May 8 at 20:02
  • $\begingroup$ To prevent the overflow, you need either prepare the message space as $3n$ where $n$ is the total number of votes. Or use separate messages for each candidate. If you remove $r$ you can have the equality as ECB mode, but you will lost the semantic security. $\endgroup$ – kelalaka May 8 at 20:15
  • $\begingroup$ @poncho: one $m$ should always be the same $c$ or a little weaker there need to be a function $f(c_1,c_2,(n))$ which can determine if same $m$ was used without decrypting it. Not secure because of which detail? Will $r$ get reduced to a 2nd generator? In use case the direct value of $m$ will not be used. Only ciphers will get multiplied. I'm looking for a way to encrypt the used calculations to get from one number (here ciphertext) to another and back again with 3 different ways (here candidate votes) and cyclic (overflow). $\endgroup$ – J. Doe May 8 at 20:30
0
$\begingroup$

It won't work anyways because even in case it would be secure with one $r$ and the exponent can get overflow for each candidate the ciphertext with same exponent will be different after an overflow happened.

Do you really mean deterministic (that is, one particular m always maps to the same c)

Given two ciphertext with same exponent ($\mod n$) before and after overflow. The 2nd would be result after adding $n$ times one vote to first.
$c_0 = g^0 \cdot r^n \mod n^2$
$c_{i+1} = c_i \cdot c_{add+1} = c_i \cdot g^1 \cdot r^n = g^i \cdot r^{in+n}$
$c_a=g^a \cdot r^{an+n} \not=g^{a+n} \cdot r^{an+n^2+n}=c_{a+n}$ $\mod n^2$
(because $r^{\phi(n^2)}=1$ and $n^2 \not = \phi(n^2)$ )
Decryption resolve in same $a$ but exponent of $r$ is different and with this those two ciphertexts.

$\endgroup$

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.