Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
So about that Quantum Lattice Thing: Rebuttal to Exact Coset Sampling for Quantum Lattice Algorithms
Get PDFIn this note we identify major issues with “Exact Coset Sampling for Quantum Lattice Algorithms” by Zhang. The issues include:
• in the first version, the proposed algorithm requires foreknowledge of the answer to compute
the answer;
• in the latest version, the proposed algorithm displays basic misunderstandings of quantum
mechanics.
We believe the existence of these issues refute the author’s claims
Fully Homomorphic Encryption for Matrix Arithmetic
Get PDFWe propose an efficient fully homomorphic encryption (FHE) scheme tailored for matrix arithmetic based on the Ring-Learning with Errors (RLWE) problem. The proposed scheme naturally supports matrix multiplication, addition, and Hadamard multiplication for batched matrices of various sizes over both complex numbers and integers. Encrypted matrix multiplication is reduced to four matrix multiplications of ciphertext elements, without the need for expensive operations such as slot-to-coefficient conversion or ring switching. In addition, the scheme efficiently supports matrix transformations, including general and conjugate transpositions, as well as matrix rotations: inter-matrix rotations across batched matrices and intra-matrix rotations within rows and columns. Moreover, the proposed FHE scheme can be directly combined with existing bootstrapping algorithms.
By eliminating the need for expensive operations such as repeated slot rotations and conversion between slot- and coefficient-encoding, the proposed construction achieves significant performance improvements. In our construction, encrypted multiplications of matrices under slot encoding are decomposed into two parts: (1) matrix multiplication — four matrix multiplications of ciphertext coefficients, and (2) key switching — with a total cost approximately 2–4 times that of Hadamard multiplication. We implemented the proposed scheme and utilized the FLINT library for the matrix multiplication component. Experimental results demonstrate that, even when leveraging highly optimized implementations, matrix multiplication remains the major cost, indicating that our construction substantially reduces auxiliary overheads and achieves strong overall efficiency
Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness
Get PDFWe construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement.
As an application, we establish the first PPAD hardness result based on the polynomial hardness of LWE combined with a widely believed complexity assumption.
Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we give the first construction from the polynomial hardness of LWE. This notion may be of independent interest
Multi-Party Functional Encryption (MPFE): A tool in the distributed and decentralized world
Get PDFFunctional Encryption (FE) is a concept that generalizes public-key encryption, allowing a party that owns a private key to find a function of the plaintext (instead of the plaintext itself). Multi-Party Functional Encryption (MPFE) generalizes this concept and adapts it to multi-party settings, allowing for decentralization in both the ciphertexts—which might originate from multiple sources—and the keys—thereby eliminating the necessity of a central authority and avoiding the introduction of a single point of trust and failure. The current paper presents a substantial foundation of MPFE to the non-specialist reader. It provides definitions, classifications, and discusses properties of MPFE and its relation with other cryptographic concepts. The potential applicability of MPFE, which covers multiple domains and use cases, is discussed. The paper investigates the real-world adoption of MPFE, including its presence in technical specifications or its availability in open-source libraries. Finally, the current study discusses challenges and therefore opens up new research directions
Threshold Reporting Protocol for Traceability in Anonymous Social Networks
Get PDFAs anonymous social networks continue to grow in popularity, they raise serious challenges around abuse, misinformation, and harmful behavior. While traditional de-anonymization techniques can address misuse, they often come at the cost of user privacy. Protecting honest users\u27 privacy while keeping malicious ones accountable remains a complex challenge.
A promising alternative is conditional deanonymization, where anonymity is lifted only when abuse is collectively reported and verified by an authority.
In this work, we present a new cryptographic framework for conditional de-anonymization that preserves user anonymity unless a threshold number of validated abuse reports is reached. Our design leverages threshold cryptography to ensure that de-anonymization can only be triggered under well-defined, collectively enforced conditions—resisting false reports, misuse, and collusion. We formalize the model and provide a generic construction from standard cryptographic primitives, proving strong security guarantees even in the presence of adversarial authorities or malicious users. To illustrate its viability, we also propose a concrete instantiation based on lattice-based assumptions, making it a compelling candidate for post-quantum settings
Locally Recoverable Data Availability Sampling
Get PDFWe propose Locally Recoverable Data Availability Sampling (LR-DAS), which upgrades binary, threshold-based availability to graded verification by leveraging optimal locally recoverable codes (e.g., Tamo-Barg). Local groups of size serve as atomic certification units: once verified openings fix a degree- local polynomial, the entire group is certified and accumulates monotonically toward global availability. We formalize a locality-aware commitment with a single algebraic local-global link that binds every accepted local proof to a unique global codeword, preventing cross-group splicing. Our verifier admits a two-tier IOP view (local RS-membership, global TB-proximity, one DEEP-style linking query). We instantiate this with (i) a two-layer KZG design and (ii) a transparent FRI/IOPP stack. Both support batched multi-point openings and cross-block random-weight aggregation, yielding verifier work per certified batch with field payload per block. Security is captured by graded soundness against missing-fraction and missing-group adversaries with explicit overshoot bounds. A lightweight proof-of-custody layer—one unpredictable global opening at publish time plus periodic batched local checks—composes seamlessly to enforce possession without altering the core pipeline. Empirically and analytically, LR-DAS certifies availability with fewer samples than required for global recovery under the same encoding, providing a practical univariate alternative to multivariate repair-based DAS while retaining succinct proofs and a simple prover/verifier pipeline. Design levers allow tuning responsiveness versus distance, and the transparent instantiation offers a post-quantum-ready option
CoBBl: Dynamic constraint generation for SNARKs
Get PDFGeneral-purpose probabilistic proof systems operate on
programs expressed as systems of arithmetic constraints—an
unfriendly representation. There are two broad approaches
in the literature to turning friendlier, high-level programs
into constraints suitable for proof systems: direct translation
and CPU emulation. Direct translators compile a program
into highly optimized constraints; unfortunately, this process
requires expressing all possible paths through the program,
which results in compile times that scale with the program’s
runtime rather than its size. In addition, the prover must
pay the cost of every possible program path, even those
untaken by a given input. In contrast, CPU emulators don’t
compile programs to constraints; instead, they “execute”
those programs, expressed as CPU instructions, on a CPU
emulator that is itself expressed as constraints. As a result,
this approach can’t perform powerful, program-specific op-
timizations, and may require thousands of constraints where
direct translation could use a clever handful. Worse, CPU
emulators inherit an impractically expensive program state
representation from the CPUs they emulate.
This paper presents a compiler and proof system,
CoBBl, that combines the benefits of CPU emulation and
direct translation: it takes advantage of program-specific
optimizations, but doesn’t pay for an unnecessary state
representation or unexecuted computation. COBBL outper-
forms CirC, a state-of-the-art direct translator, by on
compile time and on prover time, and outperforms
Jolt, a state-of-the-art CPU emulator, on prover time by on Jolt-friendly benchmarks, and up to on other
benchmarks
HE-based On-the-Fly MPC, Revisited: Universal Composability, Approximate and Imperfect Computation, Circuit Privacy
Get PDFOn-the-fly multi-party computation (MPC), introduced by López-Alt, Tromer, and Vaikuntanathan (STOC 2012), enables clients to dynamically join a computation without remaining continuously online. Yet, the original proposal suffers from substantial efficiency and expressivity limitations hindering practical deployments. Even though various techniques have been proposed to mitigate these shortcomings, seeing on-the-fly MPC as a combination of independent building blocks jeopardizes the security of the original model.
Thus, we revisit on-the-fly MPC in light of recent advances and extend its formal framework to incorporate efficiency and expressivity improvements. Our approach is built around \emph{multi-group homomorphic encryption} (MGHE), which generalizes threshold and multi-key HE and serves as the core primitive for on-the-fly MPC. Our contributions are fourfold:
i) We propose new security notions for MGHE (e.g., IND-CPA with partial decryption, circuit privacy) and justify their suitability to the on-the-fly MPC.
ii) We present the first ideal functionality for MGHE in the Universal Composability (UC) framework and characterize the conditions under which it can be realized, via reductions to our proposed security notions.
iii) We present a generic protocol that securely realizes our on-the-fly MPC functionality against a semi-malicious adversary from our MGHE functionality.
iv) Finally, we provide two generic compilers that lift these protocols to withstand a fully malicious adversary by leveraging zero-knowledge arguments.
Our analysis in the UC framework enables modular protocol analysis, where more efficient schemes can be seamlessly substituted as long as they meet the required security defined by the functionalities, retaining the security guarantees offered by the original construction
Quantum Cryptography and Hardness of Non-Collapsing Measurements
Get PDFOne-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in \u27\u27Microcrypt\u27\u27 where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs. In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class, , which is a sampling version of the decision class introduced in [Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]. We show that if is hard on average for quantum polynomial time, then OWPuzzs exist. We also show that if , then auxiliary-input OWPuzzs exist. is the class of sampling problems that can be solved by a classical polynomial-time deterministic algorithm that can make a single query to a non-collapsing measurement oracle, which is a \u27\u27magical\u27\u27 oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial-time, and therefore our assumptions on which OWPuzzs are based seem extremely plausible. Moreover, our assumptions do not seem to imply OWFs, because the possibility of inverting classical functions would not be helpful to realize quantum non-collapsing measurements. We also study upperbounds of the hardness of . We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing [Dubrov and Ishai, STOC 2006]. We show that dCRPuzzs imply average-case hardness of (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot message authentication codes (MACs), which are a privately-verifiable version of one-shot signatures [Amos, Georgiou, Kiayias, Zhandry, STOC 2020], imply dCRPuzzs
Block-Accumulate Codes: Accelerated Linear Codes for PCGs and ZK
Get PDFLinear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear most prominently in two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer (OT) and vector oblivious linear evaluation (VOLE), and (2) zero-knowledge (ZK) proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix , often with dimensions in the millions, making computational efficiency the dominant bottleneck.
We propose a generalized paradigm for building LPN-friendly codes with provable minimum distance. Roughly speaking, these codes are based on the idea of randomized turbo codes such as repeat accumulate codes. To prove their minimum distance, we present a generalized enumeration technique, which allows us to precisely compute the minimum distance for a broad class of codes. Although we do not prove their asymptotic behavior, the concrete parameters essentially give a linear-time encoder.
Armed with these new techniques, we construct several novel codes, the most promising of which we call Block-Accumulate codes. Our original design goal was to construct codes that run efficiently on GPUs. Surprisingly, we find that our newly constructed codes are the fastest on both GPUs and CPUs, while at the same time achieve a better minimum distance. If we restrict our attention to codes with proofs, our code is faster than state of the art on a CPU and faster on a GPU. Even if we use aggressive parameters, our code is and faster, respectively. Under these parameters, this yields overall PCG speedups of on the CPU and on the GPU, achieving about 200 million OTs or binary Beaver triples per second on the GPU (excluding the one-time 10 ms GGM seed expansion). We expect similar improvements when applied to the ZK space