Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
On the Provable Dual Attack for LWE by Modulus Switching
Get PDFAs a theoretical cornerstone of post-quantum cryptography, the Learning With Errors (LWE) problem serves as the security foundation for standardized algorithms such as Kyber and Dilithium. Recently, a framework for provable dual attacks on LWE has been proposed by Pouly et al. in Eurocrypt 2024, addressing the limitations in effectiveness caused by existing methods\u27 reliance on heuristic assumptions in LWE dual attacks. Their paper also poses an open problem on how to formally integrate modulus switching into this framework to reduce attack costs. The main purpose of this paper is to give a solution of this open problem by presenting an improved provable dual attack method that incorporates modulus switching and Chinese Remainder Theorem (CRT) techniques. First, we design a modulus switching mechanism that eliminates practical errors via the Poisson summation formula. By embedding the inherent noise from modulus switching into a rational lattice framework, our approach effectively preventing the risk of attack failure caused by the merging of such errors with LWE noise. Theoretical guarantees (Theorems \ref{main_theorem} and \ref{main_theorem_entire}) rigorously quantify the parameter ranges for successful attacks. Second, we introduce a CRT-based secret recovery method that aggregates partial secrets from independent sub-attacks. By leveraging the Chinese Remainder Theorem to reconstruct full secrets from congruence relations, our method adapts to arbitrary secret distributions. Furthermore, by using a tighter variant of Banaszczyk\u27s measure inequality, we obtain a precise parameter range for the dual attack\u27s efficacy through rigorous mathematical proof, and achieve the same complementary gap with the contradictory regime (proposed by Ducas et al.) as in Pouly et al.\u27s work. Experiments show - bits superior performance in attack estimation compared to the original framework
Vrity: Verifiable Local Differential Privacy
No full textLocal differential privacy (LDP) enables individuals to report sensitive data while preserving privacy. Unfortunately, LDP mechanisms are vulnerable to poisoning attacks, where adversaries controlling a fraction of the reporting users can significantly distort the aggregate output--much more so than in a non-private solution where the inputs are reported directly. In this paper, we present two novel solutions that prevent poisoning attacks under LDP while preserving its privacy guarantees.
Our first solution, , addresses scenarios where the users report inputs with a ground truth available to a third party. The second solution, , tackles the more challenging case in which the users locally generate their input and there is no ground truth which can be used to bootstrap verifiable randomness generation
Rerandomizable Garbling, Revisited
Get PDFIn key-and-message homomorphic encryption (KMHE), the key space is a subset of the message space, allowing encryption of secret keys such that the same homomorphism can be applied to both the key and the message of a given ciphertext.
KMHE with suitable security properties is the main building block for constructing rerandomizable garbling schemes (RGS, Gentry et al., CRYPTO 2010), which enable advanced cryptographic applications like multi-hop homomorphic encryption, the YOSO-like MPC protocol SCALES (Acharya et al., TCC 2022 and CRYPTO 2024), and more.
The BHHO scheme (Boneh et al., CRYPTO 2008) is currently the only known KMHE scheme suitable for constructing RGS. An encryption of a secret key consists of group elements, where is the security parameter, which incurs a significant bandwidth and computational overhead that makes the scheme itself, and the RGS protocols building upon it, impractical.
We present a new, more efficient KMHE scheme with linear-size ciphertexts.
Despite using heavier cryptographic tools (pairings instead of plain DDH-hard groups), the concrete ciphertext size and computational costs are very significantly reduced. We are able to shrink the ciphertext by 97.83 % (from 16.68 MB to 360 kB) and reduce the estimated computations for encryption by 99.996 % (from 4 minutes to 0.01 seconds) in comparison to BHHO.
Additionally, we introduce gate KMHE as a new tool to build more efficient RGS. Our RGS construction shrinks the size of a garbled gate by 98.99 % (from 133.43 MB to 1.35 MB) and decreases the estimated cost of garbling by 99.998 % (from 17 minutes to 0.02 seconds per gate) in comparison to Acharya et al.
In summary, our work shows for the first time that RGS and the SCALES protocol (and hence YOSO-like MPC) are practically feasible for simple circuits
Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios
Get PDFPrivate set union (PSU) allows two parties to compute the union of their sets without revealing anything else. It can be categorized into balanced and unbalanced scenarios depending on the size of the set on both sides. Recently, Jia et al. (USENIX Security 2024) highlight that existing scalable PSU solutions suffer from during-execution leakage and propose a PSU with enhanced security for the balanced setting. However, their protocol\u27s complexity is superlinear with the size of the set. Thus, the problem of constructing a linear enhanced PSU remains open, and no unbalanced enhanced PSU exists. In this work, we address these two open problems:
-Balanced case: We propose the first linear enhanced PSU. Compared to the state-of-the-art enhanced PSU (Jia et al., USENIX Security 2024), our protocol achieves a reduction in communication cost and a speedup in running time, depending on set sizes and network environments.
-Unbalanced case: We present the first unbalanced enhanced PSU, which achieves sublinear communication complexity in the size of the large set. Experimental results demonstrate that the larger the difference between the two set sizes, the better our protocol performs. For unbalanced set sizes with single thread in Mbps bandwidth, our protocol requires only MB of communication. Compared with the state-of-the-art enhanced PSU, there is shrink in communication and roughly speedup in the running time
One Bit to Rule Them All – Imperfect Randomness Harms Lattice Signatures
Get PDFThe Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol\u27s zero-knowledge property ensures that a signature does not leak information on its secret key , which is achieved by blinding via proper randomness .
Most prominent Fiat-Shamir examples are DSA signatures and the new post-quantum standard Dilithium.
In practice, DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness per signature.
Similar attacks now emerge for lattice-based signatures, such as Dilithium.
We build on, improve and generalize the pioneering leakage attack on Dilithium by Liu, Zhou, Sun, Wang, Zhang, and Ming.
In theory, their original attack can recover a 256-dimensional subkey of Dilithium-II (aka ML-DSA-44) from leakage in a single bit of per signature, in any bit position .
However, the memory requirement of their attack grows exponentially in the bit position of the leak.
As a consequence, if the bit leak is in a high-order position, then their attack is infeasible.
In our improved attack, we introduce a novel transformation, that allows us to get rid of the exponential memory requirement.
Thereby, we make the attack feasible for bit positions .
Furthermore, our novel transformation significantly reduces the number of required signatures in the attack.
The attack applies more generally to all Fiat-Shamir-type lattice-based signatures.
For a signature scheme based on module LWE over an -dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a -fraction of the secret key.
In the ring LWE setting, which can be seen as module LWE with , the attack thus recovers the whole key.
For Dilithium-II, which uses , knowledge of a -fraction of the 1024-dimensional secret key lets its security estimate drop significantly from to bits
Scrutinizing the Security of AES-based Hashing and One-way Functions
Get PDFAES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES in practical instantiations, for instance, the collision resistance of AES-based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in MPC/ZK protocols. In this work, we further advance the meet-in-the-middle (MITM) attack framework on AES-like constructions. We introduce single-color initial structure (SCIS), which leverages new structural insights to reduce the complexity of neutral word generation, a critical bottleneck in MITM attacks. As a result, we yield a series of improved results on AES over the state-of-the-art, including the first classical one-block collision attack on 7-round AES-MMO/MP, marking the first round advancement in over a decade and matching the best attack round in the quantum setting, as well as the first one-block collision attack on 4-round AES-128-DM, bridging the gap highlighted by Taiyama et al. at Asiacrypt 2024 from a non-differential-based approach. Additionally, we provide a comprehensive list of new results on the security margins of AES-192, AES-256, Rijndael-192, and Rijndael-256 in multiple attack settings
Publicly Auditable Garbled Circuit
Get PDFGeneric Secure Multiparty Computation (Generic MPC) recently received much attraction in the blockchain realm as it allows mutually distrustful parties to jointly compute a global function using their private inputs while keeping them private; and more so; the expression of the function can be done in a programmable manner (hence `generic\u27); as opposed to the first rising star cryptographic technique Zero-Knowledge Proof (ZKP) which only allows computation on private input of a single party (via the `commit-and-prove\u27 approach). While ZKP, by nature, allows public verifiability, Generic MPC is not so: Generic MPC mostly focuses on Malicious Security in which the computing result is verifiable only among the computing parties. Yet, in the blockchain realm, public verifiability is important, as the consensus protocol is not just among the computing parties but also external servers. A few works were done to bridge this gap (albeit not in the blockchain realm), i.e., Public Auditable MPC. Public Audtitability is a stronger property than Public Verifiability: the first one certifies the computation done in the MPC, while the latter certifies only the relation between the outputs and the inputs. However, they are non-constant round protocols and only for Secret-Sharing-based MPC, i.e., round complexity scales linearly with the circuit multiplicative depth, while round latency is an important cost metric in the blockchain domain. We address this problem by providing a Public Auditable Garbled Circuit protocol that is maliciously secure, publicly auditable, and constant-round. Our protocol is efficient, with only minimal overhead in terms of round, communication, and public transcript size
LEAGAN: A Decentralized Version-Control Framework for Upgradeable Smart Contracts
Get PDFSmart contracts are integral to decentralized systems like blockchains and enable the automation of processes through programmable conditions. However, their immutability, once deployed, poses challenges when addressing errors or bugs. Existing solutions, such as proxy contracts, facilitate upgrades while preserving application integrity. Yet, proxy contracts bring issues such as storage constraints and proxy selector clashes - along with complex inheritance management. This paper introduces a novel upgradeable smart contract framework with version control, named decentraLized vErsion control and updAte manaGement in upgrAdeable smart coNtracts (LEAGAN). LEAGAN is the first decentralized updatable smart contract framework that employs data separation with Incremental Hash (IH) and Revision Control System (RCS). It updates multiple contract versions without starting anew for each update, and reduces time complexity, and where RCS optimizes space utilization through differentiated version control. LEAGAN also introduces the first status contract in upgradeable smart contracts, and which reduces overhead while maintaining immutability. In Ethereum Virtual Machine (EVM) experiments, LEAGAN shows 40\% better space utilization, 30\% improved time complexity, and 25\% lower gas consumption compared to state-of-the-art models. It thus stands as a promising solution for enhancing blockchain system efficiency
Quantum pseudoresources imply cryptography
Get PDFWhile one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it.
In this work, we study the cryptographic usefulness of quantum pseudoresources —a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting.
Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource
Securing Nested Attestation of Confidential Serverless Computing without Intra-Enclave Isolation
Get PDFConfidential Computing-as-a-Service has gained significant attention in recent years, driven by rapid advances in Trusted Execution Environment (TEE) technology. Among various architectures, confidential serverless computing has emerged as a promising model. A common approach to designing confidential serverless computing involves decoupling the client workload from the initial enclave image and dynamically provisioning the workload at runtime. This enables both offloading the costly enclave bootstrapping and maintaining a fixed reference measurement for attestation. This decoupling necessitates nested attestation, where the client’s workload is attested via a custom attestation module embedded in a platform-attested enclave established at boot time. The challenge in designing nested attestation, however, is to distinguish fresh enclaves from the used ones to prevent enclave reuse. Specifically, a previously used enclave may be compromised and its attestation module tampered with. If the enclave is reused for another workload, it could bypass runtime attestation, allowing unverified code to execute.
In this paper, we present a novel approach to securing nested attestation for confidential serverless computing on Intel Software Guard Extensions (Intel SGX). Unlike prior works, our approach does not rely on intra-enclave isolation techniques to sandbox the client’s workload. Instead, we leverage the Key Separation and Sharing (KSS) feature of Intel SGX to track and prevent enclave reuse based on its immutable IDs. We develop a prototype system for confidential serverless computing for Python workloads, incorporating our nested attestation scheme, and present an empirical evaluation of its performance.
We believe our scheme unveils a unique yet previously overlooked role of KSS---post-compromise identification, with broader implications beyond serverless computing. As a concrete example, we demonstrate how KSS can be leveraged to implement an enclave-binding TPM on Intel SGX, which is of independent interest