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