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

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.
Nội dung trích xuất từ tài liệu:
Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 4Vietebooks 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étc¸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Çucñ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Ðpchøng minh kh«ng tiÕt lé th«ng tin hoµn thiÖn, ®©y lµ mét phÐp chøng minhcho 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¸nnµ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µnthiÖ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 xemxÐ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 16Vietebooks 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 α,β∈Zn trong ®ã 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 : 2. Peggy chän mét sè ngÉu nhiªn j sao chi 0≤ j ≤ l - 1 vµ tÝnh γ = αjmod 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èngchø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 tinhoµ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èngchø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étkÐt s¾t mµ c« ta biÕt m· sè. Sau ®ã Peggy trao kÐt s¾t cho Vic. MÆc dï Vickh«ng biÕt th«ng b¸o lµ g× cho tíi khi kÐt ®−îc më nh−ng ta sÏ coi r»ngPeggy ®· 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Ënt−¬ng tù ë ch−¬ng 4 ®Ó m« t¶ ý t−ëng vÒ mét hÖ mËt c«ng khai, tuy nhiªntrong tr−êng hîp ®ã Vic lµ ng−êi cã thÓ më kÐt bëi v× anh ta lµ ng−êi nhËnth«ng b¸o ). Trang 17Vietebooks 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éthµ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×nhthø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ÊtGoldwasser - 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µ ...