-
Zero Knowledge and Groth16 Protocol
서론 최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다. 이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다. 세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다. Zero Knowledge Proof (ZKP) Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다. 예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의...
-
Minimum Steiner Tree의 계산
서론 그래프 $G$와, 정점의 부분집합 $T$가 주어졌을 때, $T$를 모두 포함하는 Spanning Tree ($G$의 부분그래프 중, 정점과 간선 일부를 선택하여 만든 트리)를 $T$의 Steiner Tree라고 한다. 가중치가 주어진 방향 없는 그래프 $G$에 대해 간선 가중치 합이 가장 작은 Steiner Tree를 계산하는 문제는 일반적인 상황에서 NP-Hard임이 알려져있다. 이 게시글에서는, 해당 Steiner Tree를 계산하는 동적계획법을 다룬다. Naïve 편의상, 그래프의 $G = (V, E)$의 정점 개수를 $N$, 간선 개수를 $M$, 정점 부분집합 $T$의 크기를 $K$라고 하자. 가장 쉽게...
-
Stern-Brocot Tree를 활용한 수론적 함수의 합 계산
개요 정수론에서 주로 다루는 중요한 수론적 함수로는 약수 함수 $\sigma_k (n)$, 오일러 피 함수 $\phi (n)$, 뫼비우스 함수 $\mu (n)$ 등이 있다. 이러한 함수의 학문적 중요도는 이루 말할 수 없으며, 컴퓨터과학와 PS 분야에도 종종 등장할 정도로 다양하게 활용된다. 본 글은 수론적 함수의 대표인 약수 함수 $\sigma (n)$의 구간 합을 효율적으로 계산하는 알고리즘을 서술한다. 함수의 합을 기하적으로 해석한 후, 이를 Stern-Brocot Tree 자료구조로 계산한다. 이후, 이 알고리즘의 시간 복잡도가 $\tilde{O} \left( N^{1/3} \right)$로 아주 효율적임을 보인다....
-
세그먼트 트리의 응용
세그먼트 트리 세그먼트 트리는 수열에 다양한 구간 질의를 빠르게 온라인으로 처리할 수 있게 하는 자료구조이다. 만약 세그먼트 트리에 대해 접해본 적이 전혀 없다면, 네 편의 강의 #1, #2, #3, #4를 참조하라. 세그먼트 트리를 설명할 때에 가장 흔하게 쓰이는 연습문제는 다음과 같다. 문제 1 수열 $A[0], \cdots, A[N -1]$ 이 있다. 이 수열에 질의를 고속으로 처리해야 한다. 질의의 종류는 아래와 같다. 두 수 $i, k$ 가 입력으로 주어진다. 이 때, $A[i]$ 를 $k$만큼 증가시켜라. 두 수...
-
이동하기 4 (BOJ 18796)
이 글은 BOJ 18796 (이동하기 4)의 풀이를 다룹니다. 현재 이 문제의 solved.ac 티어는 루비 5입니다. 이 문제의 흥미로운 점은 지문이 거의 똑같은 문제가 무려 22티어나 낮은 브론즈 2라는 것입니다. 두 문제의 차이는 네 글자뿐이지만, 이는 x 방향으로 이동하는 비용이 x 좌표가 아니라 y 좌표에 의존하게 된다는 매우 치명적인 차이입니다. (물론 y 방향도 마찬가지입니다.) 60 +---+---+---+ +60-+60-+60-+ | | | | 10 90 80 70 20 +---+---+---+ +20-+20-+20-+ | | | | 10 90 80 70...