IEEE International Symposium on Information Theory (ISIT)

The one-time pad revisited

Christian Matt, Ueli M. Maurer

Published Jul 1, 2013• 28 citations

Abstract

The one-time pad, the mother of all encryption schemes, is well known to be information-theoretically secure, in contrast to most encryption schemes used in practice, which are at most computationally secure. In this paper, we focus on another, completely different aspect in which the one-time pad is superior to normal encryption, and which surfaces only when the receiver (not only the eavesdropper) is considered potentially dishonest, as can be the case in a larger protocol context in which encryption is used as a sub-protocol. For example, such a dishonest receiver (who is, say, coerced by the eavesdropper) can in normal encryption verifiably leak the message to the eavesdropper by revealing the secret key. While this leakage feature can provably not be avoided completely, it is more limited if the one-time pad is used. We use the constructive cryptography framework to make these statements precise.

DOI: 10.1109/isit.2013.6620718

Related papers

Quantum cryptography

Jonathan A. Jones, Dieter Jaksch

Cryptographic protocols can be classified by the type of security against eavesdropping which they provide. There exist mathematically secure schemes whose security relies on mathematical proofs (like the Vernam cipher discussed below) or conjectures (like public key RSA encryption) about the complexity of deciphering the message without possessing the correct key. The majority of current secure public Internet connections rely on such schemes. Alternatively, a cryptographic setup may provide a physically secure method for communicating. In these setups the security is provided by the physical laws governing the communication protocol. Here we first discuss a provably secure classical communication protocol and then quantum methods for distributing the necessary keys. The BB84 protocol relies on the impossibility of perfectly distinguishing non-orthogonal quantum states from one copy of the quantum system. The scheme was invented in 1984 and is the first of its kind. In contrast, the Ekert91 protocol makes use of Bell correlations between entangled pairs of photons. These correlations are destroyed when Eve attempts to make a measurement on one of the particles but also when imperfections, such as decoherence processes, affect the scheme. As long as no such “elements of reality” are introduced, and Bell correlations violating local realism can be generated by Alice and Bob, no eavesdropper can be present. One-time pads and the Vernam cipher The Vernam cipher is a cryptographic protocol which allows the encryption and decryption protocol to be publicly known. The security of the protocol relies entirely on the key which is private and not publicly known. Alice and Bob share identical n -bit secret key strings (one-time pad).

Cambridge University Press eBooksJul 19, 20120 citations

Self-Renewing One-Time Pad: Information-Theoretic Messaging Beyond Initial Pad Exhaustion

AriaLabs Systems LLC

The classical limitation of one-time-pad (OTP) cryptography is the key-distribution problem: to send n bits of plaintext, the parties must already share n bits of pre-distributed key. Once the pad is exhausted, the parties must meet again to exchange new pad material. This is widely viewed as making pure OTP impractical for sustained communication. We present a protocol that resolves this limitation: once an initial pad of size N is shared in person, subsequent pad material is generated by one party from a true-random source and transmitted as encrypted payload over the existing OTP channel itself. The receiver decrypts using existing pad and appends the recovered random bytes to its local pad. Net pad balance after a refill operation is unchanged — bytes of old pad are spent to deliver an equal number of bytes of new pad — but the new material is fresh, secret, and uncompromised. We prove inductively that information-theoretic security of the new pad is preserved across arbitrary refill chains. The result is a protocol with all the security guarantees of classical OTP and none of its practical key-distribution limitation, given a single in-person bootstrap.

May 5, 20265 citations

How to reuse a one-time pad and other notes on authentication, encryption, and protection of quantum information

Jonathan Oppenheim, Michał Horodecki

Quantum information is a valuable resource which can be encrypted in order to protect it. We consider the size of the one-time pad that is needed to protect quantum information in a number of cases. The situation is dramatically different from the classical case: we prove that one can recycle the one-time pad without compromising security. The protocol for recycling relies on detecting whether eavesdropping has occurred, and further relies on the fact that information contained in the encrypted quantum state cannot be fully accessed. We prove the security of recycling rates when authentication of quantum states is accepted, and when it is rejected. We note that recycling schemes respect a general law of cryptography which we introduce relating the size of private keys, sent qubits, and encrypted messages. We discuss applications for encryption of quantum information in light of the resources needed for teleportation. Potential uses include the protection of resources such as entanglement and the memory of quantum computers. We also introduce another application: encrypted secret sharing and find that one can even reuse the private key that is used to encrypt a classical message. In a number of cases, one finds that the amount of private key needed for authentication or protection is smaller than in the general case.

arXiv:quant-ph/0306161Physical Review AOct 5, 200535 citations

A TYPE OF POST–QUANTUM CRYPTOGRAPHIC ALGORITHM

Hong Dung Luu

The article proposes a type of post–quantum cryptographic algorithm based on hash function and One–Time Pad cipher. Due to inheriting a property called “perfect secrecy” of the One-Time Pad cipher, the algorithms constructed according to the method proposed here can resist various types of attacks with the help of quantum computers. In addition to high security, algorithms of this type also have the ability to authenticate the origin and integrity of the encrypted messages. On the other hand, the one-time key for encryption/decryption is established for each individual message while the management and distribution of the shared secret key between the sender/encryptor and receiver/decryptor is performed similar to symmetric – key cryptosystems being applied in practice.

Journal of Science and TechniqueJun 28, 20242 citations

Security of Quantum Key Distribution with One-Time-Pad-Protected Error Correction and Its Performance Benefits

Roman Novak

In quantum key distribution (QKD), public discussion over the authenticated classical channel inevitably leaks information about the raw key to a potential adversary, which must later be mitigated by privacy amplification. To limit this leakage, a one-time pad (OTP) has been proposed to protect message exchanges in various settings. Building on the security proof of Tomamichel and Leverrier, which is based on a non-asymptotic framework and considers the effects of finite resources, we extend the analysis to the OTP-protected scheme. We show that when the OTP key is drawn from the entropy pool of the same QKD session, the achievable quantum key rate is identical to that of the reference protocol with unprotected error-correction exchange. This equivalence holds for a fixed security level, defined via the diamond distance between the real and ideal protocols modeled as completely positive trace-preserving maps. At the same time, the proposed approach reduces the computational requirements: for non-interactive low-density parity-check codes, the encoding problem size is reduced by the square of the syndrome length, while privacy amplification requires less compression. The technique preserves security, avoids the use of QKD keys between sessions, and has the potential to improve performance.

EntropyOct 1, 20250 citations

A Framework for Partial Secrecy

Paul Cuff

We consider theoretical limits of partial secrecy in a setting where an eavesdropper attempts to causally reconstruct an information sequence with low distortion based on an intercepted transmission and the past of the sequence. The transmitter and receiver have limited secret key at their disposal but not enough to establish perfect secrecy with a one-time pad. From another viewpoint, the eavesdropper is acting as an adversary, competing in a zero-sum repeated game against the sender and receiver of the secrecy system. In this case, the information sequence represents a sequence of actions, and the distortion function captures the payoff of the game. We give an information theoretic region expressing the tradeoff between secret key rate and max-min distortion for the eavesdropper. We also simplify this characterization to a linear program. As an example, we discuss how to optimally use secret key to hide Bernoulli-p bits from an eavesdropper so that they incur maximal Hamming distortion.

arXiv:1008.0602GlobecomDec 1, 201041 citations