-
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에 대한 이해가 약하시면 내용을...
-
NP-Complete 게임들과 그 증명
안녕하세요? 우리가 여가 시간에 많이 즐기는 친숙한 여러 게임들, 가령 루빅스 큐브(의 최단거리 찾기), 스도쿠와 같은 고전적인 게임들부터 지뢰찾기, 테트리스, 솔리테어, 팩맨, 슈퍼 마리오, 캔디 크러쉬 사가, 2048, 루빅스 큐브, 쿠키 클리커 등과 같은 게임은 NP-Complete 문제임이 증명되어 있습니다. 이번 글에서는 이러한 게임들을 어떠한 decision problem으로 정의하면, 이러한 문제들이 NP-Complete가 되고 이를 어떻게 증명할지에 대해 알아보겠습니다. P 문제와 NP 문제 P와 NP, 그리고 NP-Hard와 NP-Complete가 어떠한 것인지는 널리 잘 알려져 있습니다. 멤버십 블로그에서도 기존에 이와...
-
대화형 증명 시스템과 영지식 증명
이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성zero-knowledgeness을 다루고자 합니다. 대화형 증명 시스템 NP Revisited Arthur-Merlin Protocol IP 영지식 알리바바와 동굴 Indistinguishability Revisited Fiat-Shamir Protocol Hamiltonian Cycle 마무리 각주 대화형 증명 시스템 대화형 증명 시스템interactive proof system은 두 개체 증명자prover와 검증자verifier로 이루어져...
-
COVID-19 확산의 분석
COVID-19 확산의 분석 Contents 개요 및 기존 분석들 분석 방향성 분석 결과 및 의의 이후 방향성 참고 개요 및 기존 분석들 COVID-19 사태는 현재 인류에 큰 피해를 주고 있으며, 앞으로 얼마나 더 지속될지 모르고, 후에 유사한 전염병이 다시 나타났을 때, 좀 더 유연하고 의미있는 해결책과 대비책이 존재하면 좋을 것이라고 생각했습니다. 또한 코로나와 같은 사회 경제에 직접적으로 영향을 주게 되는 경우, 어떤 패턴이 존재하고 변화하는지를 알아보는 과정이 흥미로울 것 같아서 분석을 진행해보게 되었습니다. 먼저, 기존의 분석에...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1) 그래프에서 최소 스패닝 트리 (Minimum spanning tree)를 구하는 문제는 아주 잘 알려져 있고, 일반적으로 가장 처음 공부하게 되는 그래프 알고리즘에 속하며, 매우 다양한 개념에 응용된다. 그래프의 최소 스패닝 트리는 크루스칼 알고리즘을 통해서 $O(m \log m)$ 에 효율적으로 구할 수 있다. 하지만 그래프에서 간선이 추가되고 제거되는 등의 업데이트가 가해진다면, 이 알고리즘은 매 갱신마다 전체 간선 리스트를 전부 순회해야 하니 더 이상 효율적이지 않게 된다. 이렇게 그래프의 일부가...