pith. sign in

arxiv: 2508.09673 · v2 · submitted 2025-08-13 · 💻 cs.CR

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

Damiano Abram , Giulio Malavolta , Lawrence Roy This is my paper

Pith reviewed 2026-05-18 23:30 UTC · model grok-4.3

classification 💻 cs.CR
keywords succinct oblivious tensor evaluationlaconic function evaluationlearning with errorsadaptive securitytrapdoor hashinghomomorphic secret sharingoblivious transfer
0
0 comments X

The pith

A new succinct oblivious tensor evaluation protocol from LWE yields adaptively secure laconic function evaluation with communication linear in input size plus depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines succinct oblivious tensor evaluation as a two-message protocol in which parties compute an additive secret sharing of the tensor product of their private vectors while keeping both message size and common reference string size independent of vector dimension. It gives an optimal construction of this primitive from the standard learning with errors assumption and uses it to obtain several new or improved primitives whose security also reduces to LWE. A reader would care because the resulting schemes achieve adaptive security for laconic function evaluation and trapdoor hashing without relying on non-standard assumptions, while keeping communication close to the information-theoretic minimum.

Core claim

The authors construct succinct oblivious tensor evaluation from LWE so that two parties exchange two simultaneous messages whose total length is independent of the dimension of the input vectors and obtain an additive secret sharing of their tensor product. The same construction yields the first adaptively secure laconic function evaluation scheme for depth-D functions with total communication m + ℓ + D · poly(λ), a trapdoor hash function for all circuits, optimally succinct homomorphic secret sharing for all functions, and a rate-1/2 laconic oblivious transfer protocol for batch messages, all from standard LWE.

What carries the argument

Succinct oblivious tensor evaluation, the two-message protocol that produces an additive secret sharing of x ⊗ y with communication and CRS size independent of dim(x).

If this is right

  • Adaptively secure laconic function evaluation for depth-D functions with communication m + ℓ + D · poly(λ).
  • Trapdoor hash functions that work for arbitrary circuits.
  • Optimally succinct homomorphic secret sharing for all functions.
  • Rate-1/2 laconic oblivious transfer for batches of messages.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The dimension-independent communication may allow the same techniques to scale to very large vectors in secure two-party computation without a corresponding increase in bandwidth.
  • Because all listed primitives rest on the same LWE-based encodings, they can be composed directly to build larger protocols such as secure multiparty computation for circuits of moderate depth.
  • The adaptive security property removes the need for non-adaptive assumptions in applications where the adversary can choose inputs after seeing the public parameters.

Load-bearing premise

The new adaptive lattice encodings must simultaneously be correct and satisfy the required simulation and indistinguishability properties under the LWE assumption.

What would settle it

An efficient algorithm that distinguishes the two messages of the OTE protocol from uniform random strings (or that breaks the adaptive security of the derived laconic function evaluation) when the underlying LWE instance is hard would falsify the central claims.

read the original abstract

We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors $\mathbf{x} \otimes \mathbf{y}$, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of $\mathbf{x}$. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE, such as: * Adaptively secure laconic function evaluation for depth-$D$ functions $f:\{0, 1\}^m\rightarrow\{0, 1\}^\ell$ with communication $m+\ell+D\cdot \mathrm{poly}(\lambda)$. * A trapdoor hash function for all functions. * An (optimally) succinct homomorphic secret sharing for all functions. * A rate-$1/2$ laconic oblivious transfer for batch messages, which is best possible. In particular, we obtain the first laconic function evaluation scheme that is adaptively secure from the standard LWE assumption, improving upon Quach, Wee, and Wichs (FOCS 2018). As a key technical ingredient, we introduce a new notion of \emph{adaptive lattice encodings}, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces succinct oblivious tensor evaluation (OTE), a two-message protocol in which parties obtain an additive secret sharing of the tensor product x ⊗ y with message and CRS sizes independent of dim(x). It constructs such an OTE from standard LWE via a new primitive called adaptive lattice encodings, then uses it to obtain adaptively secure laconic function evaluation for depth-D functions with communication m + ℓ + D·poly(λ), trapdoor hashing for all functions, succinct homomorphic secret sharing for all functions, and rate-1/2 laconic OT for batch messages, all with security reducible to LWE. This yields the first adaptively secure LFE from standard LWE, improving on Quach-Wee-Wichs (FOCS 2018).

Significance. If the reductions are correct, the work supplies the first adaptively secure LFE from plain LWE together with several other laconic primitives achieving optimal or near-optimal rates under the same assumption. The new adaptive lattice encodings primitive is presented as potentially reusable and the paper supplies explicit communication bounds and black-box compositions, which are concrete strengths.

major comments (2)
  1. [§3] §3 (Adaptive Lattice Encodings): The security reduction for the adaptive simulation property must be checked in full; the adversary selects the function or circuit after seeing the CRS and the first encoding message, and it is not immediately clear whether the reduction to standard LWE preserves polynomial modulus and noise without additional assumptions or loss of adaptivity.
  2. [§5.1] §5.1 (LFE construction): The claimed communication m + ℓ + D·poly(λ) for depth-D functions relies on the succinct OTE being plugged into the laconic evaluation; verify that the depth dependence does not introduce hidden super-polynomial factors in the security reduction or in the concrete parameter setting.
minor comments (2)
  1. [Abstract] Abstract and §1: the phrase 'optimal complexity' for OTE should be accompanied by a precise asymptotic statement (e.g., O(λ) or O(λ + log n)) rather than left implicit.
  2. [§2] Notation: the tensor-product notation x ⊗ y is used without an explicit definition of the underlying ring or vector spaces in the preliminaries; add a short paragraph clarifying the ambient module.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report. We address each major comment below with clarifications on the security reductions and constructions.

read point-by-point responses

  1. Referee: [§3] §3 (Adaptive Lattice Encodings): The security reduction for the adaptive simulation property must be checked in full; the adversary selects the function or circuit after seeing the CRS and the first encoding message, and it is not immediately clear whether the reduction to standard LWE preserves polynomial modulus and noise without additional assumptions or loss of adaptivity.

    Authors: In the proof of Theorem 3.1 (Section 3.3), the adaptive simulation is shown via a hybrid argument that replaces the adaptive lattice encodings with LWE samples. The CRS and first encoding message are generated independently of the function (which is chosen adaptively afterward), allowing the reduction to embed the LWE challenge directly into these components without knowledge of the function. The modulus and noise parameters are identical to the underlying LWE instance, with only a standard polynomial security loss from the hybrids and no additional assumptions required. We are happy to include an expanded remark or lemma statement in the revision to make this explicit. revision: partial

  2. Referee: [§5.1] §5.1 (LFE construction): The claimed communication m + ℓ + D·poly(λ) for depth-D functions relies on the succinct OTE being plugged into the laconic evaluation; verify that the depth dependence does not introduce hidden super-polynomial factors in the security reduction or in the concrete parameter setting.

    Authors: Section 5.1 constructs the LFE by applying the succinct OTE iteratively across the D layers of the circuit. Each layer contributes a poly(λ) communication overhead from the OTE, yielding the stated bound. The security reduction consists of a sequence of D hybrids, each invoking the OTE security; the total loss is therefore D · poly(λ), which remains polynomial for polynomial-depth circuits. Concrete parameters are set by scaling the LWE dimension and modulus polynomially in D (while keeping noise sub-exponential in λ) to ensure both correctness and security, as already outlined in the parameter discussion following Theorem 5.1. No super-polynomial factors appear in either the reduction or the parameter choice. revision: no

Circularity Check

0 steps flagged

No circularity: all security claims reduce to external standard LWE assumption

full rationale

The paper constructs succinct OTE from the standard LWE problem using a new adaptive lattice encodings primitive, then obtains applications (adaptively secure depth-D LFE, trapdoor hashing, etc.) via black-box composition with security reductions to the same external LWE assumption. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided abstract or description; the central primitive is defined and its correctness/simulation properties are claimed to be proven from LWE without reducing back to the target results by construction. The derivation chain is therefore self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Central claims rest on the standard LWE hardness assumption and the correctness/security of the newly introduced adaptive lattice encodings; no free parameters or additional invented entities beyond the new encoding notion are visible in the abstract.

axioms (1)
  • domain assumption Hardness of the Learning With Errors (LWE) problem
    Invoked as the sole source of security for the OTE construction and all listed applications.
invented entities (1)
  • Adaptive lattice encodings no independent evidence
    purpose: Core technical ingredient enabling succinct OTE and downstream primitives
    New notion introduced by the authors; no independent evidence or prior reference is given in the abstract.

pith-pipeline@v0.9.0 · 5797 in / 1339 out tokens · 30658 ms · 2026-05-18T23:30:29.970471+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.