-
Brakedown Overview
이 내용은 https://eprint.iacr.org/2021/1043 의 요약입니다. 이 논문의 목표는 Linear Code를 기반으로 한 Linear-Time PCS를 준비하고 이를 Spartan에 적용하여 Linear-Time Field-Agnostic SNARK를 얻는 것입니다. Spartan 계열 테크닉이 주목을 받는 시점에서 읽기 좋은 논문이라고 생각됩니다. 다만, 길이의 문제로 각종 증명들은 생략하도록 하겠습니다. Linear Time Polynomial Commitment Multilinear polynomial을 기준으로 생각하면, $g$의 Lagrange basis에서 coefficient를 $u$라고 했을 때 \[g(r) = \sum_i u_i \cdot \left(\prod_{k} (r_k i_k + (1 - r_k)(1 - i_k)) \right)\] 라고 쓸 수 있고, 대괄호...
-
Heavy-Light Decomposition Recursive DP
개요 Heavy-Light Decomposition Heavy-Light Decomposition(HLD)은 루트 있는 트리를 여러 개의 heavy chain으로 분할하는 알고리즘으로, 다음의 성질들을 만족합니다. 각 간선은 heavy edge 또는 light edge로 분류됩니다. 리프가 아닌 정점은 자식들 중 정확히 하나를 heavy child로 갖습니다. heavy child로 가는 간선은 heavy edge이고, 다른 자식으로 가는 간선은 모두 light edge입니다. heavy edge로 연결된 정점들의 묶음을 heavy chain이라 합니다. 각 heavy chain의 형태는 한 정점에서 출발해서 리프까지 내려가는 연속적인 경로가 되고, 모든 정점은 정확히 하나의 heavy chain에 속하게...
-
Multi Key Homomorphic Encryption - 1
Introduction 저번 글에서, Multi Party HE에 대해 간단하게 설명을 했습니다. 이번 글에서는 Multi Key HE에 대해서 간단히 설명하는 글을 쓰려고 합니다. 이번에 기준으로 한 논문은 여기에서 보실 수 있으며, 저자들의 이름을 따서 CDKS scheme이라고도 불립니다. 논문에서는 기본적인 Multi Key HE에 대한 설계를 바탕으로, BFV, CKKS에 적용시켜 Multi Key BFV, Multi Key CKKS 역시 설명하고 있으나, 이번 글에서는 아직 CKKS를 자세히 설명한 적도 없고, 적용도 그렇게 어렵지 않으므로, Multi Key HE의 구조에 대해서만 설명하려고 합니다. 저번...
-
Facebook의 설정 관리 시스템
이 글에서는 SOSP 2015 논문에 소개된 Facebook의 설정 관리 시스템을 살펴봅니다. Introduction 오늘날 대규모 웹서비스는 단순히 한대의 서버에서 돌아가지 않고, 수천대, 수만대 혹은 수십만대 이상의 서버로 이루어진 분산 환경에서 돌아갑니다. 이러한 상황에서 동일한 역할을 하는 서버들 사이에도 각 서버별로 다른 설정 값을 넣어줘야 하는 상황은 존재하며, 이를 “잘” 관리하는 것은 몹시 어려운 일입니다. 또한, 설정 값의 수정 또한 빈번한 경우에는 더더욱 어렵습니다. 예를 들어, 서버가 새로 시작하는 경우에만 설정 값을 읽어온다면, 새로운 설정을 적용하고 싶을...
-
Introduction to Bilateral Trade
Bilateral Trade Bilateral Trade란 기본적으로 구매자 한 명과 판매자 한 명이 item을 거래하는 것입니다. 즉, 다음과 같은 구성 요소로 이루어진다고 볼 수 있습니다: 두 agent: 구매자와 판매자 구매자의 item에 대한 평가(valuation) $B \sim F_B$, 판매자의 평가 $S \sim F_S$ 여기에서 $F_B$와 $F_S$는 각각 $B$와 $S$가 선택되는 확률분포를 뜻합니다. Bilateral Trade Mechanism Bilateral Trade에서의 Mechanism이란 다음 두 가지 함수를 어떻게 설정하는지를 뜻합니다. 할당 함수(allocation function) $A:\mathbb{R} \times \mathbb{R} \rightarrow { 0, 1 }$. 두 reported valuation...