Đề tài Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

ng thông báo x được bảo mật, chứ không có gì để xác nhận x là của B. Nếu ta muốn hệ truyền tin của ta vừa có tính bảo mật vừa có tính xác nhận, thì ta phải sử dụng đồng thời cả hai hệ mật mã và xác nhận (bằng chữ ký). Giả sử trên mạng truyền tin công cộng, ta có cả hai hệ mật mã khoá công khai S1 và hệ xác nhận bằng chữ ký S2. Gi sử B có bộ khoá mật mã K = (K', K'') với K' = (n, e) và K'' = d trong hệ S1, và A có bộ khoá chữ ký Ks = (K’s , K''s) với K’s = a và K''s = (n,b) trong hệ S2. A có thể gửi đến B một thông báo vừa bảo mật vừa có chữ ký để xác nhận như sau: A ký trên thông báo x trước, rồi thay cho việc gửi đến B văn bản cùng chữ ký (x,sigk’s(x)) thì A sẽ gửi cho B bản mật mã của văn bản đó được lập theo khoá công khai của B, tức là gửi cho B ek’((x, sigk’s (x)). Nhận được văn bản mật mã đó B sẽ dùng thuật toán giải mã dk’’ của mình để thu được (x, sigk’s (x)), sau đó dùng thuật toán kiểm thử chữ ký công khai verk”s của A để xác nhận chữ ký sigk’s(x) đúng là của A trên x. 2.4.Sơ đồ chữ ký Elgamal Sơ đồ chữ ký ElGamal được đề xuất năm 1985, gần như đồng thời với sơ đồ hệ mật mã ElGamal, cũng dựa trên độ khó của bài toán lôgarit rời rạc. Sơ đồ được thiết kế đặc biệt cho mục đích ký trên các văn bản điện tử, được mô tả như một hệ: S = (P , A , K , S , V) trong đó P = Z*p , A = Z*p x Zp-1, với p là một số nguyên tố sao cho bài toán tính lôgarit rời rạc trong Z*p là rất khó. Tập hợp K gồm các cặp khoá K=(K’,K''), với K’=a là một số thuộc Z*p , K'' =(p, α , β), α là một phần tử nguyên thuỷ của Z*p , và β=αamodp. K’ là khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử chữ ký. Các thuật toán ký và kiểm thử chữ ký được xác định như sau: Với mỗi thông báo x, để tạo chữ ký trên x ta chọn thêm môt số ngẫu nhiên k Î Z*p-1 , rồi tính : sig k’ (x,k ) = (γ , δ) với γ = α k modp, δ = (x – a.γ). k-1 mod(p -1). Thuật toán kiểm thử được định nghĩa bởi: verk” (x,(γ , δ)) = đúng ↔ β γ . γ δ ≡ α x (modp). Dễ thấy rằng sơ đồ chữ ký được định nghĩa như trên là hợp thức. Thực vậy, nếu sigk’(x,k ) = (γ , δ) thì ta có : β γ . γ δ ≡ α aγ. α kδ modp ≡ α x modp, vì k.δ +a.γ ≡ x mod(p -1). Do đó, verk” (x,(γ , δ)) = đúng. CHƯƠNG 3 SƠ ĐỒ CHIA SẺ BÍ MẬT 3.0. Định nghĩa : Sơ đồ chia sẻ bí mật là một phương thức để chia sẻ một bí mật ra nhiều phần sau đó phân phối cho một tập hợp những người tham gia sao cho các tập con nào đó trong số những người này được chỉ định có khả năng khôi phục lại bí mật bằng cách kết hợp dữ liệu của họ. Một sơ đồ chia sẻ bí mật là hoàn hảo nếu bất kỳ một tập hợp những người tham gia mà không được chỉ định sẽ tuyệt đối không thu được thông tin gì về bí mật. 3.1 Các thành phần của sơ đồ chia sẻ bí mật : Người phân phối bí mật (Dealer): Là người trực tiếp chia bí mật ra thành nhiều phần Những người tham gia nhận dữ liệu từ Dealer (Participant) ký hiệu P Nhóm có khả năng khôi phục bí mật (Acess structure): Là tập con của P trong đó có các tập con có khả năng khôi phục bí mật. 3.2 Một số sơ đồ chia sẻ bí mật: 3.2.1 Sơ đồ chia sẻ bí mật sơ khai: Một sơ đồ chia sẻ bí mật đảm bảo tính bảo mật là sơ đồ trong đó bất kỳ người nào có ít hơn t phần dữ liệu (là số lượng đủ để khôi phục bí mật) không có nhiều thông tin hơn một người không có dữ liệu. Xem xét sơ đồ chia sẻ bí mật sơ khai trong đó cụm từ bí mật “password” được chia thành các phần “pa…”,”ss…”,”wo…”và ”rd…”. Một người không có một trong các phần bí mật đó chỉ biết mật khẩu có 8 chữ cái. Anh ta sẽ phải đoán mật khẩu đó từ 226=8 tỷ khả năng có thể xảy ra. Một người có một phần trong số 6 phần của mật khẩu đó sẽ phải đoán 6 chữ cái tương đương với 226 khả năng. Hệ thống này không phải là một sơ đồ chia sẻ bí mật bảo mật bởi vì một người tham gia có ít hơn t phần dữ liệu thu được một phần đáng kể thông tin về bí mật.Trong một sơ đồ bảo mật, mặc dù một người tham gia chỉ thiếu một phần dữ liệu cũng có thể sẽ đối mặt với 268 = 208 tỷ khả năng. 3.2.2 Sơ đồ chia sẻ bí mật tầm thường Có một vài sơ đồ chia sẻ bí mật trong đó yêu cầu tất cả những người tham gia phải cùng nhau khôi phục lại bí mật : Mã hóa bí mật thành một số nguyên S. Đưa cho mỗi người tham gia i một số ngẫu nhiên ri (trừ một người). Đưa cho người cuối cùng một số (S- r1 - r2 -…- rn-1). Bí mật chính là tổng của các số của tất cả những người tham gia vào sơ đồ. Mã hóa bí mật bằng 1 byte S. Đưa cho mỗi người tham gia i một byte bi (trừ một người), đưa cho người cuối cùng byte (S XOR b1XOR b2 …XOR bn-1) 3.2.3 Sơ đồ chia sẻ bí mật có ngưỡng giới hạn (Threshold secret sharing schemes) Mục tiêu của sơ đồ dạng này là chia một ít dữ liệu D ra thành nhiều phần D1,D2,…,Dn sao cho : Nếu biết k hoặc nhiều hơn các phần Di có thể dễ dàng suy ngược lại D Nếu biết k-1 hoặc ít hơn các phần Di không thể suy ngược lại D Sơ đồ này được gọi là sơ đồ ngưỡng giới hạn (k,n). Nếu k = n thì tất cả mọi thành viên phải cùng nhau mới có thể suy ngược lại bí mật. Dưới đây là 2 sơ đồ bí mật dạng (k,n). 3.2.3.1 Sơ đồ chia sẻ bí mật Blakley Hai đường thẳng không song song nằm trong cùng một mặt phẳng cắt nhau tại một điểm duy nhất. Ba mặt phẳng không song song trong không gian cắt nhau tại một điểm duy nhất.Tổng quát hơn, bất kỳ n mặt siêu phẳng nào cũng cắt nhau tại một điểm cụ thể. Bí mật có thể được mã hóa là một đơn tọa độ của giao điểm đó. Nếu bí mật được mã hóa bằng cách sử dụng tất cả các tọa độ, mặc dù chúng là ngẫu nhiên, khi đó một người tham gia (ai đó sở hữu một hoặc nhiều các siêu mặt n chiều) thu được thông tin về bí mật do anh ta biết nó nhất định phải nằm trên mặt mà anh ta sở hữu. Nếu một người trong cuộc mà thu được nhiều thông tin hơn một người ngoài cuộc về bí mật, khi đó hệ thống này không còn bảo mật nữa. Nếu chỉ có một trong số các tọa độ được sử dụng, khi đó một người trong cuộc không biết về bí mật hơn một người ngoài cuộc (thí dụ:Bí mật phải nằm trên trục x trong hệ trục tọa đồ Decac). Mỗi người tham gia được đưa đủ thông tin để định nghĩa một siêu mặt; bí mật được khôi phục bằng cách tính toán điểm giao nhau của các mặt và lấy một tọa độ cố định của giao điểm đó. Sơ đồ của Blakley trong hệ tọa độ không gian 3 chiều: Thông tin của mỗi người tham gia là một mặt phẳng và bí mật chính là giao điểm của 3 mặt phẳng đó. Thông tin của 2 người không đủ để chỉ ra được bí mật mặc dù chúng đã thu hẹp được phạm vi của bí mật là 1 điểm nằm trên giao tuyến của 2 mặt phẳng đã biết. Sơ đồ của Blakley có hiệu quả không gian ít hơn sơ đồ của Shamir dưới đây; trong khi với sơ đồ của Shamir, mỗi một phần chia chỉ lớn bằng bí mật ban đầu. Các phần chia của Blakley lớn hơn t lần, với t là số người tham gia vừa đủ thu được bí mật. Sơ đồ của Blakley có thể được thu gọn bằng cách giới hạn mặt nào có thể sử dụng làm phần chia. Kết quả thu được sẽ là một sơ đồ tương đương với sơ đồ của Shamir. 3.2.3.2 Sơ đồ chia sẻ bí mật Shamir Ý tưởng về sơ đồ ngưỡng giới hạn của Shamir dựa trên tính chất: Hai điểm có thể định nghĩa một đường thẳng, 3 điểm định nghĩa được 1 parabol, 4 điểm định nghĩa được một hình lập phương, cứ như thế một cách tổng quát cần n+1 điểm để định nghĩa một đa thức bậc n. Giả sử chúng ta muốn sử dụng sơ đồ ngưỡng (k,n) để chia sẻ bí mật S với k < n. Sự lựa chọn giá trị của k và n quyết định sức mạnh của hệ thống. Chọn ngẫu nhiên (k-1) hệ số a1,…, ak-1 và đặt a0 = S. Xây dựng đa thức f(x)=a0 + a1x + a2x2 +…+ak-1xk-1 Chúng ta sẽ vẽ n điểm bất kỳ ví dụ tập i = 1,2,..,n tính được (i, f(i)). Mỗi người sẽ nhận được một cặp tọa độ thỏa mãn điều kiện là đầu vào và đầu ra của đa thức trên. Đưa bất kỳ một tập k các cặp tọa độ trên, chúng ta có thể dễ dàng các hệ số của đa thức bằng phép nội suy và tính được a0 là bí mật. Ví dụ: Bước 1: Chia sẻ bí mật Giả sử bí mật của chúng ta là một mã số ATM :1234 (S = 1234) Chúng ta muốn chia bí mật thành 6 phần (n=6), với bất kỳ 3 phần trong đó (k=3) có đủ khả năng suy ngược lại bí mật. Một cách ngẫu nhiên chúng ta thu được 2 số 166,94 (a1=166;a2=94) Đa thức của chúng ta do đó sẽ là f(x)=1234 + 166x + 94x2 Chúng ta lấy 6 điểm thỏa mãn là nghiệm của đa thức đó (1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5614) Chúng ta đưa cho mỗi người tham gia trong sơ đồ một điểm khác nhau (cả x và f(x)) Bước 2: Khôi phục bí mật Chúng ta hãy coi (x0,y0)=(2,1942); (x1,y1)=(4,3402); (x2,y2)=(5,4414) Chúng ta sẽ tính toán hệ số Lagrange Do đó : Bí mật của chúng ta chính là hệ số tự do của đa thức. Nghĩa là S=1234 3.3.Sơ đồ chia sẻ bí mật dựa trên không gian vector Brickell 3.3.1.Sơ đồ chia sẻ bí mật cơ bản Điều bí mật là 1 phần tử trong trong trường giới hạn GF(q). Người phân phối chọn một vectơ a = (a0,…, at) với t bất kỳ, mà aj ÎGF(q) và a0 là bí mật. Đánh dấu những người tham gia bằng Pi với 1 ≤ i ≤ n. Với mỗi Pi, người phân phối sẽ lấy 1 vectơ đơn vị vi trên GF(q). Tất cả các vectơ vi , 1 ≤ i ≤ n sẽ được công khai. Phần chia mà nguời phân phối đưa cho Pi sẽ là si = vi .a Ký hiệu ei là vectơ đơn vị t chiều thứ i (ví du e1=(1,0,…,0)) Định lý 1: Đặt γ = (Pi1,…,Pik) là tập những người tham gia (1)Những người tham gia trong γ có thể chỉ ra được bí mật nếu tập ‹ vi1,…,vik › chứa e1 (2)Những người tham gia trong γ không nhận được một ít thông tin nào về bí mật nếu tập ‹ vi1,…,vik › không chứa e1 Chứng minh: Đặt M là ma trận với các hàng vi1,…,vik. Đặt s = (si1,…,sik). Để chứng minh (1), đặt w là vectơ sao cho wM = e1. Khi đó wMa = a0 . Do đó w.s = a0. Để chứng minh (2), đặt w0 ,…, wt là cột của vectơ M. Nếu w0 khi đó tồn tại d sao cho d.wi = 0 với 1≤ i ≤ t và d.w0 = 1. Do đó dM = e1 nhưng điều này trái với giả thiết e (vi1,…, vik). Do đó w0 Î (w1,…, wt). Vì vậy tồn tại b sao cho Mb = 0 và b0 ≠ 0. Thông tin duy nhất mà những người tham gia trong γ biết về a0 là Ma = s . Nhưng s = Ma = M(a + αb) với tất cả α Î GF(q). Bởi vậy cho trước bất kỳ c0 Î GF(q), tồn tại c = (c0,…,ct) với ci Î GF(q), 1 ≤ i ≤ t sao cho Mc = s. Do đó những người tham gia trong γ không thể loại bỏ bất kỳ phần tử nào trong GF(q) có khả năng là a0 3.3.2.Sơ đồ chia sẻ bí mật đa cấp Trong phần này chúng ta sẽ đưa ra một chứng mính có sẵn là bất kỳ cấu trúc truy cập đa mức (multilevel access structure) nào cũng có thể tìm được trong một sơ đồ chia sẻ bí mật hoàn hảo. Sau đó chúng ta sẽ đưa ra 1 cấu trúc khác yêu cầu khối lượng tính toán ít hơn cho công việc của người phân phối. Sơ đồ đa cấp cơ bản: Đặt Γ là một cấu trúc truy cập đa mức với các mức l1< l2 <…< lR. Đặt Nr là số người tham gia ở mức lr. Đánh dấu những người tham gia bằng Pi với 1 ≤ i ≤ n và đặt Li là cấp của Pi. Chúng ta sẽ sử dụng sơ đồ chia sẻ bí mật cơ bản. Vì thế chúng ta chỉ cần chỉ ra Dealer sẽ chọn các vectơ vi như thế nào. Với mỗi Pi, Dealer sẽ lấy một xi Î GF(q). Đặt vi là vectơ lR hướng (1, xi, xi2,…, x, 0,…, 0). Chú ý rằng nếu l1 = 1 và Pi là một người tham gia có Li = 1, khi đó vi = e1. Định nghĩa một hàm đa thức fj(x)= . Phần chia si mà Dealer đưa cho Pi sẽ thỏa mãn si = fL(xi). Để hoàn chứng minh tồn tại 1 sơ đồ chia sẻ bí mật cho bất kỳ cấu trúc truy cập đa cấp nào, chúng ta chỉ cần chỉ ra rằng với bất kỳ cấu trúc truy cập đa cấp nào cũng có 1 phương thức cho Dealer chon xi sao cho chứa e1 nếu {Pi1,…, Pik } Î Γ. Trong phần còn lại của đoạn này chúng ta sẽ đưa ra 3 phương thức khác nhau để Dealer chon xi. Định lý 1: Đặt Γ là một cấu trúc đa truy cập với các mức l1 < l2 <…< lR. Đặt Lr là số những người tham gia có cùng cấp lr. Gọi n là tổng số người tham gia. Nếu q >. Khi đó có một sơ đồ chia sẻ bí mật hoàn hảo với Γ trên GF(q). Chứng minh: Chúng ta sẽ sử dụng cấu trúc sơ đồ đa cấp cơ bản. Chúng ta chỉ cần chỉ ra Dealer sẽ chọn xi như thế nào. Đặt v0 = e1 (mặc dù không có người tham gia P0). Giả sử Dealer đã chọn xi với tất cả i sao cho 0 ≤ i ≤ h. Đặt Ω là tập các khoảng con được nối với nhau bởi vài tập con có kích thước Lh-1 của vectơ vi { vi | 0 ≤ i ≤ h }. | Ω | < (lR-1) Dealer khi đó sẽ chọn xh sao cho vector LR thành phần Vh = (1, xh, xh2,…, xhL, 0,…, 0) không nằm trong bất kỳ khoảng con nào trong Ω. Để thấy điều đó là có thể thực hiện được, đặt H Î Ω, w = (w0, w1,…, wLh-, 0,…, 0) là một vectơ pháp tuyến của H. Khi đó =0 có nhiều nhất Lh-1 nghiệm trên GF(q) Giả sử rằng k người tham gia Pi1,…,Pik của mức cao nhất k cố gắng tìm lại bí mật và giả sử không có tập con nào của tập này chứa l người tham gia của mức cao nhất l với bất kỳ l < k. Các vector vi1,…,vik là độc lập và được chứa trong một khoảng kích thước k tạo bởi bởi e1,….,ek. Do vậy e1Î (vi1,…,vik) và do đó theo định lý 1, những người tham gia có thể chỉ ra được điều bí mật. Bây giờ giả sử rằng 1 tập γ Γ của những người tham gia thử tìm lại bí mật Đặt γ = {Pi1,…,Pik}. Do các vectơ e1,vi1,…,vik là độc lập. Theo Định lý 1, những người tham gia này không thu được bất kỳ thông tin nào về a0. Sơ đồ của Blakley cũng có thể chỉnh sửa để bổ sung một cấu trúc truy cập đa mức. Dealer lại một lần nữa chọn g là trục tọa độ thứ nhất và một dãy các mặt phẳng Fi sao cho: F1 F2 ... FR , F1 g là không rỗng và G không là tập con của FR. Điều bí mật là P = F1g. Một người ở mức r sẽ được cho trước một điểm trên Fr-1. Các điểm phải được chọn sao cho bất kỳ r người tham gia nào của mức cao nhất r có thể chỉ ra điểm P và mặt phẳng F, được tạo ra bởi một nhóm của những người tham gia trong đó với bất kỳ r không có một tập con nào của r người tham gia mà tất cả có mức cao nhất r, F G phải là rỗng. Công thức này cũng được Simmons tìm ra [6]. Một vấn đề đáng quan tâm khác là khối lượng tính toán cần thiết để cho Dealer xây dựng lên hệ thống.Với hệ thống ban đầu của Blakley thì Dealer phải làm phép kiểm tra để chắc chắn rằng các điểm là nằm trong vùng chung, phương pháp rõ ràng để làm việc này yêu cầu lần nhưng nếu các điểm đã được chọn cẩn thận thì không phép kiểm tra nào là cần thiết. Cũng vậy không phép kiểm tra nào là cần thiết cho sơ đồ của Shamir. Thật không may là thuộc tính này lại không nằm trong cấu trúc với sơ đồ đa mức trên. Cách thông thường để thực thi sơ đồ trình bày trong Định lý 1 sẽ yêu cầu rất nhiều phép kiểm tra để chắc chắn rằng các điểm nằm trong vị trí chung. Tuy nhiên chúng ta cũng đã tìm ra một cách xây dựng không yêu cầu kiểm tra. Mô hình đầu tiên mà chúng ta đề cập đến chỉ khả thi nếu không có quá nhiều mức trong đó. Chúng ta sẽ sử dụng sơ đồ đa mức cơ bản và vì thế chúng ta sẽ dễ dàng miêu tả cách mà Dealer chon xi. Để minh họa, giả sử rằng chúng ta muốn cho phép mức 2 hoặc 3. Chọn q = p2. Đặt α là một đại số bậc 2 (algebraic of degree 2) trên GF(p) (Ví dụ α thỏa mãn một đa thức bậc 2 tối giản trên GF(p) ). Dealer lấy 1 phần tử yi trong GF(p) với mỗi người tham gia Pi sao cho nếu i ≠ j và Li = Lj , khi đó yi ≠ yj Với một người tham gia ở mức 3, Dealer sẽ đặt xi = yi. Với một người tham gia ở mức 2, anh ta sử dụng xi = αyi. Hệ thống này sẽ có các thuộc tính mong muốn. Để thấy rằng 3 người tham gia Pi, Pi, Pi với Li = 2, Li= Li = 3 có thể chỉ ra bí mật. Coi như ma trận M tạo thành bởi vi1, vi2, vi3. Định thức của ma trận này là một đa thức với α có bậc cao nhất là l. Có thể chỉ ra rằng giới hạn trong đa thức này là khác 0. Do α là một số đại số bậc 2, giá trị của đa thức đó phải khác 0. Trong công thức chung hơn, với các mức l1<….< lR , Dealer lấy α1,…, αR-1 mà αR thỏa mãn một đa thức không thể rút gọn bậc trên Dealer sau đó đặt xi = αLiyi. Chứng minh hệ thống này có các thuộc tính mong muốn, là một mở rộng cho lý luận bên trên. Chúng ta sẽ không đưa nó vào đây bởi vì định lý dưới đây xây dựng các sơ đồ đa mức hiệu quả hơn. Định lý 2: Đặt Γ là cấu trúc truy cập đa mức với các mức 1= l0 Nr + 1 với 1 ≤ r ≤ R.Đặt β = RLR2. Khi đó có một sơ đồ chia sẻ bí mật hoàn hảo cho Γ trên GF( qβ) có thể xây dựng được trong thời gian đa thức (N1,…, NR, q). Chứng minh: Một lần nữa, chúng ta chỉ cần chỉ ra Dealer sẽ lấy xi như thế nào để sử dụng trong sơ đồ đa mức cơ bản. Nếu không có người tham gia nào ở mức 1 thì thêm 1 người tham gia P0 với L0 =1. Dealer chọn một yi cho mỗi Pi sao cho yi ≠ yj nếu Li = Lj và i ≠ j. Định nghĩa ρ(i) là một số nguyên j sao cho Li = lj. Dealer cũng lấy α thỏa mãn bậc không rút gọn được RlR2 trên GF(p). Đặt xi = yi αR-ρ(i) . Đặt γ = {Pi1,…, Pik} là một tập của k người tham gia, mỗi người trong đó có mức cao nhất là k và giả sử là không có tập con nào của γ mà chứa nhiều hơn l người tham gia có mức cao nhất là l với mọi l < k. Gọi nj là số người tham gia đó có cấp cao nhất lj. Đặt M’(γ) là ma trận trong đó có các hàng là các vectơ vi1,…, vik Đặt M(γ) là ma trận bao gồm mỗi k cột đầu tiên của M’(γ). M(γ) về cơ bản là giống ma trận M’(γ) khi các cột bị rời đi có giá tri là 0. Để chỉ ra M = M(γ) không phải là số ít, chúng ta sẽ chỉ ra rằng đinh thức của M có thể được viết dưới dạng đa thức theo α với bậc nhỏ hơn Rl2R. Chúng ta sẽ chỉ ra rằng đa thức này không bằng 0 bằng cách chỉ ra rằng giới hạn số của nó là khác không. Xem như định thức của m là một đa thức theo α. Đặt M = (mi,j). Nhớ lại là định thức là tổng các phép nhân sơ cấp của M mà mỗi phép nhân sơ cấp là phép nhân của các số hạng m1,c1 ,…,mk,ck với dấu thích hợp mà c1,…,ck là một phép hoán vị của 1,…, k. Mọi phép nhân khác 0 cơ bản sẽ thỏa mãn ci ≤ Li với 1≤ i ≤ k Số mũ lớn nhất của α trong hàng i của M là (R-ρ(i))(Li-1). Do đó số mũ lớn nhất của α trong phép nhân sơ cấp Đặt T-1 =0 và đặt Tj =ni với 0 ≤ j ≤ R. Số mũ của α trong kết quả của một phép nhân khác 0 sẽ là . Phép tính tổng này thu được kết quả nhỏ nhất khi {CTr-1+1,…, CTr} = {Tr-1+1,…, Tr} với 0 ≤ r ≤ R Đặt Dr là ma trận con nr x nr của M được tạo bởi các hàng và các cột Tr-1+1,…, Tr Đặt z là số mũ nhỏ nhất của α trong định thức của M. Khi đó số hạng θα2 với θGF(q) trong định thức cuả M thỏa mãn θα2 =|Dr| Khi đó mỗi Dr là một phép nhân của ma trận Van der Monde, |Dr| ≠0. Do vậy hệ số của αz là khác không. Như vậy, bởi vì M(γ) không phải là số ít, những người tham gia trong γ có thể chỉ ra a0. Giả sử bây giờ γ là 1 tập của k-1 người tham gia mỗi người có mức tối đa là k và không có tập con γ’ chứa nhiều hơn l người tham gia của mức tối đa l với bất kỳ l<k. Đặt γ’=γ U {P0}. Bây giờ γ’ là tập hợp của k người tham gia với mức tối đa là k và không có tập con cua γ’ mà chứa nhiều hơn l người tham gia có mức tối đa là l với mọi l<k. Ma trận M(γ’) sẽ vì thế mà không phải là số ít. Do vậy e1 (vi|Pi Î γ) Từ định lý 1, những người tham gia trong γ không nhận được thông tin về giá trị của a0 3.3.4.Sơ đồ riêng phần (compartmented schemes) Trong một sơ đồ Riêng phần, có các tập tách rời của những người tham gia C1,…,Cu. Cấu trúc truy cập bao gồm các tập con của những người tham gia chứa ít nhất ti trong Ci với i=1,…,u và tổng số ít nhất t người tham gia. Đặt n là tổng số những người tham gia. Định lý 3: Đặt Γ là cấu trúc truy cập riêng phần (compartmented access structure). Nếu q>, khi đó có một sơ đồ chia sẻ bí mật với Γ trên GF(q) Chứng minh : chúng ta có thể thừa nhận rằng T = t- ≥ 0. Dealer chọn 1 vectơ a = (a0,…,at-1) với a0 là bí mật. Đặt T0 = T, đặt Ti = T+ với 1≤ i ≤ u. Đánh dấu những người tham gia bằng Pr,i với Pr,i nằm trong phần Cr. Với người tham gia Pi Dealer sẽ lấy 1 vector t thành phần trên GF(q) theo dạng : Với vài vr,i GF(q). Như trong Định lý 1, Dealer sẽ phải cẩn thận để chọn ra xr,i Đặt đánh dấu theo thứ tự từ điển sắp xếp các cặp. Ví dụ : (r,i) (s,j) nếu r < s hoăc (r = s và i<j).Đặt v0,0 = e1. Giả sử rằng Dealer đã chọn xr,i với tất cả (r,i) (s,j). Khi đó Dealer phải chọn xs,j ≠1 do vậy vectơ v = s,j không nằm trong bất kỳ khoảng con nào được span bởi một tập hợp của các vectơ bao gồm ít nhất tr của vr,i với mỗi r < s và ít nhất t*s = min(ts-1,j-1) của vs,i với i < j và tổng của tối đa T + t*s + với (0,0) (r,i) (s,j) Do q > , có thể thấy rằng điều đó là có khả năng bằng cách sử dụng lý luận tương tự với chúng như trong Định lý 1 Một tập của những người tham gia trong Γ có thể chỉ ra bí mật vì vectơ vr,i là độc lập. Ngược lại giả sử một tập γ = Pr,i ,|(r,i) Є I} của những người tham gia không có trong Γ Giả sử có Cs sao cho γ không chứa ít nhất ts những người tham gia trong Cs. Đặt M là ma trận với các hàng vr,i với (r,i) I. Đặt M’ là ma trận bao gồm các cột 1,Ts +1,…,Ts + ts của M. Có mỗi ts hàng phân biệt trong M’, chúng tương ứng với các vectơ vr,i với r = s và (r,i) I, và vectơ (1,1,…,1). Đặt {i1,…, its-1} = {i|(s,i) I}. Đặt M’’ là ma trận bao gồm các hàng e1, vs,i1,….,vs,i. Khi đó |M’’| = |M’’11| với M’’11 là ma trận M’’ với hàng thứ nhất và cột đã bị loại bỏ. Nhưng M’’ lại là một ma trận Van de Monde với hàng ij nhân với xTs,ij với 1≤ j ≤ ts-1. Vì vậy |M’’11| ≠0. Do vậy e1 không nằm trong (vr,i| (r,i) I ). Nếu γ chứa ít nhất tr người tham gia từ Cr với 1 ≤ r ≤ u, nhưng không chứa tổng của ít nhất t người tham gia, khi đó những người tham gia trong γ không nhận được thông tin về a0 vì vậy e1 và vectơ vr,i với (r,i) I là độc lập Cách xây dựng giới thiệu trong Định lý 3 yêu cầu Dealer kiểm tra theo hàm mũ rất nhiều khoảng con. Thật dễ dàng đưa ra một sự thực thi có hiệu quả trong trường hợp mà t= Dealer có thể chọn a0 làm bí mật một cách đơn giản và ngẫu nhiên lấy b1,…,bu sao cho a0 =. Khi đó anh ta sẽ sử dụng một sơ đồ giới hạn với 1 giới han ti và bí mật bi để phân phối các phần đến những người tham gia trong Ci. Tuy nhiên chúng ta đã không tìm ra một cấu trúc tổng quát đầy đủ cho cấu trúc truy cập riêng phần 3.4.Vấn đề chống gian lận trong sơ đồ chia sẻ bí mật 3.4.1.Mô hình PVSS không tương tác Như ta đã biết, mọi sơ đồ chia sẻ bí mật đêu tồn tại ít nhất 2 giao thức. Đó là: (1). Giao thức Phân phối: Bí mật được Dealer phân phối tới tập những người tham gia (2). Giao thức khôi phục dữ liệu: Trong đó bí mật được khôi phục lại bằng cách gộp thông tin của những người tham gia nằm trong một tập hợp được chỉ định trước. Các sơ đồ cơ bản (Blakley và Shamir) giải quyết những vấn đề đó trong trường hợp tất cả những người tham gia trong sơ đồ là trung thực.Trong trường hợp một hoặc nhiều người trong sơ đồ không trung thực thì sơ đồ không còn tác dụng nữa.Để giải quyết vấn đề này chúng ta sử dụng VSS Sơ đồ chia sẻ bí mật có xác minh (VSS),sẽ kiểm tra các gian lận bao gồm: 1) Dealer gửi thông tin sai đến cho 1 hoặc nhiều người trong sơ đồ và 2) Người tham gia cung cấp sai thông tin trong thủ tục khôi phục bí mật Chúng ta sẽ tìm hiểu sơ đồ chia sẻ bí mật có khả năng xác minh được 3.4.1.1.Sơ đồ chia xẻ bí mật xác minh công khai, không giao tiếp (PVSS) Chúng ta chú ý rằng một nét đặc trưng khác của PVSS là không có các kênh truyền riêng và bí mật giữa Dealer và những người tham gia. Tất cả các quá trình truyền tin đều qua các kênh công cộng (đã được ủy thác) sử dụng mã hóa khóa công khai. Do vậy bí mật sẽ chỉ được tính toán ẩn(hiden). Trong một sơ đồ PVSS, một Dealer D muốn phân phối các phần chia của bí mật S ∑ tới n người tham gia P1,…,Pn. Một cấu trúc truy cập monotone (monotone access structure) miêu tả những tập con nào của những người tham gia được chỉ định khôi phục lại bí mật. Ví dụ một cấu trúc truy cập có thể là một sơ đồ (t,n) nghĩa là bất kỳ tập con nào với t hoặc nhiều hơn số người tham gia sẽ có đủ khả năng khôi phục bí mật ; bất kỳ tập con nào ít hơn t người tham gia sẽ không thu được thông tin gì về bí mật (trừ trường hợp năng lực tính toán của máy tính cực lớn) Các thủ tục trong PVSS: Chú ý trong quá trình khởi tạo, không có sự giao tiếp giữa Dealer và người tham gia. Người tham gia có thể rời bỏ hoặc một người khác có thể tham gia vào sơ đồ một cách tự động.Yêu cầu duy nhất là mỗi người tham gia giữ một khóa công khai đã được đăng ký. Quá trình khởi tạo: Mọi tham số của hệ thống được sinh ra như một phần của quá trình khởi tạo. Ngoài ra mỗi người tham gia Pi sẽ đăng ký một khóa công khai được dùng trong thủ tục mã hõa Ei. Toàn bộ tập hợp những người đang tham gia vào PVSS phải là một tập con của những người tham gia đã đăng ký. Không làm mất tính tổng quát, giả sử những người tham gia P1,…,Pi tham gia toàn bộ vào PVSS dưới đây. Giao thức phân phối bí mật : Giao thức này có 2 bước: Phân phối các phần bí mật: Việc phân phối bí mật S ∑ được thực hiện bởi Dealer Dealer sẽ tạo các phần chia riêng si cho mỗi người tham gia Pi với 1≤ i ≤ n. Với mỗi người tham gia Pi, Dealer sẽ công bố phần chia đã được mã hóa Ei(si).Dealer đồng thời cũng công bố một chuỗi PROOFD để chỉ ra rằng mỗi Ei mã hóa một phần chia si Ngoài ra chuỗi PROOFD đưa Dealer đến giá trị của si , và nó cũng đảm bảo thủ tục khôi phục bí mật sẽ trả về kết quả s tương tự. Xác minh các phần chia: Bất kỳ bên nào biết được các khóa công khai của phương thức mã hóa Ei có thể xác minh các phần chia.Với mỗi người tham gia Pi,một thuật toán xác minh không cần giao tiếp có thể được chay trên PROOFD để xác minh rằng Ei(si) là một mã hóa đúng của phần chia của người Pi. Do vậy mỗi người có thể xác minh một phần chia, nó có thể được dùng để loại bỏ tình huống một người tham gia phàn nàn trong khi đã nhận một phần chia đúng.Trong trường hợp một hoặc nhiều sự xác minh có lỗi, chúng ta khi đó sẽ nói rằng Dealer lỗi và thủ tục này bị bỏ dở (Nếu nằm trong mức sai sót có thể chấp nhận được thì có thể tiếp tục chạy sơ đồ đó