13
$\begingroup$

Imagine this situation:

  • Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$
  • Bob has $X$ and $Y$
  • Alice and Bob can communicate with each other
  • Bob wants to know whether Alice holds the key which encrypts $X$ into $Y$

In this situation, Can Alice prove that she has $K$ without showing $K$?
and if so, how to do it?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Any proof involving only a single pair $(X,Y)$ cannot prove Alice has a specific $K$. She could have $K'$ that also encrypts $X$ as $Y$, of which there are many for AES-256. (This may not matter, depends on why Bob wants the proof.) $\endgroup$ – otus Feb 17 '18 at 12:05
  • $\begingroup$ Could Bob not ask Alice to encrypt Y with K again and get her send him the result, or a signed hash of it? $\endgroup$ – James Feb 17 '18 at 12:52
  • 1
    $\begingroup$ @James: no; Bob would have no way to check the result of the encryption of Y. $\endgroup$ – fgrieu♦ Feb 17 '18 at 13:54
  • $\begingroup$ Agree with @otus, the problem might not be well-defined from a crypto aspect, depending on size of X. If X and Y are only 128 bits, then an Adv might be able to find a collision on K in 2^64 time. In this case, there is no "knowledge", since anyone can find a K "efficiently". $\endgroup$ – redplum Feb 19 '18 at 4:05
14
$\begingroup$

Yes she can. She would do so by relying on a boolean circuit that takes $K$ as input, uses it to encrypt the plaintext $X$, compares it to $Y$, and outputs $1$ if and only if the comparison succeeds. Given such a boolean circuit $C$ (that both parties can construct), Alice must prove that she knows an input $K$ to $C$ so that $C(K) = 1$.

The task of proving knowledge of a witness for a relation described by a boolean circuit (in zero-knowledge, hence without leaking any information about the witness) has been studied a lot in the cryptographic community. Several protocols exist for this task, Zkboo is one example. It has three moves, and is based on the MPC-in-the-head technique introduced in this seminal paper.

Other solutions (see also this paper and the related but somewhat different solution presented in this paper) achieve a comparable efficiency, and are based on garbled circuits: Alice will hand Bob a "garbling" of $C$, which takes as input an encoding of her witness $K$, and evaluates the circuit on $K$ in a hidden way, and outputs $C(K)$ (the details are quite technical, so I'll stick to this high level explanation unless you want a deeper overview of how it works).

EDIT: corrected the statement that Zkboo was based on garbled circuit, I had confused it with another paper, thanks to redplum for pointing this out.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Zkboo is not based on garbled circuit but mpc in the head. You might be thinking of another paper by them. $\endgroup$ – redplum Feb 18 '18 at 4:45
  • $\begingroup$ You're right! I had other papers in mind that achieve the same goal, using garbled circuits. I'll edit the answer and clarify the existence of both approaches. $\endgroup$ – Geoffroy Couteau Feb 18 '18 at 10:21
3
$\begingroup$

I had never heard that such proof could be made by message exchange, as outlined in Geoffroy Couteau's answer; a very nice achievement! I describe only a classic method: a third party trusted by both; and a hardware-assisted variant: a Smart Card prepared by Bob and only very marginally trusted by Alice.

One solution involves a third party trusted by both Alice and Bob to

  • receive $K$ handed by Alice;
  • receive $X$ and $Y$ handed by Bob;
  • verify that $Y$ checks under $K$ and deciphers as $X$;
  • destroy $K$, $X$ and $Y$;
  • reveal the outcome of the verification to Bob and Alice as a yes or no answer.

Some possible extras:

  • Alice additionally gives $Y$ (or a hash of $Y$) to the third party, with instruction to abort without using $K$ unless the $Y$ submitted by Bob matches (or hashes to something that matches the hash). This prevents Bob from using the third party as an oracle to test if some other $Y'$ is valid under key $K$ and deciphers to some $X'$.
  • Bob does not give $X$ to the third party, but instead gives a random $R$ and a MAC of $X$ under key $R$. After deciphering $X$ from $Y$, the third party checks the MAC, and otherwise answers no. This gives the insurance that even if the third party is dishonest, what Bob does can't disclose $X$ to a party without access to $K$.

The third party can be replaced by a Smart Card prepared by Bob, that Alice needs to trust only marginally.

  • Bob chooses a secret $S$; computes its hash $H$; writes and load in the Smart Card a program that
    • outputs $H$;
    • accepts $K$;
    • tests if $Y$ checks under $K$ and deciphers to $X$ (the check of $X$ can be indirectly using the above MAC technique);
    • in the affirmative only, output $S$.
  • Bob gives the Smart Card to Alice.
  • Alice convince herself that the Smart Card has no way to communicate with Bob (of course she uses the Smart Card with her own PC and Smart Card reader, perhaps she does that only in a Faraday cage).
  • Alice obtains $H$ from the Smart Card, then gives $K$ to the Smart Card, and gets some answer $A$, normally $S$; she then destroy the Smart Card.
  • Alice checks that $A$ hashes to $H$, and only in the affirmative reveals $A$ to Bob.
  • Bob checks that $A$ matches $S$. This is proof to him that Alice knows $K$ (or managed to extract $S$ from the Smart Card otherwise).

Note: $H$ is a commitment of $S$, which is necessary to avoid that the Smart Card outputs some $A$ that is revealing about $K$.

Improve this answer
$\endgroup$
-1
$\begingroup$

The Socialist Millionaire Protocol was designed to do do just this. It is also very commonly used in OTR messaging to do a question based authentication of the person you are communicating with (e.g. ask the person the question and validate that you both give the same answer based, without revealing what the answers were to each other).

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ The socialist millionaire problem works here if we assume that Bob also holds the secret key, which is not the case in this question. $\endgroup$ – Geoffroy Couteau Feb 17 '18 at 17:06
  • $\begingroup$ @GeoffroyCouteau If Bob is holding the plain text and cipher text, I thought that it necessarily follows that he holds the key. AES encryption is accomplished with XOR. $\endgroup$ – Q-Club Feb 17 '18 at 21:18
  • $\begingroup$ @GeoffroyCouteau Alice hashes the key, shows Bob the digest, and it's done? $\endgroup$ – Q-Club Feb 17 '18 at 21:21
  • 3
    $\begingroup$ @Q-Club no to all of that. There is a xor in AES-GCM, but the data being xor'd isn't the key, and can't be tractably reversed to get the key. And if Bob had the key, the problem statement would say so. $\endgroup$ – hobbs Feb 17 '18 at 21:28
  • 3
    $\begingroup$ (If just having a single instance of plaintext and ciphertext immediately gave you the key, AES would be terribly weak). $\endgroup$ – hobbs Feb 17 '18 at 21:31

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.