Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Hyper-encryption against Space-Bounded Adversaries from On-Line Strong Extractors

Chi-Jen Lu

Published Jan 1, 2002• 37 citations
Publisher
DOI
10.1007/3-540-45708-9_17

Related papers

Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors

Chi-Jen Lu

Journal of Cryptology•Aug 6, 2003•71 citations

Optimization of Key Distribution Protocols Based on Extractors for Noisy Channels within Active Adversaries

Viktor Yakovlev, Коржик Валерий Иванович, Mihail Bakaev +1 more

Lecture notes in computer science•Jan 1, 2012•1 citation

Two-Source Extractors Secure against Quantum Adversaries

Roy Kasher, Julia Kempe

Lecture notes in computer science•Jan 1, 2010•11 citations

Hyper-Encryption and Everlasting Security

Yan Zong Ding, Michael O. Rabin

Lecture notes in computer science•Jan 1, 2002•76 citations

Quantum-Proof Randomness Extractors via Operator Space Theory

Mario Berta, Omar Fawzi, Volkher B. Scholz

Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC'07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.

arXiv:1409.3563•IEEE Transactions on Information Theory•Nov 11, 2016•23 citations

Public-Key Encryptions Tolerating Adaptive and Composable Adversaries

Huafei Zhu

Lecture notes in computer science•Jan 1, 2011•0 citations
Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC'07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.