Reviewed CKKS with chatGPT for the novice - 2

original post : https://blog.openmined.org/ckks-explained-part-2-ckks-encoding-and-decoding/

CKKS explained, Part 2: Full Encoding and Decoding

 

Q. canonical embedding σ 란 무엇인가?

Canonical embedding은 다항식에서 논리적인 값, 예를 들어 부울 값, 정수 또는 유리수와 같은 일반적인 수학적 값으로의 매핑을 나타내는 함수입니다. 암호학에서는 수학적 객체를 암호화하고 그 결과를 다시 수학적 객체로 복호화하는 것과 같은 작업에 유용하게 사용됩니다.

CKKS 알고리즘에서 canonical embedding은 부동 소수점 수를 다항식 계수로 변환하는 데 사용됩니다. 이것은 다항식으로부터 부동 소수점 값을 가져오는 것과 같이 부동 소수점 값을 다항식으로 가져올 수 있도록 해줍니다. 이를 통해 다항식에서 부동 소수점 계산을 수행할 수 있습니다.

In the context of homomorphic encryption, canonical embedding σ is a mathematical mapping function that embeds an input message or plaintext into the polynomial ring C[X]/(X^N+1), where C is the set of complex numbers and N is a positive integer.

This embedding function is used to convert a plaintext message into a polynomial representation that can be encrypted using a homomorphic encryption scheme such as CKKS. The canonical embedding function σ typically involves some form of encoding, such as the technique of lifting, to map the input message into a polynomial in C[X]/(X^N+1) that satisfies certain mathematical properties required by the encryption scheme.

The resulting polynomial can then be encrypted and processed using homomorphic operations to compute encrypted results that can be decrypted to obtain the desired output. The canonical embedding function is an important component of homomorphic encryption schemes and plays a critical role in enabling computations on encrypted data.

 

Q. Φ ζ σ ξ 는 어떻게 읽나?

Φ는 "파이"라고 읽으며, ζ는 "제타"라고 읽습니다. σ는 "시그마"로 읽습니다. ξ는 "크기" 혹은 "제크스" (jex)로 읽을 수 있습니다.

Φ is typically read as "phi", ζ is typically read as "zeta", σ is typically read as "sigma", and ξ is typically read as "xi".

 

Q. σ(m)=(m(ξ),m(ξ^3),...,m(ξ2^N−1))∈C^N 의 의미가 무엇인가?

 

이 식에서 σ는 canonical embedding을 나타내며, m은 다항식을 나타냅니다. 이 식은 다항식 m을 N차원 벡터 (C^N) 로 매핑하는 것을 나타냅니다. 이 매핑은 다항식 m의 계수를 2^N-1차원 복소수 체에서 정의된 원시 N차원 단위근의 값을 사용하여 벡터로 변환합니다.

 

즉, m(ξ^i)는 다항식 m을 ξ^i에 대입한 값을 의미하며, i는 0부터 2^N-1까지의 값을 가질 수 있습니다. 이렇게 얻은 값들이 σ(m)의 각 성분이 되어 N차원 벡터로 표현됩니다.

따라서, σ(m)=(m(ξ),m(ξ^3),...,m(ξ2^N−1))은 다항식 m의 계수를 2^N-1차원 복소수 체에서 정의된 원시 N차원 단위근의 값을 사용하여 N차원 벡터로 변환하는 것을 의미합니다.

In the context of the CKKS encryption scheme, σ is a canonical embedding that maps plaintext messages in some message space to a polynomial representation in the ciphertext space. Specifically, given a plaintext message m, σ maps m to a vector of complex numbers (m(ξ), m(ξ^3), ..., m(ξ^(2N-1))) where ξ is a primitive 2N-th root of unity and N is the degree of the ciphertext polynomial.

In other words, σ takes a message m and evaluates it at the 2N-th roots of unity in a specific pattern, resulting in a vector of complex numbers. This vector is then used to construct the plaintext polynomial, which is encrypted using the CKKS scheme.

The canonical embedding σ is an important part of CKKS because it ensures that the plaintext message is represented as a valid polynomial in the ciphertext space, allowing for efficient homomorphic operations on the encrypted data.

 

Q. polynomial rings이 무엇인가?

Polynomial ring은 다항식의 공간입니다. 다항식의 계수와 변수가 주어졌을 때, 이들의 모든 가능한 조합으로 이루어진 집합을 말합니다. 예를 들어, 변수 X와 계수가 정수인 다항식의 집합은 다음과 같이 나타낼 수 있습니다.

Z[X] = {a_nX^n + a_{n-1}X^{n-1} + ... + a_1X + a_0 | a_i∈Z, n∈N}

이 집합은 다음과 같은 연산이 가능합니다.

• 덧셈: 두 다항식을 더할 수 있습니다.
• 곱셈: 두 다항식을 곱할 수 있습니다.
• 계수 곱셈: 다항식의 모든 계수에 상수를 곱할 수 있습니다.

Polynomial ring는 대수적 구조의 한 종류로, 대수학이나 대수기하학 등 다양한 분야에서 중요한 개념으로 사용됩니다.

In abstract algebra, a polynomial ring is a mathematical construct that generalizes the concept of a polynomial in one variable to two or more variables. It is essentially a ring of polynomials, where a ring is a mathematical structure consisting of a set of elements and two operations, usually addition and multiplication, that satisfy certain properties.

In a polynomial ring, the variables are usually denoted by x, y, z, and so on, and the elements of the ring are polynomials in these variables with coefficients from a given ring, such as the integers or real numbers. The ring operations of addition and multiplication are defined in the usual way, with the additional requirement that the variables commute with each other.

Polynomial rings have a wide range of applications in algebra and geometry, including algebraic number theory, algebraic geometry, and coding theory. They are also important in computer science, where they are used in algorithms for symbolic computation, computer algebra systems, and cryptography.

 

Q. conjugate roots란 무엇인가?

 

 

다항식의 복소수 해 (해석학에서, 이해 가능한 가장 깊은 깊이까지만)는 복소공간에서 서로 대칭인 위치에 위치한 복소수 쌍입니다. 즉, 만약 다항식의 한 해가 a+bi라면, conjugate root는 a-bi입니다. 예를 들어, x^2-2x+2=0의 경우, 해는 x=1+i와 x=1-i입니다. 이들은 서로 conjugate roots입니다.

 

Q. conjugate의 뜻은 무엇이며 어원은 어떻게 되나?

 

conjugate는 "동료" 또는 "반대"라는 뜻을 가진 형용사이며, 라틴어 "conjugatus"에서 파생되었습니다. "conjugatus"는 "함께 결합된" 또는 "묶인"을 의미하는 "con-"과 "jugum"이라는 단어의 과거 분사형입니다. "jugum"은 "커플" 또는 "묶인 것"을 의미합니다. 따라서 "conjugate"는 두 개 이상의 요소가 묶여있거나 결합된 것을 의미하며, 복소수의 경우에는 두 개의 복소수가 서로 묶여있는 형태를 가리킵니다.

 

Q. coordinate-wise random rounding 란 무엇인가? RLWE에서는 어떤 용도인가?

 

Coordinate-wise random rounding은 벡터의 각 구성 요소를 랜덤하게 반올림하는 기술로, 암호학에서 많이 사용됩니다. RLWE (Ring Learning with Errors) 암호 시스템에서는, RLWE 문제를 해결하기 위해 평문 벡터를 랜덤 벡터와 함께 더한 후, 결과를 반올림합니다. 이때 coordinate-wise random rounding을 사용하여 반올림을 수행합니다.

RLWE에서 coordinate-wise random rounding은 중요한 역할을 합니다. 왜냐하면, RLWE 알고리즘의 보안성은 랜덤 벡터와 평문 벡터의 합이 얼마나 잘 숨겨지는지에 달려있기 때문입니다. coordinate-wise random rounding을 사용하면, 랜덤 벡터와 평문 벡터의 합을 반올림하는 것으로 랜덤 벡터의 비밀성을 보호할 수 있습니다. 이러한 반올림 작업은 RLWE 암호 시스템에서 매우 중요하며, 그 성능과 보안성에 영향을 미칩니다.

 

Q. 왜 coordinate-wies라는 표현을 사용하였는가?

 

Coordinate-wise란 각각의 좌표(원소)에 대해 따로 처리한다는 의미입니다. 즉, 여기서는 각각의 차원(원소)에 대해 랜덤 라운딩을 하는 것을 의미합니다. RLWE에서는 이를 이용해, 평문의 다항식을 랜덤 다항식과의 합으로 나타낸 다음, 이 합을 랜덤 노이즈를 더해 암호문으로 변환합니다. 이때, 랜덤 노이즈를 추가하기 전에 coordinate-wise random rounding을 수행하여, 암호문의 값이 더욱 랜덤해지도록 합니다.

 

Q. orthogonal Z-basis 의미는 무엇이며, 수학에서 orthogonal하다는 뜻은 무엇을 나타내는가?

 

Orthogonal Z-basis는 Lattice(격자)를 구성하는 벡터들 중 서로 직교하는 벡터들의 집합을 의미합니다. 이러한 벡터들의 집합은 모든 격자 점을 생성하는 기본 벡터의 집합으로 사용됩니다.

수학에서 orthogonal(직교)는 벡터 공간에서 두 벡터가 수직을 이룬다는 의미입니다. 즉, 두 벡터가 이루는 각이 90도인 경우를 말합니다. 이러한 두 벡터는 내적이 0이 되며, 이것은 두 벡터가 서로 독립적이라는 것을 의미합니다.

 

Q. hemitian product 란 무엇인가?

 

Hermitean product(에르미트 곱)은 선형 대수학에서 두 벡터의 곱을 정의하는 방법 중 하나입니다.

에르미트 곱은 내적(inner product)과 유사하지만, 내적이 실수 체에서 정의되는 반면, 에르미트 곱은 복소수 체에서 정의됩니다. 따라서 에르미트 곱은 두 벡터의 공액(conjugate transpose)을 곱한 후, 다시 벡터를 곱하는 방식으로 정의됩니다. 즉, 벡터 x와 y의 에르미트 곱은 x^H * y 로 나타낼 수 있습니다. 여기서 x^H는 벡터 x의 공액입니다.

RLWE에서 에르미트 곱은 RLWE 암호 시스템에서 벡터와 행렬의 곱셈을 정의하는 데 사용됩니다. 에르미트 곱은 벡터와 공액 행렬의 곱으로 표현됩니다. 이를 통해 RLWE에서 사용되는 행렬 연산을 간단하게 수행할 수 있습니다.

 

Q. 공액이란 무엇인가?

 

공액 (conjugate)는 복소수에서 쓰이는 용어로, 복소수의 실수부와 허수부에 대해 각각 부호를 바꾸거나, 허수부에 마이너스를 붙인 수를 말합니다. 예를 들어, 복소수 z=a+bi의 공액은 a-bi입니다. 공액은 복소수의 성질을 연구하고, 복소수에서 산술 연산을 할 때 자주 사용됩니다. 또한, 행렬에서도 공액의 개념이 사용됩니다.

 

Q. 왜 부호를 바꾸는게 중요한가?

 

부호를 바꾸는 것은 수학적으로 말하면 켤레 복소수를 취하는 것과 같습니다. 이는 주어진 수와 곱하여 결과가 실수인 수를 찾을 때 매우 유용합니다. 예를 들어, 실수 벡터의 내적을 계산할 때 두 벡터 중 하나의 부호를 바꾸어 켤레 복소수를 취하면, 내적 연산이 행렬 곱셈과 같아지기 때문에 계산이 용이해집니다. 이와 같이 부호를 바꾸는 것은 수학적으로 다양한 분야에서 유용하게 활용됩니다. RLWE에서는 부호를 바꾸어 켤레 복소수를 계산하여 벡터와 그의 켤레 복소수의 내적을 구함으로써 암호화된 메시지를 복호화하는 등의 용도로 사용됩니다.

 

Q. 실수 백터의 내적이 의미하는게 무엇인가?

 

 

실수 벡터의 내적은 두 벡터 사이의 코사인 값을 반환하는 연산입니다. 즉, 벡터 A와 벡터 B의 내적은 A와 B가 이루는 각도가 얼마인지에 대한 정보를 제공합니다. 내적 값이 0이면 두 벡터는 수직이며, 내적 값이 양수면 두 벡터가 이루는 각이 예각이고, 내적 값이 음수면 두 벡터가 이루는 각이 둔각입니다. 내적 연산은 다양한 분야에서 유용하게 사용됩니다. 예를 들어, 선형대수학에서 내적 연산을 사용하여 벡터의 길이, 직교성 등을 구할 수 있으며, 물리학에서는 내적 연산을 사용하여 물체의 운동 에너지, 일, 힘 등을 계산합니다.

 

Q. π^−1(z)∈H 의 의미는 무엇인가?

 

여기서 π는 상용원(circle map)이며, H는 상반면 상수 함수 반복하여 생성되는 모듈러 그룹(Modular group)의 상부반 평면(Upper half-plane)입니다.

π^−1(z)는 상용원 π에 대한 역함수를 나타내며, z는 상부반 평면의 한 점을 나타냅니다. 이 식의 결과는 원래의 평면에서 z와 같은 점을 지나는 상용원의 꼭지점입니다. 따라서, π^−1(z)∈H는 z와 같은 점을 지나는 상용원의 꼭지점이 상부반 평면의 점이라는 것을 의미합니다.

 

Q. H는 무엇인가?

 

H는 상반면 위상변환군(Poincaré upper half-plane)을 나타내는 것으로, 복소평면 상단 반원 모양의 영역을 말합니다. H는 복소평면에서 다음과 같이 정의됩니다.

H = {z ∈ C | Im(z) > 0}

즉, H는 허수부가 양수인 복소수들의 집합입니다. 상반면 위상변환군은 수학에서 다양한 분야에서 활용되는 중요한 개념 중 하나입니다.

 

Q. Im(z)의 의미는 무엇인가?

 

Im(z)는 복소수 z의 허수 부분을 나타내는 실수입니다. 즉, z=a+bi 형태일 때 Im(z)=b 입니다. 이는 z를 복소평면 위의 좌표로 표현할 때, z가 y축에서 얼마나 떨어져 있는지를 나타내는 값입니다.

 

 

Q. lm은 약어인가?

 

예, "lm"은 약어입니다. "lm"은 "leading monomial"의 약어로, 다항식의 가장 높은 차수의 단항식을 의미합니다.