Skein Özet (hash) fonksiyon

1. ÖZET

1.1. Giriş

Skein [13], AHS adayı olarak sunulan hızlı, çok yönlü ve güvenli bir hash işlevidir. Skein’in özelliklerinden biri, güvenlik kanıtları ile desteklenmesidir. Bu makale sunar, açıklar ve Skein’in altında yatan çeşitli kanıtlanabilir güvenlik iddialarını haklı çıkarır

1.2. ÖZET

Skein’in altında yatan temel (atomik de denir) ilkeller, ayarlanabilir blok şifrelemedir ve türetilmiş sıkıştırma işlevi. Skein, bazı çalışma modlarında bunların üzerine inşa edilmiştir. Bir Skein’in bir güvenlik mülküne sahip olduğunun kanıtı, S formunun bir kanıtıdır: “Eğer atomik ilkel, güvenlik özelliği A’ya sahiptir, sonra Skein’in güvenlik özelliği S’ye sahip olduğu garanti edilir. “Kanıt, bir saldırganın Skein’in S özelliğini ihlal etmesi durumunda, atomik ilkelin A özelliğini ihlal eden bir saldırgan oluşturur.

Böyle sağlayacağızS’nin çeşitli farklı seçimleri için kanıtlar. Bir güvenlik kanıtı bulmanın imkânsız olacağını söylemediği anlaşılmalıdır. Skein için S güvenlik özelliğini ihlal eden saldırılar. Söylediği, bulmanın imkânsız olacağıatomik ilkelin güvenlik özelliği A’yı ihlal eden saldırıları ortaya çıkarmadan bu tür saldırılar. İspat, atomik ilkelden Skein’e güven aktarır. Çalışma modunu doğrular, anlam, üst düzey tasarım. Bu tasarımda hiçbir kusur olmadığını söylüyor. Pratiksonuç, kriptanalizin atomik ilkellerle sınırlı olabilmesidir. Gerek yokSkein’e saldırmaya teşebbüs. Ayrıca, gayretinizi Threefish’e ve sıkıştırma işlevi.

Kanıtlarımıza sahip olduğumuz ilk ve en temel özellik çarpışma direncidir. Ancak, bu kanıtlarla desteklediğimiz tek güvenlik özelliği değildir. Çağdaş kullanıma bir bakış Karma işlevlerinin% 50'si, güvenlik özelliklerini iyi gerektiren şekillerde kullanıldıklarını açıkça ortaya koymaktadır. Çarpışma direncinin ötesinde ve ondan farklıdır. Özellikle mesaj için hash fonksiyonları kullanılır. Kimlik doğrulama ve anahtar türetmede sözde rasgele işlevler (PRF’ler) olarak. (Bu kullanımlar, karma işlevinin anahtarlı sürümleri, örneğin, HMAC [2, 1].) Bunlar ayrıca rastgeleaçık anahtarlı kriptografi şemalarındaki kâhinler. Bu tür kullanımın devam edeceğine inanıyoruz ve modern hash fonksiyonları bunu desteklemelidir. Bu, Skein’in altında yatan tasarım felsefesidir.

Bu ek özellikler için kanıtlanabilir destek sağlamaya yaklaşıyoruz. Skein’in altında yatan operasyonun oranı MPP’dir (Multi-Property Preserving) [5]. Bu bir sayı olduğu anlamına gelirAtomik ilkel tarafından sahip olunan farklı güvenlik özelliklerinin sahip olunması garanti edilirSkein tarafından. Bu tür ilk özellik çarpışma direncidir. İkincisi, PRF özelliğidir. bunun sonucunda anahtarlı Skein’in bir KDF ve MAC olarak kullanımı için kanıtlanabilir destek elde ediyoruz. Üçüncüsü, sözde rastgele bir oracle (PRO), yani rastgele bir oracle’dan farksızlıktır.

Hash fonksiyonlarının en yaygın güncel kullanımlarından biri HMAC [2, 16] içindir. Bu kullanımMerkle kullanan mevcut karma işlevler nesli için güvenlik kanıtlarıyla desteklenirDamgård modu [2, 1]. Gelecekteki herhangi bir hash fonksiyonunun şu uygulamalarda kullanılmaya devam edeceğini umuyoruz. HMAC modu ve bu tür bir kullanımın güvenlik kanıtları ile desteklenmeye devam etmesi gerekir. Tedarik ediyoruzbu kanıtlar.

Ayrıca Skein’in bir PRNG ve bir akış şifresi olarak kullanılmasına kanıtlanabilir destek sağlıyoruz. Şekil 1, Skein hakkında kanıtlanabilir güvenlik sonuçlarını özetlemektedir. Şimdi bu öğeleri daha fazla tartışıyoruz detay.

Skein property / mode Assumption on atomic primitive

Hash (collision-resistance) C is collision resistant

PRF, KDF, MAC, HMAC, PRNG, stream cipher Threefish is a (tweakable) PRP

Indifferentiability from RO Threefish is an ideal (tweakable) cipher

Şekil 1: Skein’in kanıtlanabilir güvenlik özniteliklerinin özeti. Her mülk için şunu belirtiyoruz: altında kurulduğu atomik ilkel varsayımı. Burada C sıkıştırmadırişlevi.

1.3. Skein’in Sağlanabilir Özellikleri

Çarpışma Direnci. Sıkıştırma işlevinin çarpışmaya dirençli olması durumundaSkein de öyle. (Yukarıdaki tartışmaya atıfta bulunarak, burada S, Skein ve A'nın çarpışma direncidir. Sıkıştırma fonksiyonunun çarpışma direncidir.) Bunun anlamı, daha kolay olmamasıdır. Skein için sıkıştırma işlevi yerine çarpışmaları bulmak için. (Güçlendirilmiş) Merkle-SHA ailesinde kullanılan Damgård [11, 21], benzer bir güvenlik garantisi ile desteklenmektedir. Garanti, yeni bir hash fonksiyonu için gerekli bir gereklilik gibi görünmektedir. İddia ediyoruzbunu sağlayabiliriz.

PRF, MAC ve KDF. Threefish'in ayarlanabilir bir PRP (sözde rasgele permu-tation) sonra Skein bir PRF'dir. Bu bağlamda bahsettiğimizi anlamak önemlidir, Skein'in anahtarlı sürümüne. PRF özelliği, anahtarlı Skein'in girdi-çıktı davranışınınanahtarı verilmeyen bir saldırgana rastgele bir işlev gibi görünmelidir. Bu kanıtanahtar türetme (KDF) için anahtarlı Skein kullanımını destekler. Ayrıca anahtarlı Skein kullanımını da desteklerMAC olarak. Bu doğrudur çünkü herhangi bir PRF güvenli bir MAC'dir [4].

PRF özelliği, SHA ailesine kıyasla Skein'in artan çok yönlülüğünü yansıtır. İkinci ailedeki işlevler PRF'ler değildir. (Doğal bir şekilde, yani, ilk vektör.) Bunun nedeni uzantı saldırısıdır. PRF güvenliğinin kanıtının çekici bir özelliğini vurguluyoruz. Yani yapılan varsayımsıkıştırma işlevi yerine (değiştirilebilir) blok şifrelemeyle ilgilidir ve dahası, aslında bu nesnenin standart varsayımı, yani bir PRP olmasıdır. Nitekim durumundaEMD [5] gibi PRF koruyan diğer modlar, varsayım, sıkıştırmanınişlev, temel blok şifresinin, anahtarla anahtarlandığında bir PRF olmasına dayanan bir PRF’dir. Anahtar bağlantı noktası yerine mesaj. Skein durumunda fark, sıkıştırma nedeniyle ortaya çıkar. Fonksiyon blok şifrelemeyi Matyas-Meyer-Oseas modunda çalıştırır [19].Bir MAC olarak anahtarlı Skein kullanımı için kanıtlanabilir destek sağladığımızı vurguluyoruz. BuAnahtarlı Skein'in, Threefish'in güvenli bir MAC olduğunu gösterdiğimiz gerçeğininbir PRP'dir. (Bunun nedeni, yukarıda belirtildiği gibi, bu varsayım altında anahtarlanmış Skein'in birPRF ve herhangi bir PRF güvenli bir MAC'dir.)Bu modlarda Skein'in yeni bir özelliği değişken çıktı uzunluğudur. İstenilen çıktı uzunluğuhash işlevinin girdilerinden biridir. Skein, çıktı değerleri olacak şekilde tasarlanmıştır. bu çıkış uzunluğu parametresinin farklı değerleri için bağımsız, diğer girişler (örneğinmesaj) aynıdır. Skein'in bu özelliği, güvenlik kanıtları tarafından da desteklenmektedir. Biz tanımlıyoruz(yeni) bir VOL (Değişken Çıkış Uzunluğu) PRF kavramı. Kanıtların Skein'i gösterdiği şey budur2

Threefish'in bir PRP olduğu varsayımı altında başarmak. Anahtarlı Skein, bir PRF ve güvenli MAC sağlama açısından HMAC-Skein'e hızlı bir alternatiftir. Ancak eski uygulamaları desteklemek için, provalar yoluyla HMAC-Skein'i de destekleyeceğiz. Rastgele Bir Kâhin’den Kayıtsızlık. Skein çalışma modununrastgele bir kehanete karşı kayıtsızlığı korur. Bu, [10, 5] 'den beri önemli birrastgele oracle'ları somutlaştırmak için kullanımlarından dolayı hash fonksiyonları gereksinimi. Sonuçlara göre, eğer Threefish'i ideal bir blok şifre ile değiştirirsek, Skein çalışma modu tarafından üretilen karma işlevi, sözde rasgele kehanet olarak adlandırılan şeydir(PRO). Bu, rastgele bir kehanetten farksız olduğu anlamına gelir. Kayıtsızlık [20, 10] birteknik terim resmi bir tanımla altındadır. Bir işlev rastgele bir işlevden farksız iseoracle, bu, rastgele bir oracle'ı bu işlevle güvenli bir şekilde değiştirebileceğimiz anlamına gelir (hepsinde değil)rastgele oracle'ın kullanımları.

Bu, Skein çalışma modunun yapısal zayıflıkları olmadığı şeklinde görülebilir. Buuzantı saldırısı gibi onu rastgele bir oracle'dan ayıran saldırıların. Bununla birlikte, bir uyarı ve açıklama kelimesi eklemeliyiz. Sonuç modla ilgilidirişlem ve blok şifrelemeye değil. İkincisi, ideal bir blok şifreleme ile değiştirildi. Buradaki ince nokta, ele geçirmek için ifade edebileceğimiz resmi bir kavram veya varsayımın olmamasıdır."Üç balık ideal bir blok şifresidir veya yaklaşık olarak tahmin etmektedir". Bu diğer sonuçlardan farklıyukarıda tartışılan. Örneğin Threefish'in bir PRP olduğunu söylemek çok anlamlı. Vurguluyoruz kayıtsızlıkla ilgili inceliklerin bizim sonuçlarımıza özgü olmadığını, daha çok endemik olduğunu bir bütün olarak nosyona. Kanıtı olan herhangi bir karma işlevi için mevcutlar ve olacaklar. Rastgele bir oracle'dan farksızlık sağlanır. Bütün bu direniş, toplumdaki genel fikir birliği, kayıtsızlığın sizi satın almasıdır. Resmen tam olarak ne olduğunu söylemek zor.

HMAC Modu için destek. Mevcut hash fonksiyonları, bir MAC elde etmek için HMAC modunda kullanılırveya bir PRF. HMAC'ın yaygın standardizasyonu ve kullanımı, bunun büyük birve hash fonksiyonu kullanımının önemli alanı. (HMAC, bir IETF RFC [17] aracılığıyla standardize edilmiştir, bir NIST FIPS [16] ve ANSI X9.71 [15]. IEEE 802.11 içindedir. SSL, SSH, Diğer yerlerin yanı sıra IPsec ve TLS.) Bu nedenle, herhangi bir yeni karma işlevinin devam etmesi önemlidir.

HMAC modunda kullanımı desteklemek için. Delillerle ilgili olarak bunun ortaya çıkardığı konu şu şekildedir. Merkle kullanan karma işlevler için Damgård [11, 21] modu (özellikle MD ve SHA aileleri), HMAC modu aşağıdakiler tarafından desteklenmektedir: yaygın ve devam eden evlat edinmede önemli bir rol oynadığı tartışmalı kanıtlar [2, 1]HMAC. Bu etki alanında HMAC için mevcut destek, [1] tarafından temsil edilmektedir. Merkle-Damgård hash işlevine sahip HMAC, güvenli bir PRF'dir (ve dolayısıyla MAC)sıkıştırma işlevinin kendisi güvenli bir PRF'dir.

Skein akımın yerini alacaksakarma işlevler, HMAC'da kullanımı için benzer bir kanıtlanabilir garanti sağlamamız önemlidir. modu. Ancak temeldeki yineleme yöntemimiz Merkle-Damgård olmadığından, önceki kanıtlargeçerli değil. Bu konudaki katkımız yeni deliller sunmaktır. Bunlar yukarıdakinin benzerini gösterir-belirtilen sonuç. Yani, sıkıştırma fonksiyonu bir PRF ise HMAC-Skein de öyle. BuSkein'in HMAC modunda mevcut hash işlevleriyle aynı kanıtlanabilir garantilere sahip olduğu anlamına gelir. Sonuç olarak, Skein'in PRF veya PRF sağlayabileceği iki farklı çalışma modu vardır.

MAC: HMAC modu ve Skein'in yerel anahtarlı modu, yukarıda tartışıldığı gibi. İkincisi daha hızlıdır. Nasıl-eskinin eski nedenlerle desteklenmesi gerekir.

PRNG ve Akış Şifresi. Bir akış şifresi için hedef güvenlik özelliği [9, 24] 'ün özelliğidir.(Girdi üzerindeki çıktı, rastgele bir tohum, sayısal olarak rasgele seçilemez olmalıdır.)PRNG'nin hedefi, [7] 'de tanımlandığı gibi ileriye dönük güvenli olmasıdır. İkisini de kanıtlıyoruzThreefish'in bir PRP olduğu varsayımı altında özellikleri

2. Tanımlar (Definitions)

M bir dizge ise | M | uzunluğunu gösterir. Eğer bir 1 , ..., a n dizge ise 1 ··· a n onların bitiştirme. M, l'nin pozitif katı uzunluğunda bir dizge ise, | M | l = | M | / l ve M [i, l], M'nin i-inci l-bit bloğunu göstersin, yani M = M [1, l] ··· M [m, l] burada m = | M | l . Blok uzunluğu olarak adlandırılan bir tamsayı b boyunca sabitliyoruz ve M [i, b] 'yi M [i] ile kısaltıyoruz. BizvIntToStr l (N) kullanın, N mod 2 l kodlamasını bir l-bit dizge olarak belirtmek için N bir tamsayıdır.

Eğer ben, j pozitif tamsayılar ve Y bir dizedir, burada i ≤ j ≤ | Y |, sonra Y [i ... j], Y'nin alt dizesini belirtir bit konumu i'den başlayıp bit konumu j'de biten.

X bir küme ise, X + , X üzerindeki tüm dizilerin (tuplelar) kümesini belirtir. Bir dizinin uzunluğu bileşenlerinin uzunluklarının toplamı olarak tanımlanır.

F: D 1 × ··· × D n → D bir fonksiyonsa, f K : D 2 × ··· × D n → D ile tanımlanan fonksiyondur

f K (x 2 , ..., x n ) = f (K, x 2 , ..., x n ) tüm K ∈ D 1 ve (x 2 , ..., x n ) ∈ D 2 × ··· × D n .

D 0 ⊆ N ise f: D 0 × ··· × D n → {0,1} ∗ değişken bir çıktı uzunluğu (VOL) fonksiyonu diyoruz.

ve | f (N, x 1 , ..., x n ) | = Tüm N ∈ D 0 ve tümü için N (x 1 , ..., x n ) ∈ D 1 × ··· × D n .

E: {0,1} b × {0,1} t × {0,1} b → {0,1} b , bir b-bit anahtarı K, bir t-bit ince ayarı T alan bir harita olsun ve

bir b-bit çıkışı E (K, T, X) döndürmek için bir b-bit girişi X. E'nin değiştirilebilir bir blok şifresi olduğunu söylüyoruz [18]

E (K, T, ·) haritası tüm K, T için {0,1} b üzerinde bir permütasyon ise .

Değiştirilebilir bir sıkıştırma işlevi basitçe bir haritadır TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b .

İlk girdi, kullanıma bağlı olarak bir anahtar veya zincirleme değişkendir. İkinci girdi, çimdik.

Bu makale boyunca, basitleştirmek için b ve t'nin her ikisinin de 8'in katları olduğunu, yani b ≥ 256 olduğunu varsayıyoruz,

ve bu t ≥ 128; Ancak buradaki sonuçlar bu kısıtlamaların ötesinde genelleştirilebilir.

Oyunlar. Güvenlik tanımlarımız ve kanıtlarımız kod tabanlı oyunlar [6] kullanır ve bu nedenle bazılarını [6] 'dan arkaplan. Bir oyunun Başlatma prosedürü, rakibe yanıt verme prosedürleri vardır oracle sorguları ve (bazen) bir Sonlandırma prosedürü. Bir G oyunu rakip A ile yürütülür aşağıdaki gibi. İlk olarak, Initialize yürütür ve çıkışları A'nın girdileridir. Sonra A çalışır, oracle soruları G'nin ilgili prosedürleri ile cevaplanıyor. Sonlandırılmadıysa

yordam, daha sonra A sona erdiğinde, çıktısına oyunun çıktısı da denir. Varsa bir Sonlandırma prosedürüdür, daha sonra A sona erdiğinde çıktısı Sonlandırmanın girdisi olur prosedür. Bu durumda, Finalize'nin çıktısına oyunun çıktısı denir. Her iki durumda da biz G A ⇒ y, bu oyun çıktısının y değerini aldığı olayı göstersin. Boole bayrağının kötü olduğu varsayılır false olarak başlatıldı. G, H oyunları, kodları yalnızca aşağıdaki ifadelerde farklılık gösteriyorsa, kötü olana kadar aynıdır. kötü ayarını doğruya doğru izleyin. "G A'nın kötü olduğunu" söyleyerek G oyununun düşman A ile idam edilir, kötüyü doğru yapar. [6] 'da G, H'nin kötü olana kadar aynıysave A bir düşman, o zaman

Pr [G A kötü ayarlar] = Pr [H A kötü ayarlar]. (1)

Oyun oynamanın temel lemması [6], eğer G, H kötü olana kadar özdeşse, o zaman

Pr [G A ⇒ y] - Pr [H A ⇒ y] ≤ Pr [G A kötü ayarlar].

Durum Bilgili Algoritmalar. Bir algoritmanın, invocations. Bazı girdilerde çalıştırıldığında, algoritma girdinin bir işlevi olarak bir yanıt hesaplar ve mevcut durumu ve ayrıca durumunu günceller. Durum bilgili algoritmalar aracılığıyla “ideal” ilkelleri modelliyoruz. Örneğin, anahtar ve blok uzunluğu b ve ince ayar uzunluğu t ile ideal bir ayarlanabilir blok şifresi

durum bilgili algoritma P başlangıçta tanımlanmamış bir çift E, E −1 tablolarından oluşan durumu korur her yerde. C, (K, T, Z) girişinde, c ∈ {+ 1, −1}, K, Z ∈ {0,1} b ve T ∈ {0,1} t , P, takip etme:

If c = +1 then

x ← Z

If not E(K, T, x) then

y

$←

{0, 1}b\{ E(K, T, x′) : x′ ∈ {0, 1}b } ; E(K, T, x) ← y ; E−1(K, T, y) ← x

Return E(K, T, x)

If c = −1 then

y ← Z

If not E−1(K, T, y) then

x

$←

{0, 1}b\{ E−1(K, T, y′) : y′ ∈ {0, 1}b } ; E−1(K, T, y) ← x ; E(K, T, x) ← y

Return E−1(K, T, y)

Benzer şekilde, D aralığı olan bir RO, başlangıçta tanımsız olan bir T tablosunu tutan durumsal algoritmadır R her yerde ve x sorgusuna yanıt verir

If not T[x] then T[x] $←D

Return T[x]

Cascade İnşaat. Cascade (veya güçlendirilmemiş MD [11, 21]) dönüşümü a sıkıştırma fonksiyonu Comp: {0,1} b × X → {0,1} b ve Comp ∗ : {0,1} b fonksiyonunu verir × X + → {0,1} b Şekil 2'de tanımlanmıştır.

3. İnşaat (Constructions)

Threefish. Threefish [14] değiştirilebilir bir blok şifresidir E: {0,1} b × {0,1} t × {0,1} b → {0,1} b ile

t = 128 ve b ∈ {256,512,1024}.

Function Comp∗(K, (X1, . . . ,Xm))

h0 ← K

For i = 1, . . . ,m do hi ← Comp(hi−1,Xi)

Return hm

Şekil 2: Basamaklı dönüşümü, sıkıştırma işlevi Comp ile ilişkilendirilir: {0,1} b × X → {0,1} b

Comp ∗ işlevi : {0,1} b × X + → {0,1} b yukarıda tanımlanmıştır.

TComp. Değiştirilebilir sıkıştırma işlevimiz TComp, ayarlanabilir blok çalıştırılarak elde edilir

Matyas-Meyer-Oseas [19] modunda şifreleme E. Özellikle, ilişkili ayarlanabilir sıkıştırma fonksiyon TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b şu şekilde tanımlanır:

TComp (K, T, X) = E (K, T, X) ⊕ X. (2)

Bu, sonunda Skein'in bir PRF'ye dayalı bir PRF olduğunu kanıtlamamıza izin veren önemli bir özelliktir.

bir varsayım (ve dahası, standart olan) bir sıkıştırma işlevi varsayımı, ikincisi karma işlevlerin büyük kısmı için geçerlidir.

Benzersiz Blok Yineleme (UBI). Benzersiz Blok Yineleme (UBI), bir ayarlanabilir sıkıştırma işlevi TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b ve bir işlev döndürür f: {0,1} b × MsgSp × TypeSp × {0,1} 7 × [0,2 t − 32 −1] → {0,1} b . MsgSp mesaj alanı settir en fazla tüm uzunluk dizilerinin (2 t − 32 −1) 2 3 bit. TypeSp tür alanı, tüm 6 bitlik dizelerin kümesidir. Dördüncü parametre daha sonra bir karma ağacındaki seviyeyi kodlamak için ve beşinci parametre kullanılacaktır. bir hash hesaplamasının başlangıç ​​ofsetini kodlamak için kullanılacaktır. F fonksiyonu Şekil 3'te tanımlanmıştır çağırdığı alt rutin Encode ile birlikte. Kodlama işlevi ayrıca bir alt yordamı çağırır MkTw (ince ayar). Bu bir harita MkTw: {0,1} × {0,1} × {0,1} 6 × {0,1} × {0,1} 7 × [0,2 t − 32 −1] → {0,1} t . Bu haritadaki tek varsayımımız, enjekte edici olmasıdır. Başaran bir örnek somutlaştırma bu

MkTw(fin, fir, type, bitpad, lvl, L) = finkfirktypekbitpadklvlk016kIntToStrt−32(L) .

SSkein. SSkein, f: {0,1} b × MsgSp × TypeSp × {0,1} 7 × işlevini alan bir dönüşümdür

[0,2 t − 32 −1] → {0,1} b ve bir SSkein işlevi döndürür: OutLens × {0,1} b × ((TypeSp− {TyCfg, TyOut}) × MsgSp) ∗ → {0,1} ∗ . MsgSp ileti alanı, en fazla tüm uzunluk dizilerinin kümesidir. (2 t − 32 - 1) 2 3 bit. TypeSp tür alanı, tüm 6 bitlik dizelerin kümesidir ve TyCfg, TyOut iki farklı, sabit 6 bitlik dizi. SSkein için ilk parametre, bit cinsinden çıktı uzunluğudur, yani, | SSkein (N, ·, ·) | = N. Burada OutLens, {8i: i ∈ [0,2 64 - 1]} kümesi olarak tanımlanır , ancak [14] 'te {i: i ∈ [0,2 64 ]} olarak tanımlanır. SSkein işlevi, alt rutin ile birlikte Şekil 4'te tanımlanmıştır. Çağırdığı çıktı. SSkein işlevi ayrıca bir SMkConfig (make-config) alt rutini çağırır. Bu bir harita SMkConfig: OutLens → {TyCfg} × {0,1} 256 . Tek varsayımımız bu haritanın enjekte edici. Bunu somutlaştıran bir örnek

SMkConfig(N) = (TyCfg, 064kIntToStr64(N/8)k08k08k08k0104) .

4. Kodlama Lemmaları (Encoding Lemmas)

Tanımlar. M 1 = (M 1 1 , ..., M 1m 1 ), M 2 = (M 21 , ..., M 2 m 2 ) ∈ X + , bazı X kümeleri için.

Şekil 3: UBI dönüşümü, ayarlanabilir sıkıştırma işlevi TComp ile ilişkilendirilir: {0,1} b ×

{0,1} t × {0,1} b → {0,1} b f fonksiyonu: {0,1} b × MsgSp × TypeSp × {0,1} 7 × [0,2 t − 32 - 1] → {0,1} b

yukarıda tanımlanmıştır.

Şekil 4: SSkein dönüşümü f: {0,1} b × MsgSp × TypeSp × {0,1} 7 × işleviyle ilişkilendirilir [0,2 t − 32 - 1] → {0,1} b SSkein: OutLens × {0,1} b × ((TypeSp - {TyCfg, TyOut}) ×MsgSp) ∗ → {0,1} ∗

Yukarıda tanımlanmıştır.

Kodlamanın Özellikleri. 4-tuple'ın (M, type, lvl, startl) startl bir b / 8'in katı, startl = 0, M = ε ve | M | + startl · 2 3 ≤ (2 t − 32 - 1) 2 3 . Olmadan başlangıç ​​sınırlamasına uyarak, Kodlamanın aynı değerleri ikinci girişe vermesi mümkün olabilir farklı gruplar (M 1 , tip 1 , lvl 1 , başlangıç 1 ) ve (M 2 , tip 2 , lvl 2 , başlangıç 2 ). Şimdi aşağıdaki önermeleri belirtiyoruz:

Lemma 4.1 (M 1 , tip 1 , lvl 1 , startl 1 ) ve (M 2 , tip 2 , lvl 2 , startl 2 ) farklı başlangıca saygı göstererek 4-

tuples ve let

İspat: m 1 <m 2 ise , M ∗ ≤ P N ∗ çünkü T 1 m 1 son bit setine sahiptir ancak T 2 m 1 değil. Eğer tip 1 = tip 2 veya lvl 1 = lvl 2 , M * ≤ P K * ince ayarlar, bu değerler kodlayan için.

Şimdi m 1 = m 2 , tip 1 = tip 2 ve lvl 1 = lvl 2 olduğunu varsayalım . M 1 = M 2 ve startl 1 = startl 2 ise ,

daha sonra M ∗ ≤ P N ∗ çünkü nihai uzunluklar veya bit doldurma alanları bir farkı veya

Bir i ∈ {1, ..., m 1 } indeksi için M 1 [i] = M 2 [i] . M 1 = M 2 ve startl 1 = startl 2 ise , M ∗ ≤ P N ∗

çünkü nihai uzunluklar bir farkı kodlayacaktır.

M 1 = M 2 ve startl 1 = startl 2 ise daha dikkatli olmalıyız. M 1 = m 2 > 1 ise T 1

1 = T 2

1'den beri

ilk ince ayar farklı bir uzunluğu kodlayacak ve dolayısıyla M ∗ ≤ P N ∗ olacaktır . Diyelim ki m 1 = m 2 = 1.

M 1 = ε ve M 2 = ε ise T 1

1 = T 2

İlk ince ayar farklı bir uzunluğu kodlayacağından 1

başlangıç ​​uzunluğu değerlerinin tümünün b / 8'in katları olduğu varsayımı) ve dolayısıyla M ∗ ≤ P N ∗ . Eğer

genellik kaybı olmadan M 1 = ε, sonra startl 1 = 0 varsayımla ve T 1

1 = T 2

İlkinden beri 1 (ve

sadece) ince ayar farklı bir uzunluğu kodlayacaktır ve dolayısıyla M ∗ ≤ P N ∗ .

Lemma 4.2 (M 1 , tip 1 , lvl 1 , startl 1 ) ve (M 2 , tip 2 , lvl 2 , startl 2 ) farklı başlangıca saygı göstererek 4-

tuples ve let

Then M ∗ ≤ S N ∗ .

İspat: Lemma 4.2'nin kanıtı, ilk bit haricinde Lemma 4.1'in ispatı ile aynıdır. m 1 <m 2 olduğu durumda son bitin rolünü oynamak (çünkü T 1 1 ilk bit setine sahip ancak T 21 + m 2 −m 1 değil).

5. Çarpışma Direnci (Collision Resistance)

5.1. Tanımlar

F: D 1 × D 2 × ··· × D d → {0,1} n bir fonksiyon olsun. Bir CR-hasım A, rastgele seçilmiş bir al-

herhangi bir girdi almayan ve bir çift farklı tuple (x 1 , x 2 , ..., x d ) döndüren gorithm, (x ′ 1 , x ′ 2 , ..., x ′ d ) ∈ D 1 × D 2 × ··· × D d . Adv cr olsun f (A), rastgele madeni paralar üzerindeki olasılığı gösterir A için, f (x 1 , x 2 , ..., x d ) = f (x ′ 1 , x ′ 2 , ..., x ′ d ).

5.2. TComp için Çarpışma Direnci

Skein'in çarpışma direnci, TComp'un çarpışma direncine göre kanıtlanmıştır. Bu kanıt standart (yani RO değil) model. Standart modelde, TComp'un CR kanıtı olmadığını bilmiyoruz ayarlanabilir blok şifrelemeye ilişkin standart bir varsayıma dayanmaktadır. Ancak TComp'un Değiştirilebilir blok şifreleme ideal ise ([8] ince ayar yapılabilir ayarı).

5.3. UBI için Çarpışma Direnci

UBI'nin çarpışma direncini koruduğunu gösteriyoruz, yani TComp CR ise f aynı zamanda CR'dir.

irkilme kısıtlı düşmanlara karşı. TComp'un CR olduğunu söylerken, bunu basitçe 3 argüman olarak görüyoruz işlev, yani çarpışma, TComp'un aynı çıktıya sahip olduğu herhangi bir farklı üçlü çiftidir. Benzer şekilde, f'ye karşı startl kısıtlamalı bir çarpışma, herhangi bir çift farklı 5-tuple ((K 1 , M 1 , tip 1 , lvl 1 , startl 1 ), (K 2 , M 2 , tip 2 , lvl 2 , startl 2 )) f'nin aynı çıktıya sahip olduğu, kısıtlama altında startl 1 = startl 2 .

Şekil 5: Teorem 5.1'de belirtilen ters B. Kodlama işlevi Şekil 3'teki gibi tanımlanmıştır.

B'nin son for döngüsünü düşünün. İ ∈ {0, ..., min (m 1 , m 2 ) - 1} en küçük değer olsun, öyle ki

Böyle bir indeks, aşağıda açıkladığımız nedenlerden dolayı mevcuttur. İ seç mi ve f (K 1 , M 1 , tip 1 , lvl 1 , startl 1 ) = f (K 2 , M 2 , tip 2 , lvl 2 , startl 2 ), h 1 m 1 –I = h 2 m 2 –I . Bu nedenle TComp (h 1 m 1 −i – 1 ,Ç 1

m 1 −i

, M

1

[m 1 - i]) = TComp (h 2

m 2 −i − 1

, T 2

m 2 −i

, M

2

[m 2 - i]) ve B bir çarpışma verir.

Böyle bir i indeksinin varlığını gerekçelendirmek için birkaç durumu ele alıyoruz. Açıkçası tip 1 = tip 2 ise

veya lvl 1 = lvl 2 ise , böyle bir i indeksi, MkTw fonksiyonunun enjektivitesinden dolayı mevcuttur.

Encode çağırır. Öyleyse tip 1 = tip 2 ve lvl 1 = lvl 2 olduğunu varsayalım . Başlangıç-kısıtlama varsayımına göre

A üzerinde, startl 1 = startl 2 . | M 1 | = | M 2 |. A için çarpışma tanımına göre,

K 1 = K 2 veya M 1 = M 2 veya her ikisi ve dolayısıyla zincirleme değerleri indeks i = m 1 - 1 için farklıdır

(K 1 = K 2 ise ) veya M

1

[i] = M

2

[i] (M ise 1 = m 2 ). Şimdi düşünün

durum | M 1 | = | M 2 |. Sonra (M

1

[m 1 ], T 1

m 1 ) = (M

2

[m 2 ], T 2

m 2 ) Kodlama nedeniyle. İşte biz

M 1 veya M 2'nin bit dolgulu olmasına karşılık gelen birden çok durumu dikkate almalıdır. Eğer ikisi de değilse

bit-dolgulu, ardından T 1'de kodlanan uzunluklar

m 1 ve T 2

m 2 farklı olacaktır. Her ikisi de bit dolgulu ise,

sonra M

1

[m 1 ] = M

2

[m 2 ] veya nihai kodlu uzunlukları farklıdır. Yalnızca biri bit dolgulu ise, o zaman

bit doldurma bayrağı yalnızca ince ayar değerlerinden biri için ayarlanacaktır.

5.4. SSkein için Çarpışma Direnci

Şimdi SSkein'in çarpışma direncini koruduğunu gösteriyoruz, yani f startl- Bölüm 5.3'te tanımlandığı gibi kısıtlı düşmanlar, bu durumda H (·, ·) = SSkein (N, ·, ·) ayrıca CR'dir, burada N

herhangi bir çıktı uzunluğu en az b. (Tanım olarak, bir N-bit çıkışı N çarpmamasını ' -bit çıkışı

N = N ′ olduğunda .) Teorem 5.2 f: {0,1} b × MsgSp × TypeSp × {0,1} 7 × [0,2 t − 32 - 1] → {0,1} b UBI olsun sıkıştırma işlevi ve SSkein: OutLens × {0,1} b × ((TypeSp− {TyCfg, TyOut}) × MsgSp) ∗ → {0,1} ∗ Şekil 4'e göre f'den tanımlanan VOL işlevi olsun. Bazıları için H (·, ·) = FSkein (N, ·, ·) olsun sabit N ≥ b. A, H'ye karşı bir CR-düşmanı olsun. B, karşısında startl-kısıtlamalı CR-düşmanı olsun. f Şekil 6'da tanımlandığı gibi. Daha sonra

Adv crH (A) ≤ Adv crf (B).

Ayrıca, B'nin çalışma süresi, A'nınki artı f'nin r 1 + r 2 +4 uygulamaları için süre , burada r 1 ve r 2 , Şekil 6'daki gibidir.

İspat: A'nın H'ye karşı bir çarpışma döndürdüğünü varsayalım.Sonra SSkein (N, K 1 , ((tip 1

1 , M 1 1 ), ..., (tip 1 r 1 , M 1 r 1 ))) =

SSkein (N, K 2 , ((tür 2

1 , M 2

1 ), ..., (tip 2

r 2 , M 2

r 2 ))). Sonuç olarak h 1

r 1 +1

= h 2

r 2 +1

.

B'deki son for döngüsünü düşünün. Döngü, i'yi -1'den dk'ya (r 1 , r 2 ) yineler . Döngü değişmezi

ki, her döngünün başlangıcında ve döngünün çıkışından önce, h 1

r 1 −i

= h 2

r 2 −i

. Bu, bundan sonra

döngüdeki koşullu h 1 için kontrol eder

r 1 −i − 1

= h 2

r 2 −i − 1

ve eşit değilse geri döner.

Döngü erken çıkarsa, bu dönüşün ön koşulu döngü değişmezi ile birlikte,

döndürülen değerin f için bir çarpışma olmasını sağlar. Döngünün erken çıkacağını göstermeye devam ediyor eğer bir çarpışma döndürürse.

İlk olarak, r 1 = r 2 ise , 1 yazın

r 1 −min (r 1 , r 2 )

= tür 2

r 2 −min (r 1 , r 2 )

çünkü sadece tip 1

0 ve 2 yazın

0 olabilir

TyCfg türü. Dolayısıyla, döngünün önceki bir yinelemesi zaten bir çarpışma döndürmediyse, o zaman

i = min (r 1 , r 2 ) ile yineleme bir çarpışma döndürecektir.

Bundan böyle r 1 = r 2 olduğunu varsayalım . K 1 = K 2 ise , döngü son yinelemesinde geri dönecektir.

döngünün önceki bir yinelemesi zaten döndürülmedikçe. Bir indeks varsa r ′ ∈ {1, ..., r 1 }

öyle ki tip 1 r ′ = tür 2 r ′ , sonra döngü, bir önceki olmadıkça i = r 1 - r ′ indeksinde geri dönüş gerçekleştirecektir. döngünün yinelemesi zaten döndü. Bundan böyle K 1 = K 2 ve tip 1 olduğunu varsayalım.

r ′ = tür 2

r ′ tüm r ′ ∈ {1, ..., r 1 } için. A döndüğünden beri

bir çarpışma, M 1 olacak şekilde bir r ′ ∈ {1, ..., r 1 } indeksi olmalıdır

r ′ = M 2

r ′ . Döngü bu nedenle

döngünün önceki bir yinelemesi zaten döndürülmedikçe, i = r 1 - r ′ dizininde erken dön

Oyun Gerçek f

Prosedürü Başlat

K $

← D 1

Prosedür Fn (x 2 , ..., x n )

Dönüş f (K, x 2 , ..., x n )

Oyun Rand D

Prosedürü Başlat

Prosedür Fn (x 2 , ..., x n )

Y $ döndür

← D

Şekil 7: Bir sözde rasgele işlevin (PRF) tanımı için Games Real f ve Rand D.

Oyun Gerçek f

Prosedürü Başlat

K $

← D 1

Prosedür Fn (x)

Dönüş f (K, x)

Oyun Perma D

Prosedürü Başlat

R ← ∅

Prosedür Fn (x)

y $

← D \ R; R ← R ∪ {y}

Dönüş y

Şekil 8: Sahte rasgele permütasyon (PRP) tanımı için Games Real f ve Perm D.

6. Sözde raslantı

6.1. Tanımlar ve Araçlar

F: D'ye karşı bir prf-rakibi 1 × ··· × D n → D bir oracle'a erişebilir ve biraz çıktı verir. Her biri

oracle sorgusu x 2 , ..., x n biçiminde olmalıdır burada (x 2 , ..., x n ) ∈ D 2 × ··· × D n ve sorgular

hepsi farklı olmalıdır. Avantajı

Adv

prf

f (A) = Pr [Gerçek A

f ⇒ 1] - Pr [Rand A

D ⇒ 1]

Real f ve Rand D oyunları Şekil 7'de gösterilmektedir.

F: D 1 × D → D' ye karşı bir prp düşmanı bir oracle'a erişebilir ve biraz çıktı verir. Her kahin

sorgu D üyesi olmalı ve sorguların tümü farklı olmalıdır. Avantajı

Adv

prp

f

(A) = Pr [Gerçek A

f ⇒ 1] - Pr [Perma A

D ⇒ 1]

Real f ve Perm D oyunları Şekil 8'de gösterilmektedir.

VOL işlevine karşı bir vol-prf-düşmanı F: D 0 × D 1 × · · · × D n → {0,1} ∗ bir oracle'a erişebilir

ve biraz çıktı verir. Her oracle sorgusu N, x 2 , ..., x n biçiminde olmalıdır; burada N ∈ D 0 ⊆ Z + ∪ {0}

ve (x 2 , ..., x n ) ∈ D 2 × ··· × D n ve sorguların tümü farklı olmalıdır. Avantajı

Adv

vol-prf

F

(A) = Pr [Gerçek A

F ⇒ 1] - Pr [Rand A ⇒ 1]

Real F ve Rand oyunları Şekil 9'da gösterilmektedir.

Oyun Gerçek F

Prosedürü Başlat

K $

← D 1

Prosedür Fn (N, x 2 , ..., x n )

Dönüş F (N, K, x 2 , ..., x n )

Oyun Rand

Prosedürü Başlat

Prosedür Fn (N, x 2 , ..., x n )

Y $ döndür

← {0,1} N

Şekil 9: Bir VOL işlevi için sözde raslantı tanımı için Games Real F ve Rand

(VOL-PRF).

Sözde Rastlantısallık ve Kademeli Yapı. İspatlarımızda bir sonuç kullanacağız

[3] 'ten, bir sıkıştırma fonksiyonu alan Cascade dönüşümündeki Comp: {0,1} b × X → {0,1} b

ve Şekil 2'de tanımlanan Comp ∗ : {0,1} b × X + → {0,1} b fonksiyonunu döndürür . Bir uzantı saldırısı

Comp bir PRF olsa bile Comp ∗' nin bir PRF olmadığını göstermek için uygulanabilir . Ancak Comp ∗ bir PRF'dir

Uygulandığı hiçbir mesaj bir diğerinin öneki olmadığı sürece. Bu gerçeği [3] tarihinden itibaren

Teorem 6.3 ve Teorem 6.4'ü ispat eder.

Comp ∗'ya karşı bir prf-hasım B'nin , herhangi iki farklı oracle için M 1 ≤ P M 2 ise önek içermediği söylenir.

sorgular M 1 , E 2 B.

Lemma 6.1 ([3] 'den) Comp: {0,1} b × X → {0,1} b bir sıkıştırma fonksiyonu olsun ve

Comp ∗ , Comp'a Cascade dönüşümü uygulanarak elde edilebilir. B ∗ öneksiz bir prf- olsun

Comp karşı hasım * Daha sonra, X en unsurlar q torpil sorguları, uzunluğu her yapma

Comp'a karşı bir prf-rakip B var öyle ki

Adv

prf

Zorunlu ∗ (B ∗ ) ≤ qs · Adv

prf

Zorunlu (B).

Ayrıca B, qs oracle sorgular yapar ve çalışma süresi B ∗ artı O'nunkidir (q (log q) (s + b + x)),

burada x, X'teki en uzun dizedir.

6.2. TComp'un Sahte Rasgele Olması

Önerme 6.2 E: {0,1} b × {0,1} t × {0,1} b → {0,1} b değiştirilebilir bir blok şifresi olsun ve

TComp: {0,1} b x {0,1} t x {0,1} b → {0,1} b ile tanımlanabilir

TComp (K, T, X) = E (K, T, X) ⊕ X.

Bir TComp , q oracle sorgular yapan TComp'a karşı bir rakip olsun. Sonra bir prp-

rakip A E, E'ye karşı öyle ki

Adv

prf

TComp (A TComp ) ≤ Adv

prp

E (A E ) +

q 2

2 b + 1

.

Ayrıca, A E , q oracle sorgular yapar ve çalışma süresi, A TComp artı O (q (b + t)) ' ninki kadardır .

Kanıt: A E , bir TComp çalıştırır . İkincisi bir oracle sorgusu (T, X) yaptığında, rakip A E sorgular

(T, X) kendi kehanetine döner ve Y'yi ifade ettiği değeri geri alır ve sonra Y ⊕ X'i A TComp'a döndürür . O

A TComp'un çıktısını verir. Analiz standarttır ve kullanır (ince ayar yapılabilir

ayarları) PRP / PRF Anahtarlamalı Lemma [6]

6.3. UBI için Sözde Rasgele

UBI'ye karşı bir PRF düşmanının, tüm oracle sorguları başlarsa saygı duymaya başladığını söylüyoruz.

saygılı. UBI'nin, başlangıçtan saygı duyan düşmanlara karşı PRF'yi koruduğunu iddia ediyoruz. Bunun anlamı

TComp bir PRF ise f de öyle. Bu, aşağıdakiler tarafından ima edilmektedir.

Teorem 6.3 TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b ayarlanabilir bir sıkıştırma fonksiyonu olsun

ve f: {0,1} b × MsgSp × TypeSp × {0,1} 7 × [0,2 t − 32 - 1] → {0,1} b uygulayarak elde edilsin

Şekil 3'e göre UBI TComp'a dönüşür. A, f'ye karşı başlangıç ​​saygılı bir prf-rakip olsun.

bu, q oracle sorgularını, en fazla L uzunluğundaki her sorgunun ileti alanı yapar. Sonra bir

prf-adversary B, TComp'a karşı öyle ki

Adv

prf

f (A) ≤ sq · Adv

prf

TComp (B)

nerede s = ⌈L / b⌉. Ayrıca, B'nin çalışma süresi A artı O'nunkidir (q (log q) (s + b + t)).

Korumalı: x, = {0,1} t x {0,1} b ve tanımlamak Comp: {0,1} b x X → {0,1} b ile

Zorunlu (h, (T, X)) = TComp (h, T, X)

tüm h için, X ∈ {0,1} b ve T ∈ {0,1} t .

Şimdi B tanımlayan * olarak Comp karşı aşağıdaki * , Cascade Comp (Şekil 2) dönüşümü. B ∗ A çalıştırır.

İkincisi bir oracle sorgusu yaptığında (M, type, lvl, startl), rakip B ∗ M ∗ ∈ X + ' yı şu şekilde hesaplar:

aşağıdaki gibidir:

(M, T 1 , ..., T m ) ← Kodlama (M, tür, lvl, başlatl)

İ = için 1, ..., m M do *

i ← (T i , M [i])

M ∗ ← (M ∗

1 , ..., M ∗

m )

B ∗ , Y yanıtını geri almak için M ∗ üzerinde kendi kehanetini çağırır ve yanıt olarak Y'yi A'ya döndürür.

sorgusu M. A, bir bit çıktıyla durduğunda, B ∗ aynı çıktıyla durur.

Bu yapı şunları garanti eder:

Adv

prf

Zorunlu ∗ (B ∗ ) = Gelişmiş

prf

f (A).

(3)

Öte yandan, Lemma 4.1 , yapılan sorgulardan bağımsız olarak B ∗' nin önek içermediğini garanti eder.

A, böylece Lemma 6.1'i uygulayabiliriz. D, Comp'a karşı sonuçta ortaya çıkan prf-düşmanı olsun. Biz şimdi

D'yi TComp'a karşı bir prf-hasım B'ye dönüştürür ki

Adv

prf

TComp (B) = Gelişmiş

prf

Zorunlu (D).

(4)

Teorem, Denklem (5), Denklem (6) ve Lemma 6.1'den gelir. B'yi tarif etmeye devam ediyor.

B, D'yi çalıştırır. İkincisi bir oracle sorgusu W ∈ X yaptığında, rakip B bunu W = (T, X) olarak çözümler.

ile | T | = t ve | X | = b. T, X üzerinde kendi kehanetini çağırır ve cevabı D'ye döndürür

6.4. SSkein için Sözde Rasgele

SSkein'in sözde raslantısallığını sözde rastlantısallıktan bir azalma ile kanıtlamak mümkündür.

UBI. Daha sıkı bir sınır için, SSkein'ın sözde raslantısallığından bir azalma belirtiyor ve kanıtlıyoruz.

temeldeki sıkıştırma işlevi.

Teorem 6.4 TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b ayarlanabilir bir sıkıştırma işlevi olsun-

yon. F: {0,1} b × MsgSp × TypeSp × {0,1} 7 × [0,2 t − 32 - 1] → {0,1} b ap- Şekil 3'e göre UBI dönüşümünü TComp'a bağlamak. SSkein: OutLens × {0,1} b × ((TypeSp - {TyCfg, TyOut}) × MsgSp) ∗ → {0,1} ∗ Şekil 4'e göre f'den tanımlanan VOL fonksiyonu olsun.Bir SSkein , en fazla soru soran SSkein'e karşı bir vol-prf-düşmanı olabilir.

sorgu, en fazla N i olan bir tam sayıdan (çıktı uzunluğu değeri) ve en fazla l çiftinin bir listesinden oluşur,

her mesaj en fazla l ′ bit uzunluğunda bir çift halinde . Sonra bir prf-hasım A TComp var öyle ki

Ayrıca, A TComp en fazla q ′ (l · ⌈l ′ / b⌉ + 3) oracle sorgular ve çalışma süresi A SSkein artı O'dur (q ′ (log q ′ ) (l · ⌈l ′ / b⌉ + b + t)). Korumalı: x, = {0,1} t x {0,1} b ve tanımlamak Comp: {0,1} b x X → {0,1} b ile

Zorunlu (h, (T, X)) = TComp (h, T, X) tüm h için, X ∈ {0,1} b ve T ∈ {0,1} t .

Şimdi B tanımlayan * olarak Comp karşı aşağıdaki * , Cascade Comp (Şekil 2) dönüşümü. B ∗ koşar

Bir SSkein . İkincisi bir oracle sorgusu yaptığında (N, (tip 1 , M 1 ), ..., (tip r , M r )), rakip B ∗

M i ∈ X + , i ∈ {1, ..., ⌈N / b⌉} 'yi şu şekilde hesaplar:

B ∗ , Y 1 , ..., Y d yanıtlarını geri almak için M 1 , ..., M d üzerinde kendi oracle'ını çağırır ve ilk N'yi döndürür

Y 1 ··· Y d' den A SSkein'e sorgusuna yanıt olarak bitler . Bir SSkein biraz çıktı ile durduğunda ,

B ∗ aynı çıktıyla durur.

Bu yapı şunları garanti eder:

Adv

prf

Zorunlu ∗ (B ∗ ) = Gelişmiş

vol-prf

SSkein (Bir SSkein )

Şekil 10: Sözde rastgele oracle (PRO) tanımı için Games Real H, P ve Sim S. Ayrıca , son öğede özel TyOut tipinin kullanılması nedeniyle B ∗' nin önek içermediğine dikkat edin. her oracle sorgusu. Böylece Lemma 6.1'i uygulayabiliriz. Burada B ∗ 'nin q ′ oracle sorgularını yaptığına dikkat edin

burada q ′ = ∑

q

i = 1 ⌈N i / b⌉ ve her oracle sorgusu en fazla l · ⌈l ′ / b⌉ + 3 öğeden oluşur. X. D, Comp'a karşı sonuçta ortaya çıkan prf-hasım olsun. Şimdi D'yi prf-hasımına dönüştürüyoruz

Bir TComp TComp şekilde karşı

Adv

Prf TComp (A TComp ) = Gelişmiş prf

Zorunlu (D).

(6)

Teorem, Denklem (5), Denklem (6) ve Lemma 6.1'den gelir. Tarif etmeye devam ediyor

Bir TComp .

Bir TComp , D' yi çalıştırır. İkincisi bir oracle sorgusu W ∈ X yaptığında, rakip B bunu W =

(T, X) ile | T | = t ve | X | = b. T, X üzerinde kendi kehanetini çağırır ve cevabı D'ye döndürür.

Değiştirilebilir sıkıştırma işlevimiz TComp, değiştirilebilir blok şifresi E çalıştırılarak elde edilir.

Matyas-Meyer-Oseas [19] modunda. Sonuç olarak, E'nin bir PRP (standart

E'deki varsayım), o zaman TComp bir PRF'dir (Önerme 6.2). Davies için bu doğru olmaz.

Meyer [22, 23] modu. Önerme 6.2 ve Teorem 6.4'ü birleştirerek, PRF güvenliğini elde ederiz.

SSkein, yapımızın diğerlerine kıyasla bir avantajı olan E'nin PRP güvenliği ile ima edilmektedir.

7. Kayıtsızlık

7.1. Tanımlar ve Araçlar

Bir sözde rasgele kahin olmanın tanımı [10, 20], VOL ilkelleri durumuna kadar uzanır. İzin Vermek

H: D 0 × D 1 → {0,1} ∗ idealize edilmiş ilkel P'ye oracle erişimi olan bir VOL işlevi olabilir.

simülatör, durum bilgisi olan bir algoritmadır.

oyunların Şekil 10'da tanımlandığı yerde. A'nın bir oracle sorgusunu asla tekrarlamadığı varsayılır ve

H. etki alanı dışında hiçbir zaman sorgu yapmaz.

Görüntü Öncesi Farkındalık. [12] 'nin ön-görüntü farkındalığı kavramını kullanıyoruz. H bir işlev olsun

idealleştirilmiş bir ilkel P'ye oracle erişimi ile ve E'nin çıkarıcı adı verilen bir algoritma olmasına izin verin. İzin Vermek

oyun PrA'nın Şekil 11'de tanımlandığı yer.

[12] 'den iki sonuca ihtiyacımız var. Birincisi, Comp PrA ise, o zaman kademesinin eksiz PrA olması.

girdiler. Şimdi bunu resmileştirelim.

G: D → X + fonksiyonunun , eğer X 1 = X 2 , tümü için g (X 1 ) ≤ S g (X 2 ) anlamına geliyorsa, soneksiz olduğunu söylüyoruz.

X 1 , X 2 ∈ D. Eğer g sonek içermiyorsa, o zaman da enjeksiyon amaçlıdır, aşağıda kullanacağımız bir şey.

Lemma 7.1 ([12] 'den itibaren) Comp: {0,1} b × X → {0,1} b oracle erişimi olan bir fonksiyon olsun

idealleştirilmiş bir ilkel P. g: D → X + sonek içermeyen bir fonksiyon olsun. Comp ∗ : {0,1} b × X + →

{0,1} b Comp basamaklı olsun. K ∈ {0,1} b ve h: D → {0,1} b şu şekilde tanımlansın:

h (X) = Zorunlu ∗ (K, g (X))

tüm x ∈ D'ler için. O zaman herhangi bir çıkarıcı E Comp için, herhangi bir düşman için bir çıkarıcı E h vardır.

Bir h, Comp'a karşı rakip bir A Comp'dan çıkar, öyle ki

Adv

Pra

h, P, E h

(A h ) ≤ Adv

Pra

Comp, P, E Comp

(A Comp ).

İkinci sonuç, bir PrA fonksiyonunun ve bir RO'nun bileşiminin bir

rastgele oracle.

Lemma 7.2 ([12] 'den itibaren) h: D → {0,1} b , idealize edilmiş bir ilkele erişimi olan bir fonksiyon olsun.

P ve R bir VOL RO olsun. H: N × D → {0,1} b , tarafından tanımlanan VOL işlevi olsun

H (N, X) = R (N, h (X))

tüm N ∈ N ve X ∈ D için. O zaman herhangi bir çıkarıcı E h için herhangi bir

Fn oracle'ına q 1 sorguları ve İlk oracle'ına q 2 sorguları yapan H'ye karşı düşman A H

h'ye karşı bir düşman A h var öyle ki

Adv

profesyonel

H, P, S (A H ) ≤ Adv

Pra

h, P, E h

(A h ).

7.2. 7.2 TComp için Görüntü Öncesi Farkındalık

Önerme 7.3 P, anahtar ve blok uzunluğu b ile ince ayarlı ideal bir değiştirilebilir blok şifresi olsun

uzunluk t. İzin Vermek

7.3. UBI için Ön Görüntü Farkındalığı

Lemma 7.4, TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b'nin oracle erişimi olan bir işlev olmasına izin verir. idealleştirilmiş bir ilkel P. Let f: {0,1} b × MsgSp × TypeSp × {0,1} 6 × [0,2 t − 32 - 1] → {0,1} b be

TComp'tan UBI dönüşümü ile elde edilmiştir. K ∈ {0,1} b ve F = f K olsun . Sonra bir var

çıkarıcı E F öyle ki her çıkarıcı E TComp ve her rakip A F için bir düşman var

Lemma 7.5, TComp: {0,1} b × {0,1} t × {0,1} b → {0,1} b'nin oracle erişimi olan bir işlev olmasına izin verir. İdealleştirilmiş bir ilkel P. Let f: {0,1} b × MsgSp × TypeSp × {0,1} 6 × [0,2 t − 32 - 1] → {0,1} b

TComp'tan UBI dönüşümü yoluyla elde edilebilir. K {0,1} b ve F = f K kısıtlı etki alanı D ⊂ MsgSp × TypeSp × {0,1} 6 × [0,2 t − 32 −1] öyle ki tüm demetler için (M, type, lvl, startl) ∈ D

startl'nin b / 8'in katı olması durumdur, startl = 0 eğer M = ε ve | M | + startl · 2 3 ≤ (2 t − 32 −1) 2 3 .

Daha sonra, bir sıkma E yoktur F , öyle ki her bir özütleme E için TComp her etkisiz bir F orada

rakip bir TComp öyle ki

İspat: X = {0,1} t × {0,1} b ve Comp: {0,1} b × X → {0,1} b Comp (h, (T, X)) = ile tanımlansın

TComp (h, T, X). D = MsgSp × TypeSp × {0,1} 6 × [0,2 t − 32 - 1] olsun ve g: D → X + ile tanımlayın

7.4. SSkein için Kayıtsızlık

Şimdi H'nin sabit IV K ile tam olarak Skein olduğunu gözlemleyin, bu yüzden amacımız H'nin bir PRO olduğunu kanıtlamaktır. ispatın üç adımı vardır.

İlk adım, P 2'nin ideal bir değiştirilebilir blok şifresi olduğunu varsayarak Out'un bir VOL PRO olduğunu göstermektir. TComp 2 bu varsayım altında bir PRO olsaydı, bu kolaylıkla takip edilebilirdi, ancak bu maalesef doğru değil. Bizi burada kurtaran şey, Çıkış'ta TComp 2'ye M i girişinin birkaç sabit değer almasıdır. ve muhalif kontrol altında değil. Her sabit i için h → TComp 2 (h, T 1 , M i ) fonksiyonu bir

PRO ve Out'un bir VOL PRO olduğunu izler. Kayıtsızlığın tanımı daha sonra şunu ima eder:

Denklem (8) 'deki Out'u VOL RO ile değiştirebiliriz. Şimdi, Lemma 7.2, H'nin bir PRO olduğunu söylüyor h PrA olduğu gibi.

Son olarak, Denklem (7) ve Lemma 7.1, f 1 PrA olduğu ve g soneki olmadığı sürece h'nin PrA olduğunu belirtir. Birincisi Lemma 7.4 tarafından ima edilir ve ikincisi türlerle ilgili kurallar tarafından doğrudur.

Hem h hem de Out aynı ideal ilkeli, yani E'ye dayanmaktadır. Bununla birlikte, Out yalnızca E ile birlikte

h tarafından hiçbir zaman kullanılmayan TyOut türü, bu nedenle ikisi bağımsızdır. Bu, yukarıda çok önemlidir. Çerçevemiz, ayrı ideal ayarlanabilir blok şifreleri P 1 , P 2'yi ayrık olarak dikkate alarak bunu yakalar Tam ince ayar alanında ideal değiştirilebilir blok şifrelemeyi birlikte tanımlayan boşlukları ince ayar yapın.

8. Referanslar

1- M. Bellare. NMAC ve HMAC için yeni kanıtlar: Çarpışma direnci olmayan güvenlik. İçinde C. Dwork, editör, Advances in Cryptology - CRYPTO 2006, Cilt 4117, Ders Notları Bilgisayar Bilimi. Springer-Verlag, Berlin, Almanya, 2006.

2- M. Bellare, R. Canetti ve H. Krawczyk. Mesaj kimlik doğrulaması için anahtar hash fonksiyonları.

N. Koblitz, editör, Advances in Cryptology - CRYPTO'96, cilt 1109, Ders Notları Computer Science, sayfa 1–15, Santa Barbara, CA, USA, 18–22 Ağustos 1996. Springer-Verlag, Berlin, Almanya.

3- M. Bellare, R. Canetti ve H. Krawczyk. Sözde rasgele işlevler yeniden ziyaret edildi: Cascade inşaat ve beton güvenliği. 37. Yıllık Bilgisayarın Temelleri Sempozyumunda Science, sayfalar 514–523, 14–16 Ekim, Burlington, Vermont 1996. IEEE Computer Society Press.

4- M. Bellare, J. Kilian ve P. Rogaway. Şifre bloğu zincirleme mesajının güvenliği kimlik doğrulama kodu. Y. Desmedt, editör, Advances in Cryptology - CRYPTO'94, cilt 839, Bilgisayar Bilimleri Ders Notları, sayfa 341-358, Santa Barbara, CA, ABD, 21 Ağustos 25, 1994. Springer-Verlag, Berlin, Almanya.

5- M. Bellare ve T. Ristenpart. Birden çok özelliği koruyan karma etki alanı uzantısı ve emd dönüşümü. Kriptolojideki Gelişmelerde - ASIACRYPT 2006, Bilgisayarda Ders Notları Bilim. Springer-Verlag, Berlin, Almanya, Aralık 2006.

6- M. Bellare ve P. Rogaway. Kod tabanlı oyun oynama kanıtları ve üçlü şifreleme güvenliği yon. Kriptolojideki Gelişmelerde - EUROCRYPT 2006, Bilgisayar Bilimi Ders Notları. Springer-Verlag, Berlin, Almanya, 2006

7- M. Bellare ve B. Yee. Özel anahtar kriptografisinde ileri güvenlik. Editör M. Joye'de, Kriptolojide Konular - CT-RSA 2003, Bilgisayar Bilimi Ders Notları cilt 2612, sayfalar 1–18, San Francisco, CA, ABD, 13–17 Nisan 2003. Springer-Verlag, Berlin, Almanya.

8- J. Black, P. Rogaway ve T. Shrimpton. Blok şifre tabanlı kara kutu analizi PGV'den karma işlev yapıları. M. Yung, editör, Advances in Cryptology - CRYPTO 2002, Bilgisayar Bilimleri Ders Notları'nın 2442. Hacmi. Springer-Verlag, Berlin, Almanya, 2002.

9- M. Blum ve S. Micali. Kriptografik olarak güçlü sahte rasgele dizileri nasıl oluşturulur bitler. Bilgi İşlem Üzerine SIAM Dergisi, 13 (4): 850–864, 1984.

10- J.-S. Coron, Y. Dodis, C. Malinaud ve P. Puniya. Merkle-Damgård yeniden ziyaret edildi: Nasıl yapılır bir hash işlevi oluşturun. V.Shoup, editör, Advances in Cryptology - CRYPTO 2005, Bilgisayar Bilimleri Ders Notları cilt 3621. Springer-Verlag, Berlin, Almanya, 2005.

11- I. Damgård. Hash fonksiyonları için bir tasarım prensibi. G. Brassard, editör, Advances in Cryptology - CRYPTO'89, Bilgisayar Bilimleri Ders Notları'nın 435. hacmi, Santa Barbara, CA, USA, 20–24 Ağustos 1990. Springer-Verlag, Berlin, Almanya.

12- Y. Dodis, T. Ristenpart ve T. Shrimpton. Pratik uygulamalar için merkle-damgard'ı kurtarma tions. Kriptolojide Gelişmeler - EUROCRYPT 2009, Bilgisayar Bilimi Ders Notları, Santa Barbara, CA, ABD, 2009. Springer-Verlag, Berlin, Almanya.

13- N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas ve J. Walker. Skein hash fonksiyonu ailesi. NIST Şifreleme Karma Algoritmasına Gönderme Yarışma, Ekim 2008.

14- N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas ve J. Walker Skein hash fonksiyon ailesi. NIST Şifreleme Karma Algoritmasına Gönderme Yarışma, Ekim 2008.

15- Anahtarlı karma mesaj kimlik doğrulama kodu. Amerikan Bankacılar Birliği, ANSI X9.71, 2000.

16- Anahtarlı karma mesaj kimlik doğrulama kodu (hmac). Ulusal Standartlar Enstitüsü ve Teknoloji, NIST FIPS PUB 198, ABD Ticaret Bakanlığı, Mart 2002.

17- H. Krawczyk, M. Bellare ve R. Canetti. HMAC: Mesaj kimlik doğrulaması için anahtarlı hasing. IETF Yorumlar için İnternet Talebi 2104, Şubat 1997.

18- M. Liskov, R. Rivest ve D. Wagner. Değiştirilebilir blok şifreleri. M. Yung, editör, Advances in Cryptology - CRYPTO 2002, Cilt 2442, Bilgisayar Bilimi Ders Notları, sayfalar 31–46. Springer-Verlag, Berlin, Almanya, 2002.

19- S. Matyas, C. Meyer ve J. Oseas. Şifreleme ile güçlü tek yönlü işlevler oluşturma algoritması. IBM Teknik Açıklama Bülteni, 27 (10A), 1985.

20- UM Maurer, R. Renner ve C. Holenstein. Kayıtsızlık, imkansızlık sonuçları indirimler ve rastgele oracle metodolojisine uygulamalar. M. Naor, editör, TCC 2004:1. Kriptografi Teorisi Konferansı, Bilgisayar Bilimleri Ders Notları cilt 2951, sayfalar 21–39, Cambridge, MA, USA, 19–21 Şubat 2004. Springer-Verlag, Berlin, Almanya

21- RC Merkle. Tek yönlü hash fonksiyonları ve DES. G. Brassard, editör, Advances in Cryptology- CRYPTO'89, Bilgisayar Bilimleri Ders Notları'nın 435. cildi, sayfa 428-446, Santa Barbara, CA, USA, 20–24 Ağustos 1990. Springer-Verlag, Berlin, Almanya.