Paillier cryptosystem safety

Question

I am working on system which can calculate average salary for different positions in large companies I want to use Paillier schema to do such calculation.

I have 3 fields which I want to encrypt: companyName, jobTitle, seniority and salary

Let’s say I have 3 different companies which want to calculate average salary on different positions but they don’t want to share data between them. We have such dataset

NAME	JOB TITLE	Seniority	Salary
COMPANYA	MANAGER	2	10000
COMPANYA	MANAGER	3	15000
COMPANYA	developer	1	18000
COMPANYA	developer	5	11000

NAME	JOB TITLE	Seniority	Salary
COMPANYB	MANAGER	2	11000
COMPANYB	MANAGER	3	14000
COMPANYB	developer	1	8000
COMPANYB	developer	5	14000

NAME	JOB TITLE	Seniority	Salary
COMPANYC	MANAGER	2	12000
COMPANYC	MANAGER	3	15000
COMPANYC	developer	1	8000
COMPANYC	developer	5	15000

Company A, B and C before sending data to my system encrypts them using Paillier (they all are using same key), than they are sending it to my system. My system knows only public key so it can calculate average salary for specific job title, than my system can send encrypted result to all companies and than they can decrypt it using private key and check what is average salary on specific positions taking into account salaries in other companies.

To avoid frequency attack I want to encrypt text data (company name and job title) using Paillier as well. I can assume that company name and job title is no longer than 20 bytes. Now my question: Do you think that system is safe? My system stores all information in encrypted form but don’t know private key so it can’t decrypt it. Let’s say in my system was data leak and somebody have all information in encrypted form (private key is not compromised) do you think he can perform any attack to decrypt data? Job titles are mostly dictionary data. Salary and seniority it’s a narrow range of numbers. What do you think? Thanks in advance for any input!

Answer 1

My system knows only public key so it can calculate average salary for specific job title

Actually, you can compute the sum; computing the average, that is, the value $\text{Encrypt}_k( \lfloor sum / n \rfloor )$ is rather trickier (and the floor operation is necessary if $sum$ is not necessarily a multiply of $n$ the number of values).

This could be handled by either computing $\text{Encrypt}_k( sum )$, and sending that and the value of $n$ to company A, B, C (which can decrypt and then divide). Or, by having each company implicitly multiply each salary they encrypt by $k!$ (for a reasonable value of $k$); then (assuming $n$ isn't too large), we can compute $\text{Encrypt}_k( n^{-1} \cdot sum )$, which would be the value we want (with the implied scaling factor still there).

To avoid frequency attack I want to encrypt text data (company name and job title) using pailler as well.

Will the companies encrypt the job title or would you? If they encrypted it, you don't have access to it, and so you wouldn't know which to sum.

On the other hand, if they provided the job titles in the clear and you encrypted it, that'd be fine (if, in my opinion, a bit pointless).

However, your question really was:

Let’s say in my system was data leak and somebody have all informations in encrypted form (private key is not compromised) do you think he can perform any attack to decrypt data?

You'd be fine - with Paillier, the attacker cannot retrieve any information from the ciphertext (assuming that the private key and the random values used during the encryption process is secure); even if he knew that the plaintext is one of two values, he still cannot determine which it is.

Answer 2

Regarding average, I was thinking about multiplying each entry by $2$ to make sure it is even. The number of all elements is known in my service so I can divide the encrypted numbers by non-encrypted values. Then the encrypted results can be sent to all companies and they can divide it by $2$ to get the final result, do you think it's fine?

About the second point, right I forgot that I would not be able to know if two job titles are equals using Pailler. Previously I was thinking about storing hashes but it will be easy to attack because the number of different job names is limited. I have to find a better algorithm for that.