Unconditional security against memory-bounded adversaries.
To prove security of a cryptographic system two approaches are commonly used. In the first one, the security of the cryptosystem is based on the difficulty of an underlying computational problem. An alternative approach is based on the notion of information-theoretic (or unconditional) security under the assumption that an adversary's computational power is not limited. The traditional information-theoretic definition of perfect security is well known to lead to perfectly secure but impractical cryptosystems. However, it has been shown recently that by relaxing or removing some assumptions of the original model, a practical provably secure cryptosystem becomes possible. So far two such modifications were proposed, namely relaxing the requirement that perfect security means complete independence between the plaintext and the cryptanalyst's knowledge, or removing the assumption that the adversary receives exactly the same information as the legitimate users. In the paper yet another modification is introduced and shown to allow the realization of unconditionally secure encryption. The key assumption of the new model is that an adversary's memory capacity is limited while nothing is assumed about her computing power. Particularly, it is shown that assuming that all parties can receive a random bit string of length larger than the adversary's memory capacity, practical unconditionally secure private-key encryption and key-agreement (by public discussion) protocol can be implemented. It must be stressed, however, that the proposed scheme requires that a random bit string must be generated and broadcast at a very high rate. An additional distinctive feature of the new approach is that a future breaking of the basic assumption (i.e. future increase of an adversary's storage capacity) does not yield to the breaking of messages encrypted earlier. Some other features as well as possible drawbacks of the approach are also discussed. For the entire collection see [Zbl 0870.00047].
- Non-interactive timestamping in the bounded-storage model
- Analyzing security protocols using time-bounded task-PIOAs
- Fine-grained secure computation
- Encryption against storage-bounded adversaries from on-line strong extractors
- One-way functions using algorithmic and classical information theories
- Tight time-space lower bounds for finding multiple collision pairs and their applications
- Resource-restricted cryptography: revisiting MPC bounds in the proof-of-work era
- On the streaming indistinguishability of a random permutation and a random function
- Separating adaptive streaming from oblivious streaming using the bounded storage model
- Secure multiparty computation in the bounded storage model
- Everlasting UC commitments from fully malicious PUFs
- Incompressible cryptography
- Authentication in the bounded storage model
- Interactive non-malleable codes
- Data-independent memory hard functions: new attacks and stronger constructions
- On the (im)possibility of non-interactive correlation distillation
- Long term confidentiality: a survey
- Fine-Grained Cryptography
- Big-key symmetric encryption: resisting key exfiltration
- Gambling, computational information and encryption security
- A new spin on quantum cryptography: avoiding trapdoors and embracing public keys
- Bit commitment in the bounded storage model: tight bound and simple optimal construction
- The symbiosis between collision and preimage resistance
- scientific article; zbMATH DE number 1346368 (Why is no real title available?)
- Aspects concerning entropy and utility
- Bounded memory Dolev-Yao adversaries in collaborative systems
- Public-key cryptography based on bounded quantum reference frames
- Using quantum key distribution for cryptographic purposes: a survey
- Information Security and Privacy
- Basing Weak Public-Key Cryptography on Strong One-Way Functions
- A Single Initialization Server for Multi-party Cryptography
- Fine-grained cryptography revisited
- Long-term security and universal composability
- scientific article; zbMATH DE number 7758323 (Why is no real title available?)
- Rate-1 incompressible encryption from standard assumptions
- Speak much, remember little: cryptography in the bounded storage model, revisited
- Information-Theoretic Security of Cryptographic Channels
- Memory-sample lower bounds for learning with classical-quantum hybrid memory
- Fine-grained non-interactive key-exchange without idealized assumptions
- Zero-knowledge in streaming interactive proofs
- On bounded storage key agreement and one-way functions
- How to verify that a small device is quantum, unconditionally
- New constructions of pseudorandom codes
- Quantum cryptography beyond quantum key distribution
This page was built for publication: Unconditional security against memory-bounded adversaries.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4364559)
