Permutace bez drápů - Claw-free permutation

v matematický a počítačová věda pole kryptografie, skupina tří čísel (X,y,z) se říká, že je dráp dvou permutací F0 a F1 -li

F0(X) = F1(y) = z.

Pár permutací F0 a F1 se říká, že jsou bez drápů pokud neexistuje efektivní algoritmus pro výpočet drápu.

Terminologie drápy zdarma představili Goldwasser, Micali a Rivest ve svém příspěvku „Paradoxní řešení problému podpisu“ z roku 1984 (a později v ucelenějším časopiseckém článku), kde ukázali, že existence dvojice permutací padacích dveří bez drápů znamená existenci systémů digitálního podpisu zabezpečených proti adaptivní útok na vybranou zprávu.[1][2] Tato konstrukce byla později nahrazena konstrukcí digitálních podpisů z jakékoli jednosměrné permutace padacích dveří.[3] Existence permutace padacích dveří sám o sobě neznamená, že neexistují permutace bez drápů;[4] ukázalo se však, že permutace bez drápů existují, pokud je factoring tvrdý.[5]

Obecný pojem permutace bez drápů (ne nutně padací dveře) byl dále studován Ivan Damgård ve své disertační práci Aplikace funkcí Claw Free v kryptografii (Aarhus University, 1988), kde ukázal, jak konstruovat Funkce hash odolné proti kolizi z permutací bez drápů.[5] Pojem dráp-volnost úzce souvisí s pojmem odolnosti proti kolizi v hashových funkcích. Rozdíl je v tom, že permutace bez drápů jsou páry funkcí, ve kterých je těžké vytvořit kolizi mezi nimi, zatímco hašovací funkce odolná proti kolizi je jedna funkce, ve které je těžké najít kolizi, tj. funkce H je odolný proti kolizi, pokud je těžké najít pár odlišných hodnot X,y takhle

H(X) = H(y).

V literatuře s hashovací funkcí se tomu běžně říká a hash kolize. Říká se, že hashovací funkce, kde je obtížné najít kolize odolnost proti kolizi.

Bit závazek

Vzhledem k dvojici permutací bez drápů F0 a F1 je jednoduché vytvořit schéma závazků. Trochu se zavázat b odesílatel vybere náhodně Xa vypočítá Fb(X). Protože oba F0 a F1 sdílet stejnou doménu (a rozsah), bit b je statisticky skrytý před přijímačem. Chcete-li otevřít závazek, odesílatel jednoduše odešle náhodnost X do přijímače. Odesílatel je vázán na svůj kousek, protože otevření závazku k 1 -b je přesně ekvivalentní nalezení drápu. Všimněte si, že stejně jako konstrukce funkcí Collision Resistant Hash nevyžaduje tato konstrukce, aby funkce bez drápů měly padací dveře.

Reference

  1. ^ Goldwasser, Shafi; Micali, Silvio; Rivest, Ronald L. (1984). „Paradoxní řešení problému podpisu“. Sborník FOCS (PDF). 441–448.
  2. ^ Goldwasser, Shafi; Micali, Silvio; Rivest, Ronald L. (Duben 1988). "Schéma digitálního podpisu zabezpečené proti adaptivním útokům na vybrané zprávy". SIAM J. Comput. 17 (2): 281–308. CiteSeerX  10.1.1.20.8353.
  3. ^ Bellare, Mihir; Micali, Silvio. „Jak se přihlásit při jakékoli permutaci padacích dveří“. Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ Dodis, Jevgenij; Reyzin, Leonid (2002). „V moci permutací bez drápů“. CiteSeerX  10.1.1.19.6331. Citovat deník vyžaduje | deník = (Pomoc)
  5. ^ A b Damgård, Ivan Bjerre (1988). Msgstr "Hash funkce bez kolize a schémata podpisu veřejného klíče". Pokroky v kryptologii - EUROCRYPT ‘87. Přednášky z informatiky. 304. Springer. 203–216. doi:10.1007/3-540-39118-5_19.

Další čtení