Abstract
In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almostuniversal hash functions such that each function in the family is computable by (2n + o(n))gate circuits of fanin 2 over the B₂ basis. Applying this family, they established the existence of pseudorandom functions computable by circuits of the same complexity, under the standard assumption that OWFs exist. However, a major disadvantage of the hash family construction by Fan, Li, and Yang (STOC 2022) is that it requires a seed length of poly(n), which limits its potential applications.
We address this issue by giving an improved construction of almostuniversal hash functions with seed length polylog(n), such that each function in the family is computable with POLYLOGTIMEuniform (2n + o(n))gate circuits. Our new construction has the following applications in both complexity theory and cryptography.
 (Hardness magnification). Let α : ℕ → ℕ be any function such that α(n) ≤ log n / log log n. We show that if there is an n^{α(n)}sparse NP language that does not have probabilistic circuits of 2n + O(n/log log n) gates, then we have (1) NTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) NP ⊈ SIZE[n^k] for every constant k. Complementing this magnification phenomenon, we present an O(n)sparse language in P which requires probabilistic circuits of size at least 2n  2. This is the first result in hardness magnification showing that even a sublinear additive improvement on known circuit size lower bounds would imply NEXP ⊄ P_{/poly}.
Following Chen, Jin, and Williams (STOC 2020), we also establish a sharp threshold for explicit obstructions: we give an explict obstruction against (2n2)size circuits, and prove that a sublinear additive improvement on the circuit size would imply (1) DTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) P ⊈ SIZE[n^k] for every constant k.
 (Extremely efficient construction of pseudorandom functions). Assuming that one of integer factoring, decisional DiffieHellman, or ring learningwitherrors is subexponentially hard, we show the existence of pseudorandom functions computable by POLYLOGTIMEuniform AC⁰[2] circuits with 2n + o(n) wires, with key length polylog(n). We also show that PRFs computable by POLYLOGTIMEuniform B₂ circuits of 2n + o(n) gates follows from the existence of subexponentially secure oneway functions.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs.CCC.2022.23,
author = {Chen, Lijie and Li, Jiatu and Yang, Tianqi},
title = {{Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {23:123:37},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16585},
URN = {urn:nbn:de:0030drops165852},
doi = {10.4230/LIPIcs.CCC.2022.23},
annote = {Keywords: Almost universal hash functions, hardness magnification, pseudorandom functions}
}
Keywords: 

Almost universal hash functions, hardness magnification, pseudorandom functions 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 