21.02.14: Teorio-informacyjnie bezpieczne obliczenia wielopodmiotowe

Zajęcia zaczęliśmy od krótkiego powtórzenia zagadnień związanych z obliczeniami dwu-podmiotowymi, patrz:

• Two-Party Computation Protocols [pptx,pdf] (slajdy 3-5)

Potem mówiliśmy o obliczeniach wielopodmiotowych, patrz:

• Multiparty Computation Protocols [pptx,pdf] (w zasadzie całość, choć w trochę innej kolejności), oraz
• wykład Benny'ego Pinkasa [pdf,video] (slajdy 1-20, bez dowodów).

Znacznie formalniej i dokładniej materiał ten jest przedstawiony w 

• Gilad Asharov and Yehuda Lindell A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation [pdf]

Potem zrobilśmy zadanie, które można z grubsza streścić: 

Pokaż przykład protokołu obliczeń wielopodmiotowych który jest bezpieczny nieadaptywnie, ale nie jest bezpieczny adaptywnie.

A następnie pokazaliśmy, że funkcji AND nie da się teorio-informacyjnie bezpiecznie policzyć przy $t=n/2$ korupcjach, dla dowolnego $n$, o ile ten fakt zachodzi dla $n=2$. Przypadek $n=2$ został jako zadanie domowe.