Hårdt lidt
I kryptografi er et hårdt prædikat for en envejsfunktion en funktion , der tager værdien 0 eller 1, mens dens værdi er let at beregne ved at kende , og svær at beregne kun ved . Formelt set er en polynomisk beregnelig funktion et hårdt prædikat for en funktion, hvis den stokastiske variabel er svær at beregne ud fra den stokastiske variabel , hvor er en stokastisk variabel ensartet fordelt 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 også
Links
- Girsh EA " Computational Complexity and Fundamentals of Cryptography " . Et kursus med forelæsninger, der beskriver det grundlæggende i beregningsmæssig kompleksitet og kryptografi.
- Vereshchagin N.K. Forelæsningsnotater fra kurset om kryptografi.