Are there cryptographic scheme where encryption is sequential and take a long time (in a way that it can be quantified) while instead decryption with a secret key takes very short time?

Some sort of reverse time-lock encryption where it takes a long time to decrypt rather than encrypt?

(Either with symmetric or asymmetric)

  • 1
    $\begingroup$ Generate a random key, encrypt the data, discard some number of bits from the key and publish it. You can't gate on the amount of time, but you can gate on "number of operations required, on average". Choose that number based on the number of ops/s you anticipate the other party will commit to decrypting the payload (taking Moore's law into account). $\endgroup$ – Stephen Touset Mar 16 '17 at 23:19
  • 1
    $\begingroup$ The question is not clear: It appears to be asking for an encryption technique that is slow, but then goes on to imply that decryption should be slow, rather then encryption? If "normal" "time-lock" encryption offers fast encryption and slow decryption, then does "reverse" time-lock encryption offer slow encryption with fast decryption? $\endgroup$ – Ella Rose Mar 16 '17 at 23:58
  • $\begingroup$ yes @EllaRose. I have updated my question $\endgroup$ – graphtheory92 Mar 17 '17 at 0:13
  • $\begingroup$ I just have to ask: Why? $\endgroup$ – Elias Mar 17 '17 at 11:02

One obvious way (which is a variant of the normal time-lock encryption technique) is to do RSA encryption, with a truly huge $e$.

That is, to encrypt, you compute $M^{3^\lambda} \bmod N$; by making $\lambda$ sufficiently large, you can make this take a long time.

To decrypt, you would have precomputed the values $(3^\lambda)^{-1} \bmod p-1$ and $(3^\lambda)^{-1} \bmod q-1$, which can be done in $O(\log \lambda)$ time; you proceed with RSA decryption in the standard way.


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.