# 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?

• Is Alice trying to convince Bob she knows the value? Are they mutually trying to convince each other they know the same value? Commented Nov 21, 2019 at 14:04
• Socialist millionaires problem? Symmetric/balanced password-authenticated key agreement? Commented Nov 21, 2019 at 14:19
• Does a zero-knowledge password proof (ZKPP) suit your requirements? Commented Nov 21, 2019 at 14:45
• Can Alice learn Bob's secret? If yes, it's trivial in three moves from commitments. Commented Nov 21, 2019 at 14:58

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. Commented Nov 22, 2019 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. Commented Nov 22, 2019 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
Commented Nov 23, 2019 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
Commented Nov 23, 2019 at 10:46
• I did mention "not even this can save you for weak secrets.". Commented Nov 25, 2019 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. Commented Dec 25, 2019 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"! Commented Nov 22, 2019 at 9:57
• Oh, is it? Sorry, I wasn't aware of that. Commented Nov 22, 2019 at 10:42