Cryptography II

Dan Boneh’nin kriptografi üzerine yayınladığı dersler devam ediyor. Şifreleme sistemlerine geçmeden önce hızlı bir Discrete Probability dersi verdi. Yaklaşık yarım saatlik bu dersin sonlarına doğru iki teorem inanılmaz ilgimi çekti. Dolayısıyla bunları paylaşmak istiyorum:

An important property of XOR

XOR işlemi yuvarlak içine alınmış artı işaretiyle gösteriliyor. Bitwise olarak truth table’ı şu şekilde:

xor-tableDiscrete Probability’den konuşurken random variable, uniform variable ve independence gibi terimleri ve ne anlama geldiklerini bilmek gerekiyor. Bu terimleri uzun uzun anlatacak kadar zamanım ve bilgim yok. Altta kısaca bahsedeceğim ama yine de terimleri bildiğinizi varsayıyorum. Eğer bilmiyorsanız ve yazının devamını okumak istiyorsanız, tavsiyem wikipedia üzerinden bu terimlere bir göz atmanız.

Teorem diyor ki;

Y {0,1}^n üzerinde bir random variable olsun.
X {0,1}^n üzerinde bir independent uniform variable olsun.

Yani Y’nin alacağı distribution değerlerini bilmiyoruz ama X’inkileri (uniform olduğu için) biliyoruz.

Öyle ki, Z = Y xor X {0,1}^n üzerinde bir uniform variable’dır. Yani Y’nin dağılımı ne olursa olsun, Z’yi etkilemiyor.

Bunun kanıtını da n=1 için yapalım; n=1 için Y’nin de X’in de alabileceği ikişer değer var: Bunlar 0 ve 1.

Y’nin 0 olma olasılığına P0, 1 olma olasılığına P1 diyelim.
X’in uniform olması, bizi X’in 0 olma olasılığının da 1 olma olasılığının da 1/2 olduğu gerçeğine götürüyor.

Şimdi Z’nin değerlerini hesaplayalım. Z’nin alabileceği iki değer var: Bunlar 0 ve 1. X’in dağılımındaki değerler birbirinden farklı oldukları için (independence), Y xor X’in sonucuna olasılıkların çarpımlarıyla ulaşabiliyoruz. Yani;

Y=0, X=0 için Pr[Z]=P0/2
Y=0, X=1 için Pr[Z]=P0/2
Y=1, X=0 için Pr[Z]=P1/2
Y=1, X=1 için Pr[Z]=P1/2

Bu noktada tamamen bizim tercihimize bağlı olarak, Z’nin 0 olduğu olasılığı bulalım. Z’nin 0 olması için (x,y) = (0,0) veya (x,y) = (1,1) olması gerekiyor. Öyleyse Pr[Z=0] = P0/2 + P1/2 = (P0+P1) / 2.

Y’nin 0 olma olasılığına P0, 1 olma olasılığına P1 demiştik. Yani P0+P1=1 olmalı. Bu durumda Pr[Z=0] = 1/2 çıkıyor. Aynı şekilde Pr[Z=1] = 1/2 çıkıyor. Biz de Z’nin uniform variable olduğunu görmüş oluyoruz.

The birthday paradox

Bir diğer özellik ise, doğum günü paradoksu. Teorem diyor ki:

U adında bir universe belirleyelim ve bu universe’ün 1’den n’e kadar giden r1, r2, …, rn şeklinde independent ve identically distributed random variableları olsun. |U|’ya U’nun boyutu dersek,

n = 1.2 * |U|^(1/2) olursa, birbirine eşit olmayan i ve j için ri ve rj variablelarının eşit olma olasılığı 1/2’den fazladır. Bunu söze dökecek olursak, bu U içerisinde n’i hesaplayacağız ve eğer U’da n kadar eleman varsa, bu iki elemanın değerinin ya da bu iki kişinin doğum gününün aynı olma olasılığı oldukça yüksektir.

Bu teoremi ilkokulda bile gösterilen kesinlik ilkesine bağlayacak olursak, aslında bu doğum günü işini oldukça eksik öğrendiğimizi görüyoruz. Bir yıl 365 gün ve eğer ortamad 366 kişi varsa en az iki kişinin doğum günü kesinlikle aynıdır deriz. Ancak bu teoreme göre |U|=365’ten n yaklaşık olarak 24 çıkıyor. Yani teoreme göre ortamda 24 kişi varsa, bu 24 kişinin en az ikisinin doğum günlerinin aynı olması kesin değil ama yüksek ihtimal.

 

Leave a Reply