Relativized Cryptography |
Common terms and phrases
algorithm almost-everywhere complex binary strings ciphertext cleartext message complexity theory computational complexity theory computational security CONP Construction 4.4 cryptanalytic task denote the set difficult task easy-to-check task encoding exists extends f f is safe f-relativized find the prime function f Given any integer goes to infinity goes to zero I-sparse input insecure channel Key Cryptography Knapsack Problem length an exact length-preserving permutation model of computation n-good for f nondeterministic procedure nonstandard model NP-complete NP-hard one-way functions polynomial q polynomial-time oracle machine polynomial-time procedure prime decomposition prime factorization probability problem proof of Lemma Public-Key Cryptography public-key cryptosystems recursive relativized model revealed key runs in polynomial safe cryptoracle secret key Section 3.5 secure transient-key cryptosystem set of cryptograms set of instances strings of length task is difficult task of prime Theorem threshold functions V₁(n ΕΦ