Rapid partial block decryption of compute intensive full encryption 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) ?
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&lt;t&lt;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$.