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.