-
Iterated Rounding을 이용해 Degree Bounded T-join 문제 해결하기
Introduction $T$-join 문제는 가중치 있는 무향 그래프 $G = (V, E, c)$ 와 짝수 크기의 정점의 부분집합 $T \subseteq V$ 가 주어질 때, $T$에 속하는 정점의 차수는 홀수, 그 외 정점의 차수는 짝수가 되게 하는 최소 비용의 $J \subseteq E$ 를 찾는 문제이다. 이 문제는 다양한 응용이 있으며, 대표적인 예로는 중국인 우채부 문제(Chinese Postman Problem)와 외판원 문제(TSP)에 대한 Christofides Algorithm이 있다. 과거 필자가 소개한 $s$-$t$ 경로 외판원 문제의 근사 알고리즘 또한 $T$-join 문제를 이용해 해결하였다....
-
Advanced SIMD Guide
Intro 최근에 SIMD 연산을 활용해서 최적화를 해 볼 기회가 있었습니다. 그 과정에서 겪었던 어려운 점들과 흥미로운 점들, 그리고 유용한 점들을 모아 공유하고자 합니다. 확인해보니, 암호학 분야를 깊게 보시는 blisstoner께서 기존에 SIMD에 관한 소개글을 포스팅하신 것이 있습니다. Link 이 글에서는 좀더 다양한 연산들, 주의해야 할 점들, 그리고 어떻게 쉽게 개발할 수 있을지를 집중적으로 설명해봅니다. 간단하게 다시 짚고 넘어가자면, SIMD (Single Instruction Multiple Data) 연산은 다수의 데이터에 동일한 연산을 한꺼번에 적용하고자 하는 목표를 가집니다. 여러 개의 데이터를...
-
New Updates on Proximity Testing with Logarithmic Randomness
소개 이전 글에서, “Proximity Testing with Logarithmic Randomness”라는 논문을 소개했습니다. 이 논문을 읽은 당시에 제가 논문에 있었던 증명의 작은 오류를 찾아 이를 수정하는데 기여하기도 했으며, 그 내용도 이전 글에 소개되어 있습니다. 1월 이후, 해당 논문과 관련된 여러 새로운 발견이 이루어졌습니다. 이 글에서는 1월 이후 Proximity Testing에 대한 추가적인 발전에 대해서 다룹니다. 복습 이전 논문에서 다룬 핵심적인 정리는 다음과 같습니다. For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots,...
-
PS에서 C++ 상속 활용하기
C++에는 클래스가 있고, 클래스에는 상속이 있다는 사실은 대부분 알고 계실 것입니다. 상속의 개념을 Animal, Dog, Cat의 관계로 설명하는 것을 한 번쯤은 보셨을 것입니다. 하지만 실제 PS를 할 때 C++의 상속 개념을 활용하는 경우는 그닥 많지 않습니다. 그러나 상속을 잘 활용하면, PS에서도 더 편하고 깔끔하게 코드를 짤 수 있게 됩니다. 이 글에서는 PS에서 실용적으로 상속을 활용할 수 있는 몇 가지 사례를 소개합니다. 모든 원소에 특정 값 더하기 아래의 쿼리를 해결하는 문제를 생각해봅시다. 배열에 $x$ 추가하기 배열에서...
-
Polymath: Groth16 is Not The Limit
소개 ZKP의 성능을 측정하는 요소에는 여러 가지가 있습니다. Prover와 Verifier의 입장에서 생각해보면, 가장 중요한 것은 아무래도 Prover가 proof를 생성하는데 걸리는 시간 및 리소스 Verifier가 proof를 검증하는데 걸리는 시간 및 리소스 입니다. 하지만, Recursive ZKP나 최종적으로 Verifier가 위치하는 곳이 어디인지 등을 생각해보면, 시간 및 리소스만큼이나 중요한 것이 바로 Proof의 크기, 즉 proof size임을 알 수 있습니다. Proof의 크기 자체가 크면 blockchain 위에 올리는 데 비용이 커지며, 동시에 Recursive ZKP를 하는 overhead도 커지기 때문입니다. 특히, blockchain 위에...