Author name cluster

Surya Mathialagan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

FOCS Conference 2025 Conference Paper

On Succinct Obfuscation via Propositional Proofs

Abhishek Jain 0002
Zhengzhong Jin
Surya Mathialagan
Omer Paneth

A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine’s running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook’s theory PV. In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of fully succinct IO where the size of obfuscated program only grows with the size of the program’s secret part and not with the public part or with the input size. Starting with input-succinct IO for PV-equivalent machines, which is known from super-polynomially hard IO for circuits and LWE, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct $\mathbf{p v}$-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary. We demonstrate several applications of fully succinct IO and pv-IO: (i)We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs. (ii)We show how to avoid padding the program before obfuscating it – a step often necessitated by security analysis – by replacing the padding with a public random string. (iii)We give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.

Details

STOC Conference 2025 Conference Paper

Universal SNARGs for NP from Proofs of Correctness

Zhengzhong Jin
Yael Tauman Kalai
Alex Lombardi
Surya Mathialagan

We give new constructions of succinct non-interactive arguments ( SNARG s) for NP in the settings of both non-adaptive and adaptive soundness. Our construction of non-adaptive SNARG is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption ( FHE ) scheme as well as a batch argument ( BARG ) scheme. Specifically, for any choice of parameters ℓ and L , we construct a candidate SNARG scheme for any NP language L with the following properties: (i) the proof length is ℓ· poly (λ), (ii) the common reference string crs has length L · poly (λ), and (iii) the setup is transparent (no private randomness). We prove that this SNARG has non-adaptive soundness assuming the existence of any SNARG where the proof size is ℓ, the crs size is L , and there is a size L Extended Frege ( EF ) proof of completeness for the SNARG . Moreover, we can relax the underlying SNARG to be any 2-message privately verifiable argument where the first message is of length L and the second message is of length ℓ. This yields new SNARG constructions based on any “ EF -friendly” designated-verifier SNARG or witness encryption scheme. We emphasize that our SNARG is universal in the sense that it does not depend on the argument system. We show several new implications of this construction that do not reference proof complexity: (1) a non-adaptive SNARG for NP with transparent crs from LWE under the evasive LWE heuristic. This gives a candidate lattice-based SNARG for NP . (2) a non-adaptive SNARG for NP with transparent crs assuming the (non-explicit) existence of any iO and LWE . (3) a non-adaptive SNARG for NP with a short and transparent (i.e., uniform) crs assuming LWE , FHE and the (non-explicit) existence of any hash function that makes Micali’s SNARG construction sound. (4) a non-adaptive SNARG for languages such as QR and DCR assuming only LWE . In the setting of adaptive soundness, we show how to convert any designated verifier SNARG into publicly verifiable SNARG , assuming the underlying designated verifier SNARG has an EF proof of completeness. As a corollary, we construct an adaptive SNARG for UP with a transparent crs assuming subexponential LWE under the evasive LWE heuristic. We prove our results by extending the encrypt-hash-and- BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC ’24].

Details

STOC Conference 2024 Conference Paper

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

Mina Dalirrooyfard
Surya Mathialagan
Virginia Vassilevska Williams
Yinzhan Xu

We study the problem of finding and listing k -cliques in an m -edge, n -vertex graph, for constant k ≥ 3. This is a fundamental problem of both theoretical and practical importance. Our first contribution is an algorithmic framework for finding k -cliques that gives the first improvement in 19 years over the old runtimes for 4 and 5-clique finding, as a function of m [Eisenbrand and Grandoni, TCS’04]. With the current bounds on matrix multiplication, our algorithms run in O ( m 1.66 ) and O ( m 2.06 ) time, respectively, for 4-clique and 5-clique finding. Our main contribution is an output-sensitive algorithm for listing k -cliques, for any constant k ≥ 3. We complement the algorithm with tight lower bounds based on standard fine-grained assumptions. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of 3-cliques given by Bj'orklund, Pagh, Vassilevska W. and Zwick [ICALP’14]. If the matrix multiplication exponent ω is 2, and if the number of k -cliques t is large enough, the running time of our algorithms is Õ(min{ m 1/ k −2 t 1 − 2/ k ( k −2) , n 2/ k −1 t 1−2/ k ( k −1) }), and this is tight under the Exact- k -Clique Hypothesis. This running time naturally extends the running time obtained by Bj'orklund, Pagh, Vassilevska W. and Zwick for k =3. Our framework is very general in that it gives k -clique listing algorithms whose running times can be measured in terms of the number of ℓ-cliques Δ ℓ in the graph for any 1≤ ℓ< k . This generalizes the typical parameterization in terms of n (the number of 1-cliques) and m (the number of 2-cliques). If ω is 2, and if the size of the output, Δ k , is sufficiently large, then for every ℓ< k , the running time of our algorithm for listing k -cliques is Õ(Δ ℓ 2/ℓ ( k − ℓ) Δ k 1−2/ k ( k −ℓ) ). We also show that this runtime is optimal for all 1 ≤ ℓ < k under the Exact k -Clique hypothesis.

Details