# ElGamal and Pailler combined

currently I am working on some secure accounting application. I have few requirements:

1. Application should store items which can be searched by name.
2. Every item has price and tax.
3. Every invoice contains arbitrary amount of different items.
4. Every invoice has gross and net sum of items

My idea is to use rsa or ElGamal schema for multiplication and Pailler for addition. Calculating net sum is pretty easy I can just use pailler for doing it. Problem is with gross sum. In my solution for each item I am doing multiplication: price*tax using RSA and here I am stucked. I have only one solution in my mind: adding another trusted proxy to my system which will receive result of each multiplication, decrypt it and encrypt using Pailler scheme and than send it back to my server (which now can sum gross values of each item). That solution requires a lot of communication between server and proxy and client has to give his private keys to the proxy. Do you have any idea how can I improve it? Thanks in advance!

• thanks for the answers, both help me a lot! TBH next year I have to write my bachelor thesis and in future I would like to work in security area, I am just trying to write some system which will help me get familiar with encryption algorithmes and I have to propose topic which is related to security. I would like to write something which is not already implemented and something which will allow me get deeper in security algorithmes. As you said tax is probably something doesn't have to be secret. I have to find better usecase which will allow me understand things better, thanks! – sorror May 20 at 14:34

There exist methods which allow to switch between a multiplicatively homomorphic encryption scheme - such as ElGamal - and an additively homomorphic encryption scheme - such as Paillier. By switch, I mean securely converting an encryption of a plaintext under one scheme into an encryption of the same plaintext under the other scheme. This is precisely what we described in this paper (see also the follow up). In these works, no proxy knows the full secret key of either scheme: the server and the proxy only have to know shares of the private keys of the scheme (hence, neither the server nor the proxy can decrypt any ciphertext alone).

Several important remarks, however:

• In your question, you seem to completely ignore one of the most crucial aspects: the additive and multiplicative schemes must be compatible, in the sense that they must (essentially) operate over the same structure. By default, RSA is multiplicative over $$\mathbb{Z}_n^*$$ and Paillier is additive over $$\mathbb{Z}_n$$. These rings do not even have the same order, and this is extremely problematic - it can be easily used by an attacker to completely destroy security. Solving this issue is actually one of the main hard steps in our paper.
• RSA is not secure for your application. It is only one-way; you cannot hide a money amount with a one-way scheme, since there are not so many possible values. An attacker could try to encrypt all possible amounts to learn which one was encrypted.
• Is "tax" supposed to remain secret? I do not see why it should be a secret value in your application, since tax is typically public. If tax is public, you do not need any multiplicative scheme whatsoever: Paillier already allows to compute operations of the form $$\sum_i \alpha_i \cdot m_i$$ given encrypted plaintexts $$m_i$$ and arbitrary public coefficients $$\alpha_i$$.
• In any case, if you need to do a single multiplication (or several "single multiplications" in parallel), like $$\sum_i \alpha_i \cdot m_i$$ (and not e.g. $$\prod_{i=1}^n m_i$$ for a large $$n$$), I would advise against using any technique for switching between encryption schemes. It will considerably complexify the construction, make it very hard to analyze and error prone, and it seems completely unnecessary. There are secure two-party protocols to securely compute, given Paillier encryptions of $$x$$ and $$y$$ respectively, a Paillier encryption of $$x\cdot y$$, where the two parties have shares of the secret Paillier ket (i.e. no one holds the full key). Roughly, it goes as follows: Alice picks a random mask $$r$$ and computes $$E(x+r)$$ ($$E$$ is Paillier encryption), the parties jointly decrypt such that Bob gets the plaintext $$x+r$$, and computes $$E(y\cdot (x+r))$$ from $$x+r$$ and $$E(y)$$. Bob sends back this ciphertext to Alice, who can herself compute $$E(y\cdot r)$$ (since she has $$r$$), and homomorphically substract the ciphertexts, getting $$E(x\cdot y)$$. This is a simple standard protocol to interactively multiply Paillier encrypted values.

That's the archetypal solution looking for problem and towards that goal ignoring reality. Case in point: solution = homomorphic encryption, problem = invoicing, reality = invoices need to be understandable by those who make them, since the real work is insuring the inputs are correct, or at least make some sense.

Also, the security goal is not stated: what needs to be kept confidential, from who?

Brushing the first issue aside, if in the second the "arbitrary amount of different items" (hereafter quantity) needs not be kept confidential from the entity doing the computation, and can be reduced to integer or multiple of some fraction like $$1/1000$$, Pailler encryption alone is enough, using that for any integers $$k$$ and $$x$$, $$\left(k\cdot x\bmod n\right)\ =\ D\Bigl(\bigl(E\left(x\right)\bigr)^k\bmod\left(n^2\right)\Bigr)$$

That also works the other way around if we want to hide quantity and total price, not unit price.

If we want to hide both quantity and unit price we need Fully Homomorphic Encryption, and as pointed in the other answer, RSA and Pailler won't nicely fuse into in that.

• Common substitutes for invoicing include: voting, AI, medical testing. For voting, reality includes that voters trust the outcome and whatever runs the damn thing; which is a problem since voters are not rational, as 2020-2021 actuality in the USA demonstrates. – fgrieu May 20 at 11:45