I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob. Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key and sends it to Bob. In Bob's side, we need to define whether this value is negative or positive. How can I achieve that?

  • $\begingroup$ So what want is a way for Alice to prove / assert what the most significant bit of the plaintext of the given ciphertext is? $\endgroup$ – SEJPM Sep 17 '18 at 10:12

Assume that there is a such function $f$, that can determine the sign of the number within the ciphertext .

Let the message space $P$ Using the binary technique, then an adversary can actually find the message as; where $c$ is the ciphertext

if  $f( c - E_p( |P|/2 ))$ > 0 
  if $f( c - E_p( |P| ))$ > 0 
else if $f( c - E_p( 0 ))$ > 0...

As usual binary search.

| improve this answer | |

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.