💻 computer science

Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

This paper introduces the notion of succinct oblivious tensor evaluation (OTE) constructed from the standard LWE assumption, which serves as a foundational tool to achieve adaptively secure laconic function evaluation, trapdoor hashing for all circuits, and other optimal cryptographic primitives.

Original authors: Damiano Abram, Giulio Malavolta, Lawrence Roy

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Damiano Abram, Giulio Malavolta, Lawrence Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive puzzle with a friend, but you are in different rooms and can only send each other one short note at the same time. You want to figure out a complex result based on your combined information, but you don't want to reveal your own secret pieces to the other person.

This paper introduces a new, super-efficient way to do exactly that, and then shows how this trick can unlock a whole new world of secure computing.

Here is the breakdown in simple terms:

1. The Core Problem: The "Tensor" Puzzle

Imagine Alice has a giant list of numbers (a vector) and Bob has a smaller secret list. They want to compute a "Tensor Product."

The Analogy: Think of Alice's list as a long row of dominoes and Bob's list as a set of different colored dominoes. A "Tensor Product" is like taking every single domino from Alice and pairing it with every single domino from Bob to create a giant grid of new combinations.
The Catch: Usually, to do this, they would have to send their entire lists to each other. If Alice's list has a million numbers, she'd have to send a million numbers. That's slow and expensive.
The Breakthrough: The authors found a way for Alice and Bob to send tiny notes (logarithmic size) that still allow them to figure out the giant grid result without ever revealing their original lists. It's like sending a single postcard that somehow contains the instructions to build a skyscraper.

2. The Magic Trick: "Oblivious Tensor Evaluation" (OTE)

They call this new tool Succinct Oblivious Tensor Evaluation.

Oblivious: Alice doesn't learn Bob's secret numbers, and Bob doesn't learn Alice's.
Succinct: The messages are tiny, regardless of how big the original data is.
The Secret Sauce: They used a mathematical concept called LWE (Learning With Errors). Imagine this as a "noisy lock." You can lock a message inside a box, but the box is slightly wobbly (noisy). Only someone with the right key can shake the box just enough to hear the message inside, while anyone else just hears static. The authors figured out how to make these noisy locks work together in a chain so that the noise cancels out perfectly at the end, revealing the answer.

3. The Big Wins: What Can We Do Now?

Once they built this "tiny note" machine, they used it to build several other powerful tools:

A. The "Universal Lockpick" (Trapdoor Hash)

Old Way: To check if a specific key opens a specific lock, you usually had to send the whole blueprint of the lock to the key-holder.
New Way: With their new tool, the lock-holder can send a tiny "hash" (a fingerprint) of the lock. The key-holder can then prove they have the right key without revealing the key itself or the full blueprint. This works for any function, even complex computer programs, not just simple math.

B. The "Secret Recipe" (Homomorphic Secret Sharing)

Scenario: Alice and Bob want to cook a meal together (compute a function) using their own secret ingredients.
Old Way: They had to send huge lists of ingredients back and forth.
New Way: They can send tiny, encrypted notes. When they combine their notes, they get the final dish (the result) without ever seeing each other's ingredients. This is "Homomorphic Secret Sharing," and now it works for any recipe, not just simple ones.

C. The "Adaptive" Privacy Shield (Laconic Function Evaluation)

The Problem: In many secure systems, you have to decide what you want to compute before you start the conversation. If you change your mind later, you have to start over.
The Fix: The authors created a system that is Adaptively Secure. This means the "attacker" can wait, see the public setup, and then choose what to attack. The system stays secure even in this tricky scenario.
The "Rate-1" Bonus: They achieved "Rate-1," which is the theoretical limit of efficiency. It means the amount of data you send is almost exactly the size of the answer you get. No wasted space.

4. Why This Matters

Before this paper, if you wanted to do complex, private calculations between two people with minimal communication, you either had to:

Send huge amounts of data (slow).
Trust a very strong, unproven mathematical assumption (risky).
Only do simple math (limited).

This paper says: "We can do complex, private, two-way communication with tiny messages, and we can prove it's safe using standard, well-understood math."

Summary Analogy

Imagine you and a friend are trying to calculate the total cost of a massive shopping list (Alice's list) combined with a secret discount code (Bob's list).

Before: You had to mail each other the entire 500-page shopping list and the 50-page code book.
After: You both write a single sentence on a postcard. You send them simultaneously. You both read the postcards, do a little math in your head, and suddenly you both know the final price. Neither of you saw the other's list or code, and the postcards were tiny.

The authors didn't just find a better way to send postcards; they built a machine that makes these postcards work for any secret calculation, paving the way for faster, more private, and more efficient internet security.

1. Problem Statement

The paper addresses the problem of Non-Interactive Oblivious Tensor Evaluation (NI-OTE). In this scenario, two parties, Alice (the Hasher) and Bob (the Encoder), hold vectors $x \in \mathbb{Z}_q^m$ and $y \in \mathbb{Z}_q^\ell$ respectively. They wish to exchange a single simultaneous round of messages to locally compute an additive secret sharing of the tensor product $x \otimes y$ (i.e., $v + w = x \otimes y$ ) without revealing their private inputs to each other.

The Core Challenge:
The primary goal is communication efficiency. Intuitively, specifying the tensor product requires communication proportional to the size of the inputs ( $m \cdot \ell$ ). The authors aim to construct a protocol where the communication complexity is succinct, specifically logarithmic in the dimension of the larger input ( $m$ ), while maintaining security based on standard cryptographic assumptions (Learning With Errors, LWE).

Furthermore, the paper seeks to leverage this primitive to solve open problems in Laconic Function Evaluation (LFE) and Trapdoor Hashing (TDH), specifically achieving:

Adaptive Security: Security against adversaries who choose inputs after seeing public parameters.
Rate-1: Communication size proportional to the input/output size plus a small overhead, rather than a polynomial blowup.
Support for All Circuits: Extending beyond linear functions or restricted circuit classes (like $\mathsf{NC}^1$ ).

2. Methodology and Technical Approach

The authors' approach is built on a hierarchy of cryptographic primitives, starting from a new OTE construction and evolving into lattice encodings and function evaluation schemes.

A. Succinct NI-OTE Construction

The construction proceeds in two stages:

Half-Succinct NI-OTE:
- Setup: Generates a random matrix $A \in \mathbb{Z}_q^{n \times m}$ and a matrix $B$ .
- Hashing (Alice): Computes a digest $d = A \cdot x$ .
- Encoding (Bob): Computes a matrix $C$ involving $A^\top$ , a random matrix $S$ , noise, and the input $y$ .
- Evaluation: Alice computes $v = C^\top x$ and Bob computes $w = -S^\top d$ . The sum $v+w$ yields $x \otimes y$ plus small noise.
- Limitation: In this initial version, Bob's message size depends on $m$ (the length of $x$ ).
Bootstrapping to Fully-Succinct NI-OTE:
- To make Bob's message succinct, the authors employ a recursive compression strategy.
- Pseudorandomness: Instead of sampling a large random matrix $S$ , they generate $S$ pseudorandomly using LWE samples derived from a smaller secret vector $s$ .
- Recursion: The protocol is applied recursively. Alice hashes blocks of her input $x$ to produce digests. Bob encodes the "randomness" used in the previous step.
- Key Insight: By using binary matrices and specific LWE properties, the size of the randomness vector $s$ remains constant across recursion levels, while the digest size shrinks. This allows the protocol to compress Alice's input to a logarithmic size without causing Bob's message to blow up.

B. Adaptive Lattice Encodings

A critical technical innovation is the introduction of Adaptive Lattice Encodings, which overcome the limitations of the standard BGG+ encodings (Boneh et al., 2014).

The Problem with BGG+: Standard lattice encodings are only secure in the selective setting (where the input is fixed before the public key). If the input is chosen adaptively (after seeing the public key), attacks exist to recover the secret key.
The Solution: The authors propose a new encoding format:
$c^\top = s^\top A + r^\top (x^\top \otimes G) + e^\top$
Here, $s$ is the encryption key and $r$ is the authentication key.
Homomorphic Properties: They demonstrate how to perform linear operations and multiplications between encodings with correlated keys (e.g., multiplying an encoding with keys $(s, r)$ and one with keys $(r, t)$ yields an encoding with keys $(s, t)$ ).
Compression: They introduce a compression technique using the succinct OTE to compress these adaptive encodings, allowing the size to scale logarithmically with the input length while preserving adaptive security.

C. Reverse Trapdoor Hashing (TDH)

The authors construct a Reverse TDH where the Hasher holds a function $f$ and the Encoder holds an input $x$ .

Mechanism: The Hasher sends a digest of $f$ . The Encoder sends an encoding of $x$ . They locally compute a secret sharing of $f(x)$ .
Innovation: By combining the succinct MOLE (Matrix Oblivious Linear Evaluation, derived from OTE) with the adaptive lattice encodings, they achieve a scheme where the encoding key size depends only on the description of $f$ (and is independent of the input size $m$ ), and the digest is constant size.

D. Rate-1 Adaptive LFE

Finally, they construct a Laconic Function Evaluation (LFE) scheme.

Structure: The Hasher sends a hash of $f$ . The Encoder sends an encoding of $x$ . The Hasher recovers $f(x)$ .
Technique: They decompose the function $f$ into a sequence of shallow $\mathsf{RMS}$ (Restricted Multiplication Straightline) programs. They use the Input-Succinct Reverse TDH (where the encoder knows the input to generate the key, but the hash is succinct) to evaluate these layers iteratively.
Privacy: To ensure the Hasher doesn't learn $x$ during the iterative process, they use GSW Fully Homomorphic Encryption (FHE) to encrypt $x$ and evaluate the function homomorphically, removing the one-time pad at the end.

3. Key Contributions

Succinct NI-OTE from Standard LWE:
- First construction of a non-interactive OTE with communication complexity logarithmic in the input dimension, based solely on the standard LWE assumption.
- Achieves optimal communication rates (Rate-1/2 for batched OT).
Adaptive Lattice Encodings:
- Introduces a new encoding scheme that is secure against adaptive attacks under standard LWE, bypassing the need for the "Adaptive LWE" assumption (which was previously conjectured but shown to be false by the authors).
- Provides a counterexample to the Adaptive LWE conjecture from Quach, Wee, and Wichs (FOCS 2018).
First Adaptively-Secure Rate-1 LFE:
- Constructs the first LFE scheme that is simultaneously adaptively secure and Rate-1 (communication $\approx m + \ell + D \cdot \text{poly}(\lambda)$ ).
- Previous works achieved either adaptive security (with poor rates) or Rate-1 (with weak security assumptions).
Universal Trapdoor Hashing:
- Constructs a Trapdoor Hash (TDH) for all functions (and RAM programs) with encoding key size linear in the function description size $|f|$ and independent of the input size.
- Improves upon prior work which was limited to linear functions or required non-succinct CRS.
Succinct Homomorphic Secret Sharing (HSS):
- Provides a public-key HSS scheme for all functions with communication complexity logarithmic in the long input, improving upon previous $\mathsf{NC}^1$ -only or polynomial-communication schemes.

4. Results and Performance

Communication Complexity:
- NI-OTE: $O(\ell \cdot \text{poly}(\lambda) + \text{poly}(\lambda, \log m))$ .
- LFE: $m + \ell + D \cdot \text{poly}(\lambda, \log m, \log \ell, \log D)$ .
- TDH: Encoding key size $|f| \cdot \text{poly}(\lambda, \log m)$ .
Security: All results are proven under the standard Learning With Errors (LWE) assumption. No non-standard assumptions (like Circular LWE or Adaptive LWE) are required for the main results, though Circular LWE is mentioned for optimizing certain parameters.
Rate: The LFE and OT schemes achieve Rate-1 (or Rate-1/2 for batched OT), which is asymptotically optimal.

5. Significance

This paper represents a major advancement in the field of succinct cryptography and secure computation:

Breaking the Adaptive Barrier: It resolves the long-standing open problem of constructing adaptively secure LFE and TDH from standard assumptions. The counterexample to Adaptive LWE clarifies the landscape of lattice-based assumptions, showing that previous "optimistic" parameters were insecure.
Optimality: The achieved communication rates are optimal. For example, in LFE, the communication cannot be smaller than the input size plus the output size; this work achieves exactly that plus a small depth-dependent overhead.
New Primitive (OTE): The Succinct NI-OTE is a powerful new building block that enables efficient secure computation for tensor products, which are fundamental to many cryptographic protocols (e.g., private set intersection, secure multi-party computation).
Practical Implications: The ability to evaluate arbitrary functions with succinct communication and adaptive security opens doors for more efficient privacy-preserving protocols in cloud computing, blockchain, and secure data analysis, particularly where inputs are large and functions are complex.

In summary, the paper unifies several disparate cryptographic goals (succinctness, adaptivity, and universality) under a single, robust framework based on standard LWE, utilizing novel techniques in lattice encoding and recursive compression.