5
$\begingroup$

Are there encryption schemes with which it takes (significantly) longer to encrypt than to decrypt?

I am thinking of a specific situation in which a server continuously receives encrypted messages from different senders and has to decrypt each single one of them. To cope with the possibly large amount of messages the decryption process should be fast. However, to avoid that the senders send a large amount of automatized messages, the encryption process should take much longer.

Ideally, the time to encrypt a single message should still be acceptable, but it should become unfeasible to send a large amount of messages in a short time. The specific type of encryption does not matter and the server can be assumed to have all the necessary keys for the decryption of the messages (without the key, of course, the decryption process should take much much longer!).

In other words, sending a message should be "expensive", while receiving the message should be "cheap". Is there an encryption scheme that shifts the computational load to the side of the sender, so that it takes longer to encrypt than to decrypt a message?

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Proof-of-work_system ​ ​ $\endgroup$
    – user991
    Jul 13, 2016 at 16:55
  • $\begingroup$ I made a tunable slow encryption function recently. It's certainly not standardized (and therefore to be considered “unsafe until further notice’), but the idea might set you in the right direction. Disclaimer: This is from my personal github. $\endgroup$
    – Ella Rose
    Jul 13, 2016 at 17:08
  • 1
    $\begingroup$ What about applying a PoW (with fast verification) on the cipher text so the server can verify before attempting decryption $\endgroup$
    – SEJPM
    Jul 13, 2016 at 18:28
  • 1
    $\begingroup$ This seems more easily solved at a different layer. You can throttle connections per-host with, e.g., iptables. This also has the advantage that it can't be trivially bypassed by an attacker (who can just flood you with random garbage instead of valid messages). $\endgroup$
    – Stephen Touset
    Jul 13, 2016 at 18:28
  • 2
    $\begingroup$ @StephenTouset Yes. My comment was not supposed to be a recommendation on what to implement; it should merely show that "encryption takes longer than decryption" does not necessarily imply "overwhelming the server is expensive". $\endgroup$
    – yyyyyyy
    Jul 13, 2016 at 19:19

3 Answers 3

Reset to default
6
$\begingroup$

Rather than using a form of encryption which is slow in one direction, you could use a proof-of-work function instead, as Ricky Demer pointed out in the comments. This allows you to freely tune the slowdown while still using normal, widely accepted encryption and authentication algorithms.

For example, you could make the sender look for a partial preimage for a given hash value that the server decides. Verifying that such a preimage has been found is fast, while looking for it can be made arbitrarily slow.

There are also non-cryptographic solutions to the problem, of course, which you may find or ask about on Server Fault.

Improve this answer
$\endgroup$
6
$\begingroup$

Perhaps not of relevance if the question is meant in a purely thoretical (i.e. asymptotical) sense, but the CBC encryption mode is inherently sequential, while decryption can easily be performed in parallel.

Improve this answer
$\endgroup$
5
$\begingroup$

In lattice-based encryption schemes, the encryption is often slower than the decryption (not artificially, but just as the natural way it works). See this paper Efficient Software Implementation of Ring-LWE Encryption (encryption is 3 times slower than decryption).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is of course not a scheme where you have a relatively small difference in encryption / decryption which isn't tweakable. So while it may work in some use cases - upvoted for that reason - this should not be considered a generic answer. $\endgroup$
    – Maarten Bodewes ♦
    Jan 18, 2018 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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