Entropically secure encryption is a way to encrypt a large plaintext with a small key and still have information-theoretic security, thus in a certain sense circumventing Shannon's result that perfect encryption requires the key to be at least as long as the entropy of the plaintext. Entropically secure encryption is not perfect, and it works only if a lower bound is known on the entropy of the plaintext. The typical implementation is to expand the short key to the size of the plaintext, e.g. by multiplication with a public random string, and then use one-time pad encryption. This works in the classical as well as the quantum setting. In this paper, we introduce a new key expansion method that is faster than existing ones. We prove that it achieves the same security. The speed gain is most notable when the key length is a sizeable fraction of the message length. In particular, a factor of 2 is gained in the case of approximate randomization of quantum states.
Entropically secure encryption is a way to encrypt a large plaintext with a small key and still have information-theoretic security, thus in a certain sense circumventing Shannon's result that perfect encryption requires the key to be at least as long as the entropy of the plaintext. Entropically secure encryption is not perfect, and it works only if a lower bound is known on the entropy of the plaintext. The typical implementation is to expand the short key to the size of the plaintext, e.g. by multiplication with a public random string, and then use one-time pad encryption. This works in the classical as well as the quantum setting. In this paper, we introduce a new key expansion method that is faster than existing ones. We prove that it achieves the same security. The speed gain is most notable when the key length is a sizeable fraction of the message length. In particular, a factor of 2 is gained in the case of approximate randomization of quantum states.
Abstract Entropically secure encryption is a way to encrypt a large plaintext with a small key and still have information-theoretic security, thus in a certain sense circumventing Shannon’s result that perfect encryption requires the key to be at least as long as the entropy of the plaintext. Entropically secure encryption is possible when a lower bound is known on the entropy of the plaintext from the adversary’s point of view. The typical implementation is to expand the short key to the size of the plaintext, e.g. by multiplication with a public random string, and then use one-time pad encryption. This works in the classical as well as the quantum setting. In this paper, we introduce a new key expansion method that is faster than existing ones. We prove that it achieves the same security. The speed gain is most notable when the key length is a sizeable fraction of the message length. In particular, a factor of 2 is gained in the case of approximate randomization of quantum states. In the classical case, we obtain a reduction of the ciphertext size.
Perfect encryption of a qubit state using the Quantum One-Time Pad (QOTP) requires 2 classical key bits. More generally, perfect QOTP encryption of a 2n-dimensional state requires 2n classical bits. However, almost-perfect encryption, with information-theoretic security, can be achieved with only little more than 1 key bit per qubit. In this paper we slightly improve the key length. We show that key length n+32logε1 suffices to encrypt n qubits in such a way that the cipherstate has trace distance ≤ε from the fully mixed state. The previous best result was n+2logε1. Similar to the previous literature, we expand the key to a 2n-bit pseudorandom string which is then used as a QOTP key. In this expansion we make use of 2n bits of public randomness which are included as a classical part of the cipherstate. Our key expansion is slightly faster than in previous works.
An encryption scheme is said to be entropically secure if an adversary whose min-entropy on the message is upper bounded cannot guess any function of the message. Similarly, an encryption scheme is entropically indistinguishable if the encrypted version of a message whose min-entropy is high enough is statistically indistinguishable from a fixed distribution. We present full generalizations of these two concepts to the encryption of quantum states in which the quantum conditional min-entropy, as introduced by Renner, is used to bound the adversary's prior information on the message. A proof of the equivalence between quantum entropic security and quantum entropic indistinguishability is presented. We also provide proofs of security for two different ciphers in this model and a proof for a lower bound on the key length required by any such cipher. These ciphers generalize existing schemes for approximate quantum encryption to the entropic security model.
Most cryptographic primitives require randomness (for example, to generate secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be achievable for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for information-theoretic private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness [special characters omitted]. Our main result shows that if such n-bit source [special characters omitted] allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from [special characters omitted]. Further, the restriction that b > log n is nearly tight: there exist sources [special characters omitted] allowing one to perfectly encrypt (log n – loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, true randomness is inherent for encryption : either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the one-time pad scheme is essentially "universal". Our technique also extends to related primitives which are sufficiently binding and hiding, including computationally secure commitments and public-key encryption.
Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. Up to date, only very few randomness-extraction techniques are known to work against an attacker holding quantum information on the raw key. This is very much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques are known and proven to work. We prove a new randomness-extraction technique, which is known to work in the classical setting, to be secure against a quantum attacker as well. Randomness extraction is done by XOR'ing a so-called delta-biased mask to the raw key. Our result allows to extend the classical applications of this extractor to the quantum setting. We discuss the following two applications. We show how to encrypt a long message with a short key, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker. As second application, we show how to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key.
The previous work showed that the Y00 protocol could stay secure with the eavesdropper's guessing probability on the secret keys being strictly less than one under an unlimitedly long known-plaintext attack with quantum memory. However, an assumption that at least a fast correlation attack is completely disabled by irregular mapping. The present study shows that the Y00 protocol can be information-theoretic secure under any quantum-computational crypto-analyses if the Y00 system is well designed. The Y00 protocol directly encrypts messages with short secret keys expanded into pseudo-random running keys unlike One-Time Pad. However, it may offer information-theoretic security beyond the Shannon limit of cryptography.