How to Authenticate a Non-Deterministic Computation: Shift-Hiding Functions, Compressed LWE Sampling, Broadcast Encryption, and Obfuscation
Damiano Abram, Giulio Malavolta, Lawrence Roy
Abstract
We propose a new method to construct homomorphic authentication codes supporting the evaluation of *non-deterministic* computations, extending the celebrated homomorphic lattice encodings [Boneh et al., Eurocrypt 2014]. Our approach relies on the hardness of the decomposed learning with errors problem (LWE), a recently introduced modification of Regev's LWE assumption. We then use this new technical tool to make progress on several open problems in the literature. Specifically, we obtain: 1) A constrained pseudorandom function (PRF), where the evaluation of the PRF on the master key does not depend on the complexity of the constraint, except for its circuit depth. 2) A way to securely compress and re-expand LWE samples in the plain model. 3) An adaptively secure broadcast encryption scheme, with ciphertext and secret keys growing poly-logarithmically with the size of the encrypted set. 4) A pseudorandom obfuscation for all puncturable PRFs, additionally assuming the existence of sub-exponentially secure indistinguishability obfuscation (iO). None of the above mentioned primitives was known to exist from lattice assumptions. As a bonus result, we also obtain a conceptually simple and direct heuristic construction of iO based on lattice techniques, which is not based on the function encryption-to-iO paradigm. We provide evidence that this approach can be used to build provably secure obfuscation for simple functionalities such as sampling lattice preimages using a hidden trapdoor.
AI Impact Assessments
(1 model)Scientific Impact Assessment
1. Core Contribution
This paper introduces non-deterministic homomorphic lattice encodings, extending the foundational BGG+ encodings (Boneh et al., Eurocrypt 2014) to support authentication of non-deterministic computations. The core idea is an implicit binary hash tree of exponential size where each internal node maintains a consistency invariant with its children, but only polynomial-sized paths need to be materialized. Three key properties make this tractable: (i) efficient tree initialization for structured vectors, (ii) path resolution that converts root encodings to leaf encodings, and (iii) local homomorphic computation over paths (additions and bilinear functions), combined with a flattening procedure to control norm growth.
The technical novelty lies in the ability to implicitly hash encodings of all possible bitstrings r ∈ {0,1}^d, compute a function f over the hash, then extend to obtain an encoding of f_r for any r — with the computation of the extension matrix split into an f-dependent part (proportional to circuit size) and an (f,r)-dependent part (proportional only to |r| and circuit depth δ). This "laconic" property breaks circular dependencies that previously prevented several constructions.
2. Methodological Rigor
The paper is technically dense but rigorous. The construction builds systematically from well-defined algebraic invariants maintained throughout the tree structure. Key equations are proven explicitly, norm bounds are tracked carefully through all homomorphic operations (Claims 1-4), and the flattening procedure is shown to reset matrix norms while preserving leaf values. The noise analysis follows standard lattice-based techniques with explicit polynomial bounds.
The security reductions are cleanly structured. The compressed LWE sampling security (Theorem 5) proceeds through 10 hybrid experiments, each step justified by shift-hiding properties or the decomposed LWE assumption. The broadcast encryption proof (Theorem 7) combines statistical key indistinguishability with the compressed sampling security. The pseudorandom obfuscation proof uses a puncturing argument across all inputs combined with shift-hiding.
One notable aspect: all results rely on the decomposed LWE assumption, a recently introduced variant of standard LWE. While this assumption is shown in prior work to be implied by succinct LWE, it is still relatively new and less battle-tested than standard LWE. The paper is transparent about this dependency.
The heuristic iO construction (Section 4.4) is honestly presented as unproven — the circularity preventing a security reduction is clearly acknowledged, with provable security demonstrated only for restricted functionalities (lattice preimage sampling).
3. Potential Impact
The paper makes progress on five distinct open problems, each significant independently:
1. Laconic constrained PRFs from lattices: The first construction where PRF evaluation complexity is independent of the constraint's circuit size (depending only on depth). This enables the "bootstrapping" flavor crucial for subsequent applications.
2. Compressed LWE sampling in the plain model: A practical tool for communication-efficient lattice-based protocols. The ability to compress s^⊤X + e from linear to polylogarithmic size has immediate implications for bandwidth-constrained settings.
3. Adaptively secure broadcast encryption: The first lattice-based construction achieving polylogarithmic ciphertext and key sizes with adaptive security in the plain model. Prior constructions required bilinear pairings, witness encryption, or random oracles. This is particularly significant given recent attacks on lattice-based witness encryption candidates.
4. Pseudorandom obfuscation for puncturable PRFs: Confirms a conjecture from [BDJ+25] (conditional on decomposed LWE and sub-exponential iO).
5. Heuristic lattice-based iO: A conceptually new approach to obfuscation that avoids the functional encryption-to-iO paradigm, potentially offering a simpler path to practical iO if the heuristic withstands cryptanalysis.
4. Timeliness & Relevance
This work addresses a critical bottleneck in lattice-based cryptography: the limitation to deterministic computations in homomorphic encodings. The timing is excellent — it builds on the recent decomposed LWE framework [AMR25a] and circuit commitments of Wee [Wee25], while the post-quantum security landscape makes lattice-based alternatives to pairing-based constructions increasingly important. The broadcast encryption result is particularly timely given the questioning of evasive LWE assumptions underlying witness encryption candidates [BÜW24, DJM+25].
5. Strengths & Limitations
Strengths:
Limitations:
Overall Assessment: This is a high-impact theoretical contribution that introduces a powerful new technical tool and demonstrates its utility across multiple fundamental problems. The breadth and depth of applications, combined with rigorous treatment, make it a significant advance in lattice-based cryptography.
Generated May 7, 2026
Comparison History (52)
Paper 1 introduces a new core primitive—homomorphic authentication for non-deterministic computation—built from a novel decomposed-LWE variant, then leverages it to derive multiple major cryptographic primitives (constrained PRFs, LWE sample compression, adaptively secure broadcast encryption, and connections to obfuscation). This breadth suggests wide cross-area influence and foundational novelty. Paper 2 is methodologically rigorous and timely for decentralized crypto, with strong optimality/impossibility results, but its contributions are more focused within functional encryption and multi-authority settings. Overall, Paper 1’s toolkit-like innovation and downstream applicability indicate higher potential impact.
Paper 2 appears higher impact due to broader novelty and cross-cutting implications: a new framework for homomorphic authentication of non-deterministic computation (a substantial conceptual leap) and multiple downstream primitives (constrained PRFs, LWE sample compression, adaptively secure broadcast encryption, and links to obfuscation). Its lattice-based focus is timely and widely relevant across crypto and complexity. While Paper 1 achieves strong, assumption-improving results for laconic OT/PSI and vector-commitment–specific WPRFs, its scope is narrower and more specialized to pairing-based settings.
Paper 1 makes progress on multiple fundamental open problems in cryptography (constrained PRFs, broadcast encryption, obfuscation, compressed LWE sampling) using a novel technical framework (homomorphic authentication for non-deterministic computations). Its breadth of impact across several subfields, the resolution of long-standing open questions about lattice-based constructions, and the potential pathway toward lattice-based iO give it substantially higher impact potential than Paper 2, which, while technically strong and practically relevant, addresses a more focused problem (tight signatures from search LWE).
Paper 1 makes significant advances on multiple open problems in cryptography—constrained PRFs, compressed LWE sampling, adaptively secure broadcast encryption, and obfuscation—all from lattice assumptions, where none were previously known. It introduces a fundamentally new technical tool (homomorphic authentication for non-deterministic computations) with broad applicability. Paper 2 provides important impossibility results and practical attacks on CPAD security for a class of FHE schemes, but its scope is more narrowly focused on security models for existing schemes rather than enabling new constructions across multiple areas.
Paper 1 introduces a novel framework (homomorphic authentication for non-deterministic computation) and leverages a modified LWE assumption to derive multiple previously unknown lattice-based primitives (constrained PRFs, LWE sample compression, adaptively secure broadcast encryption, and obfuscation-related results). This breadth suggests high cross-area impact in theoretical cryptography and foundations. Paper 2 is timely and practically valuable, but its contribution is mainly an incremental performance optimization within a specific bootstrapping workflow, with moderate speedups. Overall, Paper 1 is more likely to shift research directions and enable new constructions.
Paper 1 has higher likely impact: it introduces a new lattice-based technique (shift-hiding / decomposed-LWE) and uses it to derive multiple long-sought primitives (constrained PRFs with depth-only overhead, LWE sample compression, adaptively secure broadcast encryption with polylog sizes, and steps toward obfuscation). This is methodologically aligned with mainstream, well-studied hardness assumptions and could influence several subareas of cryptography. Paper 2’s “FHE without noise” via group encodings/rewriting systems is highly unconventional and historically such claims often fail under cryptanalysis; without rigorous reductions, its impact is less reliable.
Paper 2 makes progress on multiple fundamental open problems in cryptography (constrained PRFs, broadcast encryption, obfuscation from lattices) using rigorous techniques built on well-studied assumptions (LWE). It introduces a novel concept of homomorphic authentication for non-deterministic computations with broad implications. Paper 1 claims noise-free FHE, which would be extraordinary, but such claims based on group-theoretic assumptions have historically faced devastating attacks; the security analysis appears less rigorous and the underlying hardness assumptions are far less established than LWE-based constructions.
Paper 2 addresses multiple significant open problems in cryptography by introducing a novel method for authenticating non-deterministic computations. Its applications span constrained PRFs, compressed LWE sampling, broadcast encryption, and indistinguishability obfuscation (iO), offering a much broader theoretical impact and methodological innovation. While Paper 1 provides valuable efficiency improvements for CP-ABE, Paper 2's foundational contributions and breadth of impact across diverse cryptographic primitives give it a higher potential scientific impact.
Paper 1 resolves several open problems in theoretical cryptography by introducing a novel method for authenticating non-deterministic computations based on lattice assumptions. Its broad implications for fundamental primitives like broadcast encryption, constrained PRFs, and indistinguishability obfuscation offer a deeper, field-wide impact compared to Paper 2, which provides important but narrower algorithmic improvements for specific fully homomorphic encryption operations.
Paper 2 addresses multiple fundamental open problems in cryptography simultaneously—constrained PRFs, compressed LWE sampling, adaptive broadcast encryption, and obfuscation—all from lattice assumptions where none were previously known. Its breadth of impact across cryptographic foundations, introduction of novel authentication for non-deterministic computation, and progress toward lattice-based iO give it substantially higher potential impact. Paper 1 provides important efficiency improvements for homomorphic encryption operations but is more incremental and narrower in scope.