Given a block of data D: Is there a encryption/decryption scheme that would allow me to perform a resource-intensive (compute/time/memory) encryption of the full data set with a key k, but allow for a rapid decryption of arbitrary constant-length parts (say 64 bytes) of this data set?

Encryption key k is known to the decrypting instance.

Example: Data set is 65536 bytes and will be encrypted by key k. This encryption can be O(n), O(n²)

Now consider the encrypted data to be an array of 1024 x 64 byte data chunks: Can I decrypt an arbitrary chunk D[i] (for i [0,1023]) in O(1) ?

  • 2
    $\begingroup$ Please specify the security requirements, if that includes integrity, if/how that relates to chunks, and by how much ciphertext can be larger than plaintext (overall, or/and chunk per chunk). If we are bound to plaintext and ciphertext of the same size, no cipher is semantically secure nor gives integrity assurance. If we can make each encrypted data chunk larger than the corresponding plaintext, what's asked is easy. $\endgroup$
    – fgrieu
    Commented Apr 8, 2018 at 13:17
  • $\begingroup$ There are no security requirements. There are only computational requirements: The "prover" (the one who shall do encryption and submit parts of the encrypted file) shall not be able to submit "proof" in a comparable time/effort than the verifier (the one who does the decryption of the parts requested from the prover) needs for verification. Key "k" is known to both prover and verifier as well as to the general public. Ideally, ciphertext should be as big as plaintext. But it's possible to allow for a larger ciphertext - in reasonable boundaries (10%?) $\endgroup$
    – Perlator
    Commented Apr 8, 2018 at 13:24
  • $\begingroup$ It sounds like you're actually looking for a proof-of-work and/or a proof-of-knowledge scheme, but you've tried to rephrase it in terms of a "resource intensive encryption" scheme. I suspect your question would be easier to answer if you actually described it in terms of what the prover should be able to convince the verifier of. $\endgroup$ Commented Apr 8, 2018 at 13:34
  • $\begingroup$ Proof-of-Space actually. I am trying to solve a small sub-problem, so I do not think rephrasing the question as you suggest would be fruitful. Prover needs to store D. D needs to be made "individual", so other provers cannot refer to the same D (= encryption), verifier sends a specific data sample request to prover who answers with the requested encrypted chunks. Verifier shall be able to perform verification rapidly. $\endgroup$
    – Perlator
    Commented Apr 8, 2018 at 13:41
  • $\begingroup$ You probably want to look into verifiable delay functions and time-lock puzzles. $\endgroup$
    – ambiso
    Commented Dec 25, 2020 at 0:04

1 Answer 1


The following mostly solves the problem as expanded in comment, but not quite: decryption is not $O(1)$.

We use some purposely slow hash function $H_w$ (where $w$ is a workfactor parameter for e.g. PBKDF2-HMAC-SHA-256, Scrypt, Argon2, Baloon..).

We define parameter $s$, the encryption overhead in bits per chunk; and $t$ which controls the average number $2^t$ of invocations of $H_w$ for (the first) encryption of a chunk. Decryption does just above one invocation on average, and seldom many, when we assume $0<t<s-6$. Example parameters can be $s=32$, $t=20$.

Chunk $c$ is enciphered using AES-CTR, IV of $c\ll8$ (which for up to 4KiB chunk ensures no IV reuse), and an AES key $k_c$ (of say $b=128$ bits) determined as follows:

  • Using auxiliary fast Key Derivation Function, both encrypting and decrypting parties compute $\operatorname{KDF}_k(c)$ of $2b$ bit (where $k$ is the overall encryption key), and split the outcome into $\widetilde{k_c}$ and $k'_c$ each $b$-bit. The auxiliary KDF can be HMAC-SHA-256. The final $k_c$ is determined from $\widetilde{k_c}$ and $k'_c$ as follows.
  • The party that encrypts

    • sets $k_c\gets\widetilde{k_c}$;
    • tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+1\bmod2^b$ and retry (assimilating integers modulo $2^l$ and $l$-bit bitstrings per big-endian conventions);
    • computes $n=k_c-\widetilde{k_c}\bmod2^t$ and includes that 48-bit $n$ as a prefix of the ciphertext chunk;
    • sets $k_c\gets k_c\oplus k'_c$;
    • now has the final $k_c$, and encrypts the chunk.
  • The party that decrypts

    • extracts $n$ from the ciphertext chunk's prefix;
    • sets $k_c\gets\widetilde{k_c}+n\bmod2^b$;
    • tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+2^t\bmod2^b$ and retry (which should happen rarely);
    • sets $k_c\gets k_c\oplus k'_c$;
    • now has the final $k_c$ (always the same as used for encryption), and decrypts the chunk.

For large $k$, the observation of $n$ from ciphertext leaks no useful information to an adversary, assumed with no access to $k$, $k'_c$, and the final $k_c$ (the system is also protected from leaks related to $H_w$, $\widetilde{k_c}$, or intermediary values of $k_c$, e.g. by timing attack). The CTR IV unique per AES block ensures that multi-target search of $k_c$ do not apply.

Possible improvement: we can add one bit of overhead set on encryption to tell if $H_w(\widetilde{k_c}+n)\bmod2^s=0$, which occurs in most cases, and decreases the decryption overhead dramatically.

Note: a former version had no $k'_c$, and $n$ could leak some information. This revised version can thus be safely used with $b=128$, rather than the original $b=192$.

  • $\begingroup$ thanks for the thorough explanation and suggestions. After staring at the proposal for ~ 2 hours I think I began to understand and will try a prototype implementation to check it out. If I hit some wall, I'll ask for clarification. $\endgroup$
    – Perlator
    Commented Apr 9, 2018 at 5:33
  • $\begingroup$ Doing the implementation in a scripting language, I have 2^16 right now, but that's what makes this proposal so interesting, that you can parametrize the "PoW difficulty" when encrypting. Finding good parameters is merely an empirical task. $\endgroup$
    – Perlator
    Commented Apr 9, 2018 at 6:00

Your Answer

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

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