Paper 2023/409

Multi-Instance Randomness Extraction and Security against Bounded-Storage Mass Surveillance

Jiaxin Guan, Princeton University
Daniel Wichs, Northeastern University, NTT Research, Inc.
Mark Zhandry, NTT Research, Inc.

Consider a state-level adversary who observes and stores large amounts of encrypted data from all users on the Internet, but does not have the capacity to store it all. Later, it may target certain "persons of interest" in order to obtain their decryption keys. We would like to guarantee that, if the adversary's storage capacity is only (say) $1\%$ of the total encrypted data size, then even if it can later obtain the decryption keys of arbitrary users, it can only learn something about the contents of (roughly) $1\%$ of the ciphertexts, while the rest will maintain full security. This can be seen as an extension of incompressible cryptography (Dziembowski CRYPTO '06, Guan, Wichs and Zhandry EUROCRYPT '22) to the multi-user setting. We provide solutions in both the symmetric key and public key setting with various trade-offs in terms of computational assumptions and efficiency. As the core technical tool, we study an information-theoretic problem which we refer to as "multi-instance randomness extraction". Suppose $X_1, \ldots, X_t$ are correlated random variables whose total joint min-entropy rate is $\alpha$, but we know nothing else about their individual entropies. We choose $t$ random and independent seeds $S_1, \ldots, S_t$ and attempt to individually extract some small amount of randomness $Y_i = \mathsf{Ext}(X_i;S_i)$ from each $X_i$. We'd like to say that roughly an $\alpha$-fraction of the extracted outputs $Y_i$ should be indistinguishable from uniform even given all the remaining extracted outputs and all the seeds. We show that this indeed holds for specific extractors based on Hadamard and Reed-Muller codes.

Note: Renamed "somewhere randomness extraction" to "multi-instance randomness extraction" to avoid potential confusion with "somewhere extractors", which is a different object.

Available format(s)
Publication info
Information-Theoretic SecurityRandomness ExtractorsLeakage ResistanceIncompressible Cryptography
Contact author(s)
jiaxin @ guan io
danwichs @ gmail com
mzhandry @ gmail com
2023-06-05: last of 2 revisions
2023-03-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiaxin Guan and Daniel Wichs and Mark Zhandry},
      title = {Multi-Instance Randomness Extraction and Security against Bounded-Storage Mass Surveillance},
      howpublished = {Cryptology ePrint Archive, Paper 2023/409},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.