I need an encryption operation be 1000-1000000 times more complex than decryption operation. Is it possible to achieve with EC cryptography?

  • 1
    $\begingroup$ What's the purpose of this? You could combine a hash-cash style PoW with encryption. (recently popularized by bitcoin mining) $\endgroup$ – CodesInChaos Jun 27 '18 at 19:07
  • $\begingroup$ @CodesInChaos I need this algo for Proof-of-Replication, for example like Filecoin specify. Interesting idea, but if PoW will be based on input data it will be difficult only first time to encrypt... I need every time encryption to be difficult. $\endgroup$ – k06a Jun 27 '18 at 19:11
  • $\begingroup$ RSA with e=3 and a big modulus should work decently. $\endgroup$ – CodesInChaos Jun 27 '18 at 19:27
  • $\begingroup$ @k06a WRT the PoW, you'll need to be sure that the ciphertext is not copied. So if you need to compare ciphertext then you might as well compare an initial random value as starting point for the PoW. $\endgroup$ – Maarten Bodewes Jun 27 '18 at 23:35

You could use a PoW style system combined with authenticated encryption similar to SIV mode as follows:

Determine the hash of the plaintext, $H$ = SHA512$(P)$

Using a 128-bit nonce $N$, an incrementing 64-bit counter $C$, calculate $S$ = SHA512$(E_k(H) | N | C)$ until you have the required amount of sequential high order bits with a value of 0, 32 for example.

Encrypting the plaintext hash makes sure you will not generate the same secret as someone else using the same plaintext and nonce but with a different key.

Truncate $S$ to the 96 lowest bits, and use that as the nonce for CTR mode to encrypt the data

The ciphertext will be supplied with the $N$ and $C$, after decryption you calculate $H$ then $S$ and verify that it matches BOTH the ctr nonce as well as having the correct 0-bit prefix, you should also authenticate $N$ and $C$ some how.

The scheme is configurable for the workload by choosing the amount of sequential 0-bits in the hash. Using a single iteration of SHA512 (or Blake2b) means one cannot use bitcoin ASIC to accelerate encryption, and that encryption requires high cpu but low memory. Hash calculation is generally much less complex than other algorithms such as ECC.

If you want there to be no way to have the same plaintext/key combo generate the same hash, the nonce can be based on prior data like in a blockchain, or based on the current time (if not fakeable), or a sequential counter. (or a combination of several values). You can also eliminate optimization attacks on the hash message schedule by making $S$ = SHA512$(E_k(C | C) | E_k(H) | N)$, but that is probably not a concern.


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.