# Proving a secret is known without revealing it

Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S from their interaction. Additionally, S could be weak (e.g. "abc123"), so she can't simply send a hash of S to Bob, or any f(S) really since that could be brute-forced.

What are your thoughts on this? Is this even possible?

What you want is the https://en.wikipedia.org/wiki/Socialist_millionaires Problem. This problem is orignally phrased as two people want to verify if they have the same amount of money without revealing anything more. Alice has a value $$A$$ and Bob has value $$B$$ and they want to verify $$A =? B$$ without either side revealing anything more than the result of the check. See the wiki page for algorithm description.

A simple solution can involve Nestor: a trusted third party. Both Alice and Bob send the secret to Nestor and he will verify if they both have the same secret.

In real life this solution is not optimal (what if Nestor is Bob's partner? How can Bob verify that Nestor is not on Alice side?) but can be acomplished if both party trust Nestor enough to stay Neutral.

• You can extend it by having a committee and perform multiparty computations. Not having to trust Nestor alone. – shumy Nov 22 '19 at 11:08
• True, it help to trust this Nestor entity(Nestor don't have to be a physical person then it can be devided in multiple layer). But it's still based on faith about this 3rd entity. – MrHeliose Nov 22 '19 at 11:19

You could use a password-authenticated key agreement protocols, e.g. EKE.

Basically, those aim exactly at your scenario with the goal of establishing a proper key to communicate securely. If you use that key to established a secure channel(e.g. with AES-GCM), and then verify both parties have the same key, you can ensure they both used the same password. Example: Alice sends a random x and Bob answers with x+1 over the established channel.

You can use Password-Based Key Derivation Function (PBKDF2). However, not even this can save you for weak secrets.

Although a bit outdated, you can view some recommended parameters here

• If you suggest a password-based KDF, don't suggest PBKDF2, but instead Argon2. PBKDF2 is the most used one still today, but it is not state-of-the-art any more for a long, long time. – tylo Nov 23 '19 at 10:41
• Also, a password-based KDF doesn't help much if the common secret is really weak. It just acts like a hash function with a scaled up computation time per try. – tylo Nov 23 '19 at 10:46
• I did mention "not even this can save you for weak secrets.". – shumy Nov 25 '19 at 9:32

What are your thoughts on this? Is this even possible?

This is not possible as long as the varification algorithm runs in polynomial time. Even you have said it yourself:

..., or any f(S) really since that could be brute-forced ...

Unless the complexity (time or space) of your verification algorithm doesn't belong in $$P$$ - that is, it cannot end in polynomial time (deterministically). I'm not entirely certain, but one may be able to devise a verification algorithm that 1) takes a secret parameter, 2) ends quickly when correct secret is given, and 3) runs in super-polynomial time (or ideally, exponential time) when wrong secret is given.

But then again, the compromised Bob may abort the verification algorithm if he believes that the algorithm had been running for too long due to wrong input.

• This is incorrect. As noted PAKE basically solves exactly this problem. – Maeher Dec 25 '19 at 11:19

You have the answer. It's hashing. Even if S is weak, it's not possible to determine S from the hash value if the algorithm used is secure enough. Alice can send a SHA-256 hash of S to Bob. If Bob knows S, he can confirm it and Alice has convinced him. Else, we know it's just someone pretending to be Bob.

• SHA-256 is not secure enough for the size of "abc123"! – shumy Nov 22 '19 at 9:57
• Oh, is it? Sorry, I wasn't aware of that. – Tarun Mittal Nov 22 '19 at 10:42