-
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...
-
Relaxed Convolution (2)
개요 이전에 작성한 글에서는 Relaxed Convolution의 개념과 성질, 구현 방법에 대해서 다루었습니다. 이 글에서는 Relaxed Convolution을 Problem Solving에 활용하는 방법을 다룹니다. 연습 문제 AtCoder Beginner Contest 213 H. Stroll 문제 정점이 $N$개이고 간선이 매우 많은 무방향 그래프가 주어집니다. 간선 집합은 다음과 같은 방식으로 정의됩니다. $0 \leq i < M, 1 \leq d \leq T$를 만족하는 모든 $(i,d)$ 쌍에 대해, 두 정점 쌍 $(a_i, b_i)$를 잇는 길이가 $d$인 간선이 $p_{i,d}$개 존재합니다. 이 그래프의 $1$번 정점에서 출발해서...
-
Gradient Boosting Overview
소개 Machine Learning에 대한 대중적인 인식은 대부분 Deep Learning, Neural Networks에 치중되어 있지만, 그 밖에도 활발하게 연구되면서 활용되고 있는 알고리즘들이 많이 있습니다. 이 글에서는 그 중에서 Gradient Boosting에 알고리즘에 대한 소개와 이해를 목표로 합니다. 신경망의 근간이 되는 Gradient Descent 알고리즘과 이름이 비슷하지만, Gradient Boosting 알고리즘과 Gradient Descent 알고리즘은 구조적으로 큰 유사성이 없습니다. 둘 다 loss function을 최소화한다는 유사점은 있지만, 작동 원리는 상이하며 각자에 기대하는 역할이 구분됩니다. Gradient Boost 알고리즘은 결정 트리, 랜덤 포레스트 알고리즘에 기반하며,...