Số học cơ bản
Số nguyên tố và Sự chia hết (Divisibility)
Tập hợp các số nguyên được ký hiệu là Z Đối với a, b ∈ Z, a được gọi là chia hết b, ký hiệu là a | b, nếu tồn tại số nguyên c sao cho ac = b Nếu a không chia hết b, ta ký hiệu là a-b Nếu a | b và a | c, thì a cũng sẽ chia hết cho (Xb + Yc) với X, Y ∈ Z bất kỳ.
Nếu a chia hết cho b và a là số dương, thì a được xem là số chia hết của b Nếu a không phải là 1 hoặc b, thì a được gọi là số chia hết không tầm thường, tức là một thừa số của b Một số nguyên dương p lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai số chia hết là 1 và chính nó Ngược lại, một số nguyên dương lớn hơn 1 không phải là số nguyên tố thì được gọi là hợp số Theo quy ước, số 1 không được xem là hợp số cũng như không phải là số nguyên tố.
Mọi số nguyên dương N lớn hơn 1 đều có thể biểu diễn dưới dạng N = Q i p e i i, trong đó {p i } là tập hợp các số nguyên tố khác nhau và e i lớn hơn 1 cho mọi i Hơn nữa, nếu các số nguyên tố {p i } được sắp xếp theo thứ tự tăng dần, thì cách biểu diễn này là duy nhất cho mỗi số.
Mệnh đề 2.1.1 Cho a là một số nguyên và cho b là một số nguyên dương Luôn tồn tại các số nguyên q, r không cùng giá trị sao cho a=qb+r và 0≤r < b.
Cho hai số nguyên a và b, ta có thể tính toán ước chung lớn nhất (gcd) và phần dư (r) trong thời gian đa thức Thời gian thực thi của một thuật toán phụ thuộc vào độ dài đầu vào, với lý thuyết số học thuật toán, số nguyên được biểu diễn dưới dạng nhị phân Thời gian chạy của thuật toán với đầu vào là số nguyên N được đo bằng độ dài chuỗi nhị phân của N, ký hiệu là kNk Gcd(a, b) là số nguyên lớn nhất c sao cho c chia hết cho cả a và b (gcd(0,0) được coi là không xác định) Khái niệm ước chung lớn nhất cũng áp dụng cho trường hợp a và b là số âm Nếu gcd(a, b) = 1, thì a và b được gọi là nguyên tố cùng nhau.
Mệnh đề 2.1.2 khẳng định rằng với hai số nguyên dương a và b, luôn tồn tại hai số nguyên X và Y sao cho Xa + Yb = gcd(a, b) Hơn nữa, gcd(a, b) là số nguyên dương nhỏ nhất có thể được biểu diễn theo cách này.
Để tính giá trị gcd(a, b) cho hai số a và b, chúng ta có thể áp dụng thuật toán Euclidean Bên cạnh đó, thuật toán Euclidean mở rộng cho phép chúng ta tính toán các giá trị X và Y trong thời gian đa thức.
Tích trong
Trong báo cáo này, chúng ta sẽ khám phá về tích trong (inner product) giữa các vector, một khái niệm quan trọng trong hàm mã hóa và giải mã của mô hình mật mã đồng cấu BGV Theo định nghĩa, cho V là một không gian vector n-chiều trên trường F, với hai vector a = (a₁, , aₙ)ᵀ và b = (b₁, , bₙ)ᵀ thuộc V, tích trong giữa hai vector được xác định bởi công thức ha, bi = Σ (aᵢ * bᵢ) từ i = 1 đến n.
Số học Đồng dư
Với hai số nguyên a, b, N (N > 1), ký hiệu [a mod N] đại diện cho giá trị dư của phép chia a cho N Theo Mệnh đề 2.1.2, luôn tồn tại hai số khác nhau q và r sao cho a = qN + r, với điều kiện 0 ≤ r < N Do đó, [a mod N] được định nghĩa là giá trị của r Quá trình ánh xạ từ a tới [a mod N] được gọi là quy trình quy về modulo N.
Ta nói a và b là đồng dư theo modulo N, viết là a=bmodN, nếu như [amodN]
= [b modN] Ta thấy rằng nếu như a=bmodN nếu và chỉ nếu N |(a−b).
Chú ý rằnga= [bmod N] thìa=b modN, nhưng ngược lại thì không đúng Lấy ví dụ, 17 = 2mod15 nhưng 176= [3mod15].
Quan hệ đồng dư modulo N là một quan hệ tương đương với ba tính chất chính: tính phản xạ (a = a mod N), tính đối xứng (nếu a = b mod N thì b = a mod N), và tính bắc cầu (nếu a = b mod N và b = c mod N thì a = c mod N) Đồng dư modulo N cũng tuân theo các quy tắc số học cơ bản, chẳng hạn như nếu a = a₀ mod N và b = b₀ mod N thì (a + b) = (a₀ + b₀) mod N và ab = a₀b₀ mod N.
Trong một số trường hợp, ta có thể định nghĩa khái niệm phép chia trong số nguyên Nếu tồn tại một số nguyên c sao cho bc = 1 mod N với số nguyên b cho trước, thì b được gọi là khả nghịch trong modulo N và c là nghịch đảo của b theo modulo N Đáng chú ý, nếu c là nghịch đảo của b theo modulo N, thì [c mod N] cũng sẽ là nghịch đảo của b theo modulo N Thêm vào đó, nếu c khác 0, c cũng là nghịch đảo của b modulo.
N, thì ta sẽ có [cmodN] = [c 0 modN] Như vậy, khi b khả nghịch theo moduloN ta có thể lấy ký hiệub −1 để đại diện cho nghịch đảoduy nhất của bcó giá trị nằm trong khoảng 1, , N −1.
Khi b là khả nghịch trên moduloN, chúng ta định nghĩa phép chia bởi b modulo
Khi thực hiện phép chia trong toán học, điều quan trọng là b phải là khả nghịch Nếu ab = cb mod N và b là khả nghịch, chúng ta có thể chia cả hai vế của đẳng thức đồng dư bằng b, tương đương với việc nhân cả hai vế với b −1.
(ab)ãb −1 = (cb)ãb −1 mod N ⇒a =cmodN
Sau khi định nghĩa phép chia theo modulo N, một câu hỏi quan trọng nảy sinh là: những số nguyên nào là khả nghịch trong modulo N? Mệnh đề dưới đây sẽ cung cấp câu trả lời cho vấn đề này.
Mệnh đề 2.1.3 Cho b, N là các số nguyên, với b ≤ 1 và N ≤ 1, b là khả nghịch modulo N nếu và chỉ nếu gcd(b, N) = 1.
Cấu trúc Đại số
Nhóm
Gọi G là một tập hợp và ◦ là một phép toán nhị phân trên G nhận hai phần tử thuộc G làm đầu vào Đối với h, g ∈ G, chúng ta sẽ viết là a ◦ b thay vì sử dụng ký hiệu phức tạp Định nghĩa 2.2.1: Một nhóm là một tập G cùng với một phép toán nhị phân ◦ thỏa mãn các tính chất nhất định.
• (Đóng :) Với mọi g, h∈G luôn có g+h∈G.
• (Tồn tại phần tử đơn vị : ) Tồn tại một phần tử đơn vị e∈G sao cho với mọi g ∈G, e◦g =g◦e=g.
• (Tồn tại phần tử nghịch đảo : ) Với mọig ∈G tồn tại một phần tử g ∈G sao cho h◦g =g◦h=e Ta gọi h là nghịch đảo của g.
• (Tính kết hợp :) Với mọi g 1 , g 2 , g 3 ∈G, (g 1 ◦g 2)◦g 3 =g 1 ◦(g 2 ◦g 3).
Nếu G có số phần tử là giới hạn, thì ta sẽ gọi G là hữu hạn và lấy |G| cho błc của nhóm (số lượng phần tử của nhóm G).
Nhóm G với phép toán ◦ được gọi là abelian nếu như tính chất sau đây được thỏa mãn :
• (Tính giao hoán :) Với mọi g, h∈G, g◦h=h◦g.
Tính kết hợp cho phép chúng ta không cần sử dụng dấu ngoặc đơn để xác định thứ tự tính toán trong các công thức dài hơn 2 Ký hiệu 1 ◦ g2 ◦ ◦ gn không gây nhầm lẫn vì thứ tự tính toán các phép toán ◦ không ảnh hưởng đến kết quả cuối cùng của công thức.
Phần tử đơn vị trong một nhóm Glà duy nhất, và mỗi phần tửg trong nhóm chỉ có duy nhất một phần tử nghịch đảo độc nhất của nó.
Nếu G là một nhóm, thì H⊆G được coi là nhóm con của G nếu H cũng là một nhóm dưới cùng phép toán liên kết với G Để xác minh điều này, cần kiểm tra các tính chất nhóm.
Để xác định H có phải là nhóm con hay không, cần kiểm tra xem H có thỏa mãn các tính chất đóng, tồn tại phần tử đơn vị, phần tử nghịch đảo và tính kết hợp dưới phép toán ◦ hay không Mọi nhóm G đều có hai nhóm con tầm thường là G và {1} H được gọi là nhóm con chặt nếu G không phải là nhóm con tầm thường của G Thông thường, ký hiệu ◦ không được sử dụng để đại diện cho phép toán trên nhóm; thay vào đó, ký hiệu cộng tính hoặc nhân tính được áp dụng tùy thuộc vào nhóm Ký hiệu cộng tính cho phép toán giữa hai phần tử g và h là g + h, với phần tử đơn vị là 0 và phần tử nghịch đảo của g là -g Khi sử dụng ký hiệu nhân tính, phép toán giữa hai phần tử được ký hiệu là gh, với phần tử trung hòa là 1 và phần tử nghịch đảo của g là g⁻¹.
Tập hợp {0, , N −1} với phép toán cộng trên mô-đun N tạo thành một nhóm abelian bậc N, ký hiệu là Z_N, trong đó N là số nguyên lớn hơn 1 Phép cộng mô-đun này thỏa mãn tính đóng, tính kết hợp và tính giao hoán, nhờ vào các tính chất tương tự của phép cộng trên số nguyên Phần tử đơn vị trong nhóm là 0, và mỗi phần tử a có phần tử nghịch đảo là (N − a) mod N, vì a + (N − a) = 0 mod N.
Trong ví dụ 2.2.1, tập Z N = {0, , N −1} tạo thành một nhóm với phép cộng mô-đun N Bên cạnh đó, chúng ta cũng có thể xây dựng một nhóm với phép nhân mô-đun N, tuy nhiên cần loại bỏ những phần tử không thể nghịch đảo, chẳng hạn như phần tử 0 Để xác định các phần tử không khả nghịch, có thể áp dụng mệnh đề 2.1.3, và các nghịch đảo của những phần tử còn lại cũng nằm trong khoảng {0, , N −1} Từ đó, chúng ta có thể đưa ra định nghĩa cho nhóm với phép nhân mô-đun N.
Mệnh đề 2.2.1 Với N >1là một số nguyên, thì Z ∗ N là nhóm abelian với phép nhân mô-đun N.
Ta định nghĩa φ(N) là bậc của nhóm Z ∗ N, trong đó φ được gọi là hàm phi Ơ-le Để xác định bậc của nhóm Z ∗ N, ta có thể áp dụng định lý sau: Với N = Q i p e i i, trong đó {p i} là các số nguyên tố khác nhau và e i > 1, ta có công thức φ(N) = Q i p e i i −1 (p i −1).
Mệnh đề 2.2.2 Với một số nguyên N >1 tùy ý và a∈Z ∗ N thì ta luôn có a φ(N ) = 1 modN Với trường hợp N =p là một số nguyên tố và với a∈ {1, , p−1}, thì a p−1 = 1 modp
Cho Glà một nhóm vàHlà một nhóm con củaG, ta định nghĩa một coset trái của
H với đại diện g ∈G là tập gH={gh:h∈H}.
Coset phải có thể định nghĩa theo cách tương tự
Trong một số trường hợp, như với nhóm abelian, coset trái và coset phải có thể trùng nhau Nếu ngữ cảnh đã làm rõ loại coset đang được sử dụng, chúng ta có thể đơn giản sử dụng thuật ngữ "coset" mà không cần phân biệt giữa trái và phải.
Ví dụ 2.2.2 Gọi H là một nhóm con của Z6 bao gồm hai phần tử 0 và 3, ta có các coset như sau :
Vành
Vành (Ring) là một cấu trúc đại số bao gồm hai phép toán: một phép toán giao hoán và một phép toán có thể giao hoán hoặc không Nếu phép toán thứ hai là giao hoán, ta gọi đó là Vành giao hoán (communicative Ring); nếu không, đó là Vành không giao hoán (non-communicative Ring) Trong ngữ cảnh này, phép toán đầu tiên thường được gọi là phép cộng và phép toán thứ hai là phép nhân, với hai phép toán này tuân theo luật phân phối (distributive law).
Bài báo cáo này sẽ giới thiệu các khái niệm cơ bản về Vành và các mở rộng của nó, bao gồm Ideal, Vành dư và Vành đa thức Những khái niệm này rất quan trọng để hiểu về Hệ mật mã đồng cấu đầy đủ BGV, vì các kiến thức về đại số trừu tượng liên quan trực tiếp đến Vành, đặc biệt là Vành thương đa thức, không gian bản rõ và không gian mã mật.
Hệ BGV là một Vành dư đa thức, trong đó một Vành R được định nghĩa là một nhóm Abelian với phép cộng và một phép toán nhân Phép nhân trong vành có tính kết hợp và tuân theo luật phân phối liên quan đến phép cộng, cụ thể là a(b+c) = ab + ac.
Trong lý thuyết vành, nếu vành R có phần tử đơn vị 1 ∈ R và thỏa mãn 16 = 0 với 0 là phần tử đơn vị theo phép cộng, đồng thời a1 = 1a = a với mọi phần tử a ∈ R, thì R được gọi là vành đơn vị Nếu phép nhân trong vành này có tính chất giao hoán, thì R được gọi là vành giao hoán Một vành có đơn vị trở thành miền nguyên nếu với mọi a, b ∈ R, nếu ab = 0 thì a = 0 hoặc b = 0 Nếu mọi phần tử khác 0 trong vành đều có phần tử nghịch đảo duy nhất, thì đó là vành chia Nếu vành chia cũng là vành giao hoán, thì nó được gọi là trường.
Trong bài viết này, chúng ta định nghĩa phép nhân trên Z_n thông qua phép nhân mô-đun n Cụ thể, trong Z_12, phép nhân 5×7 = 11 mod 12 cho thấy rằng phép nhân này biến nhóm abelian Z_n thành một vành giao hoán Tuy nhiên, vành này có thể không đạt đủ điều kiện để trở thành miền nguyên Ví dụ, khi xem xét trường hợp 3×4 = 0 mod 12, ta nhận thấy có thể tồn tại hai phần tử khác 0 mà tích của chúng lại bằng 0.
Giả sử R là một vành giao hoán với phần tử đơn vị Đối với bất kỳ biểu thức nào có dạng f(x) = P n i=0 a i x i = a 0 + a 1 x + a 2 x 2 + + a n x n với a i ∈ R và a n ≠ 0, thì biểu thức này được gọi là đa thức trên R với biến không xác định x.
Các hệ số của đa thức f được ký hiệu là a0, , an, trong đó a n là hệ số đầu Đa thức được gọi là đa thức dạng chuẩn (monic polynomial) khi hệ số đầu là 1 Bậc của f được xác định là n, với n là số không âm lớn nhất mà a n khác 0 Tập hợp tất cả các đa thức có hệ số thuộc vành R được ký hiệu theo Định lý 2.2.2, trong đó nếu R là vành giao hoán với phần tử đơn vị, thì R[X] cũng là vành giao hoán với phần tử đơn vị.
Trong lý thuyết đa thức, một đa thức f(x) ∈ F[X] được coi là bất khả quy nếu nó không thể phân tích thành tích của hai đa thức g(x) và h(x) với bậc của cả g(x) và h(x) đều nhỏ hơn bậc của f(x).
Trong hệ mật mã đồng cấu BGV, cả bản mã và bản rõ đều được xem như phần tử của một vành thương đa thức với hệ số thuộc Zp và Zp (với qp) Do đó, bản mã mật sẽ được diễn đạt dưới dạng một đa thức.
Ideal là một khái niệm trong vành R, tương tự như số 0 trong tập số tự nhiên, với tính chất cộng và nhân đặc biệt Cụ thể, phép cộng trong ideal là đóng, và khi nhân ideal với bất kỳ phần tử nào không thuộc ideal của vành R, kết quả sẽ luôn thuộc về ideal Để hiểu rõ hơn về vành thương, trước tiên cần nắm vững định nghĩa về ideal.
R thỏa mãn có các tính chất sau :
1 I là một nhóm con của nhóm cộng tính tương ứng với R
2 Với bất kỳ phần tử r ∈ R và i ∈ I, ta luôn có ri ∈ I (ideal trái) hoặc ir ∈ I (ideal phải)
Trong vành số nguyên R = Z, ideal I = 2Z bao gồm các số nguyên chẵn Tương tự, trong vành đa thức R = Z[X], ideal Rf(X) là tập hợp các đa thức mà chia hết cho đa thức f(x) thuộc R.
Tính chất thứ hai của Ideal là với mọi phần tử r ∈ R, ta luôn có rI ⊂ I hoặc Ir ⊂ I, được gọi là tính chất hấp thụ của Ideal Tính chất này phân biệt Ideal với Nhóm con, vì mọi Ideal đều là nhóm con, nhưng không phải mọi nhóm con đều là Ideal Nếu một Ideal vừa là Ideal trái, vừa là Ideal phải, thì nó được gọi là Ideal hai phía Định nghĩa Ideal được sinh bởi một tập X thuộc R được thực hiện khi R là một vành.
(X) L là ideal trái nhỏ nhất của R chứa X Tương tự chúng ta có thể định nghĩa một ideal trái sinh bởi X :
(X) R ={ P n i=1 x i s i |s i ∈R, x i ∈X, n∈N} và ideal hai phía sinh bởi X :
Và ta kết luận (X) R và (X) lần lượt là ideal phải, và ideal hai phía nhỏ nhất chứaX.
Hai ideal I1 và I2 trong vành R được gọi là nguyên tố cùng nhau (coprime) nếu tổng của chúng là R Khái niệm này là sự mở rộng của nguyên tố cùng nhau trong tập số nguyên, nơi hai số nguyên a và b được coi là nguyên tố cùng nhau nếu gcd(a, b) = 1 Mọi phần tử c thuộc Z có thể được biểu diễn dưới dạng c = xa + yb với x, y thuộc Z Khi xem xét ideal sinh bởi các số nguyên (a) và (b), ta thấy rằng xa thuộc (a) và yb thuộc (b), do đó xa + yb thuộc (a) + (b), dẫn đến c thuộc (a) + (b) Từ đó, ta có thể kết luận rằng (a) + (b) = Z.
Cho I là một ideal hai phía của R, và một phần tửa ∈R, ta có thể định nghĩa một lớp tương đương với quan hệ tương đương arb ⇔a−b∈I
Nếu hai phần tử a và b trong vành R được coi là tương đương, thì a−b thuộc về lý thuyết lý tưởng I Tập hợp tất cả các lớp tương đương tạo thành vành thương R/I Ví dụ, trong vành R = Z với lý tưởng I = 2Z, vành thương R/I = Z/2Z có hai phần tử tương đương là [0] = { ,−4,−2,0,2,4, }.
Các lớp tương đương trong nhóm R/I có thể được xác định dễ dàng là các coset của nhóm con I với đại diện là a ∈ R Mỗi phần tử của R/I có thể được ký hiệu dưới dạng a + I.
Phép cộng và phép nhân trên vành thương được định nghĩa dựa trên phép cộng và phép nhân trên R như sau :
Phép đồng cấu và đẳng cấu
Phép đồng cấu và đẳng cấu giữa các nhóm là khái niệm quan trọng trong hệ mật mã đồng cấu đầy đủ BGV, đặc biệt liên quan đến phép đồng cấu giữa hai vành Hàm mã hóa trong hệ mã BGV thể hiện sự chuyển đổi từ không gian bản rõ sang không gian bản mã, trong khi hàm giải mã thực hiện quá trình ngược lại Phần này sẽ trình bày các kiến thức và khái niệm liên quan đến hai phép ánh xạ đặc biệt này.
Hai nhóm được gọi là đẳng cấu (isomorphic) nếu chúng có cấu trúc tương tự và tồn tại một phép ánh xạ đẳng cấu giữa chúng Điều này có thể được hình dung như hai thế giới với các cá nhân khác nhau về tên gọi nhưng có cùng một cấu trúc và mối quan hệ giữa các phần tử Trong toán học, một tập đẳng cấu của tập G cung cấp một góc nhìn thay thế nhưng vẫn tương đương với tập G Không chỉ các nhóm, mà các cấu trúc đại số khác như vành cũng có thể có quan hệ đẳng cấu.
Đẳng cấu cung cấp một cái nhìn mới về cách biểu diễn các phần tử trong nhóm G, từ đó ảnh hưởng đáng kể đến hiệu quả tính toán Trong lý thuyết mật mã, đẳng cấu giúp xây dựng biểu diễn mật cho các bản rõ, cho phép tính toán các hàm trên bản rõ thông qua việc xử lý trên bản mật Định nghĩa 2.2.6: Cho G và H là các nhóm với các phép toán tương ứng ◦ G và ◦ H, một hàm số f: G → H được gọi là phép đẳng cấu từ G đến H nếu
1 f là một song ánh, và
2 Với mọi cặp g 1 , g 2 ∈G ta luôn có f(g 1 ◦G g 2) =f(g 1 )◦H f(g 2 ).
Nếu tồn tại một đồng cấu từ Gtới H thì ta nói các nhóm này là đẳng cấu và viết là
Nếu có một ánh xạ đồng cấu giữa hai nhóm đồng nhất, chúng ta gọi đó là phép ánh xạ tự đẳng cấu trên tập Một ví dụ điển hình cho phép đồng cấu này là ánh xạ tự đẳng cấu trên tập Z ∗ N, mà chúng ta sẽ sử dụng làm ví dụ cho phép đồng cấu chung.
Ta định nghĩa một ánh xạ song ánh từ Z ∗ N tới chính nó, được ký hiệu là f(m) = m^e, với e > 1 và thỏa mãn điều kiện gcd(e, φ(N)) = 1 Phép ánh xạ này là một phép tự đẳng cấu trên Z ∗ N, có tính chất f(m1 * m2) = (m1 * m2)^e = m1^e * m2^e = f(m1) * f(m2).
Phép đẳng cấu trong RSA được hiểu là cơ sở tính toán hàm sập, với không gian mã mật và không gian bản rõ đều là Z ∗ N Khi nhân hai bản mã mật, ta nhận được giá trị tương ứng với bản mã mật của kết quả nhân hai bản rõ Định nghĩa phép ánh xạ f :R →S giữa hai vành R và S được gọi là phép đẳng cấu (isomorphism) nếu đáp ứng các điều kiện nhất định.
Phép đồng cấu (homomorphism) là khái niệm tương tự như đẳng cấu nhưng không yêu cầu ánh xạ phải là song ánh Nó chỉ cần là phép đơn ánh, cho phép tạo ra một nhóm (vành) mới từ nhóm (vành) cũ mà không giữ lại thông tin đầy đủ Trong khi phép đẳng cấu duy trì sự tương ứng 1-1 giữa các phần tử của hai nhóm, phép đồng cấu có thể làm mất mát thông tin khi ánh xạ Ví dụ, phép ánh xạ đồng cấu từ Z đến Z2, f(x) = [x mod 2], không bảo toàn thông tin của tập gốc.
Trong lý thuyết mật mã, không gian mã mật thường lớn hơn không gian bản rõ, và phép giải mã là một phép đơn ánh Do đó, khái niệm đồng cấu được áp dụng để phát triển mô hình mật mã, mà chúng ta sẽ tập trung vào trong đồ án này: Hệ mật mã đồng cấu.
Định lý đồng dư Trung hoa
Định lý đồng dư Trung Hoa được áp dụng trong hệ mật mã BGV thông qua kỹ thuật tối ưu hóa gọi là Packing Theo Định lý 2.2.3, trong một vành giao hoán R có phần tử đơn vị, nếu I₁, , Iₖ là các ideal thuộc R và nguyên tố cùng nhau từng đôi một, thì tích I của chúng bằng giao của chúng Hơn nữa, vành thương R/I là đẳng cấu với tổng trực tiếp của các vành thương R/I₁, , R/Iₖ thông qua phép đẳng cấu f: R/I → R/I₁ ⊕ ⊕ R/Iₖ, với f(a) = (a + I₁, , a + Iₖ) với a ∈ R Đối với vành thương đa thức Z[X]/F(X), ta có Z[X]/F(X) ≅ ⊕_{i=1}^k Z[X]/Fᵢ(X), với phép đẳng cấu g(x) → ([g(x) mod F₁(x)], , [g(x) mod Fₖ(x)]).
Chu trình Hoán vị (Permutation Cycle)
Xem xét một hoán vị π được định nghĩa như sau : π(1) = 2, π(2) = 3, π(3) = 4, π(4) = 5, π(5) = 1
Biểu diễn Dạng mảng(Array Form) của π được mô tả trong minh họa và Biểu diễn Giản đồ mũi tên(Arrow Diagram) được mô tả trong minh họa.
Một dạng Giản đồ mũi tên khác, được gọi là Mô tả dạng Vòng-mũi tên, cung cấp mô tả trực quan về cấu trúc của hoán vị trong minh họa.
Trong giản đồ này, tất cả thông tin về π được thể hiện một cách rõ ràng Để xác định π(3), chỉ cần tìm phần tử 3 trong giản đồ và theo dõi mũi tên chỉ đến phần tử kế tiếp Kết quả cho π(3) là 4, tức là π(3) = 4.
Biểu diễn dạng chu kỳ-mũi tên mang lại nhiều lợi thế nổi bật Thứ nhất, nó cung cấp hình ảnh trực quan về cấu trúc chu kỳ, như trong ví dụ với 5 số chu kỳ được sắp xếp quanh một hình tròn, có thể được gọi là 5-chu kỳ Thứ hai, phương pháp này chỉ sử dụng một tập hợp các điểm được đánh số duy nhất, giúp giản đồ trở nên nhỏ gọn và dễ hiểu hơn so với dạng giản đồ mũi tên truyền thống.
Hình 2-1: Các Biểu diễn khác nhau dành cho 5-chu kỳ - source:[Mul16]
Chúng ta có thể đơn giản hóa biểu diễn của các mũi tên cho 5 chu kỳ bằng cách viết dưới dạng vòng, cụ thể là: π = (1,2,3,4,5).
Biểu diễn dạng vòng cho phép mỗi phần tử được ánh xạ đến phần tử tiếp theo trong danh sách, với phần tử cuối cùng ánh xạ trở lại phần tử đầu tiên Kiểu biểu diễn này thường được gọi là Chú giải vòng.
Tất cả các biểu diễn trong minh họa 2-1 đều có những lợi thế riêng, nhưng chú giải vòng được coi là lựa chọn tinh gọn nhất và thường xuyên được áp dụng.
Khi làm việc với chú giải vòng, π= (1,2,3,4,5), chúng ta nên gọi nó như sau :
"1 đi tới 2, 2 đi tới 3, 3 tới 4, 4 tới 5, và 5 tới 1"
Chú giải dạng vòng có thể bắt đầu từ bất kỳ phần tử nào trong chuỗi, không nhất thiết phải là phần tử được đánh chỉ số là 1 Ví dụ, nếu bắt đầu từ phần tử 3, ta có chú giải dạng vòng là (3,4,5,1,2) Các chú giải vòng tương đương cho π có thể được biểu diễn như sau: π = (1,2,3,4,5) = (2,3,4,5,1) = (3,4,5,1,2) = (4,5,1,2,3) = (5,1,2,3,4).
Bây giờ chúng ta xem xét một hoán vị có cấu trúc vòng phức tạp hơn : β
Để xây dựng chú giải dạng vòng cho β, ta cần phân tích đường đi của các mũi tên, cụ thể là 1 dẫn đến 3, 3 dẫn đến 7, 7 dẫn đến 5 và 5 quay trở lại 1 Kết quả là ta có một chú giải vòng thành phần là (1,3,7,5) Tương tự, bằng cách áp dụng quy trình này cho hai thành phần còn lại, ta có thể xác định các chú giải tương ứng.
(2) và (4,8,6) Lúc này ta có thể viết chú giải vòng của β là : β = (1,3,7,5)(2)(4,8,6)
Nếu loại bỏ các phần tử ánh xạ trực tiếp, chú giải của β sẽ trở nên tinh gọn hơn, cụ thể là: β = (1,3,7,5)(4,8,6).
Ta gọi một chú giải vòng (a 1 , a 2 , , a m ) làm−vòng (m−cycle) Như vậy trong ví dụ cụ thể về hoán vịβ, thì β sẽ là tích của 3-vòng và 4-vòng.
Lý thuyết mật mã hiện đại
Những nguyên tắc cơ bản
Trong những năm gần đây, ngành mật mã học đã thu hút sự chú ý như một lĩnh vực nghiên cứu quan trọng Các hệ mật mã được phân tích và phát triển một cách hệ thống nhằm chứng minh tính bảo mật của cấu trúc mật mã Để xây dựng lập luận về tính an toàn, trước tiên cần có một định nghĩa hình thức cho khái niệm "an toàn", tuy nhiên định nghĩa này không đồng nhất và cần phù hợp với ngữ cảnh cụ thể Lý thuyết mật mã hiện đại yêu cầu mỗi hệ mật phải đưa ra một giả định rõ ràng.
Mọi lập luận đều cần có một tiền đề vững chắc, vì không thể bắt đầu từ hư vô Hầu hết các hệ mật hiện đại dựa trên giả thuyết về độ khó của các bài toán toán học Do đó, mọi giả định tiền đề cần được nêu rõ ràng và chính xác.
Bộ ba nguyên tắc gồm định nghĩa hình thức, giả định rõ ràng và lập luận chặt chẽ là những yếu tố tạo nên sự khác biệt nổi bật giữa mật mã hiện đại và mật mã cổ điển Bài báo này sẽ đi sâu vào từng nguyên tắc trong bộ ba nền móng này, dựa trên tài liệu tham khảo [KL07].
1 Định nghĩa hình thức :Bất chấp mọi thông tin mà kẻ tấn công đã có , một bản mã mật không được phép để lộ bất cứ thông tin nào về bản tin mà nó mã hóa.
2 Giả định chính xác: Giả định là một tuyên bố chưa được chứng minh, nhưng được giả định là đúng Để một giả định có thể trở nên đáng tin, nó phải được mổ xẻ, và phân tích chặt chẽ liên tục, càng được mổ xẻ, thì ta càn an tâm về tính an toàn của hệ mật.
3 Chứng minh chặt chẽ : Một chứng minh bảo mật cần cho ra một đảm bảo vững chãi - dựa trên định nghĩa và giả định đã đưa ra - là không có kẻ tấn công nào có thể thành công.
Hệ mật mã cổ điển thường nhấn mạnh vào an toàn tuyệt đối, với mục tiêu đạt được An toàn vô điều kiện, tức là khả năng chống lại mọi tấn công mà không có khả năng bị phá vỡ Tuy nhiên, việc hiện thực hóa ý tưởng này gặp nhiều khó khăn Lý thuyết mật mã hiện đại giải quyết vấn đề này bằng cách xác định khả năng của kẻ tấn công và cho phép tồn tại một xác suất bị phá vỡ rất thấp, dựa trên một hàm số đặc biệt đại diện cho sự không đáng kể Trong khi lý thuyết cổ điển nói đến sự không thể phá vỡ, lý thuyết hiện đại thay thế bằng khái niệm rất khó phá vỡ.
Theo [KL07] thì các hệ mật mã hiện đại giả định rằng có ba dạng tấn công chính như sau :
Tấn công chỉ biết bản mã mật là hình thức tấn công cơ bản, trong đó kẻ tấn công chỉ có khả năng quan sát bản mã mật và nỗ lực tìm cách lấy thông tin bản rõ từ dữ liệu đã được mã hóa.
Trong kịch bản tấn công biết bản rõ, kẻ tấn công có khả năng thu thập một hoặc một vài cặp bản rõ và bản mã mật được tạo ra Mục tiêu chính của kẻ tấn công là khai thác thông tin từ các bản rõ để phục vụ cho việc giải mã các bản mã mật khác.
Tấn công lựa chọn bản rõ là một phương thức mà kẻ tấn công có khả năng lấy được cặp bản rõ và bản mã mật, với bản rõ được lựa chọn theo ý muốn của chúng Một ví dụ điển hình cho loại tấn công này là cuộc tấn công vào máy Enigma.
Tấn công lựa chọn bản mã mật là một phương thức mà kẻ tấn công có khả năng thu thập thông tin về bản rõ của bản mã mật mà chúng chọn Mục tiêu chính của kẻ tấn công là thu thập thông tin từ các bản rõ khác thông qua các bản mã mật Trong trường hợp này, kẻ tấn công có thể hoạt động như một người gián tiếp, điều khiển các bên để lấy được bản giải mã của một số bản mã mật nhất định mà chúng cần, chẳng hạn như khi kẻ tấn công nằm trong nội bộ của hai bên.
An toàn chứng tỏ và An toàn thực
Hầu hết các kết quả trong mật mã hiện đại đều dựa trên nền tảng toán học vững chắc, bao gồm các định nghĩa, giả định và lập luận rõ ràng Một hệ mật mã chỉ được coi là an toàn khi nó được chứng minh và kiểm chứng.
Bằng cách sử dụng các phương tiện toán học, hệ thống bảo mật đạt được an toàn chứng tỏ (Provable Security) Tuy nhiên, để đảm bảo rằng hệ mật thực sự an toàn trong thế giới thực, cần phải đạt được an toàn thực Các nhà mật mã học không ngừng cập nhật định nghĩa, giả định và chứng minh nhằm cải thiện mức độ gần gũi giữa an toàn chứng tỏ và an toàn thực.
An toàn tính toán
Trong lý thuyết mật mã, an toàn tuyệt đối được định nghĩa là khi phân phối không gian bản mã và bản rõ hoàn toàn độc lập, được biểu thị bằng công thức Pr[M = m|C = c] = Pr[M = m] Tuy nhiên, nhược điểm của an toàn tuyệt đối là không gian khóa K phải lớn hơn hoặc bằng không gian tin M, dẫn đến việc khóa trở nên cồng kềnh và khó lưu trữ, giống như một bản rõ cần được bảo vệ.
An toàn tuyệt đối có thể được coi là sự cầu toàn quá mức, không chú ý đến tính thực tiễn và hiệu quả Chúng ta có thể chấp nhận một mức độ an toàn thấp hơn một chút để tối ưu hóa không gian khóa Đây là nguyên tắc cơ bản của phương pháp giải quyết vấn đề hiện đại, nơi mà việc hy sinh một phần độ chính xác có thể mang lại cải thiện lớn về công sức Hơn nữa, an toàn tuyệt đối không xem xét khả năng tính toán của kẻ tấn công, dẫn đến việc thiết kế hệ thống an toàn có thể chỉ là đối phó với một kẻ thù tưởng tượng Định nghĩa an toàn cần chú ý đến khả năng tính toán của kẻ tấn công và cho phép một mức độ thất bại nhỏ, được gọi là An toàn tính toán, hiện đang là tiêu chuẩn thực tiễn nhất để xác định an toàn cho các mục đích khác nhau.
An toàn tính toán bao gồm 2 nới lỏng quan trọng sau :
1 An toàn chỉ đảm bảo chống lại kẻ tấn công hiệu quả với một thời gian làm việc cho phép Nếu ta có thể tạo ra một hệ mật yêu cầu về năng lực tính toán, hoặc lượng thời gian để phá vỡ nó lớn hơn những gì mà kẻ tấn công có thể có, thì tức là với mọi mục tiêu thực tiễn hệ của ta không thể bị phá vỡ.
2 Kẻ tấn công có thể thành công với một xác suất rất nhỏ
Có hai cách tiếp cận để định nghĩa rõ ràng về hai nới lỏng: cách tiếp cận tiệm cận (asymptotic approach) và cách tiếp cận cụ thể (concrete approach) Cách tiếp cận tiệm cận sử dụng các khái niệm toán học để mô tả khả năng của kẻ tấn công và lượng hóa nguy cơ thất bại, được đánh giá là thực tế hơn so với cách tiếp cận cụ thể Trong phương án tiệm cận, tham số bảo mật (ký hiệu là λ) là một yếu tố quan trọng, ảnh hưởng đến cả hệ mật và các bên liên quan.
Tham số bảo mật có thể giúp kẻ tấn công ước lượng thời gian và xác suất thành công của chúng, thông qua một hàm số mà đầu vào là tham số bảo mật, thay vì sử dụng các con số cố định như trong các phương án cụ thể.
1 Với phương pháp tiếp cận tiệm cận ta sẽ coi "kẻ tấn công hiệu quả" như là một thuật toán (ngẫu nhiên) chỉ chạy trong thời gian đa thức phụ thuộc vào λ (ta viết ngắn gọn là kẻ tấn công PTT -ProbabilisticPolynomialTime Adversary). Điều đó có nghĩa là tồn tại một đa thứcp xác định giới hạn thời gian chạy của kẻ tấn công là p(λ) Đối với các bên trung thực (bên ta) cũng sở hữu các thuật toán liên quan chạy trong thời gian đa thức, mặc dù ta nhấn mạnh rằng kẻ tấn công rất có thể có sức mạnh tính toán (và có thời gian nhiều hơn) các bên trung thực.
2 Chúng ta sẽ mô tả thực tế "xác suất thành công cực nhỏ" bằng một định nghĩa hàm không đáng kể Định nghĩa 2.4.1 (Định nghĩa 3 4 trong sách [KL07]) Một hàm f ánh xạ các phần tử từ tập số tự nhiên sang tập số thực không âm là không đáng kể nếu như với mọi đa thức nguyên p đều tồn tại một số tự nhiên N sao cho với mọi λ > N ta đều có điều sau xảy ra f(λ) N.
Hệ mật mã công khai
Các hệ mật mã hiện đại được chia thành hai loại chính: Mật mã công khai và Mật mã khóa bí mật Trong Mật mã khóa bí mật, hai bên cần thống nhất một khóa bí mật để thực hiện cả việc mã hóa và giải mã Ngược lại, Mật mã công khai cho phép các bên giao tiếp an toàn mà không cần chia sẻ thông tin bí mật trước đó Tương tự như hai người trong một căn phòng có thể nói chuyện với nhau mà không ai khác nghe được nội dung cuộc trò chuyện của họ.
Hệ mật mã hóa công khai, hay còn gọi là hệ mật mã phi đối xứng, bao gồm một cặp khóa: khóa công khai (pk) và khóa bí mật (sk) Người nhận sẽ tạo ra cặp khóa này, trong đó khóa công khai được sử dụng bởi người gửi để mã hóa tin nhắn, và khóa bí mật được dùng bởi người nhận để giải mã và nhận lại nội dung gốc.
Hệ mật mã hóa công khai mang lại nhiều lợi thế vượt trội so với hệ mật mã bí mật, mặc dù tốc độ tính toán của nó chậm hơn khoảng 3 đến 4 lần (theo [KL07]) Những lợi ích này bao gồm khả năng chia sẻ khóa dễ dàng, tăng cường bảo mật và tính linh hoạt trong việc quản lý khóa, giúp người dùng có thể giao tiếp an toàn mà không cần phải trao đổi khóa bí mật trước đó.
1 Giải quyết đượcvấn đề phân phối khóa, hai bên không cần thiết lập một phương thức phân phối khóa cho nhau một cách bí mật, họ có thể hoàn toàn thực hiện truyền thông một cách bí mật cho dù truyền thông của họ hoàn toàn bị theo dõi.
2 Giải quyết được vấn đề số lượng khóa tăng đột biến, khi một bên truyền thông với nhiều bên khác nhau, với một cặp khóa công khai-bí mật, một bên tham gia có thể giao tiếp với vô hạn các bên khác muốn gửi tin cho họ.
Các hệ mật mã hiện đại dựa vào giả thiết về độ khó của các bài toán khó, như trong trường hợp của hệ mật mã RSA, dựa trên giả thiết rằng việc phân tích thừa số nguyên tố lớn là khó khăn Cụ thể, có một hàm không đáng kể negl(n) cho thấy xác suất thuật toán đa thức A đưa ra kết quả đúng cho bài toán này là thấp Tuy nhiên, với sự phát triển của mô hình tính toán lượng tử, nhiều bài toán khó có thể được giải quyết trong thời gian đa thức, điều này có thể dẫn đến việc hệ mật mã RSA bị phá vỡ nếu mô hình tính toán này được hoàn thiện.
Hiện nay, các nhà nghiên cứu đã phát triển các hệ mật mã công khai có khả năng bảo vệ tính bảo mật ngay cả khi công nghệ tính toán lượng tử tiến bộ Một ví dụ điển hình là hệ mật mã NTRU, được xây dựng dựa trên bài toán tìm vector ngắn nhất trong không gian vector Bên cạnh đó, các hệ mật mã đồng cấu mới cũng đang được nghiên cứu và phát triển, mang lại giải pháp an toàn cho tương lai.
GBV dựa trên bài toán Learning With Error, cho thấy tính an toàn của nó trước sự tấn công của tính toán lượng tử Theo định nghĩa 2.4.2, hệ mật mã hóa công khai bao gồm ba thuật toán xác suất thời gian đa thức: Gen, Enc và Dec.
1 Thuật toán sinh khóa Gen lấy đầu vào là tham số bảo mật 1 n và cho ra đầu ra là một cặp khóa (pk, sk) Ta coi khóa đầu tiên là khóa công khai và khóa thứ hai là khóa bí mật.
2 Thuật toán mật mã hóa Enclấy đầu vào là khóa công khai pk và một bản rõ m từ không gian bản rõ được chọn Và cho ra kết quả là bản mã mật c← Enc p k(m) (Enc cần có đặc tính xác suất nếu như muốn đạt được mức độ bảo mật có ý nghĩa, cụ thể là khả năng chống lại tấn công lựa chọn bản mã).
3 Thuật toán tất định giải mã Dec nhận đầu vào là khóa bí mật sk và một bản mã mật c cho đầu ra là một bản rõ m hoặc một ký tự đặc biệt nào đó cho biết quá trình giải mã thất bại Ta có thể biễu diễn nó dưới đẳng thức m s k(c)
Trong định nghĩa về mật mã hóa công khai, thuật toán mật mã hóa được mặc định là thuật toán xác suất (mật mã hóa xác suất), nghĩa là ngay cả khi hai đầu vào giống nhau, đầu ra cũng không nhất thiết phải giống nhau và xác suất để chúng giống nhau là rất nhỏ Nếu thuật toán mật mã hóa tạo ra cùng một bản mã mật cho hai bản rõ giống nhau, kẻ tấn công sẽ có lợi thế lớn trong trường hợp tấn công lựa chọn bản mã, đồng thời hệ mật sẽ dễ bị lộ không gian phân bố bản rõ Hệ mật Enigma của phát xít Đức là một ví dụ điển hình của hệ mã đơn định, đã bị lợi dụng tính chất này để bị phá hoàn toàn, nhờ vào những từ ngữ thường xuyên xuất hiện trong bản rõ như "Hitler muôn năm" hay "Buổi sáng ngày".
Bài toán Learning with Error
Bài toán tính toán
Mục tiêu của lý thuyết độ phức tạp tính toán là xác định các nguồn tài nguyên cần thiết cho việc giải quyết một bài toán tính toán và phân loại các bài toán theo mức độ khó khăn của chúng.
Có một số loại tài nguyên quan trọng trong lý thuyết độ phức tạp tính toán, trong đó tài nguyên thời gian là loại được quan tâm nhiều nhất Tiếp theo, tài nguyên không gian bộ nhớ cũng đóng vai trò quan trọng Để hiểu rõ hơn về các độ phức tạp, chúng ta cần xem xét một số bài toán cơ bản liên quan.
Một bài toán tính toán là một đối tượng thể hiện các câu hỏi mà máy tính cần giải quyết, với đầu vào là chuỗi mô tả cho một trường hợp cụ thể và đầu ra là chuỗi gọi là lời giải Mỗi bài toán tính toán bao gồm vô số cặp trường hợp và lời giải tương ứng.
Có hai nhánh nghiên cứu chính trong lĩnh vực tính toán: một là phát triển các thuật toán hiệu quả để giải quyết bài toán, và hai là phân tích lý do tại sao một số bài toán lại được coi là không thể giải quyết hoặc rất khó giải quyết, ngay cả khi có tài nguyên máy tính vô hạn Bài báo cáo này sẽ trình bày hai dạng bài toán tính toán phổ biến nhất hiện nay.
Bài toán tìm kiếm : Một bài toán tìm kiếm bao gồm một tập vô hạn các trường hợp và một đặc tả cho lời giải chính xác tương ứng.
Bài toán quyết định là một dạng bài toán bao gồm một tập hợp vô hạn các trường hợp, trong đó có một đặc tả xác định những trường hợp mà câu trả lời là ĐÚNG.
Các lớp bài toán
Độ phức tạp thời gian của một bài toán phản ánh số bước cần thiết để giải quyết một trường hợp cụ thể khi áp dụng thuật toán tối ưu nhất Để đánh giá hiệu quả về thời gian, chúng ta sử dụng Ký pháp O-Lớn, một công cụ mô tả cận trên tiệm cận cho độ lớn của một hàm dựa trên hàm khác đơn giản hơn Cụ thể, nếu f(x) và g(x) là hai hàm xác định trên một tập con M của tập số thực R, thì f(x) = O(g(x)) khi x tiến tới vô cùng nếu tồn tại một số thực x₀ và một hằng số k sao cho |f(x)| ≤ k |g(x)| với x > x₀.
Các bài toán tính toán rơi vào các tập, gọi là các lớp phức tạp(complexity classes) Một lớp phức tạp được định nghĩa bởi 3 thành tố sau :
1 Dạng bài toán tính toán: Thông thường là các bài toán quyết định nhưng có thể là các bài toán tính toán dạng khác như bài toán tìm kiếm hay bài toán tối ưu, vv
2 Mô hình tính toán : Mô hình tính toán được sử dụng ở đây hầu hết là máyTuring, nhưng có thể mô hình khác được sử dụng như mô hình mạch Boolean(trong lý thuyết mật mã đồng cấu mô hình mạch Boolean được sử dụng).
3 Tài nguyên : Hầu hết chỉ có hai loại tài nguyên , thời gian và bộ nhớ.
Bài toán lớp P bao gồm tất cả các bài toán quyết định có thể được giải quyết bởi máy Turing đơn định trong thời gian đa thức, với đầu vào tương ứng là kích thước của bài toán.
Bài toán lớp NP bao gồm tất cả các bài toán quyết định có thể giải quyết trong thời gian đa thức trên máy Turing bất định Máy Turing bất định có khả năng thực hiện mọi tác vụ mà máy Turing đơn định có thể làm, đồng thời còn vượt trội hơn, dẫn đến kết luận rằng P⊆NP Định nghĩa 2.5.2 nêu rõ rằng nếu A và B là hai bài toán quyết định, thì một sự giảm thiểu từ A về B có thể được thực hiện.
B là một hàm tính toán trong thời gian đa thức f : P ∗ → P ∗, với P ∗ đại diện cho tập hợp tất cả các chuỗi đầu vào khả thi Điều kiện x∈A xảy ra nếu và chỉ nếu f(x)∈B Nếu A quy dẫn đến B và B có thể giải quyết trong thời gian đa thức, thì A cũng có thể được giải quyết trong thời gian đa thức.
Bài toán quyết định A được coi là NP-hard nếu mọi bài toán trong lớp NP có thể được quy dẫn về A, điều này có nghĩa là độ khó của A không thấp hơn bất kỳ bài toán nào trong NP.
Nếu bài toán A thuộc lớp NP, thì A được gọi là NP-complete Điều này có nghĩa là nếu A là NP-hard, thì nó không thể được giải quyết trong thời gian đa thức trừ khi P=NP.
Bài toán khó Learning with Error
Định nghĩa 2.5.3 (LWE) liên quan đến hệ số bảo mật λ, trong đó n = n(λ) là số chiều, q = q(λ) ≥ 2 là một số nguyên, và χ = χ(λ) là một phân phối trên Z Bài toán quyết định LWE n,q,χ nhằm phân biệt hai phân phối: trong phân phối đầu tiên, mẫu (a i , b i ) được lấy từ Z n+1 q theo phân phối đều, trong khi ở phân phối thứ hai, trước tiên mẫu s ← Z n q được lấy theo phân phối đều, sau đó
(a i , b i ) ∈ Z q n+1 bằng cách sau lấy mẫu theo phân phối đều a i ← Z n q , e i ← χ, và gán b i =ha,si+e i Giả thiết LWE n,q,χ là bài toán LWE n,q,χ là bất khả thi.
Regev [Reg05] đã chứng minh rằng với giá trị moduli q phù hợp và phân phối Gaussian χ, giả thuyết LWE n,q,χ có mức độ đúng tương đương với một giả thuyết khác.
Bài toán trên lattice, đặc biệt trong trường hợp tồi tệ nhất, rất khó giải quyết bằng mô hình thuật toán lượng tử Chúng ta sẽ phân tích độ khó của bài toán này khi phân phối χ là một phân phối B-bounded Phân phối B-bounded có thể được hiểu là một phân phối trên số nguyên, trong đó xác suất lấy mẫu một phần tử bị giới hạn bởi B là lớn Định nghĩa 2.5.4 xác định rằng một tập hợp các phân phối {χ n } n∈N trên tập số nguyên được gọi là B-bounded nếu e←χ P r n.
[|e|> B] =negl(n) Chú ý : Ở đây cần giải thích tại sao lại có một lemma sau Định lý 2.5.1 Với bất kỳ giá trị của n là số chiều, với số nguyên q = q(n), và
B = B(n) ≥ 2n cho phép tồn tại một phân phối B-bounded χ, giúp việc lấy mẫu hiệu quả Nếu có một thuật toán hiệu quả (có thể là thuật toán lượng tử) giải quyết bài toán LWE n,q,χ, thì sẽ có một thuật toán lượng tử hiệu quả để giải quyết bài toán xấp xỉ-xấp xỉ O(qn˜ 1.5 /B) SIVP trong trường hợp tồi nhất cũng như bài toán gapSVP.
Bài toán Ring Learning with Errors (RLWE)
Bài toán Ring Learning with Errors (RLWE) do Lyubaskevsky, Peikert và Regev đề xuất, đóng vai trò quan trọng trong lý thuyết mật mã Mô hình mật mã BGV dựa trên giả thiết về độ khó của bài toán RLWE Để định nghĩa một biến thể của bài toán này, cần xác định các giả thiết phù hợp với các hệ mật mã Cụ thể, với hệ số bảo mật λ, ta có đa thức f(x) = x^d + 1, trong đó d = d(λ) là lũy thừa của 2, và q = q(λ) ≥ 2 là một số nguyên.
R = Z[x]/(f(x)) và R q = R/qR, trong đó χ = χ(λ) là một phân phối trên R Bài toán RLWE q,d,χ dạng quyết định yêu cầu phân biệt hai phân phối: phân phối thứ nhất lấy mẫu (a i , b i ) theo phân phối đều trên R q 2, trong khi phân phối thứ hai lấy mẫu (a i , b i ) ∈ R 2 q thông qua các bước sau: đầu tiên lấy mẫu đồng đều s từ R q, sau đó e i từ χ, và đặt b i = a i ãs + e i Giả thiết RLWE d,q,χ cho rằng việc giải quyết bài toán này là bất khả thi.
Theo Lyubashevsky, Peikert và Regev, bài toán tìm vector ngắn nhất trên ideal lattices (bài toán SVP) có thể được quy dẫn từ bài toán RLWE Định lý 2.5.2 (Lyubashevsky-Peikert-Regev) chỉ ra rằng, với một số d là lũy thừa của 2, vành R = Z[x]/(x^d + 1), một số nguyên tố q = q(d) = 1 mod d, cùng với B = ω(√d log d), tồn tại một phân phối χ cho phép lấy mẫu hiệu quả một phần tử trên R có độ dài tối đa B với xác suất cao Nếu có một thuật toán hiệu quả giải quyết bài toán RLWE d,q,χ, thì sẽ dẫn đến sự tồn tại của một thuật toán lượng tử để giải quyết hiệu quả bài toán xấp xỉ-d^ω(1) ã(q/B) SVP trong trường hợp tồi nhất.
Hệ mật mã hóa Đồng cấu
Hệ mật mã hóa đồng cấu (fully homomorphic encryption scheme) được đề xuất lần đầu bởi Rivest, Adleman và Dertouzous, chỉ một thời gian ngắn sau khi nhóm Rivest, Shamir và Adleman phát minh ra hệ mật mã khóa công khai RSA Ban đầu, khái niệm này được gọi là phép đồng cấu riêng tư (privacy homomorphism).
Thuật ngữ đồng cấu gần giống với đồng cấu trong đồng cấu nhóm và vành của Đại số trừu tượng Việc tạo ra các hệ đồng cấu này chủ yếu liên quan đến việc đề xuất một phép đồng cấu ánh xạ từ không gian bản rõ sang không gian mã mật, với đặc điểm bẫy sập Điều này có nghĩa là rất khó để ánh xạ ngược từ không gian mã mật về không gian bản rõ nếu không có thông tin đặc biệt.
Hệ mật mã đồng cấu đầy đủ cho phép thực hiện mọi phép toán trên dữ liệu được mã hóa mà không cần khóa giải mã, khác với các hệ như RSA chỉ hỗ trợ phép nhân và hệ Pallier chỉ hỗ trợ phép cộng Điều này tạo ra khả năng tìm kiếm, ghi chép và xử lý dữ liệu hiệu quả dưới dạng biểu thức Boolean, mở ra nhiều ứng dụng tiềm năng trong bảo mật thông tin.
Hệ mật mã hóa xác suất tạo ra nhiễu trong mỗi bản mã mật để chống lại các cuộc tấn công, nhưng khi tính toán trên không gian bản mã, nhiễu có thể tăng lên nhanh chóng, dẫn đến sai sót trong kết quả giải mã Năm 2009, Gentry đã đề xuất một hệ mật mã hóa dựa trên các bài toán khó, cho phép ước lượng các phép toán cộng và nhân, cùng với phương pháp xử lý lỗi gọi là bootstrapping Mặc dù lý thuyết cho thấy hệ thống của Gentry có thể tính toán trên mọi mạch với độ sâu tùy ý, nhưng hiệu suất thực tế của nó vẫn rất thấp và không phù hợp cho ứng dụng thực tiễn.
Sau này, Gentry cùng các cộng sự và nhóm nghiên cứu khác đã phát triển nhiều hệ mật mã đồng cấu đầy đủ với hiệu năng vượt trội hơn so với các hệ ban đầu của ông Trong số đó, hệ mật mã BGV do Gentry, Brakersky và Vaikuntanathan phát triển đã đạt được thành công lớn khi được một nhóm tác giả tại Tập đoàn IBM xây dựng thành một thư viện, kết hợp với các kỹ thuật tối ưu hóa dành cho hệ BGV.
Định nghĩa
Trong phần này, báo cáo sẽ trình bày các khái niệm cơ bản về hệ mật mã đồng cấu, chủ yếu tham khảo từ tài liệu [Gen09] Hệ mật mã đồng cấu được định nghĩa trong không gian bản rõ P và không gian mã mật C, với các phép toán tương ứng ◦ P và ◦ C Hàm mã hóa Enc() từ P sang C và hàm giải mã Dec() từ C về P tạo thành một hệ mật mã khóa công khai ε = (Gens, Enc, Dec) Hệ thống này được coi là đồng cấu nếu hàm mã hóa là một phép đồng cấu giữa hai không gian.
Hệ mật mã được phân loại thành hai loại chính: hệ mật mã cộng tính và hệ mật mã nhân tính Hệ mật mã cộng tính được định nghĩa khi hai phép toán trên không gian bản rõ và không gian bản mã được coi là phép toán "cộng" Ngược lại, hệ mật mã nhân tính được xác định khi hai phép toán này được xem như phép "nhân" Báo cáo cũng giới thiệu một định nghĩa nâng cao hơn từ tài liệu [Gen09], trong đó phép toán ◦ P được thay thế bằng một mạch C.
Hàm ước lượng Eval được sử dụng để thay thế C trong các hệ mật mã đồng cấu, với các định nghĩa mới và hệ đồng cấu gần đây thường biểu diễn các hàm và thuật toán dưới mô hình mạch Boolean, vì chúng tương đồng với kiến trúc máy tính thực tế Điều này cho phép ước lượng chính xác hơn về độ phức tạp thời gian của một mạch khi hệ đồng cấu thực hiện ước lượng trên dữ liệu mã hóa Theo định nghĩa 3.1.2, một hệ mật mã hóa khóa công khai ε = (Gens, Enc, Dec) được coi là đồng cấu đầy đủ nếu tồn tại thuật toán Eval ε hiệu quả, nhận đầu vào là khóa công khai pk, mạch C thuộc tập mạch cho phép C ε, và tập bản mã mật Ψ = {c 1 , , c t }, với c i ← Enc p k(m i ) Kết quả c nhận được từ Eval pk (C, Ψ) là "mật mã hóa của C(m 1 , , m t )" dưới khóa công khai pk, trong đó C(m 1 , , m t ) là đầu ra của mạch C khi áp dụng vào đầu vào m 1 , , m t.
Ta nói một hệ mật mã đồng cấu ε là đúng đắn với tập mạch C ε nếu, với một cặp
(sk, pk) tùy ý là kết quả của hàm sinh khóa Gens ε (λ), với một mạch C tùy ý thuộc
Trong hệ thống mã hóa, với một tập bản rõ m 1 , , m t thuộc không gian P và một tập bản mã mật Ψ = {c 1 , , c t } được tạo ra từ các bản rõ thông qua hàm mã hóa Enc(pk, m i ), có thể khẳng định rằng nếu c được tính toán qua Eval(pk, C,Ψ), thì quá trình giải mã Dec(sk,c) sẽ trả về tập bản rõ C(m 1 , , m t ) với xác suất sai sót không đáng kể.
Gentry cho rằng định nghĩa về tính đúng đắn là không đủ vì nó chấp nhận một mô hình mật mã vô nghĩa, trong đó hàm Eval(pk, C,Ψ) chỉ trả lại (C,Ψ) và hàm Dec giải mã phần bản mã Ψ rồi áp dụng mạch C lên kết quả Mặc dù mô hình này vẫn đúng đắn, nhưng không hấp dẫn do đẩy công việc tính toán mạch C cho hàm Dec Để khắc phục, có thể đặt chặn cho độ lớn của mạch giải mã D ε, phụ thuộc vào hệ số bảo mật λ Điều này cho thấy hàm giải mã trong hệ mật mã vô nghĩa có độ lớn liên quan đến kích thước của C.
Gentry định nghĩa một hệ mật mã đồng cấu ε là "chặt" (compact) nếu tồn tại hàm f sao cho, với mọi tham số bảo mật λ, thuật toán giải mã của ε có thể được mô tả bởi mạch D ε với kích thước không vượt quá f(λ) Định nghĩa này kết hợp với định nghĩa trước đó để hình thành khái niệm "ước lượng chặt" (compactly evaluates), trong đó hệ mật mã ε được coi là "ước lượng chặt" với các mạch thuộc lớp C ε nếu nó vừa chặt vừa đúng đắn cho mọi mạch thuộc C ε.
Gentry đã đưa ra một định nghĩa mở rộng cho tính chất chặt là "tựa-chặt" (quasi-compact), mô tả các hệ mật mã với độ lớn bản mã mật tăng tuyến tính hoặc đa thức theo độ sâu của mạch ước lượng Ông nhấn mạnh rằng các hệ mật mã hóa đồng cấu này có giá trị ứng dụng cao trong nhiều lĩnh vực.
![Hình 2-1: Các Biểu diễn khác nhau dành cho 5-chu kỳ - source:[Mul16] - Hệ mật mã đồng cấu đầy đủ BGV và thư viện mãhóa đồng cấu HeLib](https://media.store123doc.com/figures/006/297/hinh-bieu-dien-danh-chu-ky-source-mul-6297020.webp)
