zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Hệ điều hành

Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 6

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

63
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 6

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
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
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: Vic chén mét sè ngÉu nhiªn v∈Zn* vµ tÝnh 1 2. 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 NÕu z ∈ QR(n) th× Peggy x¸c ®Þnh j= 0, ng−îc l¹i Peggy 3. 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
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 ∈ QP(n), i=0 hoÆc 1, z∈Zn* vµ z2 ≡ xiy (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 ®ã γ ∈ Zn , i = 0 hoÆc 1, 0 ≤ h ≤ l – 1 vµ αh ≡ βi γ (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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.