Witness Encryption

Witness Encryption is an encryption scheme which allows anyone who has a solution to some problem (a witness) to decrypt the encrypted message.
Witness encryption is especially useful in decentralized apps, since you can’t trust anyone to reveal the key when some conditions are met.

Examples for uses of witness encryption are time lock encryption (the witness can be for example a chain of bitcoin blocks, since block generation takes approximately 10 minutes).

Another is when you have a decentralized text adventure game, and you want to prevent brute forcing the game. The problem is that since it is decentralized, anything could be emulated locally. You could have a smart contract for any decision point, but reveal the the next smart contract only to someone who committed to certain choice, using witness encryption, if you can prove you committed to a certain choice on chain, you can decrypt the address of the next smart contract decision point. Add to that a need to pay some fee each time you restart the game, and you made brute forcing not worth it.

There is no secure implementation to witness encryption, but I think maybe we can create a contest for one. This paper for example: How to build time-lock encryption | SpringerLink suggest a scheme which I think is secure. (it’s also the one who brought the idea of using bitcoin blocks for time lock encryption). The main problem, if I understand correctly, is that there is no efficient secure instance of Cryptographic MultiLinear Maps yet. But as that paper suggests, if you use snarks it would make the witness shorter, which might make up for the inefficiency of current secure cryptographic multilinear maps instances.

What do you think?


I suggested the similar implementation i.e. Time-lock encryption in the SMM Telegram chat. Personally, I support the ideas because it can be useful for the so many things even for the Free TON blockchain network especially, different contests can be run effectively. I expect all the developers to get rolled out at the one place.

This is great direction to go! Please prepare a draft contest. It would be much better to do it not as a pure code contest but as a real game example with frontend as well.

1 Like

I’m waiting for @nemo to check if their crypto3 can help with that.
I’m not sure jumping to applications is the right thing to do, remember that witness encryption was never used before, the same is true for cryptographic multilinear maps. Maybe it would have to be multi stage, first develop multilinear maps, then, on top of that, witness encryption.

Just a little bit of clarification why am I taking a look into if there is anything crypto3 can help with regarding this. In case it does, we could start proving and verifying all the witness encryption operations almost right after it gets done, out of the box.