Parallel Cryptography and Complexity Theorems
Explore the world of parallel cryptography and complexity theorems with a focus on Kolmogorov complexity variants, one-way functions, Liu-Pass result, and intriguing results linked to the existence of OWFs in uniform distributions. Discover how AIK plays a pivotal role in transforming functions between different complexities.
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
Hardness of ?? Characterizes Parallel Cryptography Hanlin Ren, Tsinghua Oxford Joint work with Rahul Santhanam (Oxford) CCC 2021 ? ? ? ? ? ? 1 / 7
Kolmogorov Complexity Variants: ????? and ?? K?? : length of the shortest program computing ? in ? steps K?00000 0 = ? log? for reasonable ? ? = poly ? computing K?is in ??! KT: a Kolmogorov-version of circuit complexity KT ? min ? + ?: ?,??? = ??in ? steps print("0"*n) Henceforth Kpoly Universal Turing machine, with random access to ? ?? ?? Fact: KT truth table is polynomially related to its circuit complexity circuit ? ? 2 / 7
One-Way Functions Arguably the single most fundamental concept in crypto ? is a OWF if it is poly-time computable, and for every poly-time adversary ?, Pr ? 0,1?? ? ? Why are OWFs fundamental? necessary for (almost all) crypto [IL 89] sufficient for minicrypt ? 1? ? negl ? . OWF Private-key encryption, Pseudorandom generators, Digital signatures, Authentication schemes, Pseudorandom functions, Commitment schemes, Coin-tossing, ZK proofs (from Yanyi s FOCS 20 slides) easy ? ? ? hard 3 / 7
The Liu-Pass Result On One-Way Functions and Kolmogorov Complexity Theorem. Kpolyis bounded-error hard on average if and only if OWFs exist. Characterizing the central crypto primitive (OWF) by the complexity of a natural problem over the uniform distribution! 4 / 7
Our Result 1 Theorem (Main). KT is (bounded-error) hard on average if and only if there exist one-way functions in (uniform) ??0. ?? It turns out that KT also characterizes some natural crypto problem! SUPER easy (??0) ? ? ? hard ? Recap: Cryptography in ??0[AIK 06] OWFs computable in ??1implies OWFs computable in ??0! Therefore, ??0-OWFs are widely believed to exist. (E.g. they follow from hardness of factoring / LWE) 5 / 7
Our Result 2: AIK as a Reduction AIK is a (non-black-box) transformation from ??1functions to ??0functions And we could interpret it as a (black-box) reduction from ??1- meta-complexity to ??0-meta-complexity! Theorem (Informal). There is an average-case reduction from ??1-Kpolyto KT. Corollary: If KT is bounded-error easy on average, then so is ??1-Kpoly. If KT is zero-error easy on average, then so is ??1-Kpoly. Previously, it s unknown if Kpolyand KT has ANY connection at all!!! 6 / 7
Other Results A High-end version of [Liu-Pass 20] Characterizing the most secure weak OWF using Kpoly! Results for MCSP (Minimum Circuit Size Problem) Non-trivial relationship between OWFs and hardness of MCSP! Not as tight as KT-results Results for Levin s Kt complexity Despite being EXP-complete in the worst case, the bounded-error average-case complexity of Kt characterizes existence of OWFs! 7 / 7
