Matthew M. Hong

dblp:279/6103 · also Matthew Man-Hou Hong · DBLP profile ↗
← Back
4ranked-venue papers
2as first author
3since 2021 · last 2025
0009-0003-0969-0140ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Security and privacy · 2 · 1 first-author · 1 since 2021Theory of computation · 2 · 1 first-author · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2025 Efficiently Batching Unambiguous Interactive Proofs
abstract
We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where a bits are communicated per round, then the batch language ${\mathcal{L}}^{\otimes k}$, i.e. the set of k-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity $\ell \cdot$ polylog $(k)$, per-round communication of $a \cdot \ell \cdot$ polylog $(k)+$ poly $(\ell)$ bits, assuming the verifier in the UIP has depth bounded by polylog $(k)$. Prior to this work, the best known batch UIP for ${\mathcal{L}}^{\otimes k}$ required communication complexity at least ($\operatorname{poly}(a) \cdot k^{\epsilon}+k$) $\cdot \ell^{1 / \epsilon}$ for any arbitrarily small constant $\epsilon\gt 0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log \log n}}\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{(\log n)^{\delta}}$ for a small $\delta\gt 0$ significantly smaller than 1/2 (Reingold-Rothblum-Rothblum, STOC 2016).
Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai
FOCS3
2024 Secure Discovery of Genetic Relatives Across Large-Scale and Distributed Genomic Datasets
Matthew M. Hong, David Froelicher, Ricky Magner, Victoria Popic, Bonnie Berger, Hyunghoon Cho
RECOMB1
2023 One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, Vinod Vaikuntanathan
USENIX Security Symposium2
2020 On Computational Shortcuts for Information-Theoretic PIR
Matthew M. Hong, Yuval Ishai, Victor I. Kolobov, Russell W. F. Lai
TCC (1)1