# Is Paillier cryptosystem commutative?

Is Paillier cryptosystem commutative?

If not, how can we construct an oblivious decryption protocol based on Paillier?

• What have you tried in trying to answer this yourself? This site is not an answering service, we appreciate it when askers can show us their attempt at answering basic questions like this and where they are getting stuck. That will help us to best help you. – mikeazo Nov 3 '14 at 14:32
• @mikeazo one solution I can think of is to let Alice do c=E(pk,m+r)= E(pk,m)+E(pk,r) (where r is random) and send c to Bob. Bob decrypts c and sends m+r to Alice. Alice output (m+r)-r. But How to prevent Bob from reply with a wrong value instead of m+r. – Jan Leo Nov 4 '14 at 12:37

Your proposal for doing oblivious decryption is almost correct. Multiplication in the ciphertext domain is addition in the plaintext domain, so $E(pk, m+r) = E(pk, m) \cdot E(pk, r)$. Given $m+r$ in a finite group, Bob cannot figure out $m$ as long as $r$ is only ever used once.