Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Ion: Concretely Efficient Submaximal-Fluid MPC with Linear Communication
Get PDFSecure Multi-Party Computation (MPC) in the classical setting requires parties to stay online through the whole computation, which engenders significant inconvenience, especially when dealing with large-scale and complex tasks. The notion of fluid MPC, introduced by Choudhuri et al. (Crypto 2021), aims to tackle this obstacle by presenting a dynamic participation model where parties have the flexibility to join and leave as needed. The best-known honest-majority MPC protocol by Bienstock et al. (Crypto 2023) in the fluid setting achieves linear communication complexity, but still requires significantly larger communication than MPC in the classical setting.
In this paper, we present two concretely efficient fluid MPC protocols with semi-honest security and linear communication in the honest majority setting. To achieve low concrete communication, we propose a separation-generation approach for random double sharings, along with a linear-communication resharing technique for transmitting sharings across two committees. For evaluating multiplication gates, our protocols in the fluid setting achieve the (almost) same communication as the state-of-the-art protocol ATLAS by Goyal et al. (Crypto 2021) in the classical setting. We also extend the two protocols to achieve malicious security while doubling the communication cost. Compared to the best-known fluid MPC protocol, we reduce the communication cost per multiplication gate by a factor of 6 ∼ 9× (resp., 19 ∼ 28×) for semi-honest security (resp., malicious security). As a trade-off, we relax the maximal fluidity where the parties only need to be active in a single round to the submaximal fluidity allowing an extra internal communication round for each committee. We believe that the new setting is a reasonable relaxation for applications and allows us to achieve practical efficiency for fluid MPC
A Novel Quantum Voting System Based on Quantum Blind Signature without Entanglement
Get PDFIn this paper, we specifically review Xu et al.’s quantum blind signature scheme for distributed e-voting systems, which primarily focuses on simulating real-life e-voting. The scheme aims to ensure voter anonymity in an e-voting system. However, we found that it not only suffers from identity impersonation attacks but also lacks the blindness property essential to a blind quantum signature. To address these shortcomings, we propose a new quantum blind signature scheme that leverages quantum mechanical properties and a one-way hash function. Considering that a voting scheme naturally involves an election committee member blindly signing a ballot embedded with the name of the selected candidate, we use our quantum blind signature as the foundation to design a quantum voting system. This system effectively prevents the repudiation and counterfeiting issues present in Xu et al.’s scheme. Additionally, we provide relevant security analyses to support our theoretical framework. The results demonstrate that our scheme outperforms existing literature not only in terms of e-voting security properties—such as undeniability, anonymity, and untraceability—but also in conceptual simplicity and computational efficiency
Correction-Based Fault Attack Against Randomized MAYO
Get PDFThis paper introduces a novel and practical fault injection attack targeting the randomized version of the MAYO post-quantum signature scheme. While prior attacks on MAYO either relied on deterministic signing modes or specific memory assumptions, our attack succeeds without such constraints. By exploiting the inherent structural properties of MAYO signatures, we combine targeted fault injections with signature correction techniques to extract partial information about the secret oil space. By systematically accumulating such partial information across multiple fault-induced signatures and utilizing linear dependencies among oil vectors, we present an efficient method for achieving full secret key recovery. The attack requires only one fault injection per oil coefficient, repeated a small (i.e., 8, 17, 10, or 12 for the different MAYO versions, respectively) number of times. We demonstrate the targeted fault injection attack on a MAYO implementation on an ARM Cortex-M3 processor via clock glitching, establishing the feasibility of the attack in practice. Our approach is validated through simulations, and a detailed computational cost analysis is provided. Additionally, we demonstrate the ineffectiveness of some previously proposed countermeasures against our attack, thereby highlighting the urgent need for developing more robust protection mechanisms for multivariate post-quantum signature schemes, such as MAYO
New Memory Optimizations of Wagner\u27s Algorithms via List Item Reduction
No full textThe Generalized Birthday Problem () serves as a cornerstone for a broad spectrum of cryptanalytic research. The classical solution, Wagner’s -tree algorithm (CRYPTO’02), is characterized by inherently high memory complexity. Subsequently, Biryukov and Khovratovich (NDSS’16) introduced , a memory-hard proof-of-work scheme constructed upon a single-list variant of Wagner’s algorithm. Due to its robust resistance to ASIC mining, has emerged as one of the most widely adopted proof-of-work schemes in blockchain. However, memory optimization for Wagner-style algorithms remains a persistent challenge in cryptographic research. Conventional approaches primarily focus on reducing list size to lower memory consumption, yet this strategy typically incurs a prohibitive time penalty. For instance, halving the peak memory usage of the mining algorithm increases its theoretical time complexity by a factor of .
In this work, we investigate a novel optimization vector: List Item Reduction (LIR), which facilitates practical and fine-grained memory-time trade-offs. We systematize existing LIR techniques and propose novel optimization methods integrated into a new hybrid framework. While our approach does not improve asymptotic memory complexity, it achieves a near-linear trade-off in practice, offering substantial benefits for the concrete design of efficient Wagner-style algorithms. Specifically, our techniques reduce peak memory usage by nearly 50% (from to bits) across all parameters, with only an approximate twofold time penalty. Furthermore, we present concrete implementations, including the first realization of an in-place . Building on these results, we propose an ASIC-friendly framework leveraging an external-memory caching mechanism
Scalable Private World Computer via Root iO: Application-Agnostic iO and Our Roadmap for Making It Practical
Get PDFEthereum has established itself as a world computer, enabling general-purpose, decentralized, and verifiable computation via smart contracts on a globally replicated state. However, because all computations and state are public by default, it is fundamentally unsuitable for confidential smart contracts that jointly process private data from multiple users. This motivates the notion of a private world computer: an ideal future form of Ethereum that preserves its integrity and availability guarantees while supporting such confidential smart contracts. Prior constructions based on implementable cryptographic primitives such as fully homomorphic encryption (FHE) inevitably rely on committees that hold secret shares and perform computations using those shares, a capability that is not provided by today\u27s Ethereum validators. We cannot simply modify the Ethereum protocol so as to shift the committee’s role onto the Ethereum validators, because the computational and communication costs borne by the committee grow with the demand for confidential smart contracts, forcing higher hardware requirements for participation, undermining decentralization, and increasing the risk of malicious collusion. Hence, there remains a fundamental trade-off between committee decentralization and scalability for confidential smart contracts.
In this position paper, we make two contributions toward a scalable private world computer. First, we show how indistinguishability/ideal obfuscation (iO), combined with FHE and succinct non-interactive arguments of knowledge (SNARK), yields a private world computer that, after a one-time obfuscation process, introduces no additional ongoing trust assumptions beyond Ethereum’s validators, incurring no additional overhead for validators to process confidential smart contracts compared to public smart contracts. In this design, a single application-agnostic obfuscated circuit, called root iO, suffices to realize arbitrary confidential smart contracts. The outputs of root iO can be verified on-chain at a cost comparable to signature verification, and the obfuscation process can be distributed among multiple parties while remaining secure as long as at least one party is honest. As the second contribution, we outline our roadmap toward a practical implementation of root iO. Assuming that the underlying assumptions of our lattice-based iO construction remain secure, the remaining missing pieces are technically concrete: namely, practical implementations of verifiable FHE and of homomorphic evaluation of a pseudorandom function (PRF) and SNARK verification over key-homomorphic encodings, which together would allow us to implement root iO without incurring prohibitive overhead
Language-Agnostic Detection of Computation-Constraint Inconsistencies in ZKP Programs via Value Inference
Get PDFZero-knowledge proofs (ZKPs) allow a prover to convince a verifier of a statement\u27s truth without revealing any other information. In recent years, ZKPs have matured into a practical technology underpinning major applications. However, implementing ZKP programs remains challenging, as they operate over arithmetic circuits that encode the logic of both the prover and the verifier. Therefore, developers must not only express the computations for generating proofs, but also explicitly specify the constraints for verification. As recent studies have shown, this decoupling may lead to critical ZKP-specific vulnerabilities.
Unfortunately, existing tools for detecting them are limited, as they:
(1) are tightly coupled to specific ZKP languages,
(2) are confined to the constraint level, preventing reasoning about the underlying computations,
(3) target only a narrow class of bugs,
and (4) suffer from scalability bottlenecks due to reliance on SMT solvers.
To address these limitations, we propose a language-agnostic formal model, called the Domain Consistency Model (DCM), which captures the relationship between computations and constraints. Using this model, we provide a taxonomy of vulnerabilities based on computation-constraint mismatches, including novel subclasses overlooked by existing models. Next, we implement a lightweight automated bug detection tool, called CCC-Check, which is based on abstract interpretation. We evaluate CCC-Check on a dataset of 20 benchmark programs. Compared to the SoTA verification tool CIVER, our tool achieves a 100-1000 speedup, while maintaining a low false positive rate. Finally, using the DCM, we examine six widely adopted ZKP projects and uncover 15 previously unknown vulnerabilities. We reported these bugs to the projects\u27 maintainers, 13 of which have since been patched. Of these 15 vulnerabilities, 12 could not be captured by existing models
Postponing the Glitches is Not Enough - A Critical Analysis of the DATE 2024 E-ISW Masking Scheme
Get PDFThe Enhanced ISW (E-ISW) masking scheme, recently proposed at DATE 2024, was introduced as a refinement to the classical ISW construction to restore provable security guarantees in hardware implementations affected by glitches. By enforcing input-complete gate evaluations through the use of artificial delays, E-ISW seeks to mitigate the glitch-induced leakage that compromises standard masking techniques. However, in this work, we demonstrate that this modification is fundamentally insufficient to ensure robust side-channel resistance in realistic hardware environments. We conduct a detailed analysis and present concrete examples where E-ISW fails to prevent information leakage, even when the prescribed countermeasures are correctly applied. These vulnerabilities arise due to deeper conceptual shortcomings in the design, particularly the absence of compositional reasoning about the interaction between glitches and masking. Our results show that the security claims of E-ISW do not hold in practice, and they expose critical limitations in relying on heuristic delay-based fixes without formal and compositional proofs of security. This study serves as a cautionary note for the cryptographic engineering community, emphasizing the necessity of rigorous validation when proposing enhancements to established secure computation techniques
Non-Interactive Blind Signatures from RSA Assumption and More
Get PDFBlind signatures have received increased attention from researchers and practitioners. They allow users to obtain a signature under a message without revealing it to the signer. One of the most popular applications of blind signatures is to use them as one-time tokens, where the issuing is not linkable to the redeeming phase, and the signature under a random identifier forms a valid token. This concept is the backbone of the Privacy Pass system, which uses it to identify honest but anonymous users and protect content delivery networks from botnets.
Non-interactive blind signatures for random messages were introduced by Hanzlik (Eurocrypt\u2723). They allow a signer to create a pre-signature with respect to a particular public key, while the corresponding secret key can later be used to finalize the signature. This non-interaction allows for more applications than in the case of blind signatures. In particular, the author suggested using regular PKI keys as the recipient public key, allowing for a distribution of one-time tokens to users outside the system, e.g., to public keys of GitHub users, similar to airdropping of cryptocurrencies. Unfortunately, despite introducing this concept, the paper fails to provide schemes that work with keys used in the wild.
We solve this open problem. We introduce a generic construction of non-interactive blind signatures that relies on Yao\u27s garbled circuit techniques and provide particular improvements to this generic setting. We replace oblivious transfer with their non-interactive variant and show how to construct them so that the recipient\u27s public key, encoding the choice, is a standard RSA public key . To improve the efficiency of the garbling, we show how to garble the signing algorithm of the pairing-based Pointcheval-Sanders (PS) signatures and the RSA-based signature scheme with efficient protocols by Camenisch and Lysyanskaya. Our technique also apply to the well-known BBS signatures. All our improvements are of independent interest and are central to our contribution
Real-Time Encrypted Emotion Recognition Using Homomorphic Encryption
Get PDFEmotion recognition has been an actively researched topic in the field of HCI. However, multimodal datasets used for
emotion recognition often contain sensitive personal information, such as physiological signals, facial images, and behavioral
patterns, raising significant privacy concerns. In particular, the privacy issues become crucial in workplace settings because
of the risks such as surveillance and unauthorized data usage caused by the misuse of collected datasets. To address this
issue, we propose an Encrypted Emotion Recognition (EER) framework that performs real-time inference on encrypted data
using the CKKS homomorphic encryption (HE) scheme. We evaluated the proposed framework using publicly available
WESAD and Hide-and-seek datasets, demonstrating successful stress/emotion recognition under encryption. The results
demonstrated that encrypted inference achieved similar accuracy to plaintext inference, with accuracy of 0.966 (plaintext)
vs. 0.967 (ciphertext) on the WESAD dataset, and 0.868 for both cases on the Hide-and-Seek dataset. Encrypted inference
was performed on a GPU, with average inference times of 333 milliseconds for the general model and 455 milliseconds for
the personalized model. Furthermore, we validated the feasibility of semi-supervised learning and model personalization in
encrypted environments, enhancing the framework’s real-world applicability. Our findings suggest that the EER framework
provides a scalable, privacy-preserving solution for emotion recognition in domains such as healthcare and workplace settings,
where securing sensitive data is of critical importance
Time-Lock Encrypted Storage for Blockchains
Get PDFWe introduce time-lock encrypted storage (tTLES), a storage service provided by blockchains. In tTLES, clients store encrypted values towards a future decryption time (measured in block height). The security of tTLES requires that a value is decrypted only if (i) the encrypted value is included in the blockchain, and (ii) the time has passed. This is crucially different from existing schemes, which only enforce either of these conditions but not both. We formalize tTLES, and present an efficient protocol that relies on (in a black-box manner) a threshold identity-based encryption scheme, and a recent batch threshold decryption scheme. Finally, we discuss various applications that will benefit from tTLES