June 2018 Issue
Topics

Theoretical aspects of cryptography: How do we know if the system is secure?

Mitsugu Iwamoto, Associate professor, Department of Informatics, Graduate School of Informatics and Engineering, University of Electro-Communications, Tokyo.

Theoretical research on cryptography plays a central role in the development of information security because only mathematical proofs can rigorously guarantee the accuracy of security models. Namely, how can we be sure if the system is secure?

Most of security systems consist of several combinations of the basic building blocks (primitives) of cryptography, such as symmetric-key cryptography, public-key cryptography, and authentication systems. From a mathematical perspective, security of cryptographic primitives is classified into two paradigms: computational security and information-theoretic security.

"Roughly speaking, under computational security, we assume that adversaries are computers (theoretically, Turing machines), and we believe that the primitive is secure because it takes such as long time (e.g., more than the age of universe!) in breaking the system by the computers," explains Iwamoto. "Computational security is very nice trick, since it allows us to realize public-key cryptography which is one of the most important inventions in the history of communications, but it becomes vulnerable if faster computation, e.g., invention of quantum computers, are eventually available."

Information-theoretic security, on the other side, tries to guarantee the security against adversaries with unbounded computing power, that is, computational power is independent of the security. This requirement is so severe that several important cryptographic primitives such as public-key cryptography are not available under this setting. However, due to its strong requirement for security, information-theoretically secure primitives are very important for protecting the data which must be kept secret very long time.

Iwamoto and colleagues are conducting research in many field including information-theoretic security. It is notable that cryptography has been extensively studied since computationally secure cryptography such as RSA (the first public-key cryptography) and DES (data encryption standard, the first standard of symmetric-key encryption adopted by NIST), was invented in late 70's.

In particular, the theory of cryptography has been developed along with the discussion of security notions, which suggest to us why and how we can say "the cryptosystem is secure". On the other hand, study of security notions for information-theoretically secure cryptography has not been explored so deeply although it was initiated by Shannon in 1950 far before the invention of computationally secure cryptography.

Recently, however, there is a much greater realization in the importance of information-theoretic security due to needs for long-term security. Therefore, Iwamoto and colleagues investigated the information-theoretic security notions from the computational security viewpoint. The researchers have two main concerns: finding the relationship among security notions of information-theoretically secure cryptography; and what would happen by combining information-theoretically secure cryptosystems with other ones. These problems were tackled in the case of symmetric-key cryptography and key-agreement.

The research showed relationships among the information-theoretic security notions. "Technically, it is interesting to find security gaps among the security notions called indistinguishability," says Iwamoto. "Traditionally, computational cryptography requires indistinguishability of messages whereas information-theoretic security requires no information leakage from ciphertexts. We captured both notions from the viewpoint of indistinguishability, and we clarified that information-theoretic security notion requires higher security than the indistinguishability in computational security notion, even if the adversary's computing power is infinite."

Reference

  • Authors: Mitsugu Iwamoto, Kazuo Ohta, and Junji Shikata
  • Title of original paper: Security Formalizations and Their Relationships for Encryption and Key Agreement in Information-Theoretic Cryptography
  • Journal, volume, pages and year: IEEE Transactions on Information Theory, vol. 64, issue 1 pp. 654-685(2018).
  • Digital Object Identifier (DOI): DOI: 10.1109/TIT.2017.2744650
  • Affiliations: Department of Informatics, Graduate School of Informatics and Engineering, University of Electro-Communications
  • Department website: https://www.uec.ac.jp/eng/education/ie_graduate/j/index.html
Mitsugu, IWAMOTO