-
Multi-Party Computation 2
1. Introduction 저번 시간에 이어서 Multi-Party Computation을 살펴보겠습니다. 저번 시간에는 MPC를 할 수 있는 Garbled Circuit을 만드는 방법을 알아보고 Garbled Circuit이 처음 등장한 1982년부터 Half-gates technique이 발표된 2015년까지 어떠한 흐름을 통해 발전해왔는지 확인했습니다. 이번 시간에는 실제 Garbled Circuit을 구현할 때에는 어떤 방법을 이용하는지, 그리고 그와 관련한 안전성과 공격을 살펴보겠습니다. 2. Half-gates technique 저번 글에서는 이 Half-gates technique에 관해 아주 간략하게 설명을 하고 넘어갔습니다. 그러나 이번 글에서 본격적으로 안전성에 대해 논의를 하다보면 Half-gates technique의 동작에 대해...
-
Disjoint Set & Union-find
Disjoint Set Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. 모든 집합들 사이에 공통된 원소가 존재하지 않는다는 것을, 각 원소들은 하나의 집합에만 속함을 의미하므로, 모든 원소들은 자신이 속해있는 유일한 집합만을 가지게 됩니다. Disjoint set data structure를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는데에 유용히 사용할 수 있습니다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. 정의에 의해 Disjoint Set...
-
Ray Casting Algorithm의 이분 탐색을 이용한 응용
Ray Casting Algorithm (단순) 다각형과 점이 주어졌을 때, 점이 다각형 안에 있는지 판정하는 문제는 계산 기하학뿐 아니라 컴퓨터 그래픽스에서도 중요한 문제이다. 이를 해결하는 대표적인 알고리즘이 Ray casting algorithm이다. 가장 간단한 버전의 ray casting algorithm은 다음과 같은 문제를 푸는 데 사용된다. “2차원 좌표평면 위에 단순 다각형 $(x_0, y_0), \cdots, (x_N, y_N)$이 있다. 마찬가지로 2차원 좌표평면 위에 점 $P=(x, y)$가 주어질 때, 이 점이 다각형 안에 있는지 밖에 있는지 판정하라.” Ray casting algorithm은 이를 다음과 같은 아이디어로...
-
Offline Incremental SCC
본 글에서는 간선이 하나씩 추가됨에 따라 SCC를 관리하는 Incremental SCC를 오프라인으로 처리하는 방법에 대해서 설명하겠습니다. Link Cut Digraph 문제를 보겠습니다. 문제를 간단하게 요약하자면 $N$개의 정점이 있고 $M$개의 간선을 추가하는 쿼리가 있을 때, 간선을 추가할 때마다 u에서 v로 가는 경로가 있고, v에서 u로 가는 경로가 존재하는 (u, v)(u < v, u != v)쌍의 개수를 구하는 문제입니다. 방향 그래프에서 u에서 v로, v에서 u로 갈 수 있다는 것은 u와 v가 서로 같은 SCC에 있다는 것을 의미합니다. 따라서 위...
-
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...