Pençesiz permütasyon - Claw-free permutation

İçinde matematiksel ve bilgisayar Bilimi alanı kriptografi, üç sayılık bir grup (x,y,z) olduğu söyleniyor pençe iki permütasyon f0 ve f1 Eğer

f0(x) = f1(y) = z.

Bir çift permütasyon f0 ve f1 Olduğu söyleniyor pençesiz pençe hesaplamak için etkili bir algoritma yoksa.

Terminoloji pençesiz Goldwasser, Micali ve Rivest tarafından 1984 tarihli "A Paradoxical Solution to the Signature Problem" (ve daha sonra daha eksiksiz bir dergi makalesinde) ile tanıtıldı ve burada pençesiz trapdoor permütasyon çiftleri dijital imza şemalarının varlığını ima eder. uyarlanabilir seçilmiş mesaj saldırısı.[1][2] Bu yapının yerini daha sonra herhangi bir tek yönlü tuzak kapısı permütasyonundan dijital imzaların oluşturulması aldı.[3] Varoluşu trapdoor permütasyonları kendi başına pençesiz permütasyonların var olduğu anlamına gelmez;[4] ancak, faktoring zorsa pençesiz permütasyonların var olduğu gösterilmiştir.[5]

Pençesiz permütasyonun genel kavramı (zorunlu olarak tuzak kapısı olması gerekmez) Ivan Damgård doktora tezinde Kriptografide Pençesiz Fonksiyonların Uygulanması (Aarhus Üniversitesi, 1988), nasıl inşa edileceğini gösterdiği yer Çarpışmaya Dayanıklı Hash Fonksiyonları pençesiz permütasyonlardan.[5] Kıskaçsızlık kavramı, hash fonksiyonlarındaki çarpışma direnci ile yakından ilgilidir. Fark, pençesiz permütasyonların çiftler Çarpışmaya dirençli bir hash fonksiyonu, çarpışmayı bulmanın zor olduğu tek bir fonksiyon iken, aralarında bir çarpışma yaratmanın zor olduğu fonksiyonlar, yani bir fonksiyon H bir çift farklı değer bulmak zorsa çarpışmaya dayanıklıdır x,y öyle ki

H(x) = H(y).

Hash fonksiyonu literatüründe, bu genellikle a karma çarpışma. Çarpışmaların bulunmasının zor olduğu bir hash fonksiyonunun çarpışma direnci.

Biraz bağlılık

Bir çift pençesiz permütasyon verildiğinde f0 ve f1 oluşturmak kolaydır taahhüt şeması. Biraz taahhüt vermek b gönderen rastgele seçer xve hesaplar fb(x). İkisinden beri f0 ve f1 aynı alanı (ve aralığı) paylaşın, bit b alıcıdan istatistiksel olarak gizlenir. Taahhüdü açmak için, gönderen sadece rastgeleliği gönderir x alıcıya. Gönderen, kendi payına bağlıdır çünkü 1'e bir taahhüt açmaktadır -b tam olarak bir pençe bulmaya eşdeğerdir. Çarpışmaya Dirençli Hash fonksiyonlarının yapımı gibi, bu yapının pençesiz fonksiyonların bir tuzak kapısı olmasını gerektirmediğine dikkat edin.

Referanslar

  1. ^ Goldwasser, Shafi; Micali, Silvio; Rivest, Ronald L. (1984). "İmza Problemine Paradoksal Bir Çözüm". FOCS Tutanakları (PDF). sayfa 441–448.
  2. ^ Goldwasser, Shafi; Micali, Silvio; Rivest, Ronald L. (Nisan 1988). "Uyarlanabilir seçilmiş mesaj saldırılarına karşı güvenli bir dijital imza şeması". SIAM J. Comput. 17 (2): 281–308. CiteSeerX  10.1.1.20.8353.
  3. ^ Bellare, Mihir; Micali, Silvio. "Herhangi bir trapdoor permütasyonu verildiğinde nasıl imzalanır". Alıntı dergisi gerektirir | günlük = (Yardım)
  4. ^ Dodis, Yevgeniy; Reyzin, Leonid (2002). "Pençesiz Permütasyonların Gücü Üzerine". CiteSeerX  10.1.1.19.6331. Alıntı dergisi gerektirir | günlük = (Yardım)
  5. ^ a b Damgård, Ivan Bjerre (1988). "Çarpışmasız hash fonksiyonları ve genel anahtar imza şemaları". Kriptolojideki Gelişmeler - EUROCRYPT ’87. Bilgisayar Bilimlerinde Ders Notları. 304. Springer. s. 203–216. doi:10.1007/3-540-39118-5_19.

daha fazla okuma