A Direct PRF Construction from Kolmogorov Complexity
Kolmogorov Complexity and Crypto, Pseudorandom Functions (PRFs), Construction Paradigm, Time-Bounded Kolmogorov Complexity in practical cryptography.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Direct PRF Construction from Kolmogorov Complexity Yanyi Liu Rafael Pass Cornell Tech Tel Aviv University & Cornell Tech
Kolmogorov Complexity and Crypto Characterization of OWFs [LP 20] OWFs (and thus private-key primitives) exist iff computing time- bounded Kolmogorov complexity is mildly hard-on-average (Time-bounded) Kolmogorov complexity: Given a string x, what is the shortest (efficient) program that outputs x? Studied in the Soviet Union since 60s [Kol 68,T 84] Independently by Hartmanis [83], Sipser [83], Ko [86] Today s focus: on the practical side
Pseudorandom Functions (PRFs) [GGM84] PRFs are the Swiss army knife of practical crypto : Private-key encryption [GM 84, GGM 85] (Enck(m): (r, m fk(r)); Deck(r, y): y fk(r).) Message authentication code [GGM 85] (tagk(m) = fk(m).) Identification schemes [FS 90] Besides, PRFs also have found applications in Resettable security [CGGM 00] Oblivious RAM [GO 96] Outside Crypto: Computational complexity [RR 97] Learning theory [Val 84]
Pseudorandom Functions (PRFs) [GGM84] A family of functions {fz}z {0,1}*that is Efficient: fz(x) can be computed in poly time Pseudorandom: {xi, fz(xi) : z {0,1}k} is indistinguishable from {xi, F(xi) : F (in the eyes of efficient machines) RF} xi xi fz F vs fz(xi) F(xi) M M Remarks: Adversarially(-adaptively)-selected inputs Quasi-poly security: T-secure for some T(n) = 2c log^2 n
PRFs Construction Paradigm Existing constructions: Generic (OWF + [HILL 99] + [GGM 84]) Advanced Encryption Scheme (AES) Decisional Diffie-Hellman (DDH) [NR 99,NR 04] Factoring Blum-integers [NRR 00] Lattice problems [BPR 12] Concerns: Too inefficient No provable security Broken in BQP [Sho 97] Broken in BQP [Sho 97] Some attempts [Chen 24] Today: PRFs from time-bounded Kolmogorov complexity [LP 21] (Qpoly) OWFs exist if and only if MKtP[s] is mildly hard on average. Note The first direct (quasi-poly secure) PRF construction from a minimal assumption. (If you break it, you break all PRF candidates.)
Time-Bounded Kolmogorov Complexity Give a truthtable x {0,1}nof a Boolean function, what is the size of the smallest program that computes x? program = time-bounded TMs t-time-bounded Kolmogorov Complexity [Kol 68, Ko 86, Sip 83, Har 83, AKB+06] Kt(x) = length of the shortest program ? computing turthtable x within time t(|?|) Fix a universal TM U, and a running time bound t(*). We are looking for the length of the shortest program ? s.t. U(?(i),1t(|?|)) = xi, i <= |x|. MKtP[s] : { truthtable x | Kt(x) <= s(|x|) }
Avg-case Hardness for Sparse Languages Observation: |MKtP[s] {0,1}n| 2s(n). When s(n) = n/2, the trivial outputting NO heuristic succeeds w.p. 1-2-n/2. so MKtP[s] is trivially easy-on-average Our notion [LP 21]: require hardness conditioned on both YES and NO. ?-heuristic* H for L: H succeeds on at least a 1-?(n*) fraction of YES instances, and at least a 1-?(n*) fraction of NO instances, where n* = log|L {0,1}n| Def: We say that MKtP[s] is ?- HoA* w.r.t T-time attackers if MKtP[s] does not have T-time ?-heuristic* w.r.t. infinitely many input length.
PRFs from Kolmogorov Complexity THM [LP 21, LP 23] For any poly t(n) >= 2n, ? > 0, the following are equivalent Quasi-poly secure OWFs exist MKtP[s(n) = ??( ??? ? )] is (1/n?)-HoA* w.r.t. n3-time attackers. THM [HILL 99, GGM 84, IL 90] (Quasi-poly secure) OWFs exist if and only if (Quasi-poly secure) PRFs exist.
PRFs from Kolmogorov Complexity THM [LP 21, LP 23] For any poly t(n) >= 2n, ? > 0, the following are equivalent Quasi-poly secure OWFs exist MKtP[??( ??? ? )] is (1/n?)-HoA* w.r.t. n3-time attackers. Main THM [Today] Assume that for poly t(n)>2n, ? > 0, MKtP[??( ??? ? )] is (1/n? ?)-HoA* w.r.t. n3-time attackers. Then there exists a (direct construction of) (quasi-poly secure) PRF h: 1 {0,1} ^(1+ )*poly log {0,1}log^2( )-> {0,1}
PRFs from Kolmogorov Complexity Main THM [Today] Assume that for poly t(n)>2n, ? > 0, MKtP[??( ??? ? )] is (1/n? ?)- HoA* w.r.t. n3-time attackers. Then there exists a (direct construction of) (quasi- poly secure) PRF h: 1 {0,1} ^(1+ )*poly log {0,1}log^2( )-> {0,1} Remarks: 1. The first direct construction of PRF from a natural hardness assumption that is also implied by PRFs 2. PRF input length: log2 . - Sufficient for CPA-SKE. - Obtain ?input length if s = poly log n. 3. n3-time hardness => quasi-poly OWFs Hardness Magnification [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19, CHO+20]
PRFs from Kolmogorov Complexity Main THM [Today] Assume that for poly t(n)>2n, ? > 0, MKtP[??( ??? ? )] is (1/n? ?)- HoA* w.r.t. n3-time attackers. Then there exists a (direct construction of) (quasi- poly secure) PRF h: 1 {0,1} ^(1+ )*poly log {0,1}log^2( )-> {0,1} Security and efficiency: 1. (Think of t(n) = O(n), ? = 0.1) Running time: ( 1+ ), seed length: ( 1+ ) 2. Security of h (on sec par ) is based on MKtP over length n, where = s(n) = ??( ??? ? ) MKtP[s] can be solved in time 2O(s). (In fact, it is conjectured to be 2O(s)-hard, known as the Perebor Conjecture .) 3. Comparisons with existing constructions: All constructions (except for the LWE or the generic one) have the same efficiency, ours is ? worst in the exponent.
Construction Overview Main THM [Today] Assume that for poly t(n)>2n, ? > 0, MKtP[??( ??? ? )] is (1/n? ?)- HoA* w.r.t. n3-time attackers. Then there exists a (direct construction of) (quasi- poly secure) PRF h: 1 {0,1} ^(1+ )*poly log {0,1}log^2( )-> {0,1} Our construction relies on the following building blocks LP20 OWF Nisan-Wigderson generators
Construction Overview The PRF construction Step 1: Rely on the LP 20 OWF. (Fix some sec par ?.) - Sample an index j [?], a random program of length j (with running time t(| |)). - Define f: f(i) = ?(i) for i {0,1}^(log^2 ?) Step 2: NW generator g(j,?,y) = NWf(y) (with S1=(1,4,7), S2=(1,5,9), , Sm, m = 2O(log^2 ?)) y5 y6 y8 y9 y1 y2 y3 y4 y7 On input seed y = Efficiency Analysis: 1. (g) One call on each bit 2. ( ) repetitions Output g(j, ?, y) = f( ), f( ), f(yS_3), ., f(yS_m) y1 y5y9 y1 y4y7 Step 3: Security amplification. - Take r = ( ) (fresh) repetitions and XOR them together. - Formally h(j1,?1,y1, , jr,?r, yr) = g(j1,?1,y1) g(jr,?r, yr) Security: Any attacker breaking h can be used to break MKtP
Crypto vs. Derandomization NW generators are mostly used in the setting of derandomization, where (Weaker attackers) Only secure when the attacker runs in less time than it s needed to compute the generator - can t assume this for crypto (The need of ECC) Usually instantiated with hard functions encoded by error- correcting codes (ECC) - can t really use ECC (locally computable ECCs don t exist.) Solution: we rely on the fact that we start with average-case hardness of a particular function (based on MKtP).
Conclusion We present a direct PRF construction (with good asymptotic efficiency) from average-case hardness of MKtP[s(n) = ??( ??? ? )] This is the first PRF construction based on a concrete hardness assumption that is also implied by PRF Perspectives: 1. Our proof shows that - The hardness of the search version suffices - Any pseudo-incompressibility generator (a primitive in between OWFs and PRGs) gives direct construction of PRFs. 2. Our result opens up the door for practical PRFs constructions from minimal assumption.
Towards Practical Security Which security parameter to run the PRF on in practice? Meta-complexity Challenge: Pick a random TM M of length n. Output x = M(1), .. M(n^2). Challenge: output a compression of x of length at most 2n. Closely related to Hutter Prize (compression of first 1GB of Wikipedia) Generic attack: Gzip Sufficient for building a PRG Unfortunately, our PRF requires hardness of lossy/approximate compression . (We leave it open to construct a PRF from lossless compression.)
