Yao'nun milyoner problemi

Vikipedi, özgür ansiklopedi

Yao'nun Milyoner Problemi, Andrew Yao tarafından güvenli çoklu iletişim sorunu olarak ortaya konulmuştur.Problem iki milyoner olan Alice ve Bob'un, birbirlerine ne kadar paraları olduğunu söylemeden hangisinin daha zengin olduğunu öğrenmeye çalışmasıdır.

Problem aslında iki sayının değerlerini bilmeden bir biriyle kıyaslanmasıdır. Milyoner Problemi çok kullanıcılı iletişim güvenliğine (SMPC) örnektir ve kriptoloji için önemlidir.

ÖRNEK[değiştir | kaynağı değiştir]

Alice 5 milyona sahip , ve Bob 6 milyona sahiptir. Alice'in sahip olduğu parayı "A" ile , Bob'un sahip olduğu parayı "B" ile iç gösterelim. Alice RSA açık anahtarlı şifreleme sistemin kullanmakta ve açık anahtarı (79,3337) kapalı anahtarı 1019'dur.

A=5 , B=6
1.Adım[değiştir | kaynağı değiştir]

Bob rastgele bir 'x' sayısı seçsin ve bunu Alice gönderir.Alice gelen x sayısını RSA ile şifreler ve çıkan 'c' sonucunu Bob'a geri gönderir.

x=1234 
c=1234^79mod3337=901
2.Adım[değiştir | kaynağı değiştir]

Bob Alice'den c sayısını alır ve bundan kendi para miktarını çıkartır (6 milyonu 6 olarak kabul ediyoruz). ve bir ekler. Çıkan sonucu Alice gönderir.

901-6+1=896
3.Adım[değiştir | kaynağı değiştir]

Alice gelen sonucu birer farkla ardaşık bir seri olacak şekilde toplama işlemi yapar.Yeni oluşan seriyi sırasıyla RSA ile deşifreler ve yeni sonucu YN şeklinde gösterir.Çıkan sonuçların tamamını Bob'a gönderir.Bob kendi sayısı 6 olduğu için 6. sayıya bakar.6. sayının değişmediğini gören Bob , Alice parasının kendi parasından az olduğunu görür.Böylece Alice ve Bob birbirlerinin parasını bilmeden hangisinin daha zengin olduğunu öğrenmiş olur.

N (C-B+N) RSA Fonksyonu YN
1 896 896^1019 mod 3337 1059
2 897 897^1019 mod 3337 1156
3 898 898^1019 mod 3337 2502
4 899 899^1019 mod 3337 2918
5 900 900^1019 mod 3337 385
6 901 901^1019 mod 3337 1234
7 902 902^1019 mod 3337 296
8 903 903^1019 mod 3337 1596
9 904 904^1019 mod 3337 2804
10 905 905^1019 mod 3337 1311