Yao'nun milyoner problemi
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
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
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
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
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 |