# Verifying without knowing key?

Say user Bob sends an encrypted message to a server. People can download the message from this server and later get the key directly from Bob.

Is it possible for the server to somehow verify that users are able to decrypt the message later on with Bob's key without letting the server be capable of decrypting the message itself? So the server knows the message is being opened but itself can’t “see” the contents? Is it – at least theoretically – feasible to have an implementation which allows for this situation?

• a) who should be able to verify this capability (other users?) b) Do you trust the clients no to lie about this? c) Is bob allowed to attach additional (server-view only) data? – SEJPM Apr 19 '16 at 20:10
• The purpose would be so that the server can verify Bob is actually distributing valid keys, not the other users. We do not trust the clients which is why the server should be able to make the verification's. Bob can attach server only data. – tacoma Apr 19 '16 at 20:55
• What about requiring Bob to append a (signed) hash of the message for the server only and verify the correctness of the key by receiving the correct (same) hash from the client? – SEJPM Apr 19 '16 at 21:01
• Doesn't this require that the client is trusted to send the correct data? – tacoma Apr 19 '16 at 23:24
• Yes, this would require Bob and the clients to be trusted to send the correct hash to the server and not lie about being able to open the file. (so not 100% optimal I guess). BTW: Are we talking about symmetric or asymmetric encryption here? – SEJPM Apr 20 '16 at 9:43

A solution from the top of my head:

Bob will end the server $(Enc(m), h(m))$ where $h$ is a collision resistant hash. Now, Bob will interact with the server and provide a zero-knowledge proof that $m$ is the same one in $Enc(m)$ and $h(m)$.

We note that this verification is in NP (the certificate for the verification is the key used to encrypt $m$). Therefore, it is feasible to do the zero-knowledge proof part in polynomial time.

• The required proof in the question seems to be that Bob has provided a valid out of band key to Alice. Your solution only shows bob has signed garbage. – dave.zap Dec 18 '16 at 23:36
• Verifying this relation would open message to the server, which was asked to not. – Vadym Fedyukovych Jan 18 '17 at 10:06

If Bob attaches a digital signature to the encrypted message, and the server knows Bob's public key for the digital signature, The server would know that it is Bob who sent the message. For decrypting the message, if an algorithm such as aes or des is used, the user is able to decrypt the message with any key, although the decrypted message will probably be different from the original message if the user has the wrong key.

Bob could embed a private key in the encrypted message, and give the public key to the server. The client can prove to the server that they decrypted the message via challenge-response from the server.

• It is not obvious embedding the key would help such a proof in any way. – Vadym Fedyukovych Jan 18 '17 at 10:13
• Why not? What am I missing? – user13741 Jan 18 '17 at 12:22
• Would the message (with the key embedded) be sent to server as a part of such proof? – Vadym Fedyukovych Jan 18 '17 at 16:14
• No. The client gets the private key from the decrypted message. The client can then do a challenge-response with the server and prove it is in possession of the private key, since the server has the public key. – user13741 Jan 18 '17 at 16:44
• Ok, client is proving knowledge of private key to the server keeping public key. – Vadym Fedyukovych Jan 19 '17 at 13:36