# How can Alice and Bob prove that they share a file?

Carl asks Alice and Bob if they have a file `f` such that for a secure cryptographic
hash function `h`, `h(f) = K`. Both claim to have `f`, but they can't show the file.

Carl doesn't believe them. He can ask further questions to Alice and Bob, although
they can secretly talk to each other (note that even if Alice or Bob have `f`, they
can't show `f` to each other). Could Carl discover whether both have `f`?
Could Carl discover whether some of them has `f`?

• Sounds like a homework question. What work have you done to try to answer this question yourself? – schroeder Mar 17 '15 at 21:42
• pssst: the hint is for each to sign the file with their own private keys .... what they do next I leave to your work ... – schroeder Mar 17 '15 at 21:45
• the concept you are learning is called non-repudiation – schroeder Mar 17 '15 at 21:54
• @schroeder I couldn't find the solution. I guess I'm too slow for that hint. Note that Carl doesn't know the content of `f`. My assumption was that Carl can't know anything, but I don't know about cryptography. (Btw I'd read the crypt related pages from the wikipedia. Yes, it's not the best. It's not a homework). – user70561 Mar 17 '15 at 23:28
• read about how you achieve non-repudiation and signing – schroeder Mar 18 '15 at 3:10

Carl can ask Alice and Bob (independently) to calculate hashes of specific fileparts and compare the results. For example C asks A to calc h(f[0-100]) and receives h' then C asks B to do the same and B returns h''. If h' == h'' they both have the same knowledge about this part of f. You can repeat this for different sections of the file.

Notice: If A and B cooperate (and want to trick C) and only one of them has the file there is no way for C to tell if they both have f or of they're just cooperating.

• with the element that A and B can communicate secretly, I think this approach is defeated – schroeder Mar 18 '15 at 4:24
• As I mentioned in the last paragraph. If A and B cooperate against C there is NO way for C to tell! It depends on the problem user70561 is trying to solve if this does or doesn't matter! – wischi Mar 18 '15 at 4:36
• @wischi the problem is the worst case scenario. If A and B cooperate, or C has `f` it's easy to resolve. What I'm not sure if there is some hash function `f` with some property that could led C to know something. (When you say that is A and B cooperates, is it necessary that one of them have the file `f`?) – user70561 Mar 18 '15 at 8:35
• Note that there might be a MITM: Alice+Bob try to prove it to Carl, but Carl with Diana try to prove it simultaneously to Elizabeth. To mitigate such issue, A+B would have to add an identification of Carl as a "salt". But chosing a proper identifier might be tricky. Moreover you should be aware of Length Extension Attack, but this is rather a technical detail. – v6ak Mar 18 '15 at 10:23

If Alice and Bob can talk to each other secretly, and are willing to collude, there is no way.

Assuming we know that at least one of them has the file (lets say Alice), then any question that Bob could answer if he had the file, he could forward to Alice to answer - Bob would be a "man in the middle".

In any case, if they were willing to collude, they could share the file. Or, since there is nothing identifiable about the file, they could agree that the file is 0 bytes long, thereby instantly "having the same file" which they could answer any question about - any checksum, any computation.

It seems pointless to find out if they "have the same file", unless there is something specific about that file, that differentiates it from any other file.

A knows `Sa`

B knows `Sb`

Goal: Prove `Sa == Sb`

Given a one-way function `H` with the following properties:

`H(x, y) = H(y, x)` (Commutative)

`H(H(x, y), z) = H(x, H(y, z))` (Associative)

C generates random `k`, `l`, `m`, `n`

C shares `k` to A only and `l` to B only, then:

A computes `Saₖ = H(Sa, k)`

B computes `Sbₗ = H(Sb, l)`

A shares `Saₖ` publicly

B shares `Sbₗ` publicly

A now knows `Sa`, `k`, `Saₖ`, `Sbₗ`

B now knows `Sb`, `l`, `Saₖ`, `Sbₗ`

C computes `Saₖₘ = H(Saₖ, m)`

C computes `Sbₗₙ = H(Sbₗ, n)`

C shares `Saₖₘ` and `Sbₗₙ` publicly

A now knows `Sa`, `k`, `Saₖ`, `Sbₗ`, `Saₖₘ`, `Sbₗₙ`

B now knows `Sb`, `l`, `Saₖ`, `Sbₗ`, `Saₖₘ`, `Sbₗₙ`

A computes `Sbₗₙₖ = H(Sbₗₙ, k)`

B computes `Saₖₘₗ = H(Saₖₘ, l)`

A shares `Sbₗₙₖ` publicly

B shares `Saₖₘₗ` publicly

A now knows `Sa`, `k`, `Saₖ`, `Sbₗ`, `Saₖₘ`, `Sbₗₙ`, `Saₖₘₗ`, `Sbₗₙₖ`

B now knows `Sb`, `l`, `Saₖ`, `Sbₗ`, `Saₖₘ`, `Sbₗₙ`, `Saₖₘₗ`, `Sbₗₙₖ`

C computes `Saₖₘₗₙ = H(Saₖₘₗ, n)`

C computes `Sbₗₙₖₘ = H(Sbₗₙₖ, m)`

C compares `Saₖₘₗₙ` and `Sbₗₙₖₘ` must be equal.

Due to commutativity and associativity, we know that `Saₖₘₗₙ == Sbₗₙₖₘ` if `Sa` and `Sb` are equal.

This is inspired by n-ways Diffie-Hellman-Mekrle Key Exchange, but how the things are put together is of my own invention just a few hours ago without doing mathematical proofs or proper analysis, there is probably a glaringly obvious hole there that I didn't just thunk about.

The `H` function in Diffie-Hellman would probably be usable here, with a little bit of modification.

Assumptions:

• A and B cannot share `Sa` and `Sb` with each other
• A and B cannot share `k` and `l` with each other
• C has a way to verify that A and B are doing their calculations using the correct file (they can't collude to both use another file instead of `Sa` and `Sb` to fool C)
• C has a way to make it impossible for A and B to leak `k`, `l` to each other. For example, `k`, `l` may be stored in a hardware token that can be be unlocked by a password known only to C.
• A, B, and C does not all have to be at the same place at the same time

Disclaimer: I'm not a mathematician or cryptographer, and I don't play as one on TV. Inventing your own cryptography scheme may be harmful to your security. You agree to assume all risk from the use of this material, and release me from any responsibility for any harm caused, real or imagined. No representation or warranty, express or implied, with respect to the completeness, accuracy, fitness for a particular purpose, or utility of these materials or any information or opinion contained herein.