-
O(N) Precomputation, O(1) RMQ (Farach-Colton and Bender Algorithm)
이 글은 Sparse Table을 이용한 $O(N \log N)$ 전처리, $O(1)$ LCA 쿼리(소멤 글 링크)와 sqrt decomposition를 이용한 $O(N)$ 전처리, $O(\sqrt N)$ RMQ(cp-algorithms 링크)를 선행 지식으로 가지고 있다면 더 쉽게 이해할 수 있습니다. $O(N)$ 전처리, $O(1)$ LCA 쿼리 우리는 LCA 쿼리를 Euler Tour 테크닉을 통해 RMQ로 변환시킬 수 있습니다. 이는 위 Sparse Table을 이용한 $O(1)$ LCA 쿼리에서도 사용하는 방법이기 때문에 위 링크된 소멤 글에 자세히 설명되어 있으므로 이 글에서는 설명을 생략하겠습니다. 이 테크닉을 이용해 주어진 트리에서...
-
Isochronous Gaussian Sampling of [HPRR20]
논문은 https://eprint.iacr.org/2019/1411.pdf 입니다. Post Quantum Cryptography and Lattices 지금 사용되고 있는 많은 암호화 체계, 예를 들면 블록체인에서 많이 사용되고 있는 ECDSA/EDDSA나 공개키 암호화를 위해 사용되는 RSA 등은 전부 충분히 강력한 양자컴퓨터가 나오면 더 이상 안전하지 않게 됩니다. 양자컴퓨터가 나오는 미래에 대비하기 위해 NIST는 2010년대 후반부터 양자컴퓨터가 나오더라도 안전한, Post Quantum Cryptography에 (이하 PQC) 대한 표준을 정하기 위한 과정을 밟기 시작했습니다. 여러 과정을 거쳐서 매우 최근 Round 4 발표 및 첫 표준이 등장하게 되었는데, PQC 암호체계를...
-
Characteristic Polynomial in a Commutative Ring
Introduction $n \times n$ 정사각행렬 $A = (a _ {ij})$가 주어져 있을 때, $A$의 determinant $\det A$는 아래와 같이 계산할 수 있습니다. \[\det A = \sum _ {\sigma \in S _ {n}} \mathrm{sgn}(\sigma) \cdot \prod _ {i = 1}^{n} a _ {i \sigma _ {i}}\] 오늘은 $\det A$ 와, 그를 일반화하는 특성다항식(Characteristic polynomial) $\phi _ {A}(x) = \det(x I - A) = x^{n} - \mathrm{tr} (A) x^{n-1} + \cdots + (-1)^{n-1} \det A$를 계산하는 방법을...
-
Conditional Hardness for Sensitivity Problems
Conditional Hardness for Sensitivity Problems 이 글에서는 Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams의 Conditional Hardness for Sensitivity Problems 라는 논문을 요약한다. 이론 전산에서 Dynamic algorithm은, 입력 데이터에 작은 변화가 점진적으로 가해지더라도 데이터에 대해 물어볼 수 있는 특정한 문제들의 답을 그대로 보존하는 알고리즘을 뜻한다. 예를 들어서, 그래프의 “연결성” (connectivity) 를 보존하는 dynamic algorithm은 입력 그래프에 간선 추가와 제거가 이루어질 때 $s - t$ 간에 경로가 있는지 여부의 쿼리를 반환할 수 있다. 최근 이루어진...
-
IND-CCA2 Encryption schemes and Fujisaki-Okamoto transform
Introduction 암호의 안전성 암호는 수천년 전에 로마나 고대 그리스에서 사용하던 고전암호로부터 시작해 20세기 초에는 상당히 발전되어 전쟁에서 사용되기도 했으며, 그 후 현재까지 쓰이고 있는 대칭키 암호(symmetric key cryptography) 및 공개키 암호(public key cryptography)가 개발되었습니다. 현재는 그 외에도 Lattice-based cryptography 등의 여러 암호가 활발하게 연구되고 있습니다. 초창기의 암호 중 몇몇은 하나의 문자가 하나의 문자에 대응되는 형식을 띠고 있습니다. 이러한 암호의 경우 문자마다 실제 단어에 사용되는 빈도가 달라 암호문이 충분히 주어진다면 그 빈도를 파악하여 대응되는 문자를 파악하여...