-
SABER: Mod-LWR based KEM
1. Introduction 저번 글에서는 양자 컴퓨터와 Post Quantum Cryptography에 대해 다루었습니다. 이번 포스팅에서는 어떤 암호 시스템을 다루어볼까 고민하다가 NIST에서 진행하는 PQC contest의 3라운드 7개의 후보 중에서 5개가 Lattice-based인 만큼 Lattice를 기반 문제로 사용하는 SABER 암호의 동작 원리, 장단점을 소개해보려고 합니다. 저도 불과 한달 전까지만 해도 PQC에서 사용하는 Lattice에 대해 아주 얕은 지식만을 가지고 있었기 때문에 Lattice를 잘 모르더라도 글을 이해하는데 큰 어려움은 없습니다. 다만 Group Theory가 많이 쓰이기 때문에 Group Theory에 대한 이해가 약하시면 내용을...
-
Post-Quantum Cryptography
1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...
-
양자 컴퓨팅 - Surface Code
최근 양자 컴퓨팅의 error detection 및 correction에 사용되는 surface code의 기초를 잘 설명한 논문인 Surface codes: Towards practical large-scale quantum computation을 접했습니다. 이 포스트를 통해 양자 컴퓨팅에서 어떻게 error detection을 진행하고, surface code가 어떤 개념인지 설명하고자 합니다. 배경 지식 Shor’s Algorithm이나 Grover’s Algorithm 등의 양자 알고리즘이 개발되며 양자 컴퓨팅에 대한 관심이 커졌습니다. 2020년 현재 IBM Q Experience나 Amazon Braket, Microsoft QDK 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
양자 컴퓨팅 입문 (2) - Grover's Algorithm
Grover’s Algorithm은 정렬되지 않은 데이터베이스에 있는 $N$개의 항목 중 특정한 조건을 만족하는 항목을 $O(\sqrt{N})$에 찾는 알고리즘입니다. 고전 컴퓨팅에서 이 문제를 해결하려면, 간단하지만 느리게 갈 수밖에 없습니다. 전수 조사(brute force)가 유일한 해결책입니다. 당연히 시간 복잡도는 $O(N)$이며, 랜덤하게 셔플해서 순서를 바꾼다 해도 마찬가지입니다. 그리고 이보다 더 나은 시간복잡도로 찾을 수는 없습니다. Grover’s Algorithm은 이 시간복잡도를 $O(\sqrt{N})$으로 낮추는데 성공하였고, 이 시간복잡도가 최적이라는 것이 알려져 있습니다. 또다른 유명한 양자 알고리즘인 Shor’s Algorithm과는 달리 알고리즘 자체가 간단하면서도 심도 있기 때문에...
-
양자 컴퓨팅 입문 (1) - 개요
“양자(quantum)를 이용해서 상태를 저장하는 컴퓨터를 만들면 어떨까?” 이 허무맹랑할 수도 있는 1981년 리처드 파인만에 의해 제기되었습니다. 양자 컴퓨팅은 암호학 쪽에서 1997년 Shor가 다항 시간에 인수분해를 할 수 있는 양자 알고리즘을 발견하면서 각광받기 시작했습니다. 지금까지도 고전 컴퓨팅으로 인수분해를 다항 시간 안에 할 수 없고, 또 RSA 같은 많은 암호체계가 인수분해의 수학적 어려움(infeasibility)을 기반으로 두고 있는데 다항 시간에 인수분해를 할 수 있다는 소식은 획기적인 발전이었습니다. 또 Grover는 정렬되지 않은 $N$개의 항목 중 특정 조건을 만족하는 항목을 $O(\sqrt{N})$에...