Uniwersalna jednokierunkowa funkcja skrótu

W kryptografii uniwersalna jednokierunkowa funkcja skrótu ( UOWHF , często wymawiana jako „woof”) jest rodzajem uniwersalnej funkcji skrótu o szczególnym znaczeniu dla kryptografii . UOWHF są proponowane jako alternatywa dla odpornych na kolizje funkcji mieszających (CRHF). CRHF mają silną właściwość odporności na kolizje: trudno jest, biorąc pod uwagę losowo wybrane parametry funkcji skrótu, znaleźć jakąkolwiek kolizję funkcji skrótu. Natomiast UOWHF wymagają, aby trudno było znaleźć kolizję, w której jeden obraz wstępny jest wybierany niezależnie od parametrów funkcji skrótu. Prymityw został zasugerowany przez Moni Naor i Moti Yung i jest również znany jako funkcje skrótu „odporne na kolizje celu”; był używany do konstruowania ogólnych schematów podpisów cyfrowych bez funkcji pułapek, a także w ramach schematów bezpiecznego szyfrowania klucza publicznego z wybranym tekstem zaszyfrowanym.

Rodzina UOWHF zawiera skończoną liczbę funkcji mieszających, z których każda ma takie samo prawdopodobieństwo użycia.

Definicja

Właściwość bezpieczeństwa UOWHF jest następująca. Niech będzie algorytmem działającym w dwóch fazach: ${\ displaystyle A}$

• Początkowo nie otrzymuje żadnych $wejściowych (lub$$tylko$ parametr bezpieczeństwa) i wybiera .
• Funkcja skrótu $wybierana$ losowo z rodziny. ${\ Displaystyle A}$ następnie otrzymuje ${\ Displaystyle H}$ i musi wyprowadzać ${\ Displaystyle y \ neq x}$ tak, że ${\ Displaystyle H (x) = H (y )}$ .

Wtedy dla całego czasu wielomianowego $jest$ , że $powiedzie,$ znikome.

Aplikacje

Uważa się, że UOWHF są mniej kosztowne obliczeniowo niż CRHF i są najczęściej używane do celów wydajnościowych w schematach, w których wybór funkcji skrótu odbywa się na pewnym etapie wykonania, a nie wcześniej. Na przykład system kryptograficzny Cramer-Shoup wykorzystuje UOWHF jako część sprawdzania ważności w swoich zaszyfrowanych tekstach.

Zobacz też

• Atak przedobrazowy

Dalsza lektura

• Goldreich, Oded (2004). Podstawy kryptografii . Tom. 2. Cambridge University Press.

Linki zewnętrzne

• Moni Naor i Moti Yung , „ Uniwersalne jednokierunkowe funkcje skrótu i ​​ich zastosowania kryptograficzne ”, 1989.