# How to prove that two hashes correspond to the same original message, without using the message to verify?

Let's suppose this:

• Message is "I love crypto.stackexchange.com" (M)
• Bob creates hash H1 with the message M and his private key (Priv)
• Alice receives a message X, and hash H2 with message X and the public key of Bob (Pub)

So from ๐ป1=๐ป(๐,Priv) and ๐ป2=๐ป(๐,Pub) can we tell if ๐=๐? (thanks to @fgrieu)

If it's not possible with a standard hashing function for an asymmetric cryptosystem, in what case it would be possible?

The goal here is to verify the integrity of a message and of the author through the use of two hashes (which serve as proxies of messages and identity of the author).

Thanks!

• @fgrieu I feel this may be some form of a poorly described pairing-based scheme, and it can only be answered by completely disregarding Jeremy's use of terminologies. Also Jeremy can consider check out pairing-based cryptography in addition to hash functions. Does BLS ring a bell? I think CRFG of IETF has a draft on this. Nov 24, 2022 at 13:51
• This is not only paired-based cryptography. Coz the goal here is to use hashs as proxies to compare two messages. A same message will not give the same hash, coz I hash with it a simple string (a public key or private key). Given these two hash, and that one is created with a private key, and another with a public key, how can I verify that they come from the same message ? Thanks Nov 24, 2022 at 15:31
• I use here the private key and public key of same entity as an additionnal string on the message, cause maybe there is a pattern given a public/private key pair that we can substrat from the two different hash and so we can verify/compare more easily that the two hash come from the same message. Nov 24, 2022 at 15:36
• @DannyNiu: no, I fail to see any relation to BLS, if we use "hash" in it's standard meaning. I'm reading the question as: from $H_1=H(M,\text{Priv})$ and $H_2=H(X,\text{Pub})$ can we tell if $M=X$? And the answer is no for $H$ a standard hash, for any asymmetric cryptosystem I can think of (including hash-based, e.g. Lamport signature and friends).
– fgrieu
Nov 24, 2022 at 17:55
• Yes, it's exactly that. Thanks for the mathematic rephrasing of the problem. So if it's not possible with a standard hash for whatever asymmetric cryptosystem, in what case it could be possible ? Nov 24, 2022 at 18:21

I'll rephrase the question as:

• Bob draws a public/private key pair $$(\text{Pub},\text{Priv})$$, and publishes $$\text{Pub}$$
• Bob somewhat obtains $$M$$, then computes and publishes $$H_1=H(M,\text{Priv})$$
• Alice somewhat obtains $$X$$, then computes and publishes $$H_2=H(X,\text{Pub})$$
• A referee Robert, assumed to have unaltered $$H_1$$, $$H_2$$, and $$\text{Pub}$$, wants to determine if $$M=X$$.

That can't be achieved with a regular cryptographic hash for $$H$$ (that is, a hash that aims at behaving as a random oracle), because whatever relation between $$\text{Pub}$$ and $$\text{Priv}$$ making them a public/private key pair is immaterial to the hash, making the equality of $$M$$ and $$X$$ indiscernible from $$H_1$$ and $$H_2$$. As far as I can tell, that's including for hash-based signature like Lamport and friends even if the hash is the one used in the signature system.

But we can craft a special construction for $$H$$ that allows what's asked:

• $$(\text{Pub},\text{Priv})$$ are assumed to be for a signature system such that it's possible to distinguish a public key from a private key. This could be EdDSA.
• We assume a standard hash function $$H'$$ with the same output width as a signature.
• Given input $$(I,K)$$ and asked to compute $$H(I,K)$$, our $$H$$ recognizes if $$K$$ is a private key
• if so, then $$H$$ computes and outputs $$H'(I)\oplus\operatorname{Sign}_{\text{Priv}}(H'(I))$$, so that $$H_1$$ is $$H'(M)\oplus\operatorname{Sign}_{\text{Priv}}(H'(M))$$.
• otherwise, $$H$$ computes and outputs $$H'(I)$$, so that $$H_2$$ is $$H'(X)$$.
• Robert tests if $$M=X$$ from $$(H_1,H_2)$$ as $$\operatorname{Verify}_{\text{Pub}}(H_2,H_1\oplus H_2)$$, where the signature's verification function $$\operatorname{Verify}_{\text{Pub}}(J,S)$$ returns true or false according to if $$S$$ is a signature of $$J$$ under a private key matching $$\text{Pub}$$, or not.

Note: the $$\oplus$$ is here so that the output of $$H$$ is indistinguishable from random for one without a full guess of it's message input $$I$$ (here $$M$$ or $$X$$), as expected from a standard hash. That assumes some plausible hypothesis for the signature, such as this one almost universally met: the signature's message input is only used as part of the input of some hash.

• Wow, that's a brillant answer. You totally understood what I'm trying to do and formulated a very elegant solution. Do you know if this special construct has any name or terminology in cryptographic researchs? so I can explore deeper on it, and try a coding implementation. Thanks again for your time and efforts! Nov 25, 2022 at 19:38
• @JeremyDEX: this is out of my head, so no reference. It's quite a bit artificial, in particular because the public key input is ignored by the hash/the computation Alice performs, and I don't immediately see a practical application. For me, it was an exercise in meeting a spec, for the sake of it, and that was pleasant.
– fgrieu
Nov 25, 2022 at 20:57
• I think the fact the public key is ignored is not a problem here. Coz we can still verify that a specific person hash the good message without using this message. So in my case of thinking about a DSN (decentralized social network), I already have the original hash (computed with good message at first writing) in a blockchain, and I just want to verify that the distributor (who stores message) had retrieved the good message, so we can reward him (and in case it's corrupted or censored, punish him by taking his deposit). Thanks again Nov 26, 2022 at 8:39