Cryptographic Algorithms for Quantum Computations

Abstract

The advent of a quantum mechanical computer presents a clear threat to existing cryptography. On the other hand, the quantum computer also suggests the possibility of a new cryptographic protocol through the properties of quantum mechanics. These two perspectives, respectively, gave rise to a new field called post-quantum cryptography as a countermeasure against quantum attacks and quantum cryptography as a new cryptographic technology using quantum mechanics, which are the subject of this thesis.

In this thesis, we reconsider the security of the current post-quantum cryptography through a new quantum attack, model, and security proof. We present the fine-grained quantum security of hash functions as cryptographic primitives against preprocessing adversaries. We also bring recent quantum information theoretic research into cryptography, creating new quantum public key encryption and quantum commitment. Along the way, we resolve various open problems such as limitations of quantum algorithms with preprocessing computation, oracle separation problems in quantum complexity theory, and public key encryption using group action.

양자역학을 이용한 컴퓨터의 등장은 쇼어의 알고리즘 등을 통해 기존 암호학에 명백한 위협을 제시하며, 양자역학의 성질을 통한 새로운 암호프로토콜의 가능성 또한 제시한다. 이러한 두 가지 관점은 각각 이 학위 논문의 주제가 되는 양자공격에 대한 대응책으로써의 대양자암호와 양자역학을 이용한 암호기술인 양자암호라고 불리는 새로운 분야를 발생시켰다.

이 학위 논문에서는 현재 대양자암호의 안전성을 새로운 양자암호 공격 알고리즘과 모델, 안전성 증명을 통해 재고한다. 특히 암호학적 해쉬함수의 일방향함수, 암호학적 의사난수생성기로서의 대양자 암호 안전성의 구체적인 평가를 제시한다. 또한 최근 양자역학의 연구를 양자암호에 도입함으로써 새로운 양자 공개키암호와 양자 커밋먼트 등의 새로운 발견을 제시한다. 이 과정에서 전처리 계산을 포함한 양자알고리즘의 한계, 양자 복잡계들의 오라클분리 문제, 군의 작용을 이용한 공개키 암호 등의 여러 열린문제들의 해결을 제시한다.