-
HE Sanitization - Washing Machine
Introduction 지금까지는 주로 동형암호(Homomorphic Encryption)의 scheme들에 관해 글을 써왔는데, 이번 글에서는 동형암호와 관련돼 있는 연구 분야 중 하나인 Circuit Privacy에 관련된 Sanitization에 관련된 글을 써보려고 합니다. 이 글에서는 Ducas - Stehlé Washing machine에 대해서 중점적으로 설명하도록 하겠습니다. 원 논문은 이 링크에서 확인하실 수 있습니다. Backgrounds Homomorphic Encryption 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 지금까지 쓴 글들에 설명이 자세하게 나와 있으니, 자세한 설명은 생략하겠습니다. Bootstrapping 동형암호들의 경우 error를 필수적으로 가지게...
-
Learning shallow quantum circuits
올해 1월 18일, Learning shallow quantum circuits라는 제목의 연구가 arxiv에 올라왔고, 가장 큰 양자정보 학회인 QIP에서 해당 논문을 가지고 발표까지 진행되었다. 이 연구는 양자 회로를 학습하던 방식을 바꿔놓을 가능성이 있는 연구이고, 어쩌면 Quantum Machine Learning(QML)의 미래 자체에 영향을 줄 수도 있을것 같아 보인다. 굉장히 좋은 아이디어도 얻어갈 것이 많은 연구라고 생각하여서 공유해보고자 한다. 요약 이 논문에서 해결하고자 하는 문제는 두 가지이다. Unknown unitary $U$에 여러 입력으로 여러 번 접근할 수 있을 때, 최대한 가까운 unitary...
-
Degree Bounded Travel Salesman Problem
1. Introduction 우리가 아는 일반적인 TSP(Travel Salesman Problem) 문제는 간선에 가중치가 있는 연결 그래프 $G = (V, E, c) (c : E \to \mathbb{R}_{\ge 0})$ 가 주어질 때 아무 정점에서 시작해 다른 모든 정점을 방문하고 다시 시작 정점으로 돌아오는 최소 비용의 이동 방법을 구하는 문제이다. 이 글에서는 Degree Bounded TSP 문제에 대해 ISAAC 2022에서 발표된 내용을 다룬다. 이 문제에서는 각 정점에 차수 제한 $b_v \ge 0 (v \in V)$ 가 추가적으로 주어진다. (단, $b_v$는 짝수인...
-
CUDA #01: Introduction to Many-Core Programming
Introduction Many-Core Programming Many-core processor는 많은 수의 core를 가져 대규모의 병렬 연산이 가능한 프로세서를 의미하며, 이를 활용하는 것을 many-core programming이라고 부른다. 유사한 용어인 multi-core는 수~수십 개 정도의 core들에 대한 의미를 주로 포함하는 것과는 달리, many-core는 그보다 훨씬 많은 수천~수만 개의 core들에 대하여 사용한다. 최근 many-core programming은 GPU(Graphics Processing Unit)가 게임, 계산과학, 인공지능 등 다양한 workload들을 처리하기 시작하면서 매우 중요해지고 있는 추세이다. 특히 GPT, ViT 등 Transformer 기반의 거대 AI 모델들은 실수의 행렬곱이라는 병렬화가 매우 잘...
-
Communication complexity
Introduction two-party model of deterministic communication (늘 그렇듯이) Alice와 Bob이라는 이름의 두 사람이 있다. 함수 $f: X \times Y \rightarrow Z$에 대해, Alice는 $x \in X$, Bob은 $y \in Y$를 알고 있을 때 두 사람이 $f(x,y)$를 최소 bit의 커뮤니케이션으로 알아내는 것이 목표이다. 즉, 목표는 $f(x,y)$의 값을 두 명이 알아내는 것이고, cost가 주고받은 bit의 개수일 때 cost를 minimize하는 문제이다. 먼저 여러 가지 $f$의 예를 살펴보며 각각 어떤 방식으로 해결하는 것이 확인해 보자. Example 1. $EQ_n: \{...