I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme.

I don't need a full implementation but I am not sure if what I want is even possible at all. So I am looking for some direction or explanation on why this is impossible (which is my gut feeling).

So let me explain. There a third party that generates a merkle tree(MT=root) with N leaves(L). The encrypting party encrypts a secret(T) with enc(T, MT, Lx) = CT + Decrypt function

The decrypting party publishes CT or a Helper.

Other random parties publish random data that (indirectly) have Hash(CT) in them, creating a hash chain.

Creating HC(Hash(data, Hash(data, Hash(data, Hash(CT))))). The hash chain can be of arbitrary length.

The decryption function should decrypt CT if the leaf is present in the hash chain that is higher then Lx but part of the Merkle tree's root.

So HC(Hash(Lx+N, Hash(data, Hash(data, Hash(data, Hash(CT))))))

In short it means, decrypt if the hash chain, where your 'request' is part of, contains a reveal with an index higher then when then the secret was encrypted.

The idea is to force the publication of the request data.

Is this even remotely possible or are there components in here that are just straight-up impossible?


  • $\begingroup$ Is enc a homomorphic/LWE decryption? What does "CT + decrypt function" mean (does it outputs a decryption function and a ciphertext)? Does "Lx" mean "leaf number $x$"? To clarify your goal without reference to any primitives: We encrypt some secret $T$ with some kind of trapdoor $x$. The ciphertext starts some sort of public protocol, where any party can modify the public value. The ciphertext is not decryptable until someone adds the trapdoor $x$ to the public value, after which anyone can use the public value to decrypt the original ciphertext? $\endgroup$ – Sam Jaques Jun 15 '20 at 15:44
  • $\begingroup$ @SamJaques thnx for replying! I am not really well versed in mathematical notations so excuse me on that. I think you have it right, but the idea is the party who creates the trapdoor has no particular knowledge of T, any number of T's could be part of it. Or none. And yes it is Leaf NR x. And the trapdoor is essentially leaf nr > x. But it is essential that the CT request is part of the hashchain. It is to force the request in the public domain. (Just knowing Lx+n shouldn't be enough to decrypt) $\endgroup$ – ovanwijk Jun 16 '20 at 13:57
  • $\begingroup$ I'm not sure how to force that last requirement: Even if the hash chain is public, couldn't the person with Lx+n compute Hash(Lx+n, hashchain) privately, then use that to decrypt the original ciphertext without ever publishing it? I think the only way to force them to publish the next value of the hash chain would be if it was some sort of multi-round protocol - but the only way to prevent the owner of Lx+n from privately simulating the protocol is if other users have secret data. $\endgroup$ – Sam Jaques Jun 16 '20 at 15:11
  • $\begingroup$ Maybe: people add secret values to the hash chain, so it's $H(s_i, H(s_{i-1},\dots, H(s_1, H(CT))\dots )$. Then once $Lx+n$ is added to the chain, someone reveals $s_j$ for some previous $s_j$, and then there is some protocol that uses $s_j$ and the new hash chain to decrypt the original ciphertext? $\endgroup$ – Sam Jaques Jun 16 '20 at 15:12
  • $\begingroup$ Yes that party could, but this is not the entire method. The idea is to have multiple parties issuing. Besides that is the encrypted secret is only part of what is required to receiver access. There is a private component as well, so only the public component would not be enough. But for the sake of this question I didn't include all of it as the workings depend on if I can get the 'trapdoor' to work. $\endgroup$ – ovanwijk Jun 16 '20 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.