-
문자열 해싱
이번 글에선 해싱의 다양한 활용을 정리하고자 한다. 너무 기본적인 내용이나 필자도 모르는 너무 고급 기술은 다루지 않고, 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를 가지고 전체...
-
Multi Key Homomorphic Encryption - 3
Introduction 저번 글에서, 이어서, MKHE에 대한 설명을 하겠습니다. 저번 글을 읽고 오시는 것이 이해하기 편할 것 같습니다. Notation의 경우 저번 글에서 사용한 것을 그대로 가져다가 사용하겠습니다. 이 글에서는 저번 글에서 설명을 다 하지 못한 Multiplication에 대한 설명을 하도록 하겠습니다. Backgrounds MKHE의 경우 저번 글에서 기준으로 한 논문에 이어서 추가 연구가 진행됐습니다. 다른 연산의 경우 거의 바뀐 것이 없습니다. 다만, Multiplication의 경우, 현재는 저 논문보다 더 개선된 방식으로 key를 생성해서 evaluation을 수행합니다. 새로 사용하는 방식이 이해도...
-
Maximum matching in CONGEST model
Introduction 이전에 작성한 글 A Near-Optimal Deterministic Distributed Synchronizer에서 잠깐 언급하였듯이, Distributed Graph Algorithm에서는 어떠한 모델을 가정하고 있는지에 따라 문제를 접근하는 방법이 달라지게 된다. 해당 포스트에서는 Asynchronized model을 가정하고 synchronized model처럼 문제를 해결할 수 있도록 도움을 주는 synchronizer에 대한 내용을 작성하였다. 이번 포스트에서는 synchronized model 중 하나인 CONGEST model을 가정하고, graph theory의 중요한 문제 중 하나인 maximum matching problem이 어떤 식으로 해결 가능한지에 대해 알아보도록 할 것이다. Synchronized message-passing model 분산 컴퓨팅 네트워크를 undirected graph...