-
TFHE : Fully Homomorphic Encryption over the Torus - 2
Introduction 안녕하세요. 지난 게시글에서는 동형암호 scheme중 하나인 TFHE의 암호화 / 복호화 / 덧셈 연산에 대해서 다루었습니다. 그리고 다음 게시글에서는 TFHE의 곱셈에 대해 다루기 위해서 GSW scheme과 gadget decomposition을 다루었는데요, 이 글의 이해를 위해서는 두 게시글을 읽고 오시길 추천드립니다! 이번 글에서는 TFHE에서의 곱셈(external product)가 어떻게 진행되는지와, 그리고 이러한 연산을 통해서 최종적으로 TFHE의 bootstrapping이 어떤 식으로 진행되는지에 대한 개괄적 설명을 하고자 합니다! TFHE Multiplication(External Product) Gadget Decomposition Gadget decomposition을 처음 접하시는 분은 이 글 의 설명을 읽으신다면...
-
Block Decomposition을 이용한 Online FFT 구현
Introduction 이 글에서는 Block Decomposition을 이용한 Online FFT(Fast Fourier Transform) 구현 방법을 소개합니다. 두 수열 $A$, $B$의 convolution $C$를 $\mathcal{O}(n\log n)$에 구하는 FFT 알고리즘은 두 수열 $A$, $B$가 모두 주어져야만 사용할 수 있습니다. Online FFT는 $A$, $B$의 원소 $a_i$, $b_i$가 하나씩 주어질 때 $c_i$를 온라인으로 구하는 알고리즘입니다. 이는 점화식이 convolution 형태이면서 $c_0, \cdots, c_{i-1}$을 알아야 $a_i$, $b_i$를 구할 수 있는 경우(예를 들면 카탈란 수 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$)에 사용할 수 있습니다. Online FFT는 여러...
-
Custom Select Box 만들기 (overflow 문제 해결) - (Nuxt3, Vue3)
Intro 안녕하세요. 이번 글에서는 Nuxt3에서 Custom Select Box를 구현해보려고 합니다. 이때, overflow를 허용하는 Component 내부에 존재하는 Custom Select Box에 대해 생기는 스크롤 문제를 해결하는 것이 이 글의 목표입니다. 명확한 해결책을 제시해 주는 곳이 없어 이를 해결할 수 있는 방법을 공유하고자 합니다. 또한, Select Box 외에도 Tooltip과 같이 특정 컴포넌트가 position: absolute인 상태로 상대 위치를 계산해야 하는 상황에서도 동일한 방법으로 해결할 수 있습니다. Nuxt3로 작성된 글이긴 하지만, javascript 기반으로 작동하는 여러 트릭이 많아서 굳이 Nuxt3를 몰라도,...
-
LCS 알고리즘 최적화
개요 LCS(Longest Common Subsequence) 문제는 두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제로, 컴퓨터과학에서 가장 고전적이면서 중요한 문제 중 하나입니다. 이 글에서는 이 문제를 해결하는 간단한 Dynamic Programming 해법부터, 이것의 공간 복잡도를 개선한 Hirschberg 알고리즘과, 일반적인 문자열에서 더 효율적인 Hunt-Szymanski 알고리즘을 소개할 것입니다. 그리고 이들을 비트 집합을 이용해 더욱 최적화하는 방법을 다룰 것입니다. 간단한 DP 해법 $DP[i][j]$를 $A$의 길이 $i$인 접두사와 $B$의 길이 $j$인 접두사의 LCS 길이로 정의하면 다음과 같은 점화식으로 $A$와...
-
GSW : Homomorphic Encryption with Gadget
Introduction 안녕하세요. 이전 글에서는 TFHE라는 동형암호를 다루기 위한 기본적인 암호화, 복호화와 덧셈 연산이 어떻게 이루어지는지를 알아보았습니다. 이번 글에서 다루는 주제는 동형암호는 맞으나 TFHE는 아닌데요. 이는 TFHE scheme 중간에 등장하게 되는 개념인 GGSW sample이라는 개념이 바로 지금 제가 다루고자 하는 동형암호인 GSW scheme[1] 에서 가져온 것이기 때문에, 중간에 한 번 쉬어가더라도 GSW scheme과 gadget이라는 개념을 다루고 가는 것이 도움이 될 것이라 생각해서 GSW scheme에 대한 글을 먼저 쓰게 되었습니다. 동형암호의 개념 자체에 대해 생소하신 분이라면 먼저...