Hård bit
Inom kryptografi är ett hårt predikat för en envägsfunktion en funktion som tar värdet 0 eller 1, medan dess värde är lätt att beräkna med vetskap och svårt att beräkna endast med kännedom om . Formellt är en polynomiskt beräkningsbar funktion ett hårt predikat för en funktion om den slumpmässiga variabeln är svår att beräkna från slumpvariabeln , där är en slumpvariabel likformigt fördelad på .
![{\displaystyle h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce47c5f7228e69957b5d87bf431b6d486ec780a1)
![{\displaystyle f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58f74160620cb4e1b1140239f2420537964260a8)
Se även
Länkar
- Girsh EA " Computational Complexity and Fundamentals of Cryptography " . En kurs med föreläsningar som beskriver grunderna i beräkningskomplexitet och kryptografi.
- Vereshchagin N.K. Föreläsningsanteckningar från kursen om kryptografi.