Quantum Stream Ciphers: Impossibility of Unconditionally Strong Algorithms
- PDF / 369,622 Bytes
- 14 Pages / 594 x 792 pts Page_size
- 120 Downloads / 225 Views
QUANTUM STREAM CIPHERS: IMPOSSIBILITY OF UNCONDITIONALLY STRONG ALGORITHMS P. A. Tregubov and A. S. Trushechkin
UDC 517.958:530.145
Abstract. Stream ciphers form one of two large classes of ciphers with private keys in classical cryptography. In this paper, we introduce the concept of a quantum stream cipher. Special types of quantum stream ciphers were proposed earlier by numerous researchers. We prove a general result on the nonexistence of an unconditionally strong quantum stream cipher if the length of a message is much longer than the length of a key. We analyze individual and collective attacks against a quantum stream cipher. A relationship between the problem of guessing the key by the opponent and the problem of distinguishing of random quantum states is established. Keywords and phrases: quantum cryptography, stream ciphers, unconditionally strong algorithm, distinguishing of quantum states. AMS Subject Classification: 81P68
1. Introduction. The present work is devoted to the problem of secret communication between two legitimate subjects trusting each other. In this problem, one subject called “sender” sends a secret message (called the plain text) to the other subject called “receiver” using a certain communication channel, which is monitored by an opponent. Therefore, the sender applies a certain cryptographic transformation to the message (encrypts it); this transformation (called a cipher or an encryption algorithm) depends on some information called a key. The result of this transformation is called the cipher text; it can be transmitted over the communication channel. The receiver, who also knows the key, applies the inverse transformation (the decryption algorithm) to the ciphered text and restores the original message. We assume that the opponent knows the form of the cryptographic transformation but does not know the key. A cipher is called perfectly strong if the knowledge of the ciphered text does not allow the opponent to obtain any information about the plain text. Thus, in order to establish secret communication, legitimate subjects must possess common secret information—a key. For simplicity, we assume that the key and the message are binary strings. Due to the fundamental result of Shannon (see [20]; a modern presentation see, e.g., in [1]), a cipher can be perfectly strong only in the case where the length of the message does not exceed the length of the key. This is a substantial restriction for the use of perfectly strong ciphers since the problem is to distribute the keys: the legitimate parties need to reconcile new secret keys in conditions when the communication channel between them is monitored. Due to the fact that a message transmitted should not be longer than a key, it is impossible to encrypt a useful message and a new key of the same length simultaneously. At present, the so-called public-key cryptography (see [1, 19]) is used for distributing keys. It is not perfectly strong but is based on assumptions on the limitation of the computing power of an opponent and the compu
Data Loading...
