encryption – Private key Proof of Ownership

If Bob is never allowed to see Alice’s public key, ever, then there’s no way for Alice to prove to Bob that she owns A*, if Bob only has access to h(A) and h is a general-purpose hash algorithm. Bob has insufficient information.

The only way to make this work is for Alice to send Bob A as part of the proof. He can then compute h(A) and compare it against his known hash. Afterwards, Bob can send a unique challenge C – a sufficiently long random string will do just fine – which Alice must sign with her private key, i.e. C* = s(C,A*), and return the signature to Bob. Bob can then validate the signature using A. Bob now has proof that Alice has A*. The hash h(A), distributed over some trusted channel, is an anchor through which trust is established.

This type of scheme is quite common in scenarios where you want to establish secure communication between any pair (or n-tuple) of parties in a large pool of users, where distributing all of the keys for all of the users is prohibitive and inefficient due to their size and the number of users. Instead, one can distribute the hashes of the keys associated with users, over some trusted channel, then have the users transmit their public keys to each other over an untrusted channel.

One thing to watch out for is that the security of the entire system hinges on there being no collision attacks on h. If an attacker can come up with some keypair {A', A'*} where h(A') = h(A), then they can impersonate Alice. This is possible in practice for MD5 and SHA-1, and theoretically possible for other hash functions that use Merkle-Damgård construction, such as SHA-2. It would be better to use SHA-3, which uses a different construction and is expected to have better resistance to this class of attack.