Score:0

Can two parties with a common secret jointy issue a commitment?

sy flag

Let's say parties A and B have a common secret $k$. Is there a protocol where both the parties jointly release a commitment to $k$ so that later on, neither A or B can deny what the common secret was?

Edit: Specifically, I am interested in the scenario where one of the parties can be malicious and we need to prove to a third party C that a commitment $\Phi$ is actually that of the common secret $k$.

If A and B share two commitments separately, then the malicious party can share a commitment to a completely different $k'$. C would have know way of knowing which one is the commitment to $k$.

poncho avatar
my flag
Obviously, if they both have the secret, they could individually issue commitments to it. Why isn't that sufficient? What else do you require? For example, a proof that they committed to the same thing?
Ordinary avatar
sy flag
One of the parties (say A) is malicious. If B commits to $k$ truthfully and A commits to a different $k'$ (not known to B), there is no way for a third party C to decide who is being truthful, ie, shared the commitment to $k$ - the common secret. Is there a way to ensure that C can be convinced that a commitment is of the common secret $k$?
Score:1
my flag

Another, possibly simpler, solution is this:

  • $A$ and $B$ get together and jointly select a large, fixed sized random value $r$, and publish $\text{Hash}( k || r )$

  • They both sign (using their private signature keys) the string $\text{Hash}( k || r )$; both signatures are also published.

Either can open the commitment by publishing $k$ and $r$; anyone can verify that they hash to the commitment. And, anyone with $A$ and $B$'s public keys can verify the signatures.

Obviously, as there's only one commitment which can be opened one way (assuming that $\text{Hash}$ is collision resistant, and $r$ has a well-known length; e.g. it's always 256 bits), there is no opportunity for either side to lie. The only think I can think of for a malicious actor can do is to claim "hey, someone stole my private key; I didn't sign that commitment"

Score:0
my flag

Well, one approach would be to have both parties generate and publish commitments, and that they jointly publish a zero-knowledge-proof that both commitments are to the same value.

Here's one approach at doing that: both $A$ and $B$ generate and publish Pedersen commitments; for example, $A$ selects a random value $r$ and publishes $C_A = g^k h^r$, while $B$ selects a random value $s$ and publishes $C_B = g^k h^s$ (where this is done in a group where discrete logs are hard, and no one knows the discrete log of $h$ with respect to $g$).

The zero-knowledge-proof that they're committing to the same value is a proof of knowledge of a value $v$ such that $C_A C_B^{-1} = h^v$ (which, for honest commitments, is $v = r-s$); if one side commits to another value, no one will know such a value $v$, and hence no one (not even $A, B$ jointly) will be able to publish such a proof. Note that $C_A C_B^{-1}$ can be computed by anybody with access to the two commitments.

It would appear to be fairly simple for the two sides to work together to generate such a Schnorr proof:

  • $A$ selects a random value $a$ and sends $h^a$ to $B$; $B$ selects a random value $b$ and sends $h^b$ to $A$.

  • They both compute the common value $c = \text{Hash}(h^a h^b)$

  • $A$ computes $x = a + c r$, and publishes $x, h^a$. $B$ computes $y = b - c s$, and publishes $y, h^b$.

The pair $h^ah^b, x+y$ would be a valid Schnorr proof; the verifier would check if $h^{x+y} = (h^ah^b) (C_A C_B^{-1})^{\text{Hash}(h^ah^b)}$

Now:

  • I believe that access to the 'half-proofs' $x, h^a$ and $y, h^b$ does not provide any insight into either commitment.

  • This protocol is protected from a single malicious actor; if (say) $A$ was honest, then if the zero-knowledge proof verifies, the $B$ must have committed to the same value. Actually, even if both sides are malicious, they still cannot individually commit to different values.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.