Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Information-theoretic MPC with Constant Communication Overhead
Get PDFWe study the feasibility of constant communication-overhead information-theoretic Multiparty Computation tolerating malicious adversaries in both the synchronous and asynchronous network settings. A simple observation based on the results of Damg\aa rd, Larsen and Neilsen (CRYPTO 2019) allows us to conclude that (a) any statistically-secure MPC with , requires a communication complexity of bits in the synchronous setting; (b) any statistically-secure MPC with , requires a communication complexity of bits in the asynchronous setting; where denotes the circuit, denotes the number of parties and denotes the number of corruptions. Both the results hold even for abort security.
To match the above bounds for , we propose two protocols in the synchronous and respectively in the asynchronous setting, both with guaranteed output delivery and a communication complexity of bits, for a statistical security parameter , a running time of for circuit depth (in expectancy in the asynchronous setting). For this, we require circuits with a SIMD structure. Our constructs are the first constant-overhead statistically-secure MPC protocols with optimal resilience.
Our first technical contributions is a verifiable secret sharing (VSS) protocol with constant-overhead per secret through two-dimensional packing. A second contribution is a degree-reduction (from a higher degree packed sharing to a lower degree packed sharing) protocol with constant overhead.
As a bonus, a simplified version of our statistical MPC protocols, plugged with the VSSs derived from the earlier works of Abraham, Asharov, Patil and Patra (EUROCRYPT 2023) and Choudhury and Patra (IEEE Transactions on Information Theory 2016) allow us to obtain perfectly-secure MPC protocols with a communication cost of bits, where , and a running time of with the resiliency of in synchronous setting and in the asynchronous setting. These resiliency are optimal in perfect setting due to the lower bounds of Damg\aa rd, Patil, Patra, Roy (Eprint 2025) even for abort security
Silent Threshold Cryptography from Pairings: Expressive Policies in the Plain Model
Get PDFThreshold cryptography is a standard technique for distributing trust by splitting cryptographic keys into multiple shares held by different parties. The classic model of threshold cryptography assumes either that a trusted dealer distributes the shares to the different parties (and in doing so, also knows the overall secret) or that the users participate in an interactive distributed key-generation protocol to derive their individual shares. In recent years, several works have proposed a new model where users can independently choose a public key, and there is a public and deterministic function that derives the joint public key associated with a group of users from their individual keys. Schemes with this silent (i.e., non-interactive) setup procedure allow us to take advantage of the utility of threshold cryptography without needing to rely on a trusted dealer or an expensive interactive setup phase.
Existing works have primarily focused on threshold policies. This includes notions like threshold signatures (resp., encryption) with silent setup (where only quorums with at least users can sign (resp., decrypt) a message) and distributed broadcast encryption (a special case of threshold encryption where the threshold is 1). Currently, constructions that support general threshold policies either rely on strong tools such as indistinguishability obfuscation and witness encryption, or analyze security in idealized models like the generic bilinear group model. The use of idealized models is due to the reliance on techniques for constructing succinct non-interactive arguments of knowledge (SNARKs).
In this work, we introduce a new pairing-based approach for constructing threshold signatures and encryption schemes with silent setup. On the one hand, our techniques directly allow us to support expressive policies like monotone Boolean formulas in addition to thresholds. On the other hand, we only rely on basic algebraic tools (i.e., a simple cross-term cancellation strategy), which yields constructions with shorter signatures and ciphertexts compared to previous pairing-based constructions. As an added bonus, we can also prove (static) security under -type assumptions in the plain model. Concretely, the signature size in our distributed threshold signature scheme is 3 group elements and the ciphertext size in our distributed threshold encryption scheme is 4 group elements (together with a short tag)
Breaking the Layer Barrier: Remodeling Private Transformer Inference with Hybrid CKKS and MPC
Get PDFThis paper presents an efficient framework for private Transformer inference that combines Homomorphic Encryption (HE) and Secure Multi-party Computation (MPC) to protect data privacy. Existing methods often leverage HE for linear layers (e.g., matrix multiplications) and MPC for non-linear layers (e.g., Softmax activation functions), but the conversion between HE and MPC introduces significant communication costs. The proposed framework, dubbed BLB, overcomes this by breaking down layers into fine-grained operators and further fusing adjacent linear operators, reducing the need for HE/MPC conversions. To manage the increased ciphertext bit width from the fused linear operators, BLB proposes the first secure conversion protocol between CKKS and MPC and enables CKKS-based computation of the fused operators. Additionally, BLB proposes an efficient matrix multiplication protocol for fused computation in Transformers. Extensive evaluations on BERT-base, BERT-large, and GPT2-base show that BLB achieves a reduction in communication overhead compared to BOLT (S&P\u2724) and a reduction compared to Bumblebee (NDSS\u2725), along with latency reductions of and , respectively, when leveraging GPU acceleration
UC-Security of the ZK-NR Protocol under Contextual Entropy Constraints: A Composable Zero-Knowledge Attestation Framework
Get PDFThe CRO Trilemma formalizes the inherent incompatibility between confidentiality, reliability, and legal opposability in proof systems. This paper provides the complete Universal Composability (UC) security proof for the ZK-NR protocol, a layered architecture designed to approach this bound. We model each dialectical layer (Iron, Gold, Clay) as an ideal functionality with erasure semantics and prove indistinguishability between real and ideal executions under post-quantum assumptions. The results establish the composable security of ZK-NR and formally achieve a CRO index Γ_CRO < 0.4 + negl(λ) against adaptive contextual adversaries
Access-Controlled Inner Product Function-Revealing Encryption
Get PDFWe extend the concept of access control for functional encryption, introduced by Abdalla et al. (ASIACRYPT 2020), to function-revealing encryption (Joy and Passelègue, SCN 2018). Here “access control” means that function evaluation is only possible when a specified access policy is met. Specifically, we introduce access-controlled inner product function-revealing encryption (AC-IPFRE) and give two applications.
On the theoretical side, we use AC-IPFRE to show that function-hiding inner-product functional encryption (FH-IPFE), introduced by Bishop et al. (ASIACRYPT 2015), is equivalent to IPFRE. To show this, we in particular generically construct AC-IPFRE from IPFRE for the “non-zero inner-product” (NZIP) access policy. This result uses an effective version of Lagrange’s Four Square Theorem. One consequence of this result is that lower bounds by Ünal (EUROCRYPT 2020) suggest that, as for FH-IPFE, bilinear pairings will be needed to build IPFRE.
On the practical side, we build an outsourced approximate nearest-neighbor (ANN) search protocol and mitigate its leakage via AC-IPFRE. For this, we construct a practical AC-IPFRE scheme in the generic bilinear group model for a specific access policy for ANN search. To this end, we show that techniques of Wee (TCC 2020) implicitly give the most practical FH-IPFE scheme to date. We implement the resulting outsourced ANN search protocol and report on its performance.
Of independent interest, we show AC-IPFRE for NZIP implies attribute-hiding small-universe AC-IPFRE for arbitrary access policies. Previous work on access control for FE did not achieve attribute hiding. Overall, our results demonstrate that AC-IPFRE is of both theoretical and practical interest and set the stage for future work in the area
How to Delete Without a Trace: Certified Deniability in a Quantum World
Get PDFIs it possible to comprehensively destroy a piece of quantum information, so that nothing is left behind except the memory of that one had it at some point? For example, various works, most recently Morimae, Poremba, and Yamakawa (TQC \u2724), show how to construct a signature scheme with certified deletion where a user who deletes a signature on cannot later produce a signature for . However, in all of the existing schemes, even after deletion the user is still able keep irrefutable evidence that was signed, and thus they do not fully capture the spirit of deletion.
In this work, we initiate the study of certified deniability in order to obtain a more comprehensive notion of deletion. Certified deniability uses a simulation-based security definition, ensuring that any information the user has kept after deletion could have been learned without being given the deleteable object to begin with; meaning that deletion leaves no trace behind! We define and construct two non-interactive primitives that satisfy certified deniability in the quantum random oracle model: signatures and non-interactive zero-knowledge arguments (NIZKs). As a consequence, for example, it is not possible to delete a signature/NIZK and later provide convincing evidence that it used to exist. Notably, our results utilize uniquely quantum phenomena to bypass Pass\u27s (CRYPTO \u2703) celebrated result showing that deniable NIZKs are impossible even in the random oracle model
Programmable Bitcoin Verification via Synthesis-Aided Lifting
Get PDFA new wave of proposals, such as covenants (OP_CHECKTEMPLATEVERIFY), the reactivation of OP_CAT, and BitVM-style fraud proofs, promises to turn Bitcoin into a settlement layer for decentralised finance. These projects must be expressed in Bitcoin script, a stack language with no loops or recursion; practical applications therefore expand into megabytes of unrolled opcodes whose slightest error can freeze or steal funds. Existing verification tools collapse under the resulting explosion of constraints.
We present bitguard, the first scalable verifier for programmable-Bitcoin artifacts.
Inspired by recent advances in program lifting and synthesis, bitguard automatically (i) lifts raw script into a semantics-preserving, register-based DSL and (ii) detects repetitive slices that mimic batch operations (map, fold, filter, Merkle-proof checks). Each slice is replaced with a single higher-order combinator whose behavior is captured by an axiom, shrinking downstream SMT constraints by orders of magnitude. A counter-example-guided inductive synthesis loop ensures every transformed fragment remains equivalent to its original script.
Evaluated on 104 real-world benchmarks, including full BitVM2 prover–verifier pairs, bitguard automatically verifies 88% of the cases in an average of 23.57s, outperforms direct SMT encodings by up to two orders of magnitude, and uncovers 5 previously unknown vulnerabilities. These results demonstrate that synthesis-aided lifting with axiomatized batch combinators delivers practical, rigorous assurance for the emerging ecosystem of programmable Bitcoin
Pseudorandom Obfuscation and Applications
Get PDFWe introduce the notion of pseudorandom obfuscation, a way to obfuscate (keyed) pseudorandom functions in an average-case sense. We study several variants of pseudorandom obfuscation and show a number of applications.
1. Applications in the iO World: Our weakest variant of pseudorandom obfuscation, named obfuscation for identical pseudorandom functions (iPRO), is weaker than indistinguishability obfuscation (iO): rather than obfuscating arbitrary circuits as in iO, iPRO only obfuscates circuits computing pseudorandom functions. We show that iPRO already enables several applications of iO, such as unleveled fully homomorphic encryption (without assuming circular security) and succinct randomized encodings.
2. From iPRO to iO: Despite being a weaker notion than iO, we show two transformations from iPRO to iO. Our first (and main) construction builds iO from iPRO plus standard assumptions on cryptographic bilinear maps. Our second construction builds iO, and even ideal obfuscation, from iPRO alone in the pseudorandom oracle model (Jain, Lin, Luo and Wichs, CRYPTO 2023).
We also formulate stronger variants of pseudorandom obfuscation that help us go beyond the applications of indistinguishability obfuscation.
3. Applications outside the iO World: We show how to construct a succinct witness encryption scheme from a strong version of PRO, where the size of the ciphertext is independent of the witness size. Such a witness encryption scheme is not known to exist even assuming iO.
4. Construction: We show a *heuristic* construction of the strongest version of PRO, secure under the sub-exponential hardness of the learning with errors (LWE) problem, and the private-coin evasive LWE heuristic (Wee, EUROCRYPT 2022; Tsabary, CRYPTO 2022).
Finally, we highlight some barriers in achieving the strongest version of pseudorandom obfuscation
Rate-1 Statistical Non-Interactive Zero-Knowledge
Get PDFWe give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the language, our construction achieves a proof length of where denotes the witness, is the security parameter, is a constant less than 1, and is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from the sub-exponential hardness of either the LWE assumption, or the - assumption on prime-order groups with efficiently computable bilinear maps, or the DDH assumption. Previously, Gentry et al. (Journal of Cryptology, 2015) achieved NIZKs with statistical soundness and computational zero-knowledge with the aforementioned proof length by relying on (circular-secure) Learning with Errors assumption
A Horizontal Attack on the Codes and Restricted Objects Signature Scheme (CROSS)
Get PDFCROSS is a post-quantum secure digital signature scheme submitted to NIST’s Call for Additional Signatures which was recently selected for round 2. It features signature and key sizes in the range of SLH-DSA while providing a substantially faster signing operation. Within this work, we provide the first passive side-channel attack on the scheme. The attack recovers the secret key from all except one parameter sets from a single power trace while requiring at maximum two power traces for the R-SDP(G) 1 Fast instance. To successfully mount the attack, we show how to recover the secret key from side-channel information gained from the syndrome computation in CROSS’ identification protocol. We furthermore show how the hypothesis space for the attack can be restricted using information from the published signature