-
플로우 그래프 커팅
개요 Problem Solving을 하다 보면, 주어진 문제에서 플로우 그래프를 모델링했을 때 그래프의 크기가 너무 커서 단순히 플로우 알고리즘을 사용할 경우에 시간 초과를 받게 되는 상황이 종종 발생합니다. 이 글에서는 위와 같은 상황에서 추가적인 관찰을 통해 플로우 그래프의 크기를 줄이는 몇 가지 방법을 소개합니다. 문제마다 필요한 관찰과 해결 방법이 제각기 다를 수 있으므로 다양한 연습 문제를 예시로 들어서 설명하겠습니다. 디닉 알고리즘의 구현체를 통일하기 위해 AtCoder Library의 MaxFlow를 사용하겠습니다. 연습 문제 AtCoder Beginner Contest 320 G. Slot...
-
Secure Matrix Multiplication with Homomorphic Encryption - 1
Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...
-
Number Theory Techniques
https://www.acmicpc.net/category/detail/4072 해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다. F. Queens’ Rye Cafe 요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다. Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다. Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와...
-
양자컴퓨팅으로 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} =...