-
cs71107's profile image
cs71107
January 27, 2024
HE Sanitization - Washing Machine
Introduction 지금까지는 주로 동형암호(Homomorphic Encryption)의 scheme들에 관해 글을 써왔는데, 이번 글에서는 동형암호와 관련돼 있는 연구 분야 중 하나인 Circuit Privacy에 관련된 Sanitization에 관련된 글을 써보려고 합니다. 이 글에서는 Ducas - Stehlé Washing machine에 대해서 중점적으로 설명하도록 하겠습니다. 원 논문은 이 링크에서 확인하실 수 있습니다. Backgrounds Homomorphic Encryption 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 지금까지 쓴 글들에 설명이 자세하게 나와 있으니, 자세한 설명은 생략하겠습니다. Bootstrapping 동형암호들의 경우 error를 필수적으로 가지게...
-
cs71107's profile image
cs71107
December 25, 2023
Secure Matrix Multiplication with Homomorphic Encryption - 1
Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...
-
cs71107's profile image
cs71107
October 30, 2023
Multi Key Homomorphic Encryption - 3
Introduction 저번 글에서, 이어서, MKHE에 대한 설명을 하겠습니다. 저번 글을 읽고 오시는 것이 이해하기 편할 것 같습니다. Notation의 경우 저번 글에서 사용한 것을 그대로 가져다가 사용하겠습니다. 이 글에서는 저번 글에서 설명을 다 하지 못한 Multiplication에 대한 설명을 하도록 하겠습니다. Backgrounds MKHE의 경우 저번 글에서 기준으로 한 논문에 이어서 추가 연구가 진행됐습니다. 다른 연산의 경우 거의 바뀐 것이 없습니다. 다만, Multiplication의 경우, 현재는 저 논문보다 더 개선된 방식으로 key를 생성해서 evaluation을 수행합니다. 새로 사용하는 방식이 이해도...
-
cs71107's profile image
cs71107
September 27, 2023
Multi Key Homomorphic Encryption - 2
Introduction 저번 글에서, 이어서, 이 논문의 내용을 기준으로 하여, MKHE에 대한 설명을 이어서 진행합니다. 따라서, 저번 글을 읽고 오시는 것이 여러 면에서 도움이 됩니다. 아래에 정리해둔 Notation에 잘 모르겠다는 부분이 있다면, 저번 글과 BFV를 설명한 글들을 읽고 오시는 것을 추천드립니다. Backgrounds Notation 이 글에서는 논문에서 사용한 Notation을 거의 따릅니다. 저번 글에도 썼지만, 다시 정리하면 다음과 같습니다. 먼저, $\textbf{u}, \textbf{v}$처럼 굵은 소문자들은 vector를 나타냅니다. 그리고, $\langle \textbf{u} , \textbf{v} \rangle$는 vector의 innner product를 나타냅니다. real number...
-
cs71107's profile image
cs71107
August 20, 2023
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의 구조에 대해서만 설명하려고 합니다. 저번...
-
cs71107's profile image
cs71107
July 23, 2023
Multi Party Homomorphic Encryption
Introduction Homomorphic Encryption (HE)는 secret key 가 없어도, ciphertext끼리의 evaluation이 가능한 scheme들으로, cloud computing등에 적합한 model이기 때문에 많은 관심을 받고 있습니다. Gentry가 처음으로 BGV를 제안안 이후, BFV, CKKS, TFHE 등의 scheme들이 제안됐습니다. 하지만 지금까지 제안되고, 널리 사용되는 scheme들에는 한 가지 공통점이 있는데, 그것은 하나의 고정된 secret key를 가진다는 것입니다. 얼핏 보면 당연할 수 있는 말이지만, 이는 HE scheme들이 가진 단점이기도 합니다. cloud computing 같은 걸 하면 여러 개의 party에 대해 data를 주고 받고, 해야 하는데,...
-
cs71107's profile image
cs71107
May 21, 2023
BFV scheme에 대한 소개 - 5
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV Multiplication을 어떻게 처리하는지에 대해서 설명을 했습니다. 이번 글에서는 저번 글에서 다 하지 못한 설명을 마무리하도록 하겠습니다. Backgrounds 이번 글은 기본적으로 저번 글에서 설명한 내용을 이어서 하는 것이기 때문에, 따로 Background는 필요하지 않으나, 저번 글의 내용을 이해하는 것이 중요합니다. 특히 FastBConv 함수의 정의에 대해서 잘 기억해 주세요. Step 4. 앞의 step 3의 결과를 다시 불러와 봅시다. \[FastRNSFloor_q(t \cdot ct[j], B_{sk})...
-
cs71107's profile image
cs71107
April 23, 2023
BFV scheme에 대한 소개 - 4
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV decryption을 어떻게 처리하는지에 대해서 설명했습니다. 이번 글에서는 multiplication을 어떻게 처리하는지에 대해서 설명하도록 하겠습니다. Backgrounds 이번에 설명할 연산은 RNS module의 BFV scheme에서 multiplication 입니다. 얼핏 생각했을 때, decryption에서 rounding을 correction하는 법도 이미 구했고, Multiplication 역시 비슷하게 하면 되지 않을까? 라는 생각을 할 수 있습니다. NTT등을 사용하면 속도도 빠르게 나올 것입니다. 하지만, 그냥 곱하는 방법을 쓰면 문제가 있는데, 바로 Noise Growth가...
-
cs71107's profile image
cs71107
March 16, 2023
BFV scheme에 대한 소개 - 3
Introduction 지금까지 BFV Scheme에 관한 설명글과, BFV scheme의 practical한 구현을 위해서 RNS module이라는 걸 사용한다는 것 그리고, RNS module에서 operations들이 기본적으로 어떻게 돌아가는지에 대해 설명하는 글을 썼습니다. 이번 글에서는 RNS module에서 구현하기 까다로운 연산들을 어떻게 처리하는지에 대해 설명하겠습니다. Backgrounds 저번 글에 좀 더 자세히 설명하고 있지만, Background를 한 번 더 짚고 넘어가겠습니다. RNS module은 널리 알려진 CRT(Chinese Remainder Theorem)에 기반하여 큰 범위의 수를 작은 수 여러 개로 표현하는 방식입니다. Homomorphic Encryption은 보안상의 이유 때문에 대부분...
-
cs71107's profile image
cs71107
February 14, 2023
BFV scheme에 대한 소개 - 2
Introduction 저번 글에서 BFV scheme에 대해서 소개하는 글을 썼습니다. 이 글에선 저번 글에서 사용한 notation들을 따와서 설명을 할 것이기 때문에, 이전 글을 다시 한번 읽고 오시면 이해가 더 쉬울 것입니다. 이번 글에서는 BFV scheme의 실제적인 구현을 위한 알고리즘들을 좀 더 설명하는 글을 쓰도록 하겠습니다. 이 글에서 사용한 Microsoft SEAL의 코드 구현은 이 글이 쓰여진 시점에서 최신 version의 SEAL(206648d)의 구현을 따릅니다. RNS representation Definition 본격적으로 설명하기에 앞서, RNS representation에 대해 먼저 설명을 하도록 하겠습니다. RNS(Residue Number...
-
cs71107's profile image
cs71107
January 17, 2023
BFV scheme에 대한 소개 - 1
Introduction 저번 글에서 Homomorphic Encryption, 동형암호에 대해서 소개하는 글을 썼습니다. 이번 글부터는 저번 글에서 소개한 여러가지 FHE scheme 중에서, BFV scheme에 대해 설명하는 글을 쓰려고 합니다. 저번 글에 Homomorphic Encryption에 대한 간단한 설명과 특징을 설명했습니다. 이 글에서는 Homomorphic Encryption에 기본 개념에 대해서 알고 있다고 생각하고 설명할 것이기 때문에, 이번 글을 읽기 전에 저번 글을 읽고 오시는 것을 추천드립니다. 이번 글에서는 BFV scheme의 다양한 연산들에 대해서 설명하도록 하겠습니다. Key Generation BFV scheme에서 key 생성을 어떻게 하는지...
-
cs71107's profile image
cs71107
November 22, 2022
Homomorphic Encryption에 대한 소개
Introduction 올 한해 크립토랩이라는 스타트업에서 근무할 기회가 있었습니다. 크립토랩은 Homomorphic Encryption, 즉 동형암호 scheme 중 CKKS를 바탕으로 창업한 스타트업입니다. (CKKS scheme을 제안하신 천정희 교수님이 대표입니다.) 회사에서 근무하며 그동안 잘 몰랐던 동형암호에 대해서 배울 기회가 있었습니다. 현재 국내에는 동형암호에 대해 서술하는 자료가 그리 많지 않은 것으로 보여, 동형암호에 대한 소개글을 작성하기로 했습니다. What is Homomophic Encryption? 먼저 동형암호가 무엇인지 간단하게 설명하도록 하겠습니다. 우선 보통의 암호 scheme의 경우 평문(plaintext)와 암호문(ciphertext)의 관계를 최대한 random하게 만드려고 합니다. 평문과 암호문...
-
cs71107's profile image
cs71107
August 21, 2022
MLIR 소개
들어가기 전에 MLIR, 즉 Multi-Level Intermediate Representation은 하드웨어에 따른 연산들을 지원하는, 중간 언어(Intermediate Representation)에 대한 library라고 보면 됩니다. 아마 꽤 생소할 것 같습니다. 이 글에서는 MLIR에 대한 배경, 구성 요소 등에 대해 간단히 소개하고자 합니다. BackGround 본격적으로 MLIR에 대해 설명을 하기 전에, 이 글을 이해하는 데 있어서 알고 있으면 편한 개념들에 대해서 먼저 설명하도록 하겠습니다. IR 위에서도 언급한 IR은 Intermidate Representation의 약자로, 중간언어 집합을 말합니다. 어떤 source code가 있다고 할 때, compiler는 그것을 target machine에...
-
cs71107's profile image
cs71107
July 17, 2021
XOR 관련 문제를 푸는 접근법들
들어가기 전에 XOR (bitwise exclusive or)은 대표적인 bit 연산 중 하나입니다. 다른 bit 연산인 AND,OR,NOT이 갖지 못하는 특성 때문에, PS 및 CP에서도 관련 문제가 심심치 않게 출제되곤 합니다. 하지만 문제 제목이나 지문에 XOR이 있으면 일단 긴장하거나, 기피하시는 분들도 꽤 자주 본 것 같습니다. 그래서, 이번 글에서는 이런 XOR 관련 문제들에 접근하는 방법 몇 가지를 설명해 보려고 합니다. Basic Part 본격적으로 들어가기에 앞서, XOR 연산이 가지고 있는 성질 몇 가지에 대해서 간단하게 짚고 넘어가려고 합니다. 여러...