Yemek kriptografı sorunu - Dining cryptographers problem

Kriptografide, yemek kriptografı sorunu nasıl yapılacağını inceler güvenli çok partili hesaplama boole-OR işlevinin. David Chaum Bu sorunu ilk olarak 1980'lerin başında önermiş ve koşulsuz gönderen ve alıcının izlenemeyen anonim mesajlar göndermenin mümkün olduğunu göstermek için açıklayıcı bir örnek olarak kullanmıştır. Bu soruna dayanan anonim iletişim ağlarına genellikle DC ağları (burada DC, "yemek şifrelemecileri" anlamına gelir).^[1]

Söze rağmen yemekyemek kriptografları sorunu, yemek filozofları sorunu.

Açıklama

Yemek kriptografları sorun illüstrasyon

Üç kriptograf akşam yemeği için bir masanın etrafında toplanıyor. Garson, yemeğin kriptograflardan biri veya başka biri tarafından ödendiğini bildirir. Ulusal Güvenlik Ajansı (NSA). Kriptograflar, birbirlerinin isimsiz ödeme yapma hakkına saygı duyarlar, ancak NSA'nın ödeme yapıp yapmadığını öğrenmek isterler. Bu yüzden iki aşamalı bir protokol uygulamaya karar verirler.

İlk aşamada, her iki kriptograf, örneğin bir menünün arkasına bir bozuk para atarak, her iki kriptograf için sonucu yalnızca iki kriptografın görebilmesi için paylaşılan bir bitlik sır oluşturur. Örneğin, yazı tura attıktan sonra, kriptograf A ve B'nin gizli bir bit paylaştığını varsayalım. ${displaystyle 1}$, A ve C paylaşımı ${displaystyle 0}$ve B ve C paylaşımı ${displaystyle 1}$.

İkinci aşamada, her bir kriptograf bir kısmı kamuoyuna duyurur:

• yemek için ödeme yapmazlarsa, özel veya İki komşusuyla tuttukları paylaşılan iki bitten (XOR),
• yemek için ödeme yaptılarsa, bu XOR'un tersi.

Kriptograflardan hiçbirinin ödeme yapmadığını varsayarsak, A duyurur ${displaystyle 1oplus 0 = 1}$, B duyurur ${displaystyle 1oplus 1 = 0}$ve C duyurur ${displaystyle 0oplus 1 = 1}$. Öte yandan, eğer A ödeme yaparsa duyurur ${displaystyle lnot (1oplus 0) = 0}$.

Üç halka açık duyuru, sorularının cevabını ortaya koyuyor. Biri basitçe açıklanan üç bitin XOR'unu hesaplar. Sonuç 0 ise, kriptograflardan hiçbirinin ödeme yapmadığı anlamına gelir (bu nedenle NSA faturayı ödemiş olmalıdır). Aksi takdirde, kriptograflardan biri ödeme yapar, ancak kimlikleri diğer kriptograflar tarafından bilinmez.

David Chaum terimi icat etti yemek şifreleme ağıveya DC-net, bu protokol için.

Sınırlamalar

DC-net protokolü basit ve zariftir. Birkaç sınırlaması vardır, ancak, takip araştırmasında araştırılan bazı çözümler (aşağıdaki Referanslar bölümüne bakın).

Çarpışma

Akşam yemeği için iki kriptograf ödeme yaparsa, mesajları birbirini iptal edecek ve son XOR sonucu ${displaystyle 0}$. Buna çarpışma denir ve bu protokolü kullanarak bir seferde yalnızca bir katılımcının iletim yapmasına izin verir. Daha genel bir durumda, herhangi bir çift sayıda katılımcı mesaj gönderdiği sürece bir çarpışma olur.

Bozulma

Grubun başarılı bir şekilde iletişim kurmasını istemeyen herhangi bir kötü niyetli kriptograf, XOR'un doğru sonucu yerine rastgele bitler göndererek nihai XOR sonucunun işe yaramaz olması için protokolü bozabilir. Bu sorun, orijinal protokolün herhangi bir Genel anahtar teknoloji ve katılımcıların protokolü dürüstçe takip edip etmediğini kontrol etmek için güvenilir mekanizmalardan yoksundur.^[2]

Karmaşıklık

Protokol, katılımcılar arasında ikili olarak paylaşılan gizli anahtarlar gerektirir ve bu, çok sayıda katılımcı varsa sorunlu olabilir. Ayrıca, DC-net protokolü "koşulsuz olarak güvenli" olsa da, gerçekte katılımcı çiftleri arasında zaten "koşulsuz olarak güvenli" kanalların mevcut olduğu varsayımına bağlıdır, bu pratikte elde edilmesi kolay değildir.

İlgili anonim veto ağı algoritması, bir mantıksal VEYA birleştirme işleminin doğal olarak uygun olduğu uygulamalarda yararlı olabilen, DC ağlarında olduğu gibi mantıksal bir XOR yerine birkaç kullanıcının girişlerinin mantıksal OR'sini hesaplar.

Tarih

David Chaum ilk olarak 1980'lerin başında bu sorunu düşündüm. Temel fikirlerin ana hatlarını çizen ilk yayın onun.^[3] Dergi sürümü, Journal of Cryptology'nin ilk sayısında yayınlandı.^[4]

Genellemeler

DC ağları, aşağıda açıklandığı gibi, üç katılımcıdan büyük gruplar için ve 0 ve 1 ikili rakamları dışındaki rastgele "alfabeler" için tur başına birden fazla bitlik iletimlere izin verecek şekilde kolayca genelleştirilir.

Daha uzun mesajların iletimi

Anonim bir göndericinin, DC ağları turu başına birden fazla bit bilgi iletmesini sağlamak için, kriptograflar grubu, protokolü, istenen sayıda bit değerinde iletim bant genişliği oluşturmak için basitçe istendiği kadar tekrar edebilir. Bu tekrarların seri olarak yapılması gerekmez. Pratik DC-net sistemlerinde, katılımcı çiftlerinin tek bir paylaşılan "ana" sır üzerinde önceden anlaşması tipiktir. Diffie – Hellman anahtar değişimi Örneğin. Daha sonra her katılımcı bu paylaşılan ana sırrı yerel olarak bir sözde rasgele sayı üreteci anonim bir göndericinin çok sayıda bilgi bitini iletmesine izin vermek için istenildiği kadar çok sayıda paylaşılan "yazı tura atma" üretmek için.

Daha büyük grup boyutları

Protokol bir grup olarak genelleştirilebilir ${displaystyle n}$ katılımcılar, her biri diğer katılımcılarla ortak olarak paylaşılan bir gizli anahtara sahiptir. Protokolün her turunda, bir katılımcı gruba izlenemeyen bir mesaj göndermek isterse, kamuya duyurulan bitini tersine çevirir. Katılımcılar şu şekilde görselleştirilebilir: tam bağlantılı grafik katılımcıları temsil eden köşeler ve paylaşılan gizli anahtarları temsil eden kenarlar.

Seyrek gizli paylaşım grafikleri

Protokol, katılımcıların gizli paylaşım grafiğini ayrı bağlı bileşenlere bölebilmesi durumunda anonimliğin azaltılması riski altında, pratik DC-net uygulamalarının performansını ve ölçeklenebilirliğini artırabilen, tam bağlı olmayan gizli paylaşım grafikleri ile çalıştırılabilir. Örneğin, sezgisel olarak çekici ancak daha az güvenli bir genelleme ${displaystyle n> 3}$ kullanan katılımcılar halka topolojisi, bir masanın etrafında oturan her kriptografın bir sırrı paylaştığı sadece kriptografın hemen solunda ve sağında ve değil diğer tüm kriptograflarla. Böyle bir topoloji çekicidir çünkü her kriptografın, her turda iki jeton çevirme koordine etmesi gerekir. ${displaystyle n}$. Bununla birlikte, Adam ve Charlie aslında masum bir kurban olan Bob'un hemen solunda ve sağında oturan NSA ajanlarıysa ve Adam ve Charlie sırlarını birbirlerine açıklamak için gizlice işbirliği yaparlarsa, Bob'un olup olmadığını kesin olarak belirleyebilirler. toplamda kaç katılımcı olduğuna bakılmaksızın, bir DC-net çalışmasında 1 bitin göndereni. Bunun nedeni, gizli paylaşım grafiğini, gizli paylaşım grafiğini, biri yalnızca Bob'u, diğeri ise diğer tüm dürüst katılımcıları içeren iki ayrı bileşene etkili bir şekilde "böldüğü", ortaklaşa çalışan katılımcılardan olmasıdır.

DC-net topolojisini paylaşan başka bir uzlaşma sırrı, Muhalif ölçeklenebilirlik sistemi,^[5] olarak tanımlanabilir müşteri sunucusu veya kullanıcı / güvenilir topoloji. Bu varyantta, farklı roller oynayan iki tür katılımcı olduğunu varsayıyoruz: potansiyel olarak çok sayıda n anonimlik isteyen ve çok daha az sayıda kullanıcı ${displaystyle m}$ nın-nin vekiller Kimin rolü, kullanıcıların bu anonimliği elde etmelerine yardımcı olmaktır. Bu topolojide, her biri ${displaystyle n}$ kullanıcılar her biriyle bir sır paylaşır ${displaystyle m}$ mütevelliler — ancak kullanıcılar sırları doğrudan diğer kullanıcılarla paylaşmazlar ve mütevelliler sırları doğrudan diğer mütevellilerle paylaşmazlar. ${displaystyle n imes m}$ gizli paylaşım matrisi. Mütevelli sayısı ${displaystyle m}$ küçüktür, bu durumda her kullanıcının yalnızca birkaç paylaşılan sırrı yönetmesi gerekir ve bu da halka topolojisinin yaptığı gibi kullanıcılar için verimliliği artırır. Ancak, olduğu sürece en az bir mütevelli Dürüst davranır ve sırlarını sızdırmaz veya diğer katılımcılarla işbirliği yapmazsa, bu dürüst yediemin, hangi veya kaç başka kullanıcı ve / veya mütevelli olabileceğine bakılmaksızın, tüm dürüst kullanıcıları tek bir tam bağlantılı bileşene bağlayan bir "merkez" oluşturur dürüst olmayan bir şekilde gizli anlaşma. Kullanıcıların hangi güvenilir kişinin dürüst olduğunu bilmesine veya tahmin etmesine gerek yoktur; onların güvenliği sadece şuna bağlıdır varoluş en az bir dürüst, gizli mütevelli heyeti.

Alternatif alfabeler ve birleştirme operatörleri

Basit DC ağları protokolü kullansa da ikili rakamlar iletim alfabesi olarak ve şifreleme metinlerini birleştirmek için XOR operatörünü kullanır, temel protokol herhangi bir alfabeye genelleştirir ve operatörü uygun olan Bir defalık ped şifreleme. Bu esneklik, birçok katılımcı çifti arasında paylaşılan sırların aslında tek bir DC-net turunda simetrik olarak bir araya getirilen yalnızca tek seferlik pedler olduğu gerçeğinden doğar.

DC ağları alfabesi ve birleştirme operatörünün kullanışlı bir alternatif seçimi, bir sonlu grup alfabe gibi açık anahtarlı kriptografi için uygundur - örneğin Schnorr grubu veya eliptik eğri - ve ilişkili grup operatörünü DC-ağ birleştirme operatörü olarak kullanmak. Böyle bir alfabe ve operatör seçimi, müşterilerin kullanmasını mümkün kılar sıfır bilgi kanıtı Katılımcının, DC-ağ tarafından sunulan anonimlikten ödün vermeden iletim kanalını "karıştırmaması" gibi ürettikleri DC-ağ şifreleme metinleri hakkında doğruluk özelliklerini kanıtlama teknikleri. Bu teknik ilk olarak Golle ve Juels tarafından önerildi,^[6] Franck tarafından daha da geliştirildi,^[7] ve daha sonra Karar, kriptografik olarak doğrulanabilir bir uygulama Muhalif sistemi.^[8]

Çarpışmaları idare etmek veya önlemek

Çarpışmaları önlemek için David Chaum tarafından başlangıçta önerilen önlem, bir çarpışma tespit edildiğinde mesajı yeniden iletmektir, ancak makale yeniden iletimin nasıl düzenleneceğini tam olarak açıklamamaktadır.

Muhalif DC ağları iletim programı oluşturmak için doğrulanabilir bir karıştırma kullanarak kasıtsız çarpışma olasılığını ortadan kaldırır, öyle ki her bir katılımcı programdaki hangi bitlerin kendi iletim yuvasına karşılık geldiğini tam olarak bilir, ancak diğer iletim yuvalarına kimin sahip olduğunu bilmez.^[9]

Yıkıcı saldırılara karşı koymak

Otçul Büyük bir anonimlik ağını daha küçük DC-ağ gruplarına bölerek katılımcıların kesintiye uğramış bir gruptan ayrılıp başka bir gruba katılarak kesinti girişimlerinden kaçınmasını sağlar, ta ki katılımcı engelsiz bir grup bulana kadar.^[10] Bu kaçınma yaklaşımı, çok sayıda düğüme sahip bir düşmanın seçici olarak sadece düşmanın sahip olmadığı grupları bozun tamamen tehlikeye atılır, böylece katılımcıları, tamamen tehlikeye atıldıkları için işlevsel olabilecek gruplara doğru "yönlendirir".^[11]

Muhalif kesintiye karşı koymak için çeşitli planlar uygular. Orijinal protokol^[9] doğrulanabilir bir kriptografik karıştırma bir DC-net iletim çizelgesi oluşturmak ve "iletim atamalarını" dağıtmak, sonraki DC ağ şifrelerinin doğruluğunun basit bir şekilde doğrulanmasını sağlamak kriptografik karma Kontrol. Bu teknik, her DC ağ turundan önce doğrulanabilir yeni bir teknik gerektirdi, ancak yüksek gecikmelere yol açtı. Daha sonraki, daha verimli bir şema, kesinti olmadığında karıştırmalara müdahale etmeden bir dizi DC-net turunun ilerlemesine izin verir, ancak bir kesinti olayına yanıt olarak anonim dağıtmak için bir karıştırma kullanır suçlamalar Bir aksaklık mağdurunun failin kimliğini ifşa etmesini ve kanıtlamasını sağlamak.^[5] Son olarak, daha yeni sürümler, tamamen doğrulanabilir DC ağlarını destekler - kullanımı nedeniyle hesaplama verimliliğinde önemli bir maliyetle açık anahtarlı şifreleme DC ağında - hem de melez Normal durumda verimli XOR tabanlı DC ağlarını ve yalnızca kesinti durumunda doğrulanabilir DC ağlarını kullanan, suçlamaları doğrulanabilir karıştırmalar kullanılarak mümkün olandan daha hızlı dağıtmak için.^[8]

Referanslar