1 citations · 4 across the 6 of their papers we have counts for
7 papers
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
Zhihuai Chen, Siyao Guo, Qian Li +2
We show how to distinguish circuits with negations (a.k.a -monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)…
Tight Quantum Time-Space Tradeoffs for Function Inversion
Kai-Min Chung, Siyao Guo, Qipeng Liu +1
In function inversion, we are given a function , and want to prepare some advice of size , such that we can efficiently invert any image in time . This is…
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel +2
This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic app…
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, Siyao Guo +2
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial si…
Complete Classification of Generalized Santha-Vazirani Sources
Salman Beigi, Andrej Bogdanov, Omid Etesami +1
Let be a finite alphabet and be a finite set of distributions over . A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mat…
Testing -Monotonicity
Clément L. Canonne, Elena Grigorescu, Siyao Guo +2
A Boolean -monotone function defined over a finite poset domain alternates between the values and at most times on any ascending chain in . Ther…