XTS provides greater data protection over other block cipher modes, such as CBC and ECB.
It eliminates potential vulnerabilities associated with some of the more sophisticated side channel attacks that could be used to exploit weaknesses within other modes.
XTS uses two AES keys. One key is used to perform the AES block encryption; the other is used to encrypt what is known as a "Tweak Value."
Since each block is independent and there is no chaining, if the stored cipher data is damaged and becomes corrupted, only the data for that particular block will be unrecoverable.
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와 계수가 정수인 다항식의 집합은 다음과 같이 나타낼 수 있습니다.
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"의 약어로, 다항식의 가장 높은 차수의 단항식을 의미합니다.
벡터를 다항식으로 인코딩하는 방법에는 여러 가지가 있지만, 가장 일반적인 방법 중 하나는 벡터의 각 요소를 다항식의 계수로 사용하는 것입니다. 이를 "다항식 인코딩" 또는 "벡터-다항식 매핑"이라고도 합니다.
예를 들어, 다음과 같은 3차원 벡터 $v = (1, 2, 3)$이 있다고 가정해 봅시다. 이를 다항식으로 인코딩하면 다음과 같은 방식으로 할 수 있습니다.
다항식의 각 항에 해당하는 지수는 각 요소의 인덱스입니다. 즉, 첫 번째 요소는 0차항, 두 번째 요소는 1차항, 세 번째 요소는 2차항에 해당합니다.
각 요소의 값을 해당 차수의 계수로 사용합니다. 따라서 위의 벡터 $v$를 다항식으로 인코딩하면 다음과 같습니다.
$$v(x) = 1 + 2x + 3x^2$$
이렇게 인코딩된 다항식은 일반적인 수식과 같이 다항식 계산, 미분, 적분 등 다항식 연산에 활용될 수 있습니다. 또한, 다항식의 루트를 찾는 문제에서도 활용될 수 있습니다.
Encoding a vector as a polynomial involves representing the vector as the coefficients of a polynomial. Given a vector v = (v1, v2, ..., vn), we can construct a polynomial f(x) = v1 + v2x + ... + vnx^(n-1). This polynomial has degree n-1, and its coefficients are precisely the entries of the vector v. Thus, we can encode the vector v as the polynomial f(x) with degree n-1 and coefficients (v1, v2, ..., vn).
Q. isomorphism을 설명해줘
동형사상(isomorphism)은 두 개의 대상 사이에 존재하는 구조적인 동일성을 나타내는 개념입니다.
보통 대상은 수학적인 객체들이며, 대표적으로 그룹, 벡터공간, 위상공간 등이 있습니다. 동형사상은 이러한 대상 사이의 구조적인 동일성을 나타내기 때문에, 대상 사이의 유용한 비교나 분류, 연구 등에서 중요한 역할을 합니다.
두 대상 A와 B가 있을 때, A와 B 사이에 동형사상이 존재한다는 것은 A와 B 사이의 일대일 대응(mapping) f가 존재하여, A와 B 사이의 구조를 보존하며, f가 가역함수(bijective)라는 조건을 만족한다는 것을 의미합니다. 즉, A에서 B로의 동형사상 f가 존재하면, B에서 A로의 역함수가 존재하며, 이러한 대상들은 서로 구별할 수 없는 동일한 구조를 가지게 됩니다. 이를 수식으로 나타내면, 다음과 같습니다.
동형사상은 수학에서 다양한 분야에서 유용하게 사용됩니다. 예를 들어, 그룹이 동형인지 아닌지를 판별하는데 사용되며, 벡터공간이나 위상공간에서의 성질을 파악하거나 분류하는 데에도 적용됩니다.
Isomorphism is a concept in mathematics that describes a structure-preserving mapping between two mathematical objects. In other words, if two mathematical objects are isomorphic, then they have the same structure and properties, even though they may appear different on the surface. An isomorphism is a bijective (one-to-one and onto) function between the two objects that preserve their structure, such as operations, relations, and properties. For example, two groups G and H are isomorphic if there is a bijective function between them that preserves the group structure, i.e., the function maps the group operation in G to the group operation in H.
Q. linear equation은 무엇인가?
선형 방정식(linear equation)은 변수의 차수가 1인 다항식으로 이루어진 방정식을 말합니다. 예를 들어, 다음과 같은 일차 방정식은 선형 방정식입니다.
ax + b = 0
여기서 a와 b는 상수이고, x는 변수입니다. 선형 방정식은 변수의 차수가 1로 고정되어 있기 때문에 그래프상에서 직선을 그리게 됩니다. 이러한 선형 방정식은 일반적으로 대수적으로 풀이할 수 있으며, 해를 구하는 방법에는 다양한 방법이 있습니다.
선형 방정식의 해는 일반적으로 하나의 값을 가지지만, 경우에 따라서는 무수히 많은 해를 가지기도 합니다. 예를 들어, x + y = 2와 같은 방정식은 무수히 많은 해를 가집니다. 이러한 경우에는 일반적으로 해의 집합을 나타내는 형태로 표현하게 됩니다. 선형 방정식은 선형 대수학에서 중요한 개념으로 다양한 응용 분야에서 사용됩니다.
A linear equation is a mathematical equation in which the variables are of degree 1 (raised to the first power) and the coefficients are constants. The equation has the general form of ax + b = c, where x is the variable, a and b are constants, and c is a constant or another expression containing variables. Linear equations can have one or more variables, and the goal is typically to solve for the values of the variables that satisfy the equation. Linear equations are important in many areas of mathematics and science, including algebra, geometry, physics, and engineering.
Q. 다항식을 구성하는 계수를 찾는다는 것이 무슨 이야기 인지 좀더 자세히 설명해줘
다항식을 구성하는 계수를 찾는다는 것은, 다항식의 형태가 주어졌을 때 그 다항식을 이루는 각 항의 계수를 구하는 것을 말합니다.
예를 들어, 3차 다항식 f(x) = 2x^3 - 3x^2 + 4x - 1이 주어졌을 때, 이 다항식을 이루는 각 항의 계수는 2, -3, 4, -1입니다. 이러한 계수를 구하는 것은 다항식의 형태를 알고 있다면 비교적 쉽게 할 수 있습니다. 하지만 다항식의 형태가 주어지지 않았을 경우에는 계수를 구하는 것이 어려울 수 있습니다.
이 때 Vandermonde matrix를 이용하면, 주어진 벡터에서 각 원소를 다항식에 대입한 값들을 이용하여, 그 다항식을 이루는 각 항의 계수를 구할 수 있습니다. 이는 다항식 보간법과 같은 분야에서 유용하게 사용됩니다.
In mathematics, polynomials are expressions consisting of variables (also called indeterminates) and coefficients, that involve only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. Polynomials are used in a wide range of mathematical areas, including algebra, calculus, and number theory.
Finding the coefficients of a polynomial involves determining the values of the coefficients that make the polynomial satisfy certain conditions. For example, given a polynomial of degree n, if we are given n+1 distinct points on a graph and the corresponding function values, we can use this information to find the coefficients of the polynomial that passes through those points. This process is known as polynomial interpolation.
Another example is in the case of factoring a polynomial, which involves expressing it as a product of simpler polynomials. In order to factor a polynomial, we need to determine the coefficients of the simpler polynomials that make up the original polynomial. This process can be done through methods such as long division or factoring by grouping.
Overall, finding the coefficients of a polynomial is an important process in many areas of mathematics and can involve a range of techniques and methods depending on the specific problem being considered.
Q.linear regression을 자세히 설명해줘
선형 회귀(Linear Regression)는 통계학에서 가장 기본적인 예측 모형 중 하나로, 독립 변수와 종속 변수 사이의 선형적인 관계를 모델링하는 회귀 분석 기법입니다.
선형 회귀는 주어진 데이터를 가장 잘 설명하는 직선을 찾는 것으로, 이를 통해 독립 변수(입력 변수)와 종속 변수(출력 변수) 사이의 관계를 모델링하고 예측하는 데 사용됩니다. 일반적으로, 선형 회귀 모형은 다음과 같은 수식으로 나타낼 수 있습니다.
y = β0 + β1x1 + β2x2 + ... + βnxn + ε
여기서 y는 종속 변수, x1, x2, ..., xn은 독립 변수, β0, β1, β2, ..., βn은 모델의 계수(회귀 계수)이며, ε는 오차항(error term)입니다. 이러한 모델은 주어진 독립 변수 값(x)에 대한 종속 변수(y)의 예측값을 출력하는데 사용됩니다.
선형 회귀에서는 주어진 데이터를 가장 잘 설명하는 회귀 계수를 찾기 위해 최소 제곱법(Least Squares)을 사용합니다. 최소 제곱법은 오차항의 제곱을 최소화하는 회귀 계수를 구하는 방법으로, 이를 위해 일반적으로 경사 하강법(Gradient Descent)이나 정규 방정식(Normal Equation)을 사용합니다.
선형 회귀는 예측 모델링에 널리 사용되며, 데이터 분석, 통계학, 경제학, 금융 등 다양한 분야에서 응용됩니다.
Linear regression is a statistical method used to study the relationship between a dependent variable (also called response variable) and one or more independent variables (also called predictor variables or explanatory variables). It is used to find the best linear relationship between the dependent variable and the independent variables.
The goal of linear regression is to create a linear equation that predicts the dependent variable from the independent variables. The equation has the form:
y = b0 + b1x1 + b2x2 + ... + bn*xn
where y is the dependent variable, x1, x2, ..., xn are the independent variables, and b0, b1, b2, ..., bn are the coefficients of the model that need to be estimated.
To estimate the coefficients, the method of least squares is often used, which aims to minimize the sum of the squared differences between the observed values of the dependent variable and the predicted values based on the linear equation. Once the coefficients are estimated, the linear equation can be used to predict the value of the dependent variable for a given set of values of the independent variables.
Linear regression can be used for both simple and multiple regression, depending on the number of independent variables. It is commonly used in various fields, such as economics, finance, biology, psychology, and engineering, to study the relationships between variables and make predictions.
Q.ring theory는 무엇인가?
환이론(Ring Theory)은 수학의 대표적인 분야 중 하나로, 덧셈과 곱셈 연산이 정의된 대수적 구조인 환(Ring)을 연구하는 분야입니다.
환은 다음과 같은 조건을 만족하는 대수적 구조를 말합니다.
가환군(Abelian Group) : 덧셈에 대해 닫혀있으며, 덧셈은 결합법칙, 교환법칙, 항등원, 역원을 가지는 가환군입니다.
단면환(Semi-ring) : 곱셈에 대해 닫혀있으며, 곱셈은 결합법칙, 분배법칙, 항등원을 가지는 단면환입니다.
곱셈 항등원 : 1은 곱셈에 대한 항등원이며, 0과 1은 서로 다른 원소입니다.
분배법칙 : a, b, c ∈ R인 임의의 원소 a, b, c에 대해 a × (b + c) = (a × b) + (a × c)와 (b + c) × a = (b × a) + (c × a)가 성립합니다.
환이론에서는 이러한 조건을 만족하는 구조인 환의 성질과 구조에 대해 연구합니다. 이를 통해, 환의 부분환, 이상환, 환의 직접 곱, 환의 이상 등 다양한 대수적 개념을 다룰 수 있으며, 그와 함께 다른 대수적 구조와의 관계, 미분환, 전이식 함수, 표현 이론 등 환을 바탕으로 한 응용분야에 대한 연구가 이루어지고 있습니다.
Q.ring theory가 왜 중요한가?
환론(Ring Theory)은 대수학에서 가장 중요하고 폭넓게 연구되는 분야 중 하나입니다. 이유는 다음과 같습니다.
대수학의 핵심 개념 중 하나인 '환'을 다루는 분야이다. 환은 대수학의 대표적인 대수적 구조 중 하나이며, 다양한 분야에서 활용되고 있습니다. 예를 들어, 대수적으로 표현 가능한 대부분의 대수적 구조들은 환의 부분환, 이상환, 직접 곱 등의 방식으로 구성되어 있습니다.
대수적 구조와 성질을 이해하는 데 필수적이다. 환론은 집합론, 군론, 체론 등과 함께 대수학의 기본 개념과 이론을 구성하는 핵심 분야입니다. 환론을 이해하면, 대수학의 다양한 분야에서 사용되는 중요한 개념들인 부분환, 이상환, 정규환 등에 대해 이해할 수 있습니다.
다양한 응용 분야가 있다. 환론은 다양한 분야에서 응용되고 있습니다. 예를 들어, 암호학, 그래프 이론, 코호몰로지 등에서 환론의 개념이 활용됩니다. 또한, 실제 과학 분야에서는 양자역학과 관련된 분야에서도 환론의 개념과 이론이 사용됩니다.
수학 분야에서 새로운 연구 주제를 발견할 수 있다. 환론은 아직도 다양한 개념과 이론이 발견되지 않은 분야입니다. 따라서, 새로운 이론과 개념을 발견하고, 이를 다양한 응용 분야에 적용해나갈 수 있는 매우 흥미로운 분야입니다.
따라서, 환론은 대수학 분야에서 핵심적인 개념 중 하나이며, 이를 이해하고 연구하는 것은 대수학뿐만 아니라 다양한 분야에서 응용될 수 있는 중요한 기반을 제공합니다.
Ring theory is a branch of abstract algebra that studies rings, which are sets equipped with two binary operations, typically called addition and multiplication. Rings generalize many familiar algebraic structures, such as the integers, polynomials, and matrices. In ring theory, one studies the properties of rings, their ideals, homomorphisms, and various algebraic constructions such as polynomial rings, quotient rings, and localization.
Ring theory has many applications in different fields of mathematics, including algebraic geometry, number theory, representation theory, and algebraic topology. It also has many applications outside of mathematics, including in physics, computer science, and cryptography.
Q. root of unity의 뜻
루트 오브 유니티(Root of Unity)는 복소수 평면 상에서 원의 n등분점을 의미합니다. 즉, 복소수 평면에서 1부터 시작하여 반시계 방향으로 원을 n등분한 점 중 하나입니다.
여기서 "루트"는 제곱근을 의미하는 것이 아니라 "근" 또는 "해"를 의미합니다. 루트 오브 유니티를 구하는 것은 다음과 같은 방식으로 이루어집니다.
원의 n등분점을 구하는 방법 중 하나는, n개의 복소수 중 하나인 e^(2πi/n)의 거듭제곱을 계산하는 것입니다. 이 복소수는 삼각함수의 지수함수 형태인 오일러 공식을 통해 구할 수 있습니다.
n이 자연수일 때, e^(2πi/n)를 거듭제곱한 값들은 원의 n등분점을 나타냅니다. 이 중에서도 1부터 시작하여 반시계 방향으로 n등분한 점이 바로 루트 오브 유니티입니다. 따라서, 루트 오브 유니티는 원의 n등분점 중 하나이며, 복소수 평면 상에서의 위치에 따라 다른 값을 가지게 됩니다.
In mathematics, a root of unity is a complex number that, when raised to a positive integer power, equals 1. More formally, a complex number z is called an nth root of unity if z^n = 1, where n is a positive integer.
The nth roots of unity form a regular n-gon on the complex plane, with one vertex located at the origin and the other vertices equally spaced along the unit circle. For example, the fourth roots of unity are 1, i, -1, and -i, which form a square on the complex plane.
Roots of unity have important applications in many areas of mathematics, including number theory, algebra, and geometry. For example, they are used in the study of cyclotomic fields and in the construction of regular polygons. They also play a key role in signal processing and digital signal processing, where they are used to generate complex waveforms with a period of n samples.
High level view of CKKS
Q. C^(N/2) 의 의미는 무엇인가?
C^(N/2)는 복소수(complex number) N/2개의 집합을 의미합니다. 여기서 C는 복소수의 집합을 나타내는 기호이며, N은 양의 정수입니다. 따라서 C^(N/2)는 N/2개의 복소수를 원소로 가지는 집합을 나타내게 됩니다. 예를 들어, C^(4)는 복소수 4개의 집합을 의미하며, 이는 {z1, z2, z3, z4}와 같이 표기할 수 있습니다. 여기서 z1, z2, z3, z4는 모두 복소수입니다.
In mathematics, C^(N/2) represents the set of complex vectors of length N/2, where C denotes the field of complex numbers.
For example, if N=4, then C^(N/2) represents the set of complex vectors of length 2, which can be written as (z1, z2), where z1 and z2 are complex numbers. Similarly, if N=6, then C^(N/2) represents the set of complex vectors of length 3, which can be written as (z1, z2, z3).
In the context of certain mathematical problems, such as those related to the discrete Fourier transform, the set C^(N/2) may have specific meanings and properties.
Q. 왜 C^(N)이라고 안하고 C^(N/2)로 표현하는가?
C^(N)은 복소수 N개의 집합을 나타내는 표기법입니다. 이와 달리, C^(N/2)는 복소수 N개의 집합을 반으로 나눈 것을 나타내는 표기법입니다. 이렇게 N을 2로 나눈 이유는 DFT (Discrete Fourier Transform)와 같은 알고리즘에서 시간 복잡도를 줄이기 위해서입니다. DFT는 주어진 시계열 데이터를 주파수 도메인으로 변환하는 알고리즘으로, 이때 주파수 대역을 계산하기 위해 복소수 계산을 수행합니다. DFT를 수행할 때 N을 2로 나누는 것은 시간 복잡도를 O(N^2)에서 O(N*log(N))으로 줄일 수 있게 해주는 효과가 있습니다. 이렇게 하면 시간 복잡도를 줄이면서도 정확한 계산 결과를 얻을 수 있습니다.
In the context of root of unity, the notation C^(N/2) is used to indicate a complex vector space of dimension N/2. This is because the set of N-th roots of unity can be partitioned into two subsets of size N/2, where each subset contains complex conjugate pairs. Thus, the use of C^(N/2) reflects the fact that we only need to consider one element from each conjugate pair in order to fully describe the set of N-th roots of unity.
Alternatively, one could use the notation C^(N) to denote the vector space of all N complex numbers, but in the context of root of unity, this may lead to redundant or unnecessary computations as we only need to consider N/2 distinct values.
When performing the DFT, the computation of each Fourier coefficient requires a sum over all N input samples, which can be computationally expensive for large values of N. However, it turns out that the DFT has a symmetry property known as the Hermitian symmetry, which means that if x[n] is a real-valued signal (i.e., all its samples are real numbers), then X[k] = conj(X[N-k]), where conj denotes the complex conjugate. This property implies that only the first N/2+1 Fourier coefficients are unique and the rest can be obtained by taking the complex conjugates of the first N/2-1 coefficients. Therefore, we only need to compute and store the first N/2+1 Fourier coefficients, which reduces the computational complexity of the DFT by a factor of two.
Q. CKKS의 message를 m이라고 표기하는데 C^(N/2)와 어떠한 연관이 있는가?
CKKS의 메시지 m은 다항식 m(X)를 나타냅니다. 이 때, m(X)는 Z_2의 계수를 가지며, X^(N/2)까지의 차수를 가집니다.
CKKS에서 C^(N/2)는 암호화된 메시지를 나타내는 암호문입니다. C^(N/2)는 (Z_q[x]/(x^n+1))^2 의 원소 중 하나이며, 2개의 다항식 c_0(X), c_1(X)로 구성됩니다. c_0(X), c_1(X)는 각각 X^(N/2)까지의 차수를 가지며, 각 계수는 Z_q의 원소입니다. 따라서, 암호문 C^(N/2)는 메시지 m(X)의 암호화 결과로 생성됩니다.
In the context of the CKKS encryption scheme, the message m is typically encoded as a polynomial with integer coefficients using the Chinese Remainder Theorem (CRT) technique. This polynomial is then transformed into a polynomial with complex coefficients using the NTT, which is equivalent to evaluating the polynomial at the N/2-th roots of unity in the complex plane. The resulting polynomial has coefficients that are elements of the ring C^(N/2), which is a subset of the complex numbers consisting of the first N/2 complex roots of unity. Thus, C^(N/2) is the ring of complex numbers used to represent the encrypted polynomial in the CKKS scheme.
Q. CKKS에서 C^(N/2)는 vector message이고 이를 encode한 이후 encryption한 경우 (Z_q[x]/(x^n+1))^2 집합이 되는 것 같은데, 방금 전 설명이 정말 맞는 것인가?
네, 맞습니다. CKKS에서는 먼저, plaintext인 벡터 메시지를 C^(N/2)의 형태로 인코딩한 다음, 이를 암호화하여 (Z_q[x]/(x^n+1))^2의 원소인 c = (c_0(x), c_1(x))으로 변환합니다. 이때 C^(N/2)는 메시지를 표현하는데 사용되는 공간이며, (Z_q[x]/(x^n+1))^2는 암호화된 결과를 표현하는데 사용되는 공간입니다. 이렇게 함으로써 암호화된 결과가 원래 메시지와 같은 크기를 갖는 벡터가 되도록 보장할 수 있습니다.
Q. 다시 말해 메세지 m은 C^(N/2) 공간의 원소라는 것을 의미하는 건가? CKKS 논문에서는 plaintext인 p(X)가 Z[x]/(x^n+1) 공간의 원소로 표기되어 있는데, C^(N/2)의 형태로 인코딩하는건 아니지 않나?
네, 맞습니다. CKKS에서 메시지 m은 C^(N/2) 공간의 벡터입니다. 이 벡터를 다항식 p(x)로 변환한 후 Z_q[x]/(x^n+1) 공간의 다항식으로 표현합니다. 이러한 다항식은 평문(plaintext)으로 간주되며, 이를 암호화하여 암호문(ciphertext)을 생성합니다. 즉, 평문 p(x)은 C^(N/2) 공간의 벡터 m을 통해 인코딩되고, 이를 다시 Z_q[x]/(x^n+1) 공간의 다항식으로 변환하여 암호화합니다. 따라서 m과 p(x)는 동일한 정보를 나타내지만 다른 표현 방식을 사용합니다.
Q. plaintext polynomial을 계산할때 Z[X]/(X^N + 1)의 의미가 무엇인가?
Z[X]/(X^N + 1)는 다항식 Z[X]의 이상(ideal) 중 하나입니다. 이 이상은 다항식 X^N + 1을 생성자(generator)로 하는 이상으로, X^N + 1로 나누어 떨어지는 모든 다항식의 집합을 나타냅니다. 이러한 이상은 주로 암호학에서 사용되는데, 이 이상의 모든 원소는 다항식 X^N + 1로 나누어 떨어지기 때문에, 이상의 원소들은 모두 N차 다항식으로 표현됩니다.
암호학에서는 이러한 이상을 사용하여 다항식을 나누어줌으로써, 다항식의 크기를 N보다 작게 유지할 수 있습니다. 예를 들어, 주어진 N보다 큰 다항식을 암호화하고자 할 때, 이를 X^N + 1로 나눈 나머지를 계산하여, 나머지 다항식만을 전송하고 이를 복호화한 후에 다시 X^N + 1로 나누어줌으로써 원래의 다항식을 복원할 수 있습니다.
따라서, plaintext polynomial을 계산할 때 Z[X]/(X^N + 1)의 의미는, 크기가 N보다 작은 다항식들의 집합을 의미합니다. 이러한 집합에서 원하는 다항식을 선택하여 사용함으로써, 다항식의 크기를 N 이하로 유지할 수 있습니다.
Z[X]/(X^N + 1) represents the quotient ring of polynomials over the integers Z with the ideal generated by the polynomial X^N + 1. The quotient ring is formed by dividing the polynomial ring Z[X] by the ideal (X^N + 1), which means that all polynomials in the ideal are considered equivalent to zero in the quotient ring.
In the context of CKKS, plaintext polynomials are represented as elements of this quotient ring, where N is a power of two and represents the degree of the polynomial. This means that each coefficient of the plaintext polynomial is an integer modulo the prime number used in the scheme, and the polynomial itself has degree less than N. By using this representation, CKKS allows for efficient homomorphic operations on the plaintext polynomial, which can be encrypted and processed by the scheme without revealing its original value.
Q. Z[X]이 이상(ideal) 이라는게 어떤 의미인가?
Z[X]는 정수 계수 다항식의 집합입니다. 이상(ideal)은 이러한 다항식의 집합 중 특정한 규칙을 만족하는 부분집합을 의미합니다. 이러한 규칙은 두 다항식을 더하거나 빼고, 다항식에 상수를 곱하거나, 두 다항식을 곱하여 얻은 다항식들이 모두 이 부분집합에 속하는 경우입니다. 다른 말로는 "이상은 그룹의 부분집합으로, 덧셈에 대해서 닫혀 있으며, 그 이상의 곱셈에 대해서도 닫혀 있는 집합"이라고도 할 수 있습니다.
예를 들어, 2Z는 정수 집합에서 2의 배수만 모은 집합입니다. 이는 2의 배수를 더하거나 빼고, 2의 배수에 정수를 곱하면 여전히 2의 배수가 되기 때문에 이상의 조건을 만족합니다. 따라서 2Z는 2를 생성자로 하는 이상(ideal)입니다.
Z[X]에서도 이상을 정의할 수 있습니다. 예를 들어, XZ[X]는 X를 곱한 결과가 정수 계수 다항식의 집합으로 이루어진 이상입니다. XZ[X]에서는 X를 곱하거나 더해도 여전히 X의 배수가 되므로 이상의 조건을 만족합니다.
이러한 이상은 대수학, 특히 추상대수학에서 중요한 개념으로 사용되며, 링이나 그룹과 같은 대수적 구조를 연구하는 데에 매우 유용합니다. 암호학에서는 이상을 사용하여 암호화 및 복호화를 수행할 수 있습니다.
In algebra, an ideal is a special subset of a ring that has properties similar to those of the ring itself. Specifically, an ideal is a subset of a ring such that if you multiply any element of the ring by an element of the ideal, the result is always in the ideal. In the case of the ring Z[X], which is the ring of polynomials with integer coefficients, an ideal is a subset of Z[X] that satisfies this property. The ideal (X^N + 1) is the set of all polynomials in Z[X] that are divisible by X^N + 1, and taking the quotient Z[X]/(X^N + 1) means that we are considering the set of all equivalence classes of polynomials in Z[X] that differ by a multiple of X^N + 1. This has important implications for the encryption scheme used in CKKS, since it allows us to encrypt a polynomial of degree at most N-1 in a way that is homomorphic, meaning we can perform computations on the encrypted polynomial without first decrypting it.
Q. (Z_q[x]/(x^n+1))^2)의 의미는?
(zq[x]/(x^n+1))^2는 zq[x]/(x^n+1)을 원소로 가지는 2개의 다항식 집합의 집합을 나타냅니다. 각각의 집합은 q 원소를 계수로 가지는 n차 다항식의 집합이며, 이러한 집합이 2개 존재합니다.
즉, 이것은 서로 다른 2개의 다항식 집합의 집합으로 이루어져 있으며, 각 집합은 다음과 같이 정의됩니다.
첫 번째 집합: (zq[x]/(x^n+1))에서 원소 두 개로 이루어진 순서쌍 {a, b}의 집합
두 번째 집합: (zq[x]/(x^n+1))에서 원소 두 개로 이루어진 순서쌍 {c, d}의 집합
여기서 a, b, c, d는 각각 q 원소를 계수로 가지는 n차 다항식입니다.
(Z_q[x]/(x^n+1))^2 in CKKS refers to the ring of pairs of polynomials over Z_q, modulo the polynomial x^n+1. In other words, it is the Cartesian product of two copies of the ring Z_q[x]/(x^n+1), where each element of the product is a pair of polynomials. The first element of the pair represents the real part of the complex number and the second element represents the imaginary part. This ring is used in CKKS to perform homomorphic operations on encrypted data, where each ciphertext is a pair of polynomials representing a complex number.
Q. ckks에서 위 공식의 의미는?
CKKS 알고리즘에서 위 공식은 부분 평문공간 (partial plaintext space) 에서 부분 암호공간 (partial ciphertext space) 으로 매핑하는 작업을 나타냅니다.
보다 구체적으로, CKKS에서 평문 공간 (plaintext space) 에서는 다항식의 계수 (coefficients) 로 이루어진 벡터가 평문으로 사용됩니다. 이때 위 공식은 이러한 다항식의 계수를 암호화하여 암호문 공간 (ciphertext space) 에서 부분 암호문 벡터를 생성합니다. 이때 각 다항식의 계수는 벡터의 요소(element)로 나타내어지며, 위의 공식에서는 Z_q 에 속하는 임의의 정수 를 선택하여 평문 다항식의 계수를 Z_q 상의 정수로 스케일링 하고, 이를 정규 분포를 따르는 임의의 노이즈 벡터와 함께 암호문 다항식의 계수로 매핑(mapping) 합니다.
여기서 c_k는 k번째 계수에 대한 암호문 값이며, x_i는 i번째 계수에 대한 평문 값, e_k는 k번째 계수에 대한 노이즈 값, v는 공개 키의 일부이며, q는 큰 소수, sigma는 노이즈의 분산, alpha는 다항식을 평문공간과 암호공간 사이에서 매핑할 때 사용되는 스케일링 파라미터입니다.
In CKKS (Cheon, Kim, Kim, and Song) scheme, the notation (Z_q[x]/(x^n+1))^2 refers to the ring of pairs of polynomials modulo x^n+1 with coefficients in the finite field Z_q. In other words, the elements of this ring are pairs of polynomials (a_0(x),a_1(x)) where a_0(x) and a_1(x) are polynomials of degree less than n and with coefficients in Z_q. The addition and multiplication operations in this ring are defined coordinate-wise, which means that (a_0(x),a_1(x)) + (b_0(x),b_1(x)) = (a_0(x)+b_0(x),a_1(x)+b_1(x)) and (a_0(x),a_1(x)) * (b_0(x),b_1(x)) = (a_0(x)*b_0(x),a_1(x)*b_1(x)).
The use of this ring in CKKS allows for the encryption of two plaintext messages simultaneously, which can be useful for certain applications such as secure multiparty computation.
Q. Z_q의 의미가 무엇이며 스케일링의 의미는 무엇인가?
Z_q는 유한체(Finite Field)로 크기가 q인 정수 모듈러 연산(remainder operation)에 대한 집합을 의미합니다. 예를 들어, Z_2는 {0, 1}이며, Z_3은 {0, 1, 2}입니다.
스케일링(scaling)은 어떤 벡터나 행렬의 모든 요소에 대해 상수배를 곱하는 것을 의미합니다. CKKS 알고리즘에서는 부동소수점 수를 다루기 때문에 정수 형태로 인코딩 된 값을 스케일링하여 부동소수점 수 형태로 바꾸어 줍니다. 이러한 스케일링을 통해 노이즈의 크기를 제어하고, 부동소수점 연산을 수행할 수 있게 됩니다.
Z_q: This represents the ring of integers modulo q. In other words, it consists of all integers between 0 and q-1, inclusive, and the arithmetic is performed modulo q. In CKKS, q is typically a large prime number that is chosen to be a power of 2, and it is used to ensure the security of the encryption scheme.
Scaling: This refers to the process of multiplying a ciphertext by a constant factor. In CKKS, scaling is used to ensure that the noise level in the ciphertext remains below a certain threshold. Specifically, when a ciphertext is scaled by a factor of 2^k, the noise level is reduced by a factor of 2^k. This makes it possible to perform multiple homomorphic operations on the ciphertext without the noise level growing too large and affecting the correctness of the computation.
Q. (Z_q[x]/(x^n+1))^2)의 예제를 알려줘
예를 들어, (Z_2[x]/(x^4+1))^2는 크기가 2인 유한체 Z_2에서 4차 다항식 x^4+1을 나누어 생성된 이상 (ideal)에 대한 다항식 집합의 곱셈군(multiplicative group)입니다. 이 집합은 다음과 같은 형태의 다항식의 집합입니다.
이때 + 와 * 연산은 modulo 2 연산을 사용하여 다항식의 덧셈과 곱셈을 수행합니다. 이러한 집합은 CKKS 알고리즘에서 암호화와 같은 보안 계산을 수행하는 데 사용됩니다.
Here are some examples of elements in the ring (Z_q[x]/(x^n+1))^2):
(1 + x^2, 3x + 5): This is an element of the ring for n = 3, q = 7. It consists of two polynomials modulo (x^3 + 1), where the coefficients are taken from the field Z_7.
(x^2 + 1, 2x): This is another element of the ring for n = 3, q = 5. The first polynomial is equivalent to -x modulo (x^3+1), and the second polynomial has coefficients taken from Z_5.
(1 + 2x + 3x^2, 0): This is an element of the ring for n = 2, q = 4. It consists of two polynomials modulo (x^2+1), where the coefficients are taken from the field Z_4.
These are just a few examples, and the elements of this ring can take many different forms depending on the choice of n and q.
Q. CKKS에서 두개의 다항식 집합을 사용하는 특별한 이유는?
CKKS에서 두 개의 다항식 집합을 사용하는 이유는, 하나의 다항식 집합만 사용하는 경우와는 달리, 부동 소수점 수를 포함한 실수 값을 암호화하고 연산을 수행하는 데 더 효과적인 방법을 제공하기 위함입니다.
CKKS에서는 부동 소수점 수를 다항식의 계수로 사용하고, 이를 암호화하여 두 개의 다항식 집합을 생성합니다. 첫 번째 다항식 집합은 각 계수의 정수 부분을 나타내고, 두 번째 다항식 집합은 각 계수의 소수점 이하 부분을 나타냅니다. 이렇게 나누어진 두 개의 다항식 집합은 서로 다른 크기의 다항식을 가지며, 이를 곱셈 연산을 통해 다항식 집합으로 합치면 부동 소수점 값을 나타내는 다항식을 얻을 수 있습니다.
두 개의 다항식 집합을 사용하면, 보안성과 정확도 사이의 균형점을 선택할 수 있습니다. 부동 소수점 수를 정수와 소수 부분으로 나누어 다항식에 매핑함으로써, 암호화된 부동 소수점 수의 정확도를 조절하면서도, 연산을 수행할 때 발생하는 오차를 최소화할 수 있습니다. 이는 기계 학습 및 데이터 분석과 같은 실제 응용에서 중요한 역할을 합니다
n CKKS, ciphertexts are polynomials with complex-valued coefficients. The reason for using two sets of polynomials is to enable homomorphic computations of both integer and fractional parts of real numbers. One set of polynomials represents the integers modulo a prime number, while the other set represents polynomials over the complex numbers modulo the cyclotomic polynomial x^n+1. This allows for efficient computation of both the integer and fractional parts of a real number in the encrypted domain.
Q. modular 2연산을 사용하여 다항식의 덧셈과 곱셈을 수행하는 예를 들어줘
모듈러 2 연산을 사용하여 다항식의 덧셈과 곱셈을 수행하는 예를 아래와 같이 들 수 있습니다.
우선, 두 다항식 $f(x) = x^3 + x + 1$과 $g(x) = x^2 + x$을 생각해 봅시다. 이 두 다항식은 다음과 같이 표현할 수 있습니다.
$$f(x) = 1x^3 + 0x^2 + 1x^1 + 1x^0$$
$$g(x) = 1x^2 + 1x^1 + 0x^0$$
여기서 각 항의 계수는 0 또는 1인 이진수로 표현됩니다. 이제 두 다항식을 모듈러 2 연산을 사용하여 더하면 다음과 같이 됩니다.
Let's consider two polynomials f(x) and g(x) in Z_2[x], which means that their coefficients are either 0 or 1 modulo 2. Then the addition of these polynomials can be done as follows:
where fi and gi are the coefficients of f(x) and g(x) respectively.
For multiplication, we use the standard method of multiplying each term in f(x) by each term in g(x), and then perform modular reduction of the resulting polynomial by the polynomial x^N + 1, where N is the degree of the polynomial we are working with.
For example, suppose we have f(x) = x^2 + x + 1 and g(x) = x + 1. Then their product is given by:
We then perform modular reduction of this polynomial by x^3 + 1, which gives:
x^3 + 2x^2 + 2x + 1 ≡ x^2 + x + 1 (mod 2)
Thus, the product of f(x) and g(x) modulo 2 is x^2 + x + 1.
Q. 그런데 CKKS에서 ciphertext를 생성할때 Z_q로 제한을 두고 modular 연산으로 +와 x를 하는 이유가 있어?
CKKS에서 ciphertext를 생성할 때 Z_q로 제한을 두는 이유는 보안상의 이유입니다. 더 정확하게 말하면, plaintext와 ciphertext의 크기를 제한함으로써, 공격자가 plaintext 또는 ciphertext를 통해 비밀 키를 추론하는 것을 방지하기 위해서입니다.
또한, modular 연산으로 +와 x를 하는 이유는 다항식 계산에 대한 효율성을 보장하기 위해서입니다. 일반적으로 다항식 계산에서는 modular 연산을 사용하여 계산을 수행하는 것이 효율적입니다. 이유는 modular 연산이 일반적인 연산보다 더 빠르기 때문입니다. 또한, modular 연산을 사용하면 다항식의 크기를 제한할 수 있기 때문에, ciphertext의 크기를 제한할 수 있습니다.
In CKKS, restricting the range to Z_q and performing modular operations for addition and multiplication is necessary because the encryption process involves rounding and rescaling, and these operations can introduce errors in the ciphertext. By limiting the range and performing modular arithmetic, the size of the error is also limited, ensuring that it remains small enough to be corrected during the decryption process. Additionally, modular arithmetic allows for efficient computation using binary operations, which is crucial for implementing CKKS on hardware platforms with limited resources.
Q. CKKS에서 (Z_q[x]/(x^n+1))^2 에서 c=(c0(X), c1(X)) 의 부분집합이 생성되는 건가? 그런다면 c0, c1의 의미는 무엇인가?
맞습니다. CKKS에서 (Z_q[x]/(x^n+1))^2 는 2개의 다항식 집합을 가지게 됩니다. 이 중에서 c=(c0(X), c1(X))는 이들 중 하나의 부분집합을 의미합니다.
여기서 c0(X)와 c1(X)는 각각 암호화된 다항식의 일부분으로서, 원래 다항식을 2개의 다항식으로 분해한 것입니다.
일반적으로 c0(X)는 실수 부분을, c1(X)는 허수 부분을 나타내게 됩니다. 이러한 분해는 CKKS의 방식에서 필수적인데, 이를 통해 실수와 허수 부분을 나누어 처리하고, 나중에 복호화 과정에서 이를 다시 합쳐 원래의 값을 복원할 수 있습니다.
In CKKS, a subset of (Z_q[x]/(x^n+1))^2 is used to represent ciphertexts, denoted as c = (c0(x), c1(x)). Here, c0(x) and c1(x) are polynomials of degree less than n, and they represent the two parts of the ciphertext.
More specifically, c0(x) represents the polynomial that contains the encrypted message coefficients, while c1(x) is used to ensure the correctness of the ciphertext after homomorphic operations are performed on it. This allows CKKS to perform homomorphic computations while keeping the encrypted data secure and private.
Q. 위에서 나온 CKKS의 encode와 encrypt 과정중에 사용되는 key들은 어떻게 표기되는가?
CKKS에서 사용되는 암호화 및 복호화에 사용되는 키들은 다음과 같이 표기됩니다:
Secret key (SK): 암호화 및 복호화에 사용되는 비밀 키로, 일반적으로 길이가 큰 무작위 다항식으로 표현됩니다.
Public key (PK): 암호화에 사용되는 공개 키로, 주로 secret key를 기반으로 생성됩니다. 다항식의 집합으로 표현됩니다.
Relin key: 암호화된 다항식을 조작할 때 사용되는 키로, 다항식의 각 항을 스케일링 및 반올림합니다. 다항식의 집합으로 표현됩니다.
Evaluation key (EK): 다항식의 값을 계산할 때 사용되는 키로, 다항식의 곱셈 연산에서 사용됩니다. 다항식의 집합으로 표현됩니다.
이러한 키들은 암호화 및 복호화 과정에서 사용되며, 이들은 공개 키와 비밀 키를 구분하는 데 중요한 역할을 합니다. 암호화된 데이터를 복호화하는 데 필요한 비밀 키는 누구에게도 노출되지 않아야 하므로, 이들은 안전한 방식으로 저장 및 관리되어야 합니다.
Here are the main steps in CKKS algorithm, along with the corresponding keys used for encoding and encryption:
Encoding:
Choose a message m to be encoded Choose a scaling factor sc to determine the precision of the encoded message Use a polynomial encoder with a key (n, T) to encode m into a plaintext polynomial p(x) in Z_q[x]/(x^n+1) Encryption:
Generate a random polynomial e(x) in Z_q[x]/(x^n+1) with coefficients in the range [-T/2, T/2) Add e(x) to the plaintext polynomial p(x) to obtain a perturbed polynomial p'(x) = p(x) + e(x) Use a public key (n, q, T, Delta) to encrypt p'(x) into a ciphertext c = (c0(x), c1(x)) in (Z_q[x]/(x^n+1))^2 The public key also includes a set of "special primes" p_i, which are used for various purposes such as key switching and relinearization
Q. vanilla encoding은 무엇인가?
Vanilla encoding은 부동소수점 메시지를 다항식으로 변환하는 데 사용되는 기본적인 인코딩 방법입니다. Vanilla encoding에서, 메시지 m은 다음과 같이 다항식 p(X)로 인코딩됩니다.
p(X) = round(m * X^precision) mod (X^n + 1)
여기서, precision은 정수부와 소수부의 비율을 나타내는 인코딩 매개변수이며, n은 다항식의 차수를 나타냅니다. 이러한 인코딩은 메시지를 다항식으로 변환하는 데 사용되며, 이후 암호화 및 복호화를 수행하는 데 사용됩니다.
Vanilla encoding in the context of homomorphic encryption refers to a simple method of converting a plaintext message into a ciphertext that can be used in homomorphic computations. In the CKKS scheme, vanilla encoding involves first scaling the plaintext message to a value between -1 and 1, and then using a polynomial approximation to represent it as a sequence of complex values in the plaintext polynomial ring. This process can be repeated for multiple plaintext messages to create a ciphertext that can be used in homomorphic computations.
Vanilla encoding is a relatively simple and fast encoding method that can be used in a variety of homomorphic encryption schemes. However, it may not provide the same level of security or performance as more advanced encoding methods that take into account specific properties of the plaintext data.
Q. vanilla encoding에서 C[X]/(X^N+1) 공간에서 왜 X^N이 아닌 X^N+1을 사용하는가?
CKKS 스키마에서는 0을 나타내는 값과 1을 나타내는 값이 둘 다 필요합니다. 만약 X^N이 사용된다면 다항식을 계수가 0인 상수항으로 나누어주면 됩니다. 그러나 이러한 처리를 하면 다항식의 최상위 차수에 해당하는 값이 0이 되므로 실제 값에 대한 정보를 잃게 됩니다. 따라서 X^N+1을 사용하면 모든 다항식의 상수항이 1이 되어 이 문제를 해결할 수 있습니다.
Vanilla encoding in homomorphic encryption refers to a simple and basic encoding method, where a plaintext message is encoded into a polynomial and encrypted using a public key. In the case of the CKKS scheme, vanilla encoding refers to the process of encoding a real number into a polynomial that has coefficients in the ring of integers modulo q.
In vanilla encoding, we use the polynomial ring C[X]/(X^N+1) to represent the message space, where C is the set of complex numbers and N is a power of 2. The reason for using X^N+1 instead of X^N is to ensure that the polynomial is a cyclotomic polynomial, which has some desirable algebraic properties that make it suitable for homomorphic encryption.
One important property of cyclotomic polynomials is that they are irreducible over the rationals, which means that they cannot be factored into polynomials of lower degree with rational coefficients. This property is essential for ensuring the security of the encryption scheme, as it makes it difficult for an attacker to find the plaintext from the ciphertext.
Furthermore, the choice of X^N+1 also ensures that the roots of the polynomial are the Nth roots of unity, which helps to preserve the accuracy of the plaintext during homomorphic operations. This is because the roots of unity have a simple algebraic structure that allows for efficient computation of the polynomial values, which is crucial for achieving high performance in homomorphic computations.
Q. C[X]/(X^N+1)공간에서 가운데 /가 의미하는 것은?
C[X]/(X^N+1)는 가장 일반적인 방법으로 표현된 다항식의 공간이며, X^N+1은 이 공간에서 0이 되는 다항식 중 하나입니다.
여기서 /는 몫 공간(quotient space)을 나타냅니다. 이는 다항식들의 집합에서 어떤 다항식 f(X)를 선택하여, 그와 동치인 모든 다항식들의 집합을 나타냅니다. 즉, C[X]/(X^N+1)는 X^N+1로 나누어지는 모든 다항식의 집합을 나타냅니다.
이러한 몫 공간은 대수적 객체를 연구할 때 유용하게 사용되며, 일반적으로 다항식에서 몫 공간을 이용하면 보다 간단하게 다항식 계산을 수행할 수 있습니다.
In the context of algebraic structures, '/' is used to represent the quotient structure, also known as the quotient ring or factor ring. In the case of the polynomial ring C[X], C[X]/(X^N+1) represents the ring of polynomials with coefficients from the field C, where the polynomial X^N+1 has been factored out as an ideal, and all polynomials that are equivalent to X^N+1 (i.e., have the same remainder when divided by X^N+1) are identified with each other. This is a way of creating a new algebraic structure that has some of the same properties as the original structure, but with additional restrictions or equivalences imposed.
