Source author record

Amit Sahai

Amit Sahai appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Cryptography and Security Data Structures and Algorithms Artificial Intelligence Computation and Language Computational Complexity Information Theory math.IT

Catalog footprint

What is connected

6works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

SLAM: Structural Linguistic Activation Marking for Language Models

LLM watermarks must be detectable without compromising text quality, yet most existing schemes bias the next-token distribution and pay for detection with measurable quality loss. We present SLAM (Structural Linguistic Activation Marking), a novel white-box watermarking scheme that sidesteps this cost by writing the mark into structural geometry rather than token frequencies: sparse autoencoders identify residual-stream directions encoding linguistic structure (e.g., voice, tense, clause order), and we causally steer those directions at generation time, leaving lexical sampling and semantics unconstrained. On Gemma-2 2B and 9B, SLAM achieves 100% detection accuracy with a quality cost of only 1-2 reward points - compared to 7.5-11.5 for KGW, EWD, and Unigram - with naturalness and diversity preserved at near-unwatermarked levels across both models. The trade-off is a complementary robustness profile: SLAM resists word-level edits but is vulnerable to paraphrase that restructures syntax (at a quality cost), the converse of token-distribution methods.

preprint2020arXiv

Indistinguishability Obfuscation from Well-Founded Assumptions

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let $τ\in (0,\infty), δ\in (0,1), ε\in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $λ$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $λ$: - The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^λ)$, - The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^ε}$, where $k$ is the dimension of the LWE secret, - The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^δ$, where $\ell$ is the dimension of the LPN secret, - The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+τ}$, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

preprint2015arXiv

Adaptive Protocols for Interactive Communication

How much adversarial noise can protocols for interactive communication tolerate? This question was examined by Braverman and Rao (IEEE Trans. Inf. Theory, 2014) for the case of "robust" protocols, where each party sends messages only in fixed and predetermined rounds. We consider a new class of non-robust protocols for Interactive Communication, which we call adaptive protocols. Such protocols adapt structurally to the noise induced by the channel in the sense that both the order of speaking, and the length of the protocol may vary depending on observed noise. We define models that capture adaptive protocols and study upper and lower bounds on the permissible noise rate in these models. When the length of the protocol may adaptively change according to the noise, we demonstrate a protocol that tolerates noise rates up to $1/3$. When the order of speaking may adaptively change as well, we demonstrate a protocol that tolerates noise rates up to $2/3$. Hence, adaptivity circumvents an impossibility result of $1/4$ on the fraction of tolerable noise (Braverman and Rao, 2014).

preprint2012arXiv

Attribute-Based Encryption for Circuits from Multilinear Maps

In this work, we provide the first construction of Attribute-Based Encryption (ABE) for general circuits. Our construction is based on the existence of multilinear maps. We prove selective security of our scheme in the standard model under the natural multilinear generalization of the BDDH assumption. Our scheme achieves both Key-Policy and Ciphertext-Policy variants of ABE.

preprint2012arXiv

On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption

In this work, we consider the long-standing open question of constructing constant-round concurrent zero-knowledge protocols in the plain model. Resolving this question is known to require non-black-box techniques. We consider non-black-box techniques for zero-knowledge based on knowledge assumptions, a line of thinking initiated by the work of Hada and Tanaka (CRYPTO 1998). Prior to our work, it was not known whether knowledge assumptions could be used for achieving security in the concurrent setting, due to a number of significant limitations that we discuss here. Nevertheless, we obtain the following results: 1. We obtain the first constant round concurrent zero-knowledge argument for \textbf{NP} in the plain model based on a new variant of knowledge of exponent assumption. Furthermore, our construction avoids the inefficiency inherent in previous non-black-box techniques such that those of Barak (FOCS 2001); we obtain our result through an efficient protocol compiler. 2. Unlike Hada and Tanaka, we do not require a knowledge assumption to argue the soundness of our protocol. Instead, we use a discrete log like assumption, which we call Diffie-Hellman Logarithm Assumption, to prove the soundness of our protocol. 3. We give evidence that our new variant of knowledge of exponent assumption is in fact plausible. In particular, we show that our assumption holds in the generic group model. 4. Knowledge assumptions are especially delicate assumptions whose plausibility may be hard to gauge. We give a novel framework to express knowledge assumptions in a more flexible way, which may allow for formulation of plausible assumptions and exploration of their impact and application in cryptography.

preprint2011arXiv

Potent Tree Codes and their applications: Coding for Interactive Communication, revisited

We study the fundamental problem of reliable interactive communication over a noisy channel. In a breakthrough sequence of papers published in 1992 and 1993, Schulman gave non-constructive proofs of the existence of general methods to emulate any two-party interactive protocol such that: (1) the emulation protocol takes a constant-factor longer than the original protocol, and (2) if the emulation protocol is executed over a noisy channel, then the probability that the emulation protocol fails is exponentially small in the total length of the protocol. Unfortunately, Schulman's emulation procedures either only work in a model with a large amount of shared randomness, or are non-constructive in that they rely on the existence of good tree codes. The only known proofs of the existence of good tree codes are non-constructive, and finding an explicit construction remains an important open problem. Indeed, randomly generated tree codes are not good tree codes with overwhelming probability. In this work, we revisit the problem of reliable interactive communication, and obtain the following results: We introduce a new notion of goodness for a tree code, and define the notion of a potent tree code. We believe that this notion is of independent interest. We prove the correctness of an explicit emulation procedure based on any potent tree code. We show that a randomly generated tree code (with suitable constant alphabet size) is a potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result using only O(n) random bits, where $n$ is the depth of the tree. These results allow us to obtain the first fully explicit emulation procedure for reliable interactive communication over noisy channels with a constant communication overhead, and exponentially small failure probability.