# Homomorphic/Paillier crypto system for use case?: overflow for multiple counter exponent possible? Different cipher factor needed all the time?

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

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.

• 1. Use 3 ciphertexts for each candidate, no problem since semantical security. 2. $r$ guarantees semantic security. If you remove you will ECB!. – kelalaka May 8 '19 at 18:32
• "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? – poncho May 8 '19 at 19:11
• @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? – J. Doe May 8 '19 at 20:02
• 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. – kelalaka May 8 '19 at 20:15
• @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). – J. Doe May 8 '19 at 20:30

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.
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.