Oblivius – feledékeny

– bizonytalan

2–OT : 2–bizonytalan transzfer

– két játékos van

– van egy fekete doboz, ami a bizonytalan transzfert megcsinálja

b₀ , b₁,

K 2–OT F_sÎ{0,1}

b_s

Küldő:

b₀ , b₁ bitek

Fogadó:

Elküldi a doboznak, hogya b₀ vagy a b₁ bitre kiváncsi

– Ha a doboz jól működik, akkor a fogadó játékos biztos lehet benne, hogy azt kapta, amit kért, a küldő pedig nem tudja, hogy a fogadó melyiket kérte.

K–nak biztonságos: F maximum azt egyik bitet tudja meg, a másikról nem tud semmit

F–nek biztonságos: K nem tud semmit sem az s-ről

1–OT : 1–bizonytalan transzfer

b b

K 1–OT ½-ed valószínüséggel kapja meg

?

K–nak biztonságos: ½-ed valószínüséggeltudja meg, mit kap F

F–nek biztonságos: K-nak fogalma sincs, hogy b-t kapta-e meg

Példa 1–OT –re:

ötlet: n = p· q p, q: prímszámok; n: ismert

x² º a (mod n) ha (a,n)=1, akkor ennek a kongruenciának 4 megoldása van

x² º y² (mod n) és x ¹ ±y, akkor n prímtényezőkre bontható

(n, x-y)(n, x+y): n prímtényezős felbontása

Protokoll:

Küldő ismeri a p,q-t, titkos bit (pl) p és q-ban található 1-esek paritása

Fogadó ismeri a (p×q)-t, de a titkos bithez isnernie kellene a prímtényezőt

n=p×q

K ⁿ F

F választ r véletlen számot, négyzetre emeli a=r² (mod n)

K ^r2 F

Megjegyzés:

K:

és

u,v: pv+qu=-1 ® Euklideszi algoritmus

I: MO: -qu

II: MO: -pv

Euklideszi algoritmus:

(x,y) ® (n,v) xu+yv=(xy) lnko

ha x>y ® E(y,x)

ha x=y ® u=1 v=0

ha x<y ha x=0 (0,y)=y=0x+1y ® u=0 v=1

ha 0<x<y (u¢, v¢)=E(x,y-x)

xu¢+(y-x)v¢=(x,y) ® (u¢v¢, u¢)

F nem tudja meg p,q-t, ennek ½-ed valószínüsége

K: x₁, x₂, x₃, x₄:

F ki tudja számítani a p,q-t , ennek ½-ed valószínüsége

ki tudja számítani a titkos bitet

F-nek feltétlen biztonságos, K-nak szűámításilag biztonságos.

ÁLL.: Ha az egyik (1-OT vagy 2-OT) létezik, akkor a másik is létezik.

Biz:

(1) 2–OT 1–OT

a bit b=b₀ Å b₁ : b₀, b₁, véletlen

b₀ , b₁,

K 2–OT F_sÎ{0,1}

b_s

K (i, b_i) F

i véletlen i¹s

- ha a küldő a másikat mondta, mint amit F kapott, akkor b_iÅ b_s =b a titkos bit

- ha s=i F nem tud semmit

K-nak biztonságos, F ½-ed valószínüséggel nem tudja meg a kívánt bitet

(2) 1–OT 2–OT

K választ c₁, c₂ c₃ . . . . c_k véletlen biteket

c₁ ½ valószínűséggel P(F mindegyiket tudja )=( ½ )^K elég kicsi

c₁ 1–OT

? ½ valószínűséggel

c₂ ½ valószínűséggel P(F nem tud semmit sem )=( ½ )^K elég kicsi

c₂ 1–OT

? ½ valószínűséggel

.

.

.

c_k ½ valószínűséggel

c_k 1–OT

? ½ valószínűséggel

F ezen c-ket tudta meg, vagy ezen halmaz komplementerét

IÍ{1,2, . . ,k} I¹0

I^C¹0

K F

Milliomos játék: két milliomos van, meg akarják tudni, hogy ki a gazdagabb, anélkül, hogy bármelyik is elárulná mennyi vagyona van.

Oblivus: Nem lehet megcsinálni, hogy K-nak és F-nek is teljesen biztonságos legyen.

A és B résztvevők

A inputja: x

B inputja: y

fix hosszúságú bitsorozat, f kapcsolási rajzzal van megadva

x y

Å Å Å Å Å Å

összeadó kapuk

negáló kapuk

szorzó kapuk

így minden polinom leírható

Feladat:

ennek a hálózatnak a felső csúcsán lévő értékeket mindketten meg tudják, de azt, hogy mi volt a másik személyes inputja azt egyik se tudja meg.

Titokszétosztás: nincsennek magánbitek szétosztjuk az inputot

A-nak x_i-az inputja választ egy rÎ{0,1} véletlen számot

A x_iÅr ^{( i, r )} B

változók: x_a, x_b

igazi érték: x_a Å x_b

Kiszámítják privátilag a saját fájukon lévő értéket és elküldik a tetején lévő értéket a másiknak

xa	xb		Eredeti
Ha xa az egyik megváltozik (A)	xb
Ha xa	xb
xa xb	ya yb
xa ya : 2-OT s,s+ xa ya A 2-OT		(xa+xb)( ya+yb)= xaya + xayb + xbya + xbyb s(1+ ya)+(s+ xa) ya = s+s ya+s ya+ xa ya= s + xa ya A: s-t megjegyzi B: s + xa ya megjegyzi