-
양자컴퓨팅으로 PS하는법
제목을 조금 자극적이게 “양자컴퓨팅으로 PS하는 법”이라고 설명했지만, 아직 일반적인 PS를 하는 데 양자컴퓨터를 사용하는것은 어렵다. 그래도 그나마 PS스러운 max cut 문제를 양자컴퓨터로 해결하는 방법을 최대한 쉽게 소개하고자 한다. 나중에도 양자컴퓨터를 사용한 소개할만한 알고리즘이 있다면 소개해볼 계획이다. Max cut 문제란? Max cut 문제는 주어진 그래프를 두 집합으로 잘 분리하여 두 집합 사이를 연결하는 간선의 수를 최대화하는 문제이다. 그림 1. Maxcut 예시.흰색과 검은색 정점 집합으로 위와 같이 분리하면 둘 사이를 연결하는 간선(빨간색)이 5개로 최대가 된다. 따라서 이...
-
Folding Part 2: HyperNova
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Verifiable Computation은 Generator $\mathcal{G}(1^\lambda) \rightarrow pp$: security parameter $\lambda$를 받고 public parameter $pp$를 만든다 Encoder $\mathcal{K}(pp, F) \rightarrow (pk, vk)$: public parameter $pp$와 반복할 함수 $F$를 받고, prover key 및 verifier key $pk, vk$를 만든다 Prover $\mathcal{P}(pk, (i, z_0, z_i), \omega_i, \Pi_i) \rightarrow \Pi_{i+1}$은 결과 $z_i$와 이에 대한 IVC proof $\Pi_i$를 받고, $z_{i+1} =...
-
문자열 해싱
이번 글에선 해싱의 다양한 활용을 정리하고자 한다. 너무 기본적인 내용이나 필자도 모르는 너무 고급 기술은 다루지 않고, solved.ac 기준 다이아 중하위 수준까지의 문제를 해싱을 이용해 풀어보려는 사람들에게 적합하다. 해시값을 관리하는 몇가지 방법들을 소개하고, 마지막으로는 며칠 전에 출제된 따끈따끈한 문제인 ICPC 2023 Seoul Regional에 출제된 E번 문항을 해싱을 써서 해결하는 방법을 소개하며 글을 마무리한다. 해싱이란? 문자열 x[0] ~ x[l-1] 이 주어져있을 때, 소수 $p, M$을 사용하여 계산한 해시값 $(\sum_{i=0}^{l-1} x_ip^i) \text{ mod M}$ 을 비교하여 다른...
-
Taylor Shift, Sampling Points Shift
개요 최근에 Polynomial Shift를 사용하는 문제를 여러 대회에서 보았기 때문에 이 글을 작성하게 되었습니다. 다항식 $f(x)$와 정수 $c$가 주어졌을 때 새로운 다항식 $f(x+c)$를 구하는 것을 Taylor Shift라고 부릅니다. $N$차 미만의 다항식 $f(x)$가 숨겨져 있고 값 $f(0), f(1), \cdots, f(N-1)$과 정수 $c,M$이 주어졌을 때 $f(c), f(c+1), \cdots, f(c+M-1)$을 구하는 것을 Sampling Points Shift라고 부릅니다. 위의 두 문제는 조합론 문제를 해결할 때 종종 유용한 도구가 되어 줍니다. 두 문제 모두 단순하게 풀면 너무 느리지만, FFT를 사용한다면 효율적으로...
-
Folding Part 1: ProtoStar
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 ProtoStar에 대해서 다룹니다. https://eprint.iacr.org/2023/620.pdf Folding이란 무엇이며, ProtoStar의 목표는 무엇인가 Folding은, input 자체만 제외하면 증명하고자 하는 연산의 형태는 동일한 두 ZKP instance를 하나의 instance로 fold 하는 테크닉으로, 올해 초부터 더욱 본격적인 관심을 받게된 테크닉입니다. 기존에 IVC를 (Incrementally Verifiable Computation) 얻으려면 recursive SNARKs, 즉 이전 SNARK의 verification 과정을 다시 SNARK로 올려 계산하는 방식으로 구현했다면, 이제는 SNARK를 accumulate 하여 접어가면서 쌓아올린 후 최종 accumulator를 가지고 전체...