Computational Complexity and Encryption.

Abstract

Complexity theory has had a major impact on the design of encryption algorithms. Number theory has also made important contributions and is now the focus of much research in the cryptographic community. Work in theoretical computer science has lead to the development of a polynomial hierarchy used to classify the computational complexity of problems which are difficult to solve. NP-Complete problems have proven to be an excellent vehicle for the development of encryption algorithms. Asymmetrical (Public Key) encryption uses complexity theory for the design of algorithms that provide information security and integrity. Encryption algorithms based on complexity theory are relatively new, and questions remain about the security and integrity of these algorithms. Complexity theory has proven to this point to be a powerful ally in the design of encryption algorithms, but only time will tell if the polynomial hierarchy is real, or if advances in mathematics and computer science will render these algorithms insecure.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1995
Accession Number
ADA291910

Entities

People

  • John R. Coward

Organizations

  • United States Army Aviation and Missile Command

Tags

Communities of Interest

  • Cyber
  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Asymetric Encryption
  • Classification
  • Computational Complexity
  • Computer Science
  • Computers
  • Cryptography
  • Hierarchies
  • Information Security
  • Mathematics
  • Number Theory
  • Numbers
  • Polynomials
  • Prime Numbers
  • Security
  • Theoretical Computer Science

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Cybersecurity.
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design