-
GSW : Homomorphic Encryption with Gadget
Introduction 안녕하세요. 이전 글에서는 TFHE라는 동형암호를 다루기 위한 기본적인 암호화, 복호화와 덧셈 연산이 어떻게 이루어지는지를 알아보았습니다. 이번 글에서 다루는 주제는 동형암호는 맞으나 TFHE는 아닌데요. 이는 TFHE scheme 중간에 등장하게 되는 개념인 GGSW sample이라는 개념이 바로 지금 제가 다루고자 하는 동형암호인 GSW scheme[1] 에서 가져온 것이기 때문에, 중간에 한 번 쉬어가더라도 GSW scheme과 gadget이라는 개념을 다루고 가는 것이 도움이 될 것이라 생각해서 GSW scheme에 대한 글을 먼저 쓰게 되었습니다. 동형암호의 개념 자체에 대해 생소하신 분이라면 먼저...
-
Gröbner Basis와 Buchberger's algorithm, 그 활용
목표 Gröbner Basis는 주어진 몇 개의 다항식들로 생성되는 환에 대한 분석을 쉽게 해주는 강력한 툴입니다. 이 포스트의 목표는 Gröbner Basis를 구할 수 있는 Buchberger’s algorithm과 그 정당성에 대해 직관적으로 이해하고, Gröbner Basis를 통해서 해결할 수 있는 문제들에 대해 알아보는 것입니다. 사전지식 - Basic Algebra 이 단락에서는 환과 아이디얼이 무엇인지에 대해 다룹니다. 환이라는 것은, 간단히 말해 덧셈과 곱셈이 정의되어있고, 결합법칙, 분배법칙, 덧셈에 대한 교환법칙이 성립하며, 덧셈에 대한 항등원과 역원이 존재하고, 곱셈에 대한 항등원이 존재하는 대수구조를 말합니다....
-
TFHE : Fully Homomorphic Encryption over the Torus - 1
Introduction 동형암호, 영어로는 HE(Homormorphic Encryption), 또는 FHE(Fully Homomorphic Encryption)은 일반적인 암호와 다르게, 암호화된 상태에서도 연산이 가능하게 하는 scheme입니다. 예를 들어, 어떤 기업에서 MRI 결과를 입력으로 받아 그 MRI를 찍은 사람이 암에 걸렸을 확률을 계산하는 알고리즘을 개발했다고 합니다. 원래는 그 기업에게 자신의 MRI를 공개해야만 그 결과를 받아볼 수 있었을텐데, 동형암호와 함께라면 자신의 MRI를 암호화해서 보낸 뒤, 암호화된 MRI 결과를 기업이 연산하고, 받은 결과를 복호화하면 기업은 아무런 내용도 알 수 없는 것입니다! 더 자세한 개념이 궁금하시다면 이...
-
solving JIE-constant (acmicpc 22222)
문제 소개 지애 상수는 백준의 22222번째 문제를 기념하여 출제된 문제로, 문제에서 정의된 지애 상수라는 값을 소수점 222자리까지 구하는 문제입니다. 지애 상수의 정의는 아래와 같습니다. Definition of 지애 상수 지애 상수는 좌표평면의 점 $A(0,0),B(1,0),C( {1 \over 2} , { \sqrt 3 \over 2})$로 정의된 정삼각형 $ABC$에서 시작하여 만든 시에르핀스키 삼각형에서 독립적으로 균등하게 잡은 점 두 개의 유클리디안 거리의 기댓값입니다. 균등하게 점 잡기? 지애 상수를 정의하기 위해서는 우선 시에르핀스키 삼각형에서 점을 균등하게 잡는 것을 수학적으로 정의할 수...
-
Mukjjippa (BOJ 32469)
이 글은 2024 KAIST 14th ICPC Mock Competition에 출제했던 문제 중 하나인 Mukjjippa (BOJ 32469)에 대해 다룬다. Problem 두 플레이어 A와 B가 묵찌빠라는 게임을 한다. 이 게임은 여러 턴으로 이루어진다. $i$번째 턴($1\le i\le n$)에서: 각 플레이어는 $\{\mathrm R,\mathrm S,\mathrm P\}$에서 정확히 하나를 선택한다. (각각 묵(rock), 찌(scissors), 빠(paper)를 나타낸다.) $X_i$와 $Y_i$를 각각 A와 B의 선택이라 하자. 만약 $(X_i, Y_i) \in \{(\mathrm R,\mathrm S),(\mathrm S,\mathrm P),(\mathrm P,\mathrm R)\}$라면, A가 $(i+1)$번째 턴의 공격자가 되고 게임은 계속된다. 만약 그렇지...