-
Ciphers for MPC and FHE
1. Introduction 최근의 두 포스트에서 Multi-party computation에 대해 다루었습니다. Garbled circuit의 발전사와 최종적인 형태를 보면 결론적으로 AND 연산의 수가 적으면 적을수록 MPC의 성능이 올라감을 알 수 있습니다. 또한 ZK(Zeroknowlege Proof, prover가 verfier에게 어떤 문장이 참임을 증명할 때 그 문장이 참이라는 것을 제외하면 그 어떤 정보도 prover에게 노출하지 않는 프로토콜),FHE(Fully Homomorphic Encryption, 데이터를 암호화한 상태로 연산할 수 있는 암호화 방법) 등에서도 AND 연산이 XOR 연산에 비해 훨씬 큰 비중을 차지합니다. 기존에 널리 쓰이는 암호화 알고리즘으로는 AES가...
-
헝가리안 알고리즘
안녕하세요? 오늘은 헝가리안 알고리즘(Hungarian Algorithm)에 대해 살펴보겠습니다. 헝가리안 알고리즘은 가중치가 있는 이분 그래프(weighted bitarted graph)에서 maximum weight matching을 찾기 위한 알고리즘입니다. 이분 그래프의 Matching M이 edge들의 부분집합이고, 모든 vertex들에 M에 속한 edge가 최대 한 개 연결되어 있을 때, 이러한 M을 그래프의 matching이라고 합니다. 일반적인 이분 그래프에서 최대 매칭은 최대 유량을 구하는 알고리즘을 통해 구할 수 있다는 사실이 잘 알려져 있습니다. Matching M의 weight는 M에 속한 edge들의 가중치의 합으로 정의할 수 있습니다. 이제 우리는 Matching 중...
-
Shortest Path Algorithm - Dijkstra
Dijkstra 다익스트라 알고리즘은 그래프에서 한 정점(시작 정점)에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘입니다. 여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말합니다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있습니다. 다익스트라는 알고리즘의 구조 상 다음과 같은 성질들을 가지게 됩니다. 그래프 내에 음의 가중치 합을 가지는 사이클이 있을 경우에, 다익스트라를 통한...
-
Resistor Network와 Series-Parallel Graph Class
Introduction Childhood 중학교에서 전기 회로에 대해 배울 때를 떠올려 봅시다. “전압 $V$는 전류 $I$와 저항 $R$의 곱과 같다”는 옴의 법칙을 배운 뒤, 저항이 여러 개 연결되어 있을 때, 저항값이 같은 하나의 합성 저항으로 바꾸는 방법을 배웁니다. 바로 직렬 연결과 병렬 연결이죠. 직렬 연결. 저항 $R _ {1}$과 $R _ {2}$가 직렬로 연결되어 있다면, 합성 저항 $R _ {eq}$는 $R _ {eq} = R _ {1} + R _ {2}$를 만족한다. 병렬 연결. 저항 $R...
-
정수 자료형으로 기하학 문제 데이터 검증하기
개요 기하학 문제가 까다로운 이유 중 하나는 실수 자료형을 쓸 때 생기는 부동 소수점 오차 때문입니다. 같은 이유로, 데이터가 문제의 조건에 맞는지 검증하는 과정 역시 쉽지 않습니다. 심지어 실수 자료형으로는 해결할 수 없는 경우도 존재합니다. BOJ 20939 달고나를 출제하면서 겪은 문제들과 해결한 과정에 대해 정리하고자 합니다. 입력 조건 문제에서 데이터 형식과 범위를 제외하고 검증해야 하는 조건들은 다음과 같습니다. 단순 다각형의 꼭짓점은 반시계방향 순서이다. 선분의 개수와 원의 개수 합이 2,000을 넘지 않는다. 세 개 이상의 선(원...