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

Kategori:Şifreleme protokolleri