-
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 알고리즘은 결정 트리, 랜덤 포레스트 알고리즘에 기반하며,...
-
Multilinear PCS from Univariate PCS
저번 포스팅에서는 Multilinear Polynomial에 대한 linear-time commitment 중 하나인 Brakedown에 대해서 알아보았습니다. Sumcheck 관련 기법들이 떠오르면서, Multilinear Polynomial의 commitment에 대한 기법들이 더욱 중요해졌습니다. 그 방법에는 Brakedown 및 이를 강화하는 Orion, Orion+ 뿐만 아니라 Dory, Hyrax 등 다른 기법도 존재합니다. 특히, Univariate Polynomial에 대한 Commitment를 기반으로 Multilinear Polynomial에 대한 Commitment 기법을 유도하는 기법들도 여러 가지 존재합니다. 여기서는 그 방법인 Gemini와 Zeromorph에 대해서 알아보도록 하겠습니다. 이 포스팅에 대응되는 논문은 아래와 같습니다. https://eprint.iacr.org/2022/420.pdf Section 5 https://eprint.iacr.org/2023/917 KZG +...