Karar Diffie-Hellman varsayımı - Decisional Diffie–Hellman assumption

karar Diffie – Hellman (GKD) varsayımı bir hesaplamalı sertlik varsayımı ilgili belirli bir problem hakkında ayrık logaritmalar içinde döngüsel gruplar. Birçok kişinin güvenliğini kanıtlamak için temel olarak kullanılır. kriptografik protokoller, en önemlisi ElGamal ve Cramer – Shoup şifreleme sistemleri.

Tanım

Bir (çarpımsal) düşünün döngüsel grup düzenin , Ve birlikte jeneratör . GKD varsayımı, verilen ve tek tip ve bağımsız olarak seçilenler için , değer rastgele bir öğe "gibi görünür" .

Bu sezgisel kavram, aşağıdaki iki olasılık dağılımının şu şekilde olduğunu söyleyerek resmi olarak ifade edilebilir: sayısal olarak ayırt edilemez (içinde güvenlik parametresi, ):

  • , nerede ve rastgele ve bağımsız olarak seçilir .
  • , nerede rastgele ve bağımsız olarak seçilir .

Birinci türden üçlüler genellikle denir GKD üçlüsü veya DDH listeleri.

Diğer varsayımlarla ilişki

GKD varsayımı, ayrık günlük varsayımı. Ayrık günlükleri verimli bir şekilde hesaplamak mümkün olsaydı , bu durumda GKD varsayımı geçerli olmaz . Verilen verimli bir şekilde karar verebilir önce ayrık olanı alarak nın-nin ve sonra karşılaştırma ile .

GKD, bir Daha güçlü ayrık logaritma varsayımından daha fazla varsayım, çünkü ayrı günlükleri hesaplamanın zor olduğuna inanılan gruplar vardır (Ve bu nedenle DL Varsayımının doğru olduğuna inanılmaktadır), ancak GKD kayıtlarını saptamak kolaydır (Ve dolayısıyla GKD yanlıştır). Bu nedenle, bir grupta GKD varsayımının geçerli olmasını gerektirmenin, DL'den daha kısıtlayıcı bir gereksinim olduğuna inanılmaktadır.

GKD varsayımı aynı zamanda hesaplamalı Diffie – Hellman varsayımı (CDH). Verimli bir şekilde hesaplamak mümkün olsaydı itibaren , o zaman yukarıdaki iki olasılık dağılımı kolayca ayırt edilebilir. Yukarıdakine benzer şekilde, GKD, CDH'den daha güçlü bir varsayım olarak kabul edilir.

Diğer özellikler

GKD kayıtlarını tespit etme sorunu şudur: rastgele kendi kendine indirgenebilir yani, kabaca, küçük bir girdi fraksiyonu için bile zorsa, hemen hemen tüm girdiler için zordur; küçük bir girdi fraksiyonu için bile kolaysa, hemen hemen tüm girdiler için kolaydır.

GGD'nin tutulacağı varsayılan gruplar

Güvenliği GKD varsayımına bağlı olan bir şifreleme protokolü kullanırken, protokolün GKD'nin tuttuğuna inanılan gruplar kullanılarak uygulanması önemlidir:

  • Alt grubu kalıntılar modülo a asal , nerede aynı zamanda büyük bir asaldır (a Schnorr grubu ). Durum için , bu gruba karşılık gelir ikinci dereceden kalıntılar modulo a güvenli asal.
  • Bir ana sipariş eliptik eğri üzerinde alan , nerede asaldır büyük gömme derecesine sahiptir.
  • Bir Jacobian bir hiper eliptik eğri üzerinde alan asal sayıda indirgenmiş bölenlerle, Jacobian'ın büyük gömme derecesine sahip olması şartıyla asaldır.

Önemlisi, GKD varsayımı tutmaz çarpımsal grupta , nerede asal. Çünkü eğer bir jeneratör , sonra Legendre sembolü nın-nin eğer ortaya çıkar çift ​​veya tek. Verilen , ve , böylelikle en az anlamlı biti verimli bir şekilde hesaplayabilir ve karşılaştırabilir , ve sırasıyla, ayırt etmek için olasılıklı bir yöntem sağlar rastgele bir grup elemanından.

GKD varsayımı, eliptik eğrilerde geçerli değildir. küçük gömme derecesi ile (diyelim, daha az ), içeren bir sınıf supersingular eliptik eğriler. Bunun nedeni Weil eşleştirme veya Tate eşleştirme sorunu doğrudan şu şekilde çözmek için kullanılabilir: böyle bir eğri üzerinde hesaplanabilir ve . Eşleştirmelerin çift doğrusallığına göre, iki ifade eşittir ancak ve ancak sırasını değiştirmek . Gömme derecesi büyükse (örneğin ) bu durumda GGD varsayımı hala geçerli olacaktır çünkü eşleştirme hesaplanamaz. Gömme derecesi küçük olsa bile, DDH varsayımının geçerli olduğuna inanılan eğrinin bazı alt grupları vardır.

Ayrıca bakınız

Referanslar

  • Boneh, Dan (1998). Karar Diffie-Hellman Problemi. Üçüncü Algoritmik Sayılar Teorisi Sempozyumu Bildiriler Kitabı. Bilgisayar Bilimlerinde Ders Notları. 1423. sayfa 48–63. CiteSeerX  10.1.1.461.9971. doi:10.1007 / BFb0054851. ISBN  978-3-540-64657-0.