13
$\begingroup$

I recently skimmed over tho papers on time-lock encryption:

To get the data released on a specific point in time they'd extract some information from the blockchain, which can only be obtained if the blockchain has reached a certain size) and use this as a witness for witness encryption:

Is there any "easy" instance of witness encryption or can it be otherwise "simply" explained or visualized?


Requested level and amount of detail: Enough to understand how easy versions work and what they actually do. Knowledge of cryptographic standard primitives (hash, cipher, AE, …) can be assumed if neccessary.

$\endgroup$
9
$\begingroup$

In very short:

Assume you have an NP problem, stated as some condition to be met. Since it is a NP condition, the computational complexity to find a satisfying input (called the witness for the language) grows quite fast.

The setup of such an encryption scheme is based on a multilinear map (a generalization of a bilinear map, but with arbitrary many inputs). And then you only need to know the NP statement to encrypt something, but you need a witness of the according length to decrypt the ciphertext again.

The actual construction is really complex, and I don't think you can explain that in easy terms. But it is based on multilinear maps, and look at DrLecters answer in "What are Cryptographic Multi-linear Maps?" for more information on that. Current constructions build on fully homomorphic encryption.

$\endgroup$
  • 3
    $\begingroup$ "Current constructions build on fully homomorphic encryption." Now I understand why I don't want to understand witness encryption :) $\endgroup$ – SEJPM Jun 19 '15 at 20:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.