Is there a way to calculate a hash with two people so that no one knows the pre-image but if they get together they do?

Question

I'm trying to find a way to have multi party hash computation, more specifically for SHA256. I want for two people to be able to compute a hash so that none of them knows the pre-image but when they get together they can reconstruct the pre-image.

Is there any known way to do it in general or any hack that can be used in the SHA25 specific case?

Answer 1

One simple option:

1. The preimage consists of 2 segments $M_A$, $M_B$ of 64 bytes each. They are given to or chosen by $A$ and $B$ respectively.
2. $A$ computes the 32-byte $H_A=R(\mathsf{IV},M_A)$ where $R$ is the SHA-256 round function, and $\mathsf{IV}$ is the 32-byte SHA-256 Initialisation Value.
3. $B$ computes the 32-byte $H=R(R(H_A,M_B),“80\ \underbrace{00…00}_{\text{61 zeroes}}\ 04\ 00”)$, where the right string in this formula is the SHA-256 padding for a 128-byte message.

By construction, $H$ is the SHA-256 hash of $M_A\mathbin\|M_B$.

This has drawbacks:

• One can confirm a guess of $M_A$ with knowledge of $H_A$, or/and confirm a guess of $M_B$ with knowledge of $H_A$ and $H$ (but this is seems unavoidable unless we add more communication).
• $A$ must do it's thing first.
• $B$ can choose $M_B$ with knowledge of $H_A$ and thus partially choose $H$. That can be avoided by adding a hash commitment of $M_B$ before step 2.

Answer 2

As mentioned in a comment, hashes cannot reveal preimages. However you could encrypt the message.

If you want the two people be able to jointly reconstruct the message, but not individually, you could do the following. Take your message M of length L and generate a random binary string M1 of length L and M2=xor(M,M1), then have person 1 encrypt M1 and person 2 encrypt M2, each one with their own key. The encrypted messages can now be shared freely. Each one can decrypt their message but this won't reveal any info about M; they would need to recombine their messages to reconstruct M.