<div dir="ltr"><div class="gmail_default" style="font-size:small">A friend posed the following problem for which I have developed a cryptographic solution that I would like your feedback on.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">While working for Alice, Bob has discovered that Konrad is an enemy agent and notified Carol the cop. Carol tells Bob not to tell anyone about the discovery in the hope that surveillance of Konrad will lead to exposure of his co-konspirators. Meanwhile, Bob would like to be able to prove to Alice that he had made the discovery after Konrad has been arrested without revealing anything to Alice before the arrests are made.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The side constraint here being that the scheme must use only simple cryptographic constructs and not require Alice to have an encryption key of any sort.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The commitment string, s = "Konrad is an enemy agent"</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Naive method.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">witness= Base32t ( H (s))</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">where Base32t(x) is a truncated base32 encoding of the octets (x) and H (x) is the SHA2 digest function.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The obvious problem with this approach is that it is subject to a brute force attack. While the commitment string has quite a few characters, many of them are guessable.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Improved method.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">r = random (128)</div><div class="gmail_default" style="font-size:small">witness= Base32t ( SHA-2-512 (s + r)) <br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Adding a sufficiently large nonce to the scheme makes the brute force attack infeasible. This makes things a little harder for Bob as he has to keep the random value in order to be able to make a claim against the witness value.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">I am sure this has been done before, just didn't see it in the books I looked at. Is there an obvious flaw?</div><div class="gmail_default" style="font-size:small"><br></div></div>