Information-theoretic security

Last updated

A cryptosystem is considered to have information-theoretic security (also called unconditional security [1] ) if the system is secure against adversaries with unlimited computing resources and time. In contrast, a system which depends on the computational cost of cryptanalysis to be secure (and thus can be broken by an attack with unlimited computation) is called computationally, or conditionally, secure. [2]

Contents

Overview

An encryption protocol with information-theoretic security is impossible to break even with infinite computational power. Protocols proven to be information-theoretically secure are resistant to future developments in computing. The concept of information-theoretically secure communication was introduced in 1949 by American mathematician Claude Shannon, one of the founders of classical information theory, who used it to prove the one-time pad system was secure. [3] Information-theoretically secure cryptosystems have been used for the most sensitive governmental communications, such as diplomatic cables and high-level military communications.[ citation needed ]

There are a variety of cryptographic tasks for which information-theoretic security is a meaningful and useful requirement. A few of these are:

  1. Secret sharing schemes such as Shamir's are information-theoretically secure (and also perfectly secure) in that having less than the requisite number of shares of the secret provides no information about the secret.
  2. More generally, secure multiparty computation protocols often have information-theoretic security.
  3. Private information retrieval with multiple databases can be achieved with information-theoretic privacy for the user's query.
  4. Reductions between cryptographic primitives or tasks can often be achieved information-theoretically. Such reductions are important from a theoretical perspective because they establish that primitive can be realized if primitive can be realized.
  5. Symmetric encryption can be constructed under an information-theoretic notion of security called entropic security, which assumes that the adversary knows almost nothing about the message being sent. The goal here is to hide all functions of the plaintext rather than all information about it.
  6. Information-theoretic cryptography is quantum-safe.

Physical layer encryption

Technical limitations

Algorithms which are computationally or conditionally secure (i.e., they are not information-theoretically secure) are dependent on resource limits. For example, RSA relies on the assertion that factoring large numbers is hard.

A weaker notion of security, defined by Aaron D. Wyner, established a now-flourishing area of research that is known as physical layer encryption. [4] It exploits the physical wireless channel for its security by communications, signal processing, and coding techniques. The security is provable, unbreakable, and quantifiable (in bits/second/hertz).

Wyner's initial physical layer encryption work in the 1970s posed the Alice–Bob–Eve problem in which Alice wants to send a message to Bob without Eve decoding it. If the channel from Alice to Bob is statistically better than the channel from Alice to Eve, it had been shown that secure communication is possible. [5] That is intuitive, but Wyner measured the secrecy in information theoretic terms defining secrecy capacity, which essentially is the rate at which Alice can transmit secret information to Bob. Shortly afterward, Imre Csiszár and Körner showed that secret communication was possible even if Eve had a statistically better channel to Alice than Bob did. [6] The basic idea of the information theoretic approach to securely transmit confidential messages (without using an encryption key) to a legitimate receiver is to use the inherent randomness of the physical medium (including noises and channel fluctuations due to fading) and exploit the difference between the channel to a legitimate receiver and the channel to an eavesdropper to benefit the legitimate receiver. [7] More recent theoretical results are concerned with determining the secrecy capacity and optimal power allocation in broadcast fading channels. [8] [9] There are caveats, as many capacities are not computable unless the assumption is made that Alice knows the channel to Eve. If that were known, Alice could simply place a null in Eve's direction. Secrecy capacity for MIMO and multiple colluding eavesdroppers is more recent and ongoing work, [10] [11] and such results still make the non-useful assumption about eavesdropper channel state information knowledge.

Still other work is less theoretical by attempting to compare implementable schemes. One physical layer encryption scheme is to broadcast artificial noise in all directions except that of Bob's channel, which basically jams Eve. One paper by Negi and Goel details its implementation, and Khisti and Wornell computed the secrecy capacity when only statistics about Eve's channel are known. [12] [13]

Parallel to that work in the information theory community is work in the antenna community, which has been termed near-field direct antenna modulation or directional modulation. [14] It has been shown that by using a parasitic array, the transmitted modulation in different directions could be controlled independently. [15] Secrecy could be realized by making the modulations in undesired directions difficult to decode. Directional modulation data transmission was experimentally demonstrated using a phased array. [16] Others have demonstrated directional modulation with switched arrays and phase-conjugating lenses. [17] [18] [19]

That type of directional modulation is really a subset of Negi and Goel's additive artificial noise encryption scheme. Another scheme using pattern-reconfigurable transmit antennas for Alice called reconfigurable multiplicative noise (RMN) complements additive artificial noise. [20] The two work well together in channel simulations in which nothing is assumed known to Alice or Bob about the eavesdroppers.

Secret key agreement

The different works mentioned in the previous part employ, in one way or another, the randomness present in the wireless channel to transmit information-theoretically secure messages. Conversely, we could analyze how much secrecy one can extract from the randomness itself in the form of a secret key. That is the goal of secret key agreement.

In this line of work, started by Maurer [21] and Ahlswede and Csiszár, [22] the basic system model removes any restriction on the communication schemes and assumes that the legitimate users can communicate over a two-way, public, noiseless, and authenticated channel at no cost. This model has been subsequently extended to account for multiple users [23] and a noisy channel [24] among others.

See also

Related Research Articles

<span class="mw-page-title-main">Diffie–Hellman key exchange</span> Method of exchanging cryptographic keys

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

Information theory is the mathematical study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. The field, in applied mathematics, is at the intersection of probability theory, statistics, computer science, statistical mechanics, information engineering, and electrical engineering.

<span class="mw-page-title-main">Public-key cryptography</span> Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which then can be used to encrypt and decrypt messages. The process of quantum key distribution is not to be confused with quantum cryptography, as it is the best-known example of a quantum-cryptographic task.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

A passive attack on a cryptosystem is one in which the cryptanalyst cannot interact with any of the parties involved, attempting to break the system solely based upon observed data. This can also include known plaintext attacks where both the plaintext and its corresponding ciphertext are known.

<span class="mw-page-title-main">Key exchange</span> Cryptographic protocol enabling the sharing of a secret key over an insecure channel

Key exchange is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.

Proxy re-encryption (PRE) schemes are cryptosystems which allow third parties (proxies) to alter a ciphertext which has been encrypted for one party, so that it may be decrypted by another.

In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key-agreement protocols that gives assurances that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised. For HTTPS, the long-term secret is typically the private key of the server. Forward secrecy protects past sessions against future compromises of keys or passwords. By generating a unique session key for every session a user initiates, the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key. This by itself is not sufficient for forward secrecy which additionally requires that a long-term secret compromise does not affect the security of past session keys.

Hyper-encryption is a form of encryption invented by Michael O. Rabin which uses a high-bandwidth source of public random bits, together with a secret key that is shared by only the sender and recipient(s) of the message. It uses the assumptions of Ueli Maurer's bounded-storage model as the basis of its secrecy. Although everyone can see the data, decryption by adversaries without the secret key is still not feasible, because of the space limitations of storing enough data to mount an attack against the system.

Babak Hassibi is an Iranian-American electrical engineer, computer scientist, and applied mathematician who is the inaugural Mose and Lillian S. Bohn Professor of Electrical Engineering and Computing and Mathematical Sciences at the California Institute of Technology (Caltech). From 2011 to 2016 he was the Gordon M Binder/Amgen Professor of Electrical Engineering. During 2008-2015 he was the Executive Officer of Electrical Engineering and Associate Director of Information Science and Technology.

In telecommunications, dirty paper coding (DPC) or Costa precoding is a technique for efficient transmission of digital data through a channel subjected to some interference known to the transmitter. The technique consists of precoding the data in order to cancel the interference. Dirty-paper coding achieves the channel capacity, without a power penalty and without requiring the receiver to know the interfering signal.

Virgil Dorin Gligor is a Romanian-American professor of electrical and computer engineering who specializes in the research of network security and applied cryptography.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

The noisy-storage model refers to a cryptographic model employed in quantum cryptography. It assumes that the quantum memory device of an attacker (adversary) trying to break the protocol is imperfect (noisy). The main goal of this model is to enable the secure implementation of two-party cryptographic primitives, such as bit commitment, oblivious transfer and secure identification.

<span class="mw-page-title-main">Katalin Marton</span> Hungarian mathematician (1941–2019)

Katalin Marton was a Hungarian mathematician, born in Budapest.

Can Emre Koksal is an electrical engineer, computer scientist, academic, and entrepreneur. He is the Founder and CEO of Datanchor, and a professor of Electrical and Computer Engineering at Ohio State University.

Mikael Skoglund is an academic born 1969 in Kungälv, Sweden. He is a professor of Communication theory, and the Head of the Division of Information Science and Engineering of the Department of Intelligent Systems at KTH Royal Institute of Technology. His research focuses on source-channel coding, signal processing, information theory, privacy, security, and with a particular focus on how information theory applies to wireless communications.

References

  1. ↑ Diffie, Whitfield; Hellman, Martin E. (November 1976). "New Directions in Cryptography" (PDF). IEEE Transactions on Information Theory. IT-22 (6): 646. Retrieved 8 December 2021.
  2. ↑ Maurer, Ueli (August 1999). "Information-Theoretic Cryptography". Advances in Cryptology — CRYPTO' 99. Lecture Notes in Computer Science. Vol. 1666. pp. 47–64. doi: 10.1007/3-540-48405-1_4 . ISBN   978-3-540-66347-8.
  3. ↑ Shannon, Claude E. (October 1949). "Communication Theory of Secrecy Systems" (PDF). Bell System Technical Journal. 28 (4): 656–715. doi:10.1002/j.1538-7305.1949.tb00928.x. hdl:10338.dmlcz/119717 . Retrieved 2011-12-21.
  4. ↑ Koyluoglu (16 July 2010). "Information Theoretic Security" . Retrieved 11 August 2010.
  5. ↑ Wyner, A. D. (October 1975). "The Wire-Tap Channel" (PDF). Bell System Technical Journal. 54 (8): 1355–1387. doi:10.1002/j.1538-7305.1975.tb02040.x. S2CID   21512925. Archived from the original (PDF) on 2014-02-04. Retrieved 2013-04-11.
  6. ↑ Csiszár, I.; Körner, J. (May 1978). "Broadcast Channels with Confidential Messages". IEEE Transactions on Information Theory. IT-24 (3): 339–348. doi:10.1109/TIT.1978.1055892. S2CID   206733433.
  7. ↑ Liang, Y.; Vincent Poor, H.; Shamai, S. (2008). "Information Theoretic Security". Foundations and Trends in Communications and Information Theory. 5 (4–5): 355–580. doi:10.1561/0100000036.
  8. ↑ Liang, Yingbin; Poor, Vincent; Shamai (Shitz), Shlomo (June 2008). "Secure Communication Over Fading Channels". IEEE Transactions on Information Theory. 54 (6): 2470–2492. arXiv: cs/0701024 . doi:10.1109/tit.2008.921678. S2CID   7249068.
  9. ↑ Gopala, P.; Lai, L.; El Gamal, H. (October 2008). "On the Secrecy Capacity of Fading Channels". IEEE Transactions on Information Theory. 54 (10): 4687–4698. arXiv: cs/0610103 . doi:10.1109/tit.2008.928990. S2CID   3264079.
  10. ↑ Khisti, Ashish; Wornell, Gregory (November 2010). "Secure Transmission with Multiple Antennas II: The MIMOME Wiretap Channel". IEEE Transactions on Information Theory. 56 (11): 5515–5532. arXiv: 1006.5879 . Bibcode:2010arXiv1006.5879K. doi:10.1109/tit.2010.2068852. S2CID   1428.
  11. ↑ Oggier, F.; Hassibi, B. (August 2011). "The Secrecy Capacity of the MIMO Wiretap Channel". IEEE Transactions on Information Theory. 57 (8): 4961–4972. arXiv: 0710.1920 . doi:10.1109/tit.2011.2158487. S2CID   1586.
  12. ↑ Negi, R.; Goel, S. (2008). "Guaranteeing secrecy using artificial noise". IEEE Transactions on Wireless Communications. 7 (6): 2180–2189. doi:10.1109/twc.2008.060848. S2CID   5430424.
  13. ↑ Khisti, Ashish; Wornell, Gregory (Jul 2010). "Secure transmission with multiple antennas I: The MISOME wiretap channel". IEEE Transactions on Information Theory. 56 (7): 3088–3104. CiteSeerX   10.1.1.419.1480 . doi:10.1109/tit.2010.2048445. S2CID   47043747.
  14. ↑ Daly, M.P.; Bernhard, J.T. (Sep 2009). "Directional modulation technique for phased arrays". IEEE Transactions on Antennas and Propagation. 57 (9): 2633–2640. Bibcode:2009ITAP...57.2633D. doi:10.1109/tap.2009.2027047. S2CID   27139656.
  15. ↑ Babakhani, A.; Rutledge, D.B.; Hajimiri, A. (Dec 2008). "Transmitter architectures based on near-field direct antenna modulation" (PDF). IEEE Journal of Solid-State Circuits. IEEE. 76 (12): 2674–2692. Bibcode:2008IJSSC..43.2674B. doi:10.1109/JSSC.2008.2004864. S2CID   14595636.
  16. ↑ Daly, M.P.; Daly, E.L.; Bernhard, J.T. (May 2010). "Demonstration of directional modulation using a phased array". IEEE Transactions on Antennas and Propagation. 58 (5): 1545–1550. Bibcode:2010ITAP...58.1545D. doi:10.1109/tap.2010.2044357. S2CID   40708998.
  17. ↑ Hong, T.; Song, M.-Z.; Liu, Y. (2011). "RF directional modulation technique using a switched antenna array for physical layer secure communication applications". Progress in Electromagnetics Research. 116: 363–379. doi: 10.2528/PIER11031605 .
  18. ↑ Shi, H.; Tennant, A. (April 2011). Direction dependent antenna modulation using a two element array. Proceedings 5th European Conference on Antennas and Propagation(EUCAP). pp. 812–815.
  19. ↑ Malyuskin, O.; Fusco, V. (2012). "Spatial data encryption using phase conjugating lenses". IEEE Transactions on Antennas and Propagation. 60 (6): 2913–2920. Bibcode:2012ITAP...60.2913M. doi:10.1109/tap.2012.2194661. S2CID   38743535.
  20. ↑ Daly, Michael (2012). Physical layer encryption using fixed and reconfigurable antennas (Ph.D.). University of Illinois at Urbana-Champaign.
  21. ↑ Maurer, U. M. (May 1993). "Secret key agreement by public discussion from common information". IEEE Transactions on Information Theory. 39 (3): 733–742. doi:10.1109/18.256484.
  22. ↑ Ahlswede, R.; Csiszár, I. (July 1993). "Common randomness in information theory and cryptography. I. Secret sharing". IEEE Transactions on Information Theory. 39 (4): 1121–1132. doi:10.1109/18.243431.
  23. ↑ Narayan, Prakash; Tyagi, Himanshu (2016). "Multiterminal Secrecy by Public Discussion". Foundations and Trends in Communications and Information Theory. 13 (2–3): 129–275. doi:10.1561/0100000072.
  24. ↑ Bassi, G.; Piantanida, P.; Shamai, S. (2019). "The Secret Key Capacity of a Class of Noisy Channels with Correlated Sources". Entropy. 21 (8): 732. Bibcode:2019Entrp..21..732B. doi: 10.3390/e21080732 . PMC   7515261 . PMID   33267446.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.