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

Vietebooks Nguyễn Hoàng Cương

Trang 26

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) =mb

x2

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αβ.