I'm having a problem with an encryption scheme.

There are two entities, $A$ and $B$. $A$ give a simple message $m \in [0,1]$ to $B$. $B$ should generate an encrypted message of $m$: $e=Enc_{pk}(m)$ such that $A$ can verify if $B$ has correctly encrypted a message generated from $A$ without tampering it. But, at the same time, $e$ should not reveal any information that can be used from $A$ to demonstrate the value of the message $m$ in $e$. (The decryption key $sk$ is not known by either $A$ or $B$)

Basically, the goal is to have an encrypted message on which $A$ can only check if the content is something that $A$ themself generated (eg. with a signature) but without being able to demonstrate to anyone the effective plaintext value.

There are no particolar constraint in the protocol, so additional data like signature or witness can be used.

Do you know any schema that can solve this situation?

  • $\begingroup$ Why $A$ can't herself encrypt $m$ with $pk$ which is public key? $\endgroup$
    – Ievgeni
    Jun 13 '21 at 10:37
  • $\begingroup$ @Ievgeni Because, if $A$ encrypts $m$ herself, she can later prove the content of $e$ by just encrypting $m$ again with the same random values $\endgroup$ Jun 14 '21 at 16:26
  • $\begingroup$ Thank you for your answer :) $\endgroup$
    – Ievgeni
    Jun 14 '21 at 16:57

It think, it can be solved by using structure preserving encryption/signature scheme (I mean schemes which are compatible with the ZK proof system you want to use).

The general idea is that Alice will sign the message and will send the signature $\sigma$ to Bob, then Bob will commit the message $m$, and the signature $\sigma$ and will build ZK proofs that $e$ contains $m$, and $\sigma$ is a valid signature for $m$ according to the public verification key of Alice.

Because Alice only sign one message, she will be convinced that $(com_m, com_\sigma)$ contains $(m, \sigma)$ (and thus that $e = Enc_{pk}(m)$).

But because the proofs are zero-knowledge, $Enc(m)$ is perfectly indistinguishable from another message potentially signed by Alice (even the secret signing key of Alice is revealed). And thus Alice could not convince anyone about the real value in $Enc(m)$.

For concrete instantiation, you can for example use Groth-Sahai proofs-system, with El Gamal as encryption scheme, and these signatures.


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.