Bài giảng Các chứng minh không tiết lộ thông tin - Nguyễn Hoàng Cương

Nội dung text: Bài giảng Các chứng minh không tiết lộ thông tin - Nguyễn Hoàng Cương

1. Vietebooks Nguyễn Hoàng Cương Ch−ơng 13 Các chứng minh không tiết lộ thông tin 13.1.các hệ thống chứng minh t−ơng hỗ Một cách đơn giản, một hệ thống chứng minh không tiết lộ thông tin sẽ cho phép một đối t−ợng thuyết phục đ−ợc một đối t−ợng khác tin một điều nào đó mà không để lộ một tý thông tin nào về phép chứng minh. Tr−ớc tiên ta sẽ thảo luận ý t−ởng về một hệ thống chứng minh t−ơng hỗ. Trong một hệ thống chứng minh t−ơng hỗ có hai thành viên: teggy và Vic. Teggy là ng−ời chứng minh và Vic là ng−ời kiểm tra. Teggy biết một điều gì đó và cô ta muốn chứng minh cho Vic rằng cô ta biết điều đó. Điều cần thiết là phải mô tả đ−ợc các kiểu tính toán mà Peggy và Vic đ−ợc phép thực hiện và các tác động qua lại xảy ra. Ta có thể coi các thuật toán mà Peggy và Vic thực hiện là các thuật toán xác suất. Peggy và Vic sẽ thực hiện các tính toán riêng và mỗi ng−ời đều có một bộ tạo số ngẫu nhiên riêng. Họ sẽ liên lạc với nhau qua một kênh truyền tin. Thoạt đầu cả Peggy và Vic đều có một giá trị x. mục đích của phép chứng minh t−ơng hỗ là Peggy phảI thuyết Vic rằng x có một tính chất xác đình nào đó. Chính xác hơn x là câu trả lời có của một bái toán quyết định xác định ∏. Phép chứng minh t−ơng hỗ (là một giao thức hỏi-đáp) gồm một số vòng xác định. Trong mỗi vòng .Peggy và Vic luân phiên thực hiện các công việc sau: 1. Nhận một thông báo từ nhóm khác . 2.Thực hiện một tính toán riêng. 3. Gửi một thông báo toi− nhóm khác Một vòng đIển hình của giao thức sẽ gồm một yêu cầu của Vic và một đáp ứng của Peggy. Tới cuối phép chứng minh ,Vic hoặc sẽ chấp nhận hoặc từ chối tuỳ thuộc vào việc liệu Peggy có đáp ứng thành công các yêu câù của Vic hay không. Ta định nghĩa giao thức là một hệ thông chứng minh t−ơng hỗ đối với vái toán quyết định ∏ nếu hai tính chất sau đ−ợc thoả mãn mỗi khi Vic tuân theo giao thức đó: Tính đầy đủ Trang 1
2. Vietebooks Nguyễn Hoàng Cương Nếu x là câu trả lời có của hai bái toán quyết định ∏ thì Vic sẽ luôn luôn chấp nhận chứng minh của Peggy. Tính đúng đắn Nếu x là câu trả lời không của ∏ thì xác suất để Vic chấp nhận phép chứng minh là rất nhỏ. Ta hạn chết chỉ xét các hệ thống chứng minh t−ơng hỗ mà các tính toán do Vic thức hiện nằm trong thoì gian đa thức song không hàn chế thời gian tính toán mà prggy thực hiên.(Peggy đ−ợc coi là “toàn năng”). Ta sẽ bắt đầu bằng việc trình bày một hệ thống chứng minh t−ơng hỗ cho bái toán đồ thị không dẳng cấu. Bái toán đẳng cẩu đồ thị đ−ợc mô tả trên hình 13.1. Đây là một bái toán thú vị mà cho tới nay ng−ời ta ch−a biết thuật giải nào có thời gian đa thức tuy rằng không đ−ợc coi là bái toán NP đầy đủ. Hình 13.1 . tính đẳng cấu đồ thị Đặc tr−ng của bái toán : 2 đồ thị n đỉnh G =(V ,E ) và G =(V ,E ) 1 1 1 2 2 2 Câu hỏi: liệu có một song ánh π: V1ặV2 sao cho {u,v}∈E1 khi và chỉ khi {π(u), π(v)} ∈ E2 không ?. (nói cách khác liệu G1 và G2 có đẳng cấu không ?) Sau đây sẽ trình bày một hệ thống chứng minh t−ơng hỗ cho phép Peggy chứng tỏ với Vic rằng 2 đồ thị chỉ ra là không đẳng cấu. Để đơn giản, giả sử rằng mỗi đồ thị G1 và G2 có tập đỉnh {1 n}. Hệ thông chứng minh t−ơng hỗ đối với tính không đẳng cấu đồ thị đ−ợc mô tả trên hình 13.2. Trang 2
3. Vietebooks Nguyễn Hoàng Cương Hình 13.2. Một hệ thống chứng minh t−ơng hỗ đối với tính không đẳng cấu đồ thị Đầu vào :mỗi đồ thị G1 và G2 có tập đỉnh {1, ,n} 1. Hãy lặp lại các b−ớc sau n lần: 2. Vic chọn một số ngẫu nhiên I=1 hoặc 2 và một phép hoán vị ngẫu nhiên π của {1, ,m}.Vic sẽ tính H là ảnh của G theo hoán vị π và gửi H cho Peggy. 3. Peggy xác định giá trị j sao cho G là đẳng cấu với H và gửi j j cho Vic 4. Vic sẽ kiểm tra xem liệu i=j không . 5. Vic chấp nhận chứng minh của Peggy nếu I=j trong mỗi vòng. Hình 13.3 các đồ thị không đẳng cấu của Peggy và yêu cầu của Vic ????????????????????? Ví dụ nhỏ sau đây sẽ minh hoạ cho hoạt động của thuật toán Ví dụ 13.1 Trang 3
4. Vietebooks Nguyễn Hoàng Cương Giả sử G1 = (V, E1)và G2=(V, E2) trong đó V = (1, 2, 3, 4), E1 = {12, 14, 23, 34}, E2 ={112,13,14,34}. Gỉa sử ở một vòng nào đó của giao thức,Vic trao cho Peggy đồ thị H=(V, E3) trong đó E3={13, 14, 23, 24}(xem hình 13.3). Đồ thị H là đẳng cấu với G1. (Một phép đẳng cấu từ H vào G1 là phéo hoán vị (1 3 4 2)). Bởi vậy Peggy sẽ trả lời “1” Dễ dàng nhận thấy rằng, hệ thống chứng minh này thoả mãn tính đầy đủ và tính đúng đắn. Nếu G1 không đẳng cấu với G2 thì j sẽ bằng i ở mỗi vòng và Vic sẽ chấp nhận với xác suất 1. Bởi vậy giao thức là đầy đủ. Mặt khác, giả sử rằng G1 đẳng cấu với G2. Khi đó một đồ thị yêu cầu bất kỳ H đ−ợc Vic đ−a ra đẳng cấu với cả G1 và G2. Peggy sẽ không có cách nào để xác định xem H là phiên bản đẳng cấu nào của G1 hay G2 nên Peggy không còn cách nào khác hơn là phải trả lời bằng cách giả định j=1 hoặc 2. Cách duy nhất để Vic chấp nhận là xem Peggy có khả năng phán đoán tất cả n phép chọn i do Vic thực hiện hay không. Xác suất Peggy thực hiện điều này là 2n. Bởi vậygiao thức là đúng đắn. Chú ý rằng các tính toán của Vic đều trong thời gian đa thức. Ta không thể nói tý gì về thời gian tính toán củ Peggy vì bái toán đồ thị đẳng cấu ch−a có một thuật giải nào theo thờigian đa thức. Tuy nhiên hãy nhớ lại rằng ta đã cho Peggy có năng lực tính toán không hạn chế và bởi vậy đều này đ−ợc chấp nhận theo “các quy tắc của trò chơi”. 13.2. Các chứng minh không tiết lộ thông tin hoμn thiện. Mặc dù các hệ thống chứng minh t−ơng hỗ khã hay ho nh−ng kiểu chứng minh thú vị nhất lại là kiêu chứng minh không để lộ thông tin. Vấn đề là Peggy phảI thuyết phục Vic rằng x có một tính chất xác định nào đó, nh−ng vào lúc kết thúc giao thức Vic vẫn không có chút ý niệm nào về cách chứng minh (cho chính anh ta ) rằng có tính chất đó. Đây là một khái niệm rất khó định nghĩa hình thức ,bởi vậy ta sẽ đ−a ra tr−ớc khi định nghĩa nó. Trên hình 13.4 mô tả một phép chứng minh t−ơng hỗ không tiết lộ thông tin đối với tính đẳng cấu của đồ thị. Ví dụ nhỏ sau sẽ minh hoạ cho hoạt động của thuật toán. Trang 4
5. Vietebooks Nguyễn Hoàng Cương Đầu vào :hai đồ thị G1 và G2 mỗi đồ thị có tập đỉnh {1 n} 1. Lặp lại các b−ớc sau n lần 2. Peggy chọn một phứp hoán vị ngẫy nhiên π vủa {1 n} cô ta tính H là ảnh của G1 theo π và gửi H cho Vic 3. Vic chọn một số nguyên ngẫu nhiên I=1 hoặc 2 và gửi nó cho Peggy 4. Peggy tính một phép hoán vị của {1 n} sao cho H là ảnh của G1 theo p. Peggy sẽ gửu p cho Vic (nếu i= 1 thì Peggy sẽ xác định p=π nếu I=2 thì Peggy sẽ xác định p là hợp của δ và π trong δ là một phép hoán vị cố định nào đó sao cho ảnh của G theo δ là G ) 2 1 5. vic sẽ kiểm tra xem H có phải là ảnh của G theo p hay 1 không 6. vic sẽ chấp nhận chứng minh của Peggy nếu H là ảnh của G 1 ở mỗi một trong n vòng. Ví dụ 13.2: Giả sử G1 = (V, E1) và G2 = (V, E2), trong đó V = {1, 2, 3, 4}, E1 = {12, 13, 14, 34} và E2={12, 13, 23, 24}. Một phép đẳng cấu từ G2 sang G1 là hoán vị δ=(4 1 2 3). Bây giờ giả sử ở trong vòng nào đó của giao thức Peggy chọn hoán vị π = (2 4 1 3). Khi đó H có tập cạnh {12, 13, 23, 24} (xem hình 13.5) Nếu yêu cầu của Vic là i=1 thì Peggy sẽ cho Vic phép hoán vị π và Vic sẽ kiểm tra xem ảnh của G1 theo π có phải là H không. Nếu yêu cầu của Vic là i=2 thì thì Peggy sẽ cho Vic phép hợp p=π0 δ =(3 2 1 4) và Vic sẽ kiểm tra xem ảnh của G2 theo p có phải là H không. Dễ dàng diểm tra đ−ợc tính đầy đủ và tính đúng đắn của giao thức. Không khó khăn thấy rằng xác suất để Vic chấp nhận sẽ bằng 1 nếu G1 đẳng cấu với G2. Mặt khác nếu G1 không đẳng cấu với G2 thì chỉ có một cách để Peggy lừa dối đ−ợc Vic là có ta phải giả định đúng giá trị i mà Vic sẽ chọn ở Trang 5
6. Vietebooks Nguyễn Hoàng Cương mỗi vòng và ghi một bản sao đẳng cấu (ngẫu nhiên ) của G1 lên băng liên lạc. Xác suất để Peggy giả định đúng các yêu cầu của Vic là 2n. ?????????????????????????????? Tất cả các tính toán của Vic có thể thực hiện đ−ợc trong thời gian đa thức (nh− một hàm của n là số các đỉnh trong G1 và G2). Mặc dù không cần thiết lắm nh−ng ta cũng thấy rằng các tính toán của Peggy cũng có thể đ−ợc thực hiện trong thời gian đa thức miễn là cô ta biết đ−ợc sự tồn tạI của phép hoán vị δ là G1. Tại sao ta lại coi hệ thống chứng minh là hệ thông chứng minh không tiết lộ thông tin. Lý do là ở chỗ mặc dù Vic đã bị thuyết phục rằng G1 là đẳng cấu với G2 nh−ng anh ta vẫn không thu thêm đ−ợc tý kiến thức nào để giúp tìm đ−ợc phép hoán vị δ đ−a G2 về G1. Tất cả những đIều mà Vic thấy trong mỗi vòng của phép chứng minh là một bản sao ngẫu nhiên của các độ thị này mà không cần tới sự giúp đỡ của Peggy. Vì các đồ thị H đ−ợc chọn một cách độc lập và ngẫy nhiên ở mỗi phần của phép chứng minh nên đIều này không giúp đỡ đ−ợc gì vho Vic trong việc tìm một phép dẳng cấu từ G1 sang G2. Ta hãy xem xét kĩ l−ỡng thông tin mà Vic thu đ−ợc nhờ tham gia vào hệ thông chứng minh t−ơng hỗ. Có thể biểu thị cách nhình của Vic về phép chứng minh t−ơng bằng một “ bản sao ” chứa các thông tin sau: ___ 1.Các đồ thị G1 và G2 2. Tất cả các thông báo đ−ợc Peggy và Vic gửi đi. 3. Các số ngẫu nhiên mà Vic dùng để tào các yêu cầu của mình. Bởi vậy một bản sao T đối với phép chứng minh t−ơng hỗ về phép đẳng cấu đồ thị sẽ có dạng sau: T = ((G1, G2):(H1, i1, p1): . . . (Hn, in, pn)) Điểm mấu chốt (tạo cơ sở cho định nghĩa hình thức về phép chứng minh không tiết lộ thông tin ) là Vic (hay vất kỳ ng−ời nào khác) có thể giả mạo Trang 6
7. Vietebooks Nguyễn Hoàng Cương các bản sao (mà không cần phải tham gia vào hệ chứng minh t−ơng hỗ) ”giống nh−” các bản sao thực tế. Điều này có thể thực hiện đ−ợc miễn là các đồ thị G1 và G2 là đẳng cấu. Việc giả mạo đ−ợc thực hiện theo thuật toán mô tả trên hình 13.6. thuật toán giả mạo là một thuật toán xác suất theo thời gian đã thức. Theo nhôn ngữ của phép chứng minh không tiết lộ thông tin một thuật toán giả mạo th−ờng đ−ợc gọi là một bộ mô phỏng. Sự kiện một bộ mô phỏng có thể giả mạo các bản sao có một hệ quả rất quan trọng. Bất kỳ kết quả nào mà Vic (hay bất kì ai khác ) có thể tính từ một bản sao cũng có thể tính đ−ợc từ một bản sao giả mạo. Bởi vậy ,việc tham gia vào hệ thông chứng minh sẽ không làm tăng khả năng tính toán của Vic; đặc biệt là điều này không cho phép Vic tự chứng minh đ−ợc rằng G1 và G2 là đẳng cấu. Hơn nữa, Vic cũng không thể thuyết phục đ−ợc ai khác rằng G1và G2 là đẳng cấu bằng cách chỉ cho họ bản soa T bởi vì không có cách nào để phân biệt một bản sao hợp lệ với một bản sao giả mạo. Ta sẽ chính xác hoá ý t−ởng về một bản sao giả mạo “giống nh−” một bản sao thực và đ−a ra một định nghĩa chặt chẽ theo thuật ngữ về các phân bố xác suất. Định nghĩa 13.1 Giả sử ta có một chứng minh t−ơng hỗ thời gian đa thức cho bái toán quyết định ∏ và một bộ mô phỏng thời gian đa thức S. Kí hiệu tập tất cả các bản sao có thể cho kết quả có x là F(x). Các bản sao giả mạo có thể đ−ợc tạo bởi S là F(x). với bản sao bất kỳ T∈τ (x) ,cho bản sao giả mạo có thể đ−ợc tạo bởi S là F(x). với bản sao bất kì T∈τ (x) cho pτ (T) là xác suất để T là một bản sao đ−ợc tạo từ phép chứng minh t−ơng hỗ. T−ơong tự, với T∈ F(x), cho pτ (T) là xác suất để T là một bản sao (giả mạo) đ−ợc tạo bởi S, Giả sử rằng τ (x) = F(x) và với bất kỳ T∈ τ (x) ta có pτ (T) = pF(T) (nói cách khác tập các bản sao thực đồng nhất với tập các bản sao giả mạo và hai phân bố xác suất là nh− nhau). Khi đó ta định nghĩa hệ thống chứng minh t−ơng hỗ là hệ thông chứng minh không tiết lộ thiing tin hoàn thiện đối với Vic. Hình 13.6 thuật toán giả mạo cho các bản sao đối với phép đẳng cấu đồ thị Trang 7
8. Vietebooks Nguyễn Hoàng Cương Đầu vào : hai đồ thị G1 và G2 mỗi đồ thị có tập đỉnh {1 n} 1. T=(G1, G2) 2. For j=1 to n do 3. Chọn ngẫu nhiên ij=1 hoặc 2; 4. Chọn pj là một hoán vị ngẫu nhiên của{1 n} 5. Tính Hj là ảnh của G1 theo pj 6. Ghép (Hj, ij, pj) vào cuối của T Dĩ nhiên là có thể định nghĩa đặc tính không tiết lộ thông tin theo kiểu mà ta thiéc. Tuy nhiên điều quan trọng là định nghĩa phải giữ nội dung cơ bản của đặc tính này. Ta đã coi rằng một hệ thống chứng minh t−ơng hỗ là hệ không tiết lộ thông tin cho Vic nếu tồn tại một hệ mô phỏng rạo ra các bản sao có phân bố xác suất đồng nhất với phân bố xác suất của các bản sao đ−ợc tạo ra khi Vic tham gia thực sự vào giao thức. (đây là một khái niêm t−ơng đối nh−ng mạnh hơn khái niệm về các phân mốt xác suất không có khả năng phân biệt nêu trong ch−ơng 12). Ta đã biết rằng một bản sao sẽ chứa tất cả các thông tin mà Vic thu l−ợm đ−ợc nhờ tham gia vào giao thức. Bởi vậy, quả là hợp lý khi ta xem rằng bất cứ việc gì mà Vic có thể thực hiện đ−ợc sau khi tham gia vào gia thức cũng chỉ nh− việc mà anh ta có thể thực hiện đ−ợc nếu sử dụng hệ mô phỏng để tào một bản sao giả mạo. Mặc dù ta không định nghĩa” thông tin“(hiểu biết )bằng cách tiếp cận này nh−ng bất cứ đIều gì đ−ợc coi là thông tin thì Vic không thu l−ợm đ−ợc tý nào! Bây giờ ta sẽ chứng tỏ rằng hệ thống chứng minh t−ơng hỗ đối với tính đẳng cấu đồ thị là một hệ thống chứng minh không tiết lộ thông tin đối với Vic. Định lý 13.1 Hệ thông chứng minh t−ơng hỗ đối với tính đẳng cấu đồ thị là một hệ thống chứng minh không tiết lộ thông tin hoàn thiện đối với Vic. Chứng minh: Trang 8
9. Vietebooks Nguyễn Hoàng Cương Giả sử G1 và G2 là các đồ thị đẳng cấu có n đỉnh. Một bản sao T (thực hoặc giả mạo) sẽ gồm n bộ dạng(H, i, ρ)trong đó i=1 hoặc 2, p là một phép hoán vị của {1, ,n} và H là ảnh của G1 theo hoán vị ρ. Ta goim một bộ ba nh− vậy là một bộ ba hợp lệ và ký hiệu nó là ????????????. Tr−ớc tiên ta sẽ tính |??????| là số các bộ ba hợp lệ. Hiển nhiên là |????| = 2ìn! vì mỗi phép chọn i và p sẽ xác định một đồ thị duy nhất H. ở mỗi vòng cho tr−ớc j bất kỳ của thuật toán giả mạo rõ ràng là mỗi bộ ba hợp lệ (H, i, ρ)là bộ ba thứ j ở bản sao thực là gì? Trong hệ thống chứng minh t−ơng hỗ, tr−ớc tiên Peggy dẽ chọn một phép hoán vị ngẫu nhiên π sau đó tính H là ảnh của G1 theo π. Phéhoán vị p đ−ợc xác định là π nếu i = 1và nó đựoc xác định là hợp của hai phép hoán vị π nếu i = 2. Giả sử giá trị vủa i đ−ợc chọn ngẫu nhiên bởi Vic. Nếu i = 1 thì tất cả n! phép hoán vị ρ là đồ các suất vì trong tr−ờng hợp này ρ = π và π đã đ−ợc chọn là một phép hoán vị ngẫu nhiên. Mặt khác, nếu i = 2 thì ρ = π0δ ,trong đó π là ngẫu nhiên và δ là cố định. Trong tr−ờng hợp này mỗi phép hoán vị có thể đều có xác suất bằng nhau. Xét thấy, vì cả hai tr−ờng hợp i = 1 và i = 2 đều vào xác suất bằng nhau và mỗi phép hoán vị ρ đồng xác suất (không phụ thuộc vào giá trị của i) và bởi vì i và p cùng xác định H nên suy ra mọi bộ ba trong R chắc chắn sẽ đồng xác suất. Vì một bản sao gồm n bộ ngẫu nhiên độc lập ghép với nhau nên đối với mỗi bản sao có thể có T ta có: 1 pτ (T)= pF(T)= (2* n!) n Trong chứng minh trên đã giả thiết Vic tuân thủ giao thức khi anh ta tham gia vào hệ thống chứng minh t−ơng hỗ. Tình hình sẽ phức tạp hơn nhiệu nếu Vic không tuân theo giao thức. Phải chăng một phép chứng minh t−ơng hỗ vẫn còn giữ đ−ợc đặc tính không để lộ thông tin ngay cả khi Vic đi chéch khỏi giao thức?. Trong tr−ờng hợp phép đẳng cấu đồ thị, cách duy nhất mà Vic có thể đi chệch khỏi giao thức chọn các yêu cầu i của mình theo cách không ngẫu nhiên. về mặt trực giác có vẻ nh− đIều này không cung cấp cho Vic một chút “hiểu biết” nào. Tuy nhiên các bản sao đ−ợc tạo bởi bộ mô phỏng sẽ không còn giống nh− các bản sao do Vic tạo ra nếu anh ta đi chệch khỏi giao thức. Ví dụ ,giả sử Vic chọn i = 1 trong mỗi vòng vủa phép chứng minh. Khi đó một bản sao của phép chứng minh t−ơng hỗ sẽ có ij = 1 với 1 ≤ j ≤ n, trong Trang 9
10. Vietebooks Nguyễn Hoàng Cương khi đó một bản sao đ−ợc tào bởi bộ mô phỏng sẽ có ij = 1 với 1 ≤ j ≤ n, chỉ với xác suất xuất hiện bằng2. Điều khó khăn ở đây là phải chứng tỏ rằng cho dù Vic “không trung thực” đi chệch khỏi giao thức nh−ng vẫn tồn tại trong bộ mô phỏng thời gian với thời gian đa thức tạo ra các bản sao giả mạo giống nh− các bản sao đ−ợc tạo bởi Peggy và Vic (không trung thực) trong phép chứng minh t−ơng hỗ. Cũng nh− ở trên, câu “giống nh−” đ−ợc hình thức hoá bằng cách nói rằng hai phân bố xacs suất này là đồng nhất. Sau đây là một định nghĩa hình thức hơn nữa. Định nghĩa13.2 Giả sử rằng ta có một hệ thống chứng minh t−ơng hỗ th−o thời gian đa thức cho một bái toán quyết định cho tr−ớc ∏. Cho V* là một thuật toán xác suất theo thời gian đa thức mà ng−ời kiểm tra (có thể không trung thực)sử dụng dể tào các yêu cầu của mình (tức là V* biểu thị cho một ng−ời kiểm tra trung thực hoặc không trung thực). Ký hiệu tập tất cả các bản sao có thể (đ−ợc tào ra do kết quả của phép chứng minh t−ơng hỗ mà Peggy và V* thực hiện với câu trả lời có x của ∏) là ?????(V*,x). giả sử rằng với mỗi V* nh− vậy tồn tại một thuật toán xác suất theo thời gian đa thức S*=S*(V*) (bộ mô phỏng) tạo ra một bản sao giả mạo. ký hiệu tập các bản sao giả mạo có thể bằng ???(V*,x). Với một bản sao bất kỳ T ∈ ???? (V*,x) cho ???(T) là xác suât để T là một bản sao dó V* tạo ra ki tham gia vào phép chứng minh t−ơng hỗ. T−ơng tự ,với T∈F(x), cho ????(T) là xác suất để T là một bản sao (giả mạo)đ−ợc tạo bởi S*. Giả sử rằng T(V*,x)và với bất kỳ kỳ T ∈ ??????(V*,x), giả sử rằng pFv(T) =?????(T). khi đó hệ thống chứng minh t−ơng hỗ đ−ợc gọi là một hệ thống chứng minh không tiết lộ thông tin hoàn thiện(không điều kiện). Trong hợp đặc biệt khi V* giống nh− Vic (khi Vic là trung thực) thì định nghĩa trên giống nh− định nghĩa 13.1. Hình 13.7 thuật toán giả mạo cho V* đối với các bản sao cho tnsh đẳng cấu đồ thị Trang 10
11. Vietebooks Nguyễn Hoàng Cương Đầu vào: hai đồ thị đẳng cấu G1 và G2 ,mỗi đồ thị có tập đỉnh {1 n} 1. T = (G , G ) 1 2 2. For j = 1 to n do 3. Xác định tàng thái cũ bằng trạng thái (V*) 4. Repeat 5. Chọn ngẫu i =1 hoặc 2 j 6. Chọn p là phép hoán vị ngẫu nhiên của {1 n} j 7. Tính Hj là ảnh của Gi theo ρj 8. Gọi V* với đầu vào Hj ta thu đ−ợc một yêu cầu I’, 9. If ij = I’j then ghép (Hj, ij, ρj) vào đuôi của T Else Thiết lập lại V* bằng cách xác định trạng thái (V*) = trạng thái cũ 10. Until ij=i’j Để chứng minh rằng hệ thống chứng minh là không tiết lộ thông tin hoàn thiện ta cần một phép biến đổi chung để xây dựng một bộ mô phỏng S* từ V* bất kỳ. Ta sẽ tiếp tục thực hiện việc này đối với hệ thống chứng minh cho tính đẳng cấu đồ thị. Bộ mô phỏng sẽ đóng vai trò của Peggy sử dụng V* nh− một “ch−ơng trình con” có khả năng khởi tạo lại. Nói một cách không hình thức S* sẽ cố gắng giả định một yêu cầu ij mà V*sẽ đ−a ra trong mỗi vòng j. tức là S* sẽ tạo ra một bộ ba hợp lệ ngẫu nhiên có dạng (Hj, ịj, ρj) và thực hiện thuật toán V* đẻ thấy đ−ợc yêu cầu của nó dành cho vòng j. nếu giả định ij giống nh− yêu cầu i’j(nh− đ−ợc tạo bởi V*) thì bộ ba (Hj, ịj, ρj) sẽ đ−ợc gắn vào bản sao giả mạo. nếu không thị bộ ba này sẽ bị loại bỏ, S* sẽ giả định một yêu cầu mới ij và thuật toán V* sẽ đ−ợc khởi động lại sau khi thiết lập lại trạng thái của nó về tràng thái bắt đầu của vòng hiện thời . thuật ngữ “trạng thái ”đ−ợc hiểu là các giá trị của tất cả các biến dùng trong thuật toán. Bây giờ ta sẽ đ−a ra một mô tả chi tiết hơn về thuật toán mô phỏng S*.ở thời đIúm bát kỳ cho tr−ớc, trong khi thực hiên ch−ơng trình V* trạng thái hiện thời của V* sẽ đ−ợc ký hiệu là state (V*). Một mô tả giả mã của thuật toán mô phỏng đ−ợc cho ở hình 13.7 Trang 11
12. Vietebooks Nguyễn Hoàng Cương Có khả năng bộ mô phỏng sẽ không dừng lại nếu không xảy ra ij = i’j. tuy nhiên có thể chứng tỏ rằng thời gian chạy trung bình của bộ mô phỏng là thời gian đa thức và hai phân bố xác suất ????????(T)và ???????(T)là đồng nhất. Định lý 13.2 Hệ thống chứng minh t−ơng hỗ cho tính đẳng cấu đồ thị là một hệ thông chứng minh không tiết lộ thông tin hoàn thiện. Chứng minh: Tr−ớc tiên ta thấy rằng bất luận V* tạo ra các yêu cầu của nó ra sao, xác suất để giả định i’j là bằng 1/2. Nh− vậy trung bình S* phảI tạo đ−ợc hai bộ ba để tạo đ−ợc hai bộ ba ,để tạo đ−ợc một bộ ba gắn voà bản sao giả mạo. Do đó thời gian chạy trung bình là thời gian đa thức theo n . Nhiệm vụ khó khăn hơn là phảI chứng tỏ rằng hai phân bố xác suất ????????(T)và ????????????(T) là nh− nhau.ở định lý 13.1(trong đó Vic là ng−ời kiểm tra trung thực) ta đã tính đ−ợc hai phân bố xác suất và thấy rằng chúng là đồng nhất. Ta cũng đã sử dụng một yếu tố là các bộ ba (H, i, ρ) đ−ợc ở các vòng khác nhau của phép chứng minh là độc lập. Tuy nhiên trong bái toán này ta không có cách tính toán t−ờng minh hai phân bố xác suất. Hơn nữa các bộ ba đ−ợc tạo ở các vòng khác nhau của phép chứng minh lại không độc lập. Ví dụ yêu cầu mà V* đ−a ra vòng j có thể phụ phuộc theo 1 kiểu rất phức tạp nào đó vào các yêu cầu ở các vòng tr−ớc và vào cách Peggy đáp ứng các yêu cầu đó. Cách khắc phục các khó khăn này là phải xem xét các phân bố xác xuất trên các bản sao bộ phận có thể có trong quá trình mô phỏng hoặc chứng minh t−ơng hỗ và sau đó tiếp tục bằng ph−ơng pháp quy nạp trên số các vòng. Với 0 ≤ j ≤ n ta xác định các phân bố xác xuất pτ,v,j(T) và pτ,v,n(T) trên tập các bản sao bộ phận Tj xuất hiện ở cuối vòng j. Chú ý rằng pτ,v,j(T) = pτ,v(T)và pτ,v,n(T) = pτ,v(T). Bởi vậy nếu có thể chứng tỏ rằng hai phân bố pτ,v,j(T) và pτ,v,j(T) là đồng nhất với mọi j thì ta có điều cần chứng minh . Tr−ờng hợp j = 0 ứng với khi bắt đầu thuật toán : lúc này bản sao chỉ gồm hai đồ thị G1 và G2 .Bởi vậy các phân bố xác suất là đồng nhất khi j = 0 .Ta sẽ sử dụng điều kiện để bắt đầu phép quy nạp. Trang 12
13. Vietebooks Nguyễn Hoàng Cương Tr−ớc tiên ta giả sử hai phân bố xác suất pτ,v,j-1(T), và pτ,v,j-1(T) trên τj-1 là đồng nhất với giá trị j ≥ 1 nào đó. Sau đó ta sẽ chứng tỏ rằng hai phân bố xác suất pτ,v,j(T) và pτ,v,j(T) trên τj là đồng nhất . Xét điều sẽ xảy ra trong vòng j của phép chứng minh t−ơng hỗ. Xác suất để yêu cầu của V là ij =1 là một số thực p nào đó và xác suất để yêu cầu của V ij = 2 là 1-pi. ở đây pj phụ thuộc vào trạng thái của thuật toán V khi bắt đầu vòng lặp j. ở trên đã nhận xét rằng trong phép chứng minh t−ơng hỗ tất cả các đồ thị H có thể đều đ−ợc Peggy chọn với xác suất nh− nhau (không phụ thuộc vào giá trị pj), vì mọi phép hoán vị đều đồng khả năng đối với mỗi yêu cầu ij có thể .Bởi vậy xác suất đ ể bộ ba thứ j ở trên bản sao (H, i,p) bằng pi/n! nếu i=1 và bằng (1-p1)/n! nếu i=2. Tiếp theo ta sẽ thực hiện phân tích t−ơng tự cho phép mô phỏng .Trong một b−ớc lặp cho tr−ớc bất kỳ của vòng lặp REPEAT, S sẽ chọn một đồ thị H bất kỳ với xác suất 1/n! .Xác suất để i=1 và yêu cầu của V là 1 bằng p1/2 ; xác suất để i=2 và yêu cầu của V là 2 bằng (1-pj)/2. ở mỗi trạng thái này, (H, i, ρ) đ−ợc coi là bộ ba thứ j của bản sao. Với xác suất bằng 1/2 sẽ không có gì đ−ợc viết tiếp lên băng trong lần lặp cho tr−ớc bất kỳ của vòng lặp REPEAT . Tr−ớc hết sẽ xét tr−ờng hợp i =1. Nh− đã nêu ở trên, xác suất để yêu cầu của V=1 là p1. Xác suất để một bộ ba (H,i,p) đ−ợc coi là bộ ba thứ j trong bản sao ((H,i,p) đ−ợc viết tiếp lên bảng) trong b−ớc lặp thứ i của vòng lặp REPEAT bằng: P1 2l ì n! Bởi vậy, Xác suất để (H, i, ρ) là bộ ba thứ j trong bản sao là: p ⎛ 1 1 ⎞ p 1 ⎜1 + + + ⎟ = 1 2ì n!⎝ 2 4 ⎠ n! Tr−ờng hợp i = 2 đ−ợc phân tích theo cách t−ơng tự : Xác suất để (H,i,p) đ−ợc coi là bộ ba thứ j trong bản sao bằng (1-p1)/n!. Trang 13
14. Vietebooks Nguyễn Hoàng Cương Nh− vậy hai phân bố xác suất trên các bản sao bộ phận tại cuối vòng j là đồng nhất. Theo quy nạp, hai phân bố xác suất pτ,v,j-1(T),và pτ,v,j-1(T) là nh− nhau. Định lý đ−ợc chứng minh Việc xem xét hệ thống chứng minh t−ơng hỗ đối với tính không đẳng cấu đồ thị cũng rất thú vị. Không quá khó khăn để chứng minh rằng, hệ thống chứng minh này là hệ thống không tiết lộ thông tin hoàn thiện nếu Vic tuân thủ giao thức ( tức là nếu Vic chọn mỗi đồ thị yêu cầu là một phiên bản đẳng cấu ngẫu nhiên của G1, trong đó i =1 hoặc i =2 đ−ợc chọn ngẫu nhiên ). Hơn nữa nếu là Vic tạo mỗi đồ thị yêu cầu bằng cách lấy một phiên bản đẳng cấu của G1 hoặc G2 thì giao thức vẫn đảm bảo không tiết lộ thông tin ngay cả khi Vic chọn các yêu cầu của mình một cách không ngẫu nhiên. Tuy nhiên, giả sử rằng, kẻ gây rối Oscar đ−a cho Vic một đồ thị H ( H là đẳng cấu với G1 hoặc G2) nh−ng Vic không biết Gi nào là đẳng cấu với H nếu Vic sử dụng H này làm một trong các đồ thị yêu cầu của mình trong các hệ thống chứng minh t−ơng hỗ thì Peggy sẽ cho Vic một phép đẳng cấu mà tr−ớc đó anh ta không biết và không thể tính toán đ−ợc cho chính mình. Trong tình huống này, về mặt trực giác hệ thống chứng minh sẽ không còn là một hệ thống tiết lộ thông tin và bản sao do hệ thống này tạo ra khó có thể giả mạo bằng bộ mô phỏng . Có thể biến đổi phép chứng minh tính không đẳng cấu đồ thị để nó là một hệ thống không tiết lộ thông tin hoàn thiện, tuy nhiên ta sẽ không trình bày chi tiết ở đây . Bây giờ ta sẽ trình bày một số ví dụ khác về các hệ thống không tiết lộ thông tin hoàn thiện. Một phép chứng minh không tiết lộ thông tin hoàn thiện cho các thặng d− bậc hai ( Modulo n = pq, trong đó p , q là các số nguyên tố) đ−ợc cho ở hình 13.8 . Hình 13.8. Hệ thống chứng minh t−ơng hỗ không tiết lộ thông tin hoàn thiện cho các thặng d− bậc hai Trang 14
15. Vietebooks Nguyễn Hoàng Cương Đầu vào: Một số nguyên d−ơng n có phân tích n = pq không đ−ợc biết, trong đó p, q là các số nguyên tố và x∈QR(n). 1. Lập lại các b−ớc sau log2n lần : 2. Peggy chọn một số ngẫu nhiên v ∈ Zn và tính 2 y=y mod n. Peggy gửi y cho Vic. 3. Vic chọn một số ngẫu nhiêni = 0 hoặc i = 1 và gửi nó cho Peggy. 4. Peggy tính z = uj v mod n, trong đó u là căn bậc hai của x và gửi z cho Vic . 5. Vic kiểm tra xem liệu có thoả mãn : z2 ≡ xiy(mod n). 6. Vic sẽ chấp nhận chứng minh của Peeggy nếu tính toán ở b−ớc 5 đ−ợc kiểm tra cho mỗi vòng (trong log n vòng ) . 2 Peggy đang phải chứng tỏ x là một thặng d− bậc hai. ở mỗi vòng cô ta sẽ tạo ra một thặng d− bậc hai ngẫu nhiên y và gửi nó cho Vic. Sau đó tuỳ thuộc vào yêu cầu của Vic, Peggy hoặc sẽ đ−a cho Vic một căn bậc hai của y hoặc một căn bậc hai của xy. Rõ ràng là giao thức đầy đủ. Để chứng minh tính đúng đắn ta thấy rằng nếu x không phải là một thặng d− bậc hai thì Peeggy chỉ có thể trả lời một trong hai yêu cầu có thể vì trong tr−ờng hợp này y là một thặng d− bậc hai khi và chỉ khi xy không phải một thặng d− bậc hai. Bởi vậy Peggy sẽ bị tóm ở một vòng cho tr−ớc bất kỳ của giao thức với xác suất 1/2 và xác suất để Peggy đánh lừa đ−ợc Vic trong toàn bộ n vòng chỉ bằng 2 − log 2 n = 1/n ( lý do có log2n vòng là do cỡ đặc tr−ng của bái toán tỷ lệ với số bit trong biểu diễn nhị phân của n là log2n ). Bởi vậy xác suất đánh lừa của Peggy sẽ là một hàm mũ âm của cỡ đặc tr−ng của bái toán giống nh− trong phép chứng minh không tiết lộ thông tin cho tính đẳng cấu đồ thị. Có thể chỉ ra tính không tiết lộ thông tin hoàn thiện đói với Vic theo cách t−ơng tự nh− bái toán đẳng cấu đồ thị. Vic có thể tạo ra bộ ba (y,i,z) bằng cách tr−ớc tiên chọn i và z xác định: y = z2(xI)-1 mod n Trang 15
16. Vietebooks Nguyễn Hoàng Cương Các bộ ba đ−ợc tạo theo cách này có cùng phân bố xác suất các bộ ba đ−ợc tạo trong giao thức với giả thiết Vic chọn các yêu cầu của mình một cách ngẫu nhiên. Tính không tiết lộ thông tin hoàn thiện (với v tuỳ ý) có thể đ−ợc chứng minh theo ph−ơng pháp t−ơng tự nh− đối với bái toán đẳng cấu đồ thị. Nó đòi hỏi phải xây dựng một bộ mô phỏng s để giả định các yêu cầu của v và chỉ giữ lại các bộ ba ứng với các giả định đúng. Để minh hoạ thêm cho vấn đề này ta sẽ đ−a ra một ví dụ nữa về phép chứng minh không tiết lộ thông tin hoàn thiện, đây là một phép chứng minh cho một bái toán quyết định có liên quan đến bái toán logarit rời rạc. Bái toán này đ−ợc gọi là bái toán thành viên của nhóm con ( đ−ợc mô tả ở hình 13.9 ). Dĩ nhiên là số nguyên k ( nếu nó tồn tại ) chính là logarit rời rạc của β Hình 13.9. Thành viên của nhóm con. Đặc tr−ng của bái toán : Hai số nguyên d−ơng n và l, và hai phần tử phân biệt α, β ∈ Zn trong đó α có cấp l trong Zn. Vấn đề : phải chăng β = αk đối với một số nguyên tố k nào đó sao cho 0≤k≤n-1 ?(nói một cách khác là phải chăng β là một thành viên của nhóm Zn đ−ợc tạo bởi α ?) Hình 13.10 Mô tả một phép chứng minh không tiết lộ thông tin hoàn thiện cho bái toán thành viên nhóm con. Việc phân tích giao thức nỳ t−ơng tự nh− các giao thức mà ta đã xem xét ; các chi tiết đ−ợc giành cho bạn đọc xem xét. Hình 13.10. Hệ thống chứng minh t−ơng hỗ không tiết lộ thông tin hoàn thiện cho thành viên của nhóm con. Trang 16
17. Vietebooks Nguyễn Hoàng Cương Đầu vào:Một số nguyên d−ơng n và hai phần tử phân biệt α,β∈Z trong đó n cấp của α đ−ợc ký hiệu bằng l và đ−ợc công khai . 1. Lập lại các b−ớc sau log2n lần : j 2. Peggy chọn một số ngẫu nhiên j sao chi 0≤ j ≤ l - 1 và tính γ = α mod n Peggy gửi γ cho Vic. 3. Vic chọn một số ngẫu nhiên I = 0 hoặc i = 1 và gửi nó cho Peggy . 4. Peggy tính h = j+ik mod l trong đó k = logαβ và gửi cho Vic . 5. Vic kiểm tra xem liệu có thoả mãn đồng d− thức sau không : αh ≡ β iγ (mod n). 6. Vic sẽ chấp nhận chứng minh của Peeggy nếu tính toán ở b−ớc 5 đ−ợc kiểm tra cho mỗi vòng trong log2n vòng . 13.3 Các cam kết bít Hệ thống chứng minh không tiết lộ thông tin đối với bái toán đẳng cấu đồ thị là một hệ thống thú vị, tuy nhiên sẽ là hữu ích hơn nếu có các hệ thống chứng minh không tiết lộ thông tin cho các bái toán đ−ợc coi là NP đầy đủ. Về mặt lý thuyết, không tồn tại các phép chứng minh không tiết lộ thông tin hoàn thiện cho các bái toán NP đầy đủ. Tuy nhiên ta có thể mô tả các hệ thống chứng minh có dạng không tiết lộ thông tin về mặt tính toán. Các hệ thống chứng minh thực tế sẽ đ−ợc mô tả ở phần sau ; trong phần này ta sẽ mô tả kỹ thuật cam kết bít là một công cụ quan trọng đ−ợc dùng trong hệ thống chứng minh . Giả sử Peggy viết một thông báo lên một mẩu giấy rôì đặt nó vào một két sắt mà cô ta biết mã số. Sau đó Peggy trao két sắt cho Vic. Mặc dù Vic không biết thông báo là gì cho tới khi két đ−ợc mở nh−ng ta sẽ coi rằng Peggy đã bị ràng buộc với thông báo của mình vì cô ta không thể thay đổi nó. Hơn nữa, Vic không thể biết thông báo là gì ( giả sử Vic không biết mã số của két ). Trừ phi Peggy mở két cho anh ta. ( Hãy nhớ lạI là ta đã dùng lập luận t−ơng tự ở ch−ơng 4 để mô tả ý t−ởng về một hệ mật công khai, tuy nhiên trong tr−ờng hợp đó Vic là ng−ời có thể mở két bởi vì anh ta là ng−ời nhận thông báo ). Trang 17
18. Vietebooks Nguyễn Hoàng Cương Giả sử thông báo là một bít = 0 và Peggy sẽ mã hoá b theo cách nào đó. Dạng đã mã hoá của b đôI khi đ−ợc gọi blob và ph−ơng pháp mã hoá đ−ợc gọi là một sơ đồ cam kết bít. Nói chung , một sơ đồ cam kết bít là một hàm f: {0,1} x X → Y, trong đó X và Y là các tập hữu hạn. Một phép mã hoá của b là giá trị bất kỳ f(b,x), x∈X. Ta có thể định nghĩa một cách phi hình thức hai tính chất mà một sơ đồ cam kết phải thoả mãn . Tính chất giấu kín: Với một bít b = 0 hoặc 1, Vic không thể xác định đ−ợc giá trị của b từ blob f(b,x). Tính ràng buộc : Sau đó Peggy có thể mở đ−ợc blob bằng cách tiết lộ giá trị x dùng mã hoá b để thuyết phục Vic rằng b là giá trị đã mã. Peggy không thể mở một blob bởi cả hai giá trị 0 và 1. Nếu Peggy muốm cam kết ( ràng buộc) một xâu bit bất kỳ thì một cách đơn giản là cô ta phảI ràng buộc từng bit một cách độc lập . Một ph−ơng pháp để thực hiện cam kết bit là sử dụng hệ mật xác suất Goldwasser - micali mô tả ở phần 12.4 hãy nhớ lại rằng trong hệ mật này n = pq trong đó p, q là các số nguyên tố và m ∈ ???QR(n). Các số nguyên m và n là công khai và chỉ có Peggy biết phân tích n = pq trong sơ đồ cam kết bit * ta có X = Y = Zn và : f(b,x)=mb x2 mod n Peggy sẽ mã hoá giá trị b bằng cách chọn một số ngẫu nhiên x và tính y=f(b,x) ; giá trị y chính là blob . Sau đó khi peggy muốn mở y, cô ta sẽ tiết lộ các giá trị b và x. Khi đó Vic có thể kiểm tra thấy rằng : y ≡ mb x2 mod n Ta xem xét tính giấu kín và tính ràng buộc. Một blob là một phép mã hoá của 0 hoặc 1, và sẽ không để lộ thông tin về giá trị bản rõ x miễn là bái toán các thặng d− bậc hai là không có khả năng giảI ( ta đã thảo luận kỹ đIều này ch−ơng 12 ). Bởi vậy sơ đồ có tính giấu kín . Liệu sơ đồ có tính ràng buộc không ? Nếu ta giả sử là không thì 2 2 m x1 ≡ x2 (mod n) Với các giá trị x1, x2 nào đó thuộc Zn. Tuy nhiên Trang 18
19. Vietebooks Nguyễn Hoàng Cương -1 2 m ≡ (x2x1 ) mod n điều này mâu thuẫn bởi vì m ∈??????QR(n) Các sơ đồ ràng buộc bit sẽ đ−ợc dùng để xây dựng các phép chứng minh không tiết lộ thông tin. Tuy nhiên chúng còn có một ứng dụng tuyết vời khác vào một bái toán tung đồng xu qua đIện thoại. Giả sử Alice và Bob muốn đ−a ra một quyết định nào đó dựa trên phép tung đồng xu ngẫu nhiên nh−ng họ không ở cùng một địa đIểm .ĐIều này có nghĩa là không thể thực hiện đ−ợc công việc một ng−ời tung đồng xu thực còn ng−ời kia kiểm tra phép thử này. Sơ đồ ràng buộc bit sẽ cho một ph−ơng pháp thoát khỏi tình trạng bế tắc này. Một trong hai ng−ời ( chẳng hạn Alice ) sẽ chọn một bit ngẫu nhiên b và tính blob y .Cô ta sẽ trao y cho Bob. Bây giờ Bob sẽ giả định giá trị của b và rồi Alice sẽ mở blob để tiết lộ b. ở đây, tính chất giấu kín có nghĩa là Bob không có khả năng tính b theo y đã cho, và tính chất ràng buộc có nghĩa là Alice không thể thay đổi đ−ợc lựa chọn của mình sau khi Bob tiết lộ giả định của anh ta . Sau đây là một ví dụ khác về sơ đồ ràng buộc bit dựa trên bái toán logarithm rời rạc. Từ phần 5.1.2 ta đã có : Nếu p ≡ 3 ( mod 4) là một số nguyên tố sao cho bái toán logarithm trong Zp không giảI đ−ợc thì bit bậc thấp nhất thứ hai của một logarit rời rạc là an toàn. Trên thực tế, đối với các số nguyên tố p ≡ 3 (mod 4), ng−ời ta chứng minh rằng thuật toán Monte - Carlo bất kỳ cho bái toán về bit thứ hai sẽ có xác suất sai bằng 1/2 - ε với ε>0 có thể đ−ợc dùng để giảI toán logarit rời rạc trong Zp. Kết quả mạnh hơn nhiều này là cơ sở cho sơ đồ ràng buộc bit . Sơ đồ ràng buộc này sẽ có X = {1, , p-1}và Y = Zp .Bit bậc thấp nhất thứ hai của số nguyên x ( ký hiệu là SLB (x)) đ−ợc xác định nh− sau : 0 Nếu x ≡ 0, 1( mod4) SLB = 1 Nếu x ≡ 2, 3(mod4) sơ đồ ràng buộc bit đ−ợc xác định bởi : α x mod p Nếu SLB(x) = b f(b,x) = α p-1mod p Nếu SLB(x) ≠ b Nói cách khác bit b sẽ đ−ợc mã bằng cách chọn một một phần tử ngẫu nhiên có bit cuối cùng thứ hai là b và nâng α lên luỹ thừa x modulo p.( Chú ý rằng SLB ( p-x ) ≠ SLB (x) vì p ≡ 3 ( mod 4)). Trang 19
20. Vietebooks Nguyễn Hoàng Cương Sơ đồ thoả mãn tính ràng buộc và theo các nhận xét đã nêu, nó cũng thoả mãn tính giấu kín nếu bái toán logarit rời rạc trong Zp là không giảI đ−ợc . 13.4 .các chứng minh không tiết lộ thông tin về mặt tính toán . Trong phần này ta sẽ đ−a ra một hệ thống chứng minh không tiết lộ thông tin cho bái toán quyết định NP đầy đủ là bái toán về khả năng tô màu một đồ thị bằng ba màu, bái toán này đ−ợc nêu ở hình 13.11. Hệ thống chứng minh sẽ sử dụng một đồ thị cam kết ( ràng buộc ) bit: để xác định ,ta sẽ áp dụng sơ đồ ràng buộc bit đ−ợc mô tả ở 13.3 ( dựa trên mã hoá xác suất ). Giả sử Peggy biết hàm φ ba màu của đồ thị G và cô ta muốn thuyết phục Vic rằng có thể tô màu G bằng ba màu theo kiểu không tiết lộ thông tin .Không mất tính tổng quát, giả sử rằng G có tập đỉnh V={1 n}. Ký hiệu m ={E}. Hệ thống chứng minh sẽ đ−ợc mô tả theo các thuật ngữ cuả sơ đồ ràng buộc f:{0,1} x X →Y ( đ−ợc đ−a ra công khai ). Vì không thể mã hoá một màu bằng một bit nên ta thay màu 1 bằng hai bit 01, màu hai bằng 10, màu ba bằng 11.Khi đó ta sẽ mã hoá mỗi bit trong hai bit (biểu thị màu ) bằng hàm f. Hình 13.11.khả năng tô đồ thị bằng ba mằu. Đặc tr−ng của bái toán :Một đồ thị G = (V,E) có n đỉnh. Vấn đề :Liệu có thể tô G bằng đúng 3 mầu hay không? (Theo các thuật ngữ toán học có chăng một hàm ф:V(G)ặ{1,2,3} sao cho {u,v}є E thì ф (u)= ф (v)?). Hệ thống chứng minh t−ơng hỗ đ−ợc trình bày trên hình 13.12.Một cách không hình thức ,quá trình xẩy ra nh− sau:ở mỗi vòng ,Peggy sẽ quy Trang 20
21. Vietebooks Nguyễn Hoàng Cương định một mầu là một hoán vị của phép tô màu xác định ф.Vic sẽ yêu cầu Peggy mở các blob ứng với các điểm cuối của một cạnh nào đó đ−ợc chọn ngẫu nhiên.Peggy sẽ thực hiện các điều đó và rồi Víc sẽ kiểm tra xem các quy định có tuân thủ theo dòng đòi hỏi không.Chú ý rằng mọi tính toán của Víc là theo thời gian đa thức và tính toán của Peggy cũng vậy ,miễn là cô ta biết đ−ợc sự tồn tại của một phép tô 3 mầu ф. Sau đây là một ví dụ nhỏ để minh hoạ: Ví dụ 13.3 Giả sử G là một đồ thị (V,E) trong đó : V = {1, 2, 3, 4, 5} và E = {12, 14, 15, 23, 34, 45}. Giả sử Peggy biết phép tô 3 mầu ? trong đó ф(1)=1, ф(2)= ф(4)=2, và ф(3)= ф (5)=3.Ta cũng giả sử rằng các tham số của sơ đồ ràng buộc bít là n=321389 và m=156897 ,bởi vậy f(b,x)=mbx2 mod n,trong đó b=0,1 và * xєZn . Giả sử Peggy chọn phép hoán vị Π =(1, 3, 5) ở một vòng nào đó cho phép chứng minh. Khi đó cô ta tính : C1 = 1 C2 = 3 C3 = 2 C4 = 3 C5 = 2 và sẽ mã hoá phép tô mầu này ở dạnh nhị phân bằng một bộ 10: 0 1 1 1 1 0 1 1 1 0 sau đó tính các ràng buộc cho 10 bít này .Giả sử cô làm nh− sau: b x F(b,x) 0 147658 176593 1 318856 205585 1 14497 189102 1 285764 294039 1 128589 230968 0 228569 77477 Trang 21
22. Vietebooks Nguyễn Hoàng Cương 1 53369 305090 1 194634 276484 1 202445 292707 0 177561 290599 Say đó Peggy trao cho Vic 10 giá trị f(b,x) đã tính ở trên Tiếp theo ,giả sử rằng Víc chọn cạnh 34 làm yêu cầu của mình.Sau đó Peggy sẽ mở 4 blob :2 lob ứng với đình 3 ,2 lob ứng với đỉnh 4.Nh− vậy Peggy sẽ trao cho Víc các cặp đ−ợc sắp sau: (b,x) = (1,128089), (0, 228569), (1, 53369), (1, 194634) Víc sẽ kiểm tratr−ớc hết xem 2 mấu có khác nhau không :10 là mã hoá của mầu 2 và 11 là mã hoá của mầu 3 .Nh− vậy diều vừa kiểm tra là đ−ợc thỏ mãn. Tiếp theo, Víc sẽ kiểm tra thấy rằng 4 cam kết là hợp lệ.Đây là điều phải chứng minh. Cũng nh− trong các hệ thống chứng minh đã đ−ợc nghiên cứu ở trên Víc sẽ chấp nhận một phép chứng minh hợp lệ với xác suất =1 ,bởi vậy ta có đ−ợc tính đầy đủ .Xác suất để Víc sẽ chấp nhận bằng bao nhiêunếu G không thể tô bằng 3 mầu ? Trong tr−ờng hợp này ,đối với phếp tô mầu bất kì phải có ít nhâts một cạnh ij để i và j có cùng mầu .Cơ hội để Víc chọn một cạnh nh− vậy it nhất là 1/m.Xác xuất để Peggy đánh lừa đ−ợc Víc trong toàn bộ m2 vòng nhièu nhất là (1- 1/m )n vì (1- 1/m )m ặe-1 khi mặ∞ nên ta thấy rằng (1- 1/m )n ặe-m và giá trị này tiến tới 0 theo hàm mũ nh− là hàm của m | E | .Bởi vậy ta cũng có đ−ợc tính đúng đắn. Trở lại xem xét khía cạnh không tiết lộ thông tin của hệ thống chứng minh. Tất cả những cái mà Víc thấy trong mỗi vòng đã cho của giao thức là một phép tô 3 mầu đã mã của G, cùng với hai mầu phân biệt của các đỉnh trên một cạnh cụ thể nh− đã đ−ợc Peggy cam kết tr−ớc đó. Vì các mầu đ−ợc hoán vị ở mỗi vòng nên d−ờng nh− là Víc không thể kết hợp các thông tin từ các vòng khác nhau để xây dựng phép tô 3 mầu . Hệ thống chứng minh này không phải là một hệ thống chứng minh không tiết lộ thông tin hoàn thiện mà chỉ là một dạng yếu hơn của nó và đ−ợc gọi là một hệ thống chứng minh không tiết lộ thông tin về mặt tính toán .Tính Trang 22
23. Vietebooks Nguyễn Hoàng Cương không tiết lộ thông về mặt tính toán đ−ợc định nghĩa giống nh− tính không tiế lộ thông tin hoàn thiện ngoại trừ một điểm là các phân bố xác suất t−ơng ứng của các bản sao chỉ đòi hỏi không phân phân biệt theo đa thức (theo cách hiểu ở ch−ơng 12) chứ không nhất thiết phải là đồng nhất . Hình 12.13.một hệ thống chứng minh t−ơng hỗ không tiết lộ thông tin về mặt tính toán cho bái toán xét khả năng tô đồ thị bằng 3 mầu . Đầu vào : Một đồ thị G = (E,V) trên tập đỉnh {1,. . .,n} 1. lặp lại các b−ớc sau m2 lần . 2. Cho ф là một đồ thị tô 3 mầu của G .Peggy sẽ chọn một hoán vị ngẫu nhiên Π của {1,2,3}.Với 1≤i≤n,cô ta xác định Ci = Π(ф(i)) Và viết ci nh− một xâu bít có độ dái hai: C =c c i i1 i2 Sau đó ,với i≤1≤n cô ta chọn 2 phần tử ngẫu nhiên ri1,ri2?thuộc X và tính r f(c r ),j=1,2rồi gửi danh sách cho Víc ij= ij, ij (r11 ,r12 ,. . .,rn1 ,rn2) 3. Víc chọn một cách ngẫu nhiên {u,v} є E và gửi nó cho Peggy. 4. Peggy gửi (cu1,cu2,ru1,ru2) và (cv1,cv2,rv1.r v2) cho Víc. 5. Víc kiểm tra xem có thoả mãn các bất đẳng thức ,và đẳng thức sau không? (cu1,cu2 )# (cv1,cv2 ) (c ,c )# (0,0) u1 u2 (cv1,cv2 )#(0,0) R =f(c ,r ),j=1,2 u,j uj uj Rv,j=f(cvj,rvj),j=1,2 6. Víc sẽ chấp nhận phép chứng minh của Peggy nếu toán ở b−ớc 5 đ−ợc kiểm tra ở mỗi một trong m2 vòng . Chúng ta bắt đầu bằng việc chỉ ra cách các bản sao có thể đ−ợc giả mạo nh− thế nào. Sau đây sẽ đ−a ra một thuật toán trực tiếp giả mạo bản sao (các bản sao này không thể phân biệt đ−ợc với các bản sao đ−ợc tạo bởi Vic trung thực). Nếu Vic không tuân theo giao thức thì có thể xây dựng một bộ mô phỏng dùng thuật toán Vì nh− một ch−ơng trình con có thể gọi lại đ−ợc để xây dựng các bản sao giả mạo. Cả hai thuật toán giả mạo này đều theo dạng các thuật toán t−ơng đối cho hệ thống chứng minh tính đẳng cấu đồ thị. Trang 23
24. Vietebooks Nguyễn Hoàng Cương ở đây ta chỉ xem xét tr−ờng hợp khi Vic tuân thủ giao thức. Một bản sao T của phép chứng minh t−ơng hỗ về tính khả tô đồ thị (bằng ba màu) sẽ có dạng: (G:A1, ,Am2) trong đó Aj chứa 2m blob đã đ−ợc tính bởi Peggy, cạnh u v đ−ợc Vic chọn, các màu đ−ợc Peggy gán cho các đỉnh u và v ở vòng j, và 4 số ngẫu nhiên đ−ợc Peggy dùng để mã hoá các màu của hai đỉnh này. Một bản sao đ−ợc giả mạo bằng thuật toán giả mạo đ−ợc mô tả trên hình 13.13. Hình 13.13. Thuật toán giả mạo các bản sao về tính khả tô đồ thị bằng ba màu. Đầu vào: Một đồ thị G=(V,E) có tập đỉnh V={1, ,n} 1. T=(G) 2. For j=1 to m2 do 3. Chọn ngẫu nhiên một cạnh {u, v} ∈ E 4. Chọn ngẩu nhiên các màu khác nhau d = d1d2 và e = e1e2 trong đó d1, d2, e1, e2, ∈ {0, 1} 5. Chọn ri,j là một phần tử ngẩu nhiên của X, với 1 ≤ i ≤n, j = 1,2 6. Với 1 ≤ i ≤n, j = 1,2, hãy xác định f(1,r ) nếu i ≠ u,v i, j Ri, j = f(d j,ri, j ) nếu i = u f(ej,ri, j ) nếu i = v 7. Ghép (R . . . .,R , u, v, d , d , r , r , e , e , r , r ) vào đầu cuối 1,1 n,2 1 2 d,1 d,2 1 2 e,1 e,2 Phép chứng minh tính không tiết lộ thông tin (về mặt tính toán) đối với Vic đồi hỏi chứng tỏ rằng hia phân bố xác suất trên các bản sao (đ−ợc tạo bởi Vic khi tham gia vào giao thức và đ−ợc tạo bởi bộ mô phỏng ) là không thể phân biệt. ặ đây ta bỏ qua việc đó và chỉ đ−a ra vái nhận xét. Cần chú ý rằng hai phân bố xác suất không đồng nhất. Sở dĩ nh− vậy trên thực tế tất cả các Ri,,j trên một bản sao giả mạo là các blob mã hoá cho 1 ;trong khi đó các Ri, j trên một bản sao thực hiện là các blob mã hoá cho các số 1 và 0 với xác suấtgần bằng nhau. Tuy nhiên có thể chỉ ra rằng, không thể phân biệt đ−ợc hai phân bố xác suất này trong th−òi gian đa thức, nếu sơ đồ cam kết bítử dụng là an toàn. Chính xác hơn, điều đó có nghĩa lầ phân bố xác xuất trên các Trang 24
25. Vietebooks Nguyễn Hoàng Cương blob mã hoá các màu c là không thể phân biệt với phân bố xác suât trên blob mã hoá cho các màu d nếu c ≠ d. Bạn đọc đã làm quen với lý thuyết NP- đây đủ sẽ nhận thấy rằng nếu có một phép chứng minh không tiết lộ thông tin cho tr−ớc một bái tóan NP- đầy đủ nào đó thì ta có thể thu một phép chứng minh không tiết lộ thông tin cho một bái toán NP-đầy đủ bất kỳ khá. Điều này có thể đ−ợc thức hiên bằng cách áp dụng phép biến đổi đa thức một bái toán NP-đầy đủ cho tr−ớc vào một bái toán tô đồ thị bằng ba màu. 13.5. Các luận cứ không tiết lộ thông tin Ta sẽ nhắc lại các tính chất cơ bản của phép chứng minh không tiết lộ thông tin về mặt tính toán cho bái toán về tính khả tô đồ thị bằng ba màu nêu ở phần trên. ở đây không cần giả thiết nào để chứng minh cho tính đầy đủ và tính đúng đắn của giao thức mà chỉ cần một giả thiết về mặt tính toán để chứng minh tính không tiết lộ thông tin, đó là sơ đò cam kết bit phải là một sơ đồ an toàn. Nhận thấy rằng, nếu Peggy và Vic tham gia trong giao thức thì Vic sau đó có thể cố gắng phá sơ đồ ràng buộc bít đ−ợc dùng (ví dụ, nêu sơ đồ đ−ợc xây dựng trên một sơ đồ thặng d− bậc hai thì Vic sẽ cố gắng thức hiên phân tích n). Nếu Vic có thể phá đ−ợc sơ đồ ràng buộc bít thì anh có thể giải mã đ−ợc các blob (đ−ợc Peggy dùng trong giao thức) và rút ra phép toán tô ba màu. Phân tích này sẽ phụ thuộc vào các tính chất của các blob dùng trong giao thức. Mặc dù tính ràng buộc của các blob là không điều kiện song tính dấu kín lại đ−a trên giả thiết về mặt tính toán. Một ph−ơng án khá thú vị là dùng các blob trong đó tính che dấu là không điều kiện nh−ng tính ràng buộc lại đòi hỏi một giả thiết về mặt tính toán. Điều này dẫn tới một giao thức gọi là luận cứ không tiếtlộ thông tin hơi khác với phép chứng minh không tiết lộ thông tin. Bạn đọc nhớ lại rằng, cho tới nay ta vẫn giả sử rằng Peggy có đầy đủ sức mạnh, còn trong luận cứ không tiết lộ thông tin, ta sẽ coi rằng các tính toán của Peggy đ−ợc thực hiện theo thời gian đa thức (trên thực tế giả thiết này không gây ra một chút khó khăn nào vì các tính toán của Peggy là theo thời gian đa thức nếu cô ta biết phép tô màu của G). Trang 25
26. Vietebooks Nguyễn Hoàng Cương Ta sẽ mô tả hai sơ đồ ràng buộc bit thuộc loại này và sau đó đánh giá các kiểu sử dụng chúng trong giao thức tô đồ thị bằng ba màu. Sơ đồ đầu tiên đ−ợc xây dựng trên bái toán các thặng d− bậc hai. Giả sử n = pq, trong đó p và q là các số nguyên tố và cho m ∈QR(n) (chú ý rằng trong sơ đồ tr−ớc m là một thặng d− giả bậc hai). Trong sơ dồ nàyPeggy không nhất thiết phải biết phân tích của n và căn bậc hai của m. Bởi vậy Vic hoặc phải xây dựng đ−ợc các giá trị này hoặc chúng phải đ−ợc thu nhận từ một ng−ời thứ ba (tin cậy đ−ợc). * Cho X= Zn và Y= QR(n) và định nghĩa f(b ,n) =mbx2 mod n Cũng nh− tr−ớc đây, Peggy sẽ mã hoá giá trị b bằng cách chọn một giá trị ngẫu nhiên x và tính blob y = f(b,x). Trong sơ đồ này, tất cả các blob đều là các thặng d− bậc hai. Hơn nữa một giá trị bất kỳ y∈ QR(n) có thể là bản mã hoá của 0 hay của 1. Giả sử y= x2 mod n và m= k2 mod n. Khi đó: y= f(0,x) = f(1,x,k-1 mod n) Điều đó có nghĩa là sơ đồ này đạt đ−ợc tính dấu kín không điều kiện. Vậy điều kiện gì sẽ xảy ra đối với tính ràng buộc ? Peggy có thể mở một blob bất kỳ cho tr−ớc thành 0 hoặc 1 khi và chỉ khi cô ta có thể tính đ−ợc k (là một căn bậc hai của m). Nh− vậy, để cho sơ đồ này là ràng buộc (về mặt tính toán), cần phải giả thiết rằng Peggy không có khả năng tính căn bậc hai của m. (Nếu Peggy có đầy đủ sức mạnhthì dĩ nhiên cô ta có thể làm đ−ợc điều đó. Đó là lý do phải giả thiết Peggy có khả năng tính toán hạn chế). Để làm ví dụ cho một sơ đồ cam kết bit thứ hai thuộc loại này, xét một sơ đồ xây dựng trên bái toán logarithm rời rạc. Cho p là một số nguyên tố sao * cho bái toán logarithm rời rạc trong Zp là một bái toán bất khả giải, cho α là * * một phần tử nguyên thuỷ của Zp và cho β ∈Zp . Giá trị β phải đ−ợc chọn bởi Vic hoặc một ng−ời thứ ba tin cậy (chứ không phải bởi Peggy). Sơ đồ này sẽ * có X= {0, ,p-1}, Y= Zp và f đ−ợc xác định bằng: f(b,x) = βbαx mod p Không khó khăn lắm có thể thấy rằng sơ đồ này có tính dấu kín không điều kiện, và nó có tính dàng buộc khi và chỉ khi Peggy không có khả năng tính đ−ợc logarit rời rạc logαβ. Trang 26
27. Vietebooks Nguyễn Hoàng Cương Bây giờ giả sử ta dùng một trong hai sơ đồ cam kết bit trên trong giao thức về tính khả thi đồ thị bằng ba màu. Dễ dàng thấy rằng, giao thức vẫn giữ đ−ợc tính đầy đủ. Tuy nhiên điều kiện đúng đắn ở đây sẽ phụ thuộc vào mặt giả thiết về mặt tính toán: giao thức là đúng đắn khi và chỉ khi sơ đồ dàng buộc bit thoả mãn tính ràng buộc. Điều gì sẽ xảy ra đối với khía cạnh không tiết lộ thông tin của giao thức? Bởi vì sơ đồ cam kết bit đảm bảo tính dấu kín không điều kiện nên giao thức này sẽ trở thành một giao thức không tiết lộ thông tin hoàn thiện chứ không chỉ là một giao thức không tiết lộ thông tin về mặt tính toán nữa. Nh− vật ta đã có một luận cứ không tiết lộ thông tin hoàn thiện. Bảng 13.1. So sánh các tính chất của phép chứng minh và các luận cứ Tính chất Chứng minh không tiết Luận cứ không tiết lộ lộ thông tin thông tin Đầy đủ Không điều kiện Không điều kiện Đúng đắn Không điều kiện Về mặt tính toán Không tiết lộ thông tin Về mặt tính toán Hoàn thiện Giấu kín Không điều kiện Về mặt tính toán Ràng buộc Về mặt tính toán Không điều kiện Tuỳ theo áp dụng cụ thể mà ng−ời ta có thể thích dùng một luận cứ hơn là dùng một phép nhứng minh. Và khi nào thì ta phải đ−a ra một giả thiết về mặt tính toán cho Peggy hay cho Vic? Một so sánh tóm l−ợc về các tính chất của các phép chứng minhvà các luận cứ đ−ợc nêu ở bảng 13.1. ở cột “chứng minh không tiết lộ thông tin ”,các giả thiết về mặt tính toán có liên quan tới năng lực tính toán của Peggy. Trong cột “Luận cứ không tiết lộ thông tin”, các giả thiết về mặt tính toán có liên quan tới năng lực tính toán của Vic. ___ 13.6. Các chú giải vμ tái liệu h−ớng dẫn Phần lớn các kiến thức trong ch−ơng này đều dựa theo tái liệu của Brassard, Chaum và Crépeau [BBC 88] và của Goldreich, Micali và Wigderson [GMW 91]. Các sơ đồ cam kết (ràng buộc) bít và các thoả luận về sự khác nhau giữa các phép chứng minh và các luận cứ có thể tìm thấy trong [BBC 88](tuy nhiên cần để ý rằng thuật ngữ “luận cứ ” lần đầu tiên đ−ợc sử dụng trong [BC 90]. Các chứng minh không tiết lộ thông tin cho tính đẳng cấu đồ thị , tính không đẳng cấu đồ thị và tính khả tô đồ thị ba màu có thể tìm Trang 27
28. Vietebooks Nguyễn Hoàng Cương đ−ợc trong [GMW 91]. Một bái báo khác có liên quan là bái báo của Goldwasser, Micali và Rackoff [GMR 89], trong bái báo này các hệ thống chứng minh t−ơng hỗlần đầu tiên đ−ợc định nghĩa một cách hình thức. Chứng minh không tiết lộ thông tin cho bái toán các thặng d− bậc hai đ−ợc lấy từ bái báo này. ý t−ởng tung đồng tiền bằng điện thoại là của Blum [B1 28]. Một minh hoạ có tính chất giải trí và rất không hình thức cho khái niệm không tiết lộ thông tin đ−ợc Quisquater và Guilỏutình bày trong [QG 90]. Cũng có thể xem trong [Jo 88] của Johnson là một tổng quan chặt chẽ hơn về mặt toán học cho các hệ thống chứng minh t−ơng hỗ. Bái tập 13.1. Xét một hệ thống chứng minh t−ơng hỗ cho bái toán các thặng d− không bậc hai đ−ợc mô tả ở hình 13.14. Hãy chứng tỏ rằng hệ thống là đúng đắn và đầy đủ và giải thích tại sao giao thức này không tiết lộ thông tin. 13.2. Hãy tạo ra một hệ thống chứng minh t−ơng hỗ cho bái toán không là thành viên của nhóm con. Hãy chứng mỉnh rằng giao thức của bạn là đúng đắn và đầy đủ. 13.3. Xét một phép chứng minh không tiết lộ thông tin cho các thặng d− bậc hai đ−ợc trình bày ở hình 13.8. Hình 13.14. Một hệ thống chứng minh t−ơng hỗ cho các thặng d− không bậc hai. Đầu vào: Một số nguyên n có phân tích n =pq ch−a biết, trong đó p và q là các số nguyên tố, và x ∈ ????????? 1. Lặp lại các b−ớc sau log2n lần: 1 * 2. Vic chộn một số ngẫu nhiên v∈Zn và tính y = v2 mod n Vic chọn ngẫu nhiên i= 0 hoặc 1 và gửi cho Peggy: z = xiy mod n 3. Nếu z ∈ QR(n) thì Peggy xác định j= 0, ng−ợc lại Peggy sẽ xác định j=1. Sau đó cô ta gửi j cho Vic. 4. Vic sẽ kiểm tra xem liệu i=j hay không. 5. Vic chấp nhận phép chứng minh của Peggy nếu tính toán ở b−ớc 4 đ−ợc kiểm tra ở mỗi vòng trong log2n vòng. Trang 28
29. Vietebooks Nguyễn Hoàng Cương a.) Xác định một bộ ba hợp lệ là một bộ ba có dạng (y,i,z), trong đó y ∈ * 2 i QP(n), i=0 hoặc 1, z∈Zn và z ≡ x y (mod n). Hãy chứng minh rằng số các bộ ba hợp lệ là 2(p-1)(q-1), và mỗi một bộ ba nh− vậy sẽ đ−ợc tạo với xác suất nh− nhau nếu Peggy và Vic tuân theo giao thức. b) Hãy chỉ ra rằng Vic có thể tạo đ−ợc các bộ ba có cùng phân bố xác suất mà không biết phân tích n = pq. c) Hãy chứng minh rằng giao thức này là một giao thức không tiết lộ thông tin hoàn thiên đối với Vic. 13.4. Xét phép chứng minh không tiết lộ thông tin cho bái toán thành viên của nhóm con đã đ−ợc mô tả ở hình 13.10. a) Hãy chứng tỏ rằng giao thức này đúng đắn và đầy đủ. b) Xác minh một bộ ba hợp lệ là một bộ ba có dạng (γ, i, h), trong đó γ * h i ∈ Zn , i = 0 hoặc 1, 0 ≤ h ≤ l – 1 và α ≡ β γ (mod n). Hãy chứng tỏ rằng số các bộ ba hợp lệ là 2l và mỗi bộ ba nh− vậy sẽ đ−ợc tạo với xác suất băng nhau nếu Peggy va Vic tuân thhủ giao thức. c) Hãy chứng tỏ rằng có thể tạo đ−ợc các bộ ba có cùng phân bố xác suất mà không cần biết logarithm rời rạc logαβ. d) Chứng minh răng giao thức này là một giao thức không tiết lộ thông tin hoàn thiệt đối với Vic. 13.5. Chứng minh rằng sơ đồ cam kết bít logarithm rời rạc đ−ợc trình bày ở phần 13.5 là có tính giấu kín không điều kiện và chứng minh rằng nó có tính ràng buộc khi và chỉ khi Peggy không thể tính logαβ. 13.6. Giả sử ta sử dụng sơ đồ ràng buộc bịt theo các thặng d− bậc hai đ−ợc mô tả ở phần 13.5 để có một luận cứ không tiết lộ thông tin cho phép tô đồ thị bằng ba màu. Bằng cách dùng thuật toán giả mạo nêu ở hịnh 13.13. Hãy chứng minh rằng giao thức này là một giao thức không tiết lộ thông tin hoàn thiện đối với Vic. Tái liệu đọc thêm Trang 29
30. Vietebooks Nguyễn Hoàng Cương Kahn [KA 67], Koblit[Ko 87], Konheim[Ko 81], Kranakis[Kr 86], Merezes[Me 93], Meyer và Matyas[MM 82], Patterson [Pa 87], Pomerance[Po 90A], Rueppel [Ru 86], Salomaa[Sa 90], Schneier[Sc 93], Seberry và Pieprzk[SP 89], Simmons [Si 92B], van Tilborg [vT 88] và Welsh [We 88]. Bạn đọc nên đọc thêm một số giao trình và sách chuyên khảo khác về mật mã học sau đây: BecKer và Piper [BP 93], Beutelspacher[Be 94], Brassard[Br 88], Biham và Shamir[BS 93], Denning[De 82], Các tạp chí nghiên cứu chủ yếu trong mật mã học là Journal of Cryptology và Designs, Codes and Cryptography. Journal of Cryptography là tạp chí của Hiệp hội nghiên cứu mật mã quốc tế (IACR). Hiệp hội này cũng tái trợ hai Hội nghị chính về mật mã học đ−ợc tổ chức hàng năm là CRYPTO và EUROCRYPT. CRYPTO đã đựoc tổ chức từ năm 1981 ở Santa Barabara. Các báo cáo khoa học ở CRYPTO đã đ−ợc xuất bản hàng năm đáng kể từ 1982: CRYPTO’ 82[CRS 83] , CRYPTO’ 83[CH 84], CRYPTO’ 84[BC 85] CRYPTO’ 85[WI 96], CRYPTO’ 86[Oo 87], CRYPTO’ [Po 88] CRYPTO’ 88[Go 90], CRYPTO’ 89[BR 90], CRYPTO’ 90[MV 91] CRYPTO’ 9[FE 92], CRYPTO’ 92[BR 93], CRYPTO’ 93[ST 94] Và CRYPTO’ 94[DE 94]. EUROCRYPT đã đ−ợc tổ chức hàng năm kể từ năm 1982 (trừ các năm 1983 và 1986), các bái báo khoa học đã công bố gồm: EUROCRYPT’ 82[BE 83], EUROCRYPT’ 84[BCI 85], EUROCRYPT’ 85[PX86], EUROCRYPT’ 87[CP 88], EUROCRYPT’ 88[GU 88A], EUROCRYPT’ 90[DA 91], EUROCRYPT’ 91[DA 91A], EUROCRYPT’ 92[RU 93] và EUROCRYPT’ 93[HE 94]. Loại hội nghị thứ ba là AUCRYPT / ASIACRYPT đã đ−ợc tổ chức với sự kết hợp của IACR. Các báo cáo khoa học đã đ−ợc xuất bản bao gồm AUCRYPT’ 90[SP90], ASIACRYPT’ 91[IRM 93] và AUCRYPT’ 92[SZ92] Trang 30