1
$\begingroup$

Is Paillier cryptosystem commutative?

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – mikeazo Nov 3 '14 at 14:32
  • $\begingroup$ @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. $\endgroup$ – Jan Leo Nov 4 '14 at 12:37
1
$\begingroup$

No, Paillier is not commutative.

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.

| improve this answer | |
$\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.