Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
A New Generalized Attack on RSA-like Cryptosystems
Get PDFRivest, Shamir, and Adleman published the RSA cryptosystem in 1978, which has been widely used over the last four decades. The security of RSA is based on the difficulty of factoring large integers , where and are prime numbers. The public exponent and the private exponent are related by the equation . Recently, Cotan and Teseleanu (NordSec 2023) introduced a variant of RSA, where the public exponent and the private exponent satisfy the equation for some positive integer . In this paper, we study the general equation with positive integers and , and . We show that, given the public parameters and , one can recover and and factor the modulus in polynomial time by combining continued fractions with Coppersmith\u27s algorithm which relies on lattice reduction techniques, under specific conditions on , , and . Furthermore, we show that if the private exponent in an RSA-like cryptosystem is either small or too large, then can be factored in polynomial time. This attack applies to the standard RSA cryptosystem
Side-Channel and Fault Injection Attacks on VOLEitH Signature Schemes: A Case Study of Masked FAEST
Get PDFOngoing efforts to transition to post-quantum public-key cryptosystems have created the need for algorithms with a variety of performance characteristics and security assumptions.
Among the candidates in NIST\u27s post-quantum standardisation process for additional digital signatures is FAEST, a Vector Oblivious Linear Evaluation in-the-Head (VOLEitH)-based scheme, whose security relies on the one-wayness of the Advanced Encryption Standard (AES).
The VOLEitH paradigm enables competitive performance and signature sizes under conservative security assumptions.
However, since it was introduced recently, in 2023, its resistance to physical attacks has not yet been analysed. In this paper, we present the first security analysis of VOLEitH-based signature schemes in the context of side-channel and fault injection attacks. We demonstrate four practical attacks on a masked implementation of FAEST in ARM Cortex-M4 capable of recovering the full secret key with high probability (greater than 0.87) from a single signature. These attacks exploit vulnerabilities of components specific to VOLEitH schemes and FAEST, such as the parallel all-but-one vector commitments, the VOLE generation, and the AES proof generation. Finally, we propose countermeasures to mitigate these attacks and enhance the physical security of VOLEitH-based signature schemes
HiAE: A High-Throughput Authenticated Encryption Algorithm for Cross-Platform Efficiency
Get PDFThis paper addresses the critical challenges in designing cryptographic algorithms that achieve both high performance and cross-platform efficiency on ARM and x86 architectures, catering to the demanding requirements of next-generation communication systems, such as 6G and GPU/NPU interconnections. We propose HiAE, a high-throughput authenticated encryption algorithm optimized for performance exceeding 100 Gbps and designed to meet the stringent security requirements of future communication networks. HiAE leverages the stream cipher structure, integrating the AES round function for non-linear diffusion.
Our design achieves exceptional efficiency, with benchmark results from software implementations across various platforms showing over 340 Gbps on x86 processors and 180 Gbps on ARM devices in AEAD mode, making it the fastest AEAD solution on ARM chips and setting a new performance record on the latest x86 processors
Commit-and-Prove System for Vectors and Applications to Threshold Signing
Get PDFMulti-signatures allow to combine several individual signatures into a compact one and verify it against a short aggregated key. Compared to threshold signatures, multi-signatures enjoy non-interactive key generation but give up on the threshold-setting. Recent works by Das et al. (CCS\u2723) and Garg et al. (S&P\u2724) show how multi-signatures can be turned into schemes that enable efficient verification when an ad hoc threshold -- determined only at verification -- is satisfied. This allows to keep the simple key generation of multi-signatures and support flexible threshold settings in the signing process later on. Both works use the same idea of combining BLS multi-signatures with inner-product proofs over committed keys. Das et al. give a somewhat generic proof from both building blocks, which we show to be flawed, whereas Garg et al. give a direct proof for the combined construction in the algebraic group model.
In this work, we identify the common blueprint used in both works and abstract the proof-based approach through the building block of a commit-and-prove system for vectors (CP). We formally define a flexible set of security properties for the CP system and show how it can be securely combined with a multi-signature to yield a signature with ad hoc thresholds. Our scheme also lifts the threshold signatures into the multiverse setting recently introduced by Baird et al. (S&P\u2723), which allows signers to re-use their long-term keys across several groups. The challenge in the generic construction is to express -- and realize -- the combination of homomorphic proofs and commitments (needed to realize flexible thresholds over fixed group keys) and their simulation extractability (needed in the threshold signature security proof). We finally show that a CP instantiation closely following the ideas of Das et al. can be proven secure, but requires a new flexible-base DL-assumption to do so
Traceable Threshold Encryption without a Trusted Dealer
Get PDFThe fundamental assumption in -out-of- threshold encryption is that the adversary can only corrupt fewer than parties. However, this may be unrealistic in practical scenarios where shareholders could have financial incentives to collude. Boneh, Partap, and Rotem (Crypto\u2724) addressed the case where or more shareholders collude, adding a traceability mechanism to identify at least one colluder. Their constructions require a trusted dealer to distribute secret shares, but it is unclear how to achieve traceability without this trusted party. Since threshold encryption aims to avoid a single point of failure, a natural question is whether we can construct an efficient, traceable threshold encryption scheme without relying on a trusted dealer.
This paper presents two dealerless, traceable threshold encryption constructions by extending the PLBE primitive of Boneh et al. (Eurocrypt\u2706) and combining it with the silent setup threshold encryption construction of Garg et al. (Crypto\u2724). Our first construction achieves an amortized ciphertext size of (for ciphertexts), and the second achieves constant ciphertext size in the worst case but with a less efficient preprocessing phase. Both have constant secret key sizes and require no interaction between parties.
A limitation of Boneh et al.’s constructions is that they only guarantee identifying one colluder, leaving the problem of tracing more traitors unsolved. We address this by applying a technique to our first construction that enables tracing up to traitors
Hollow LWE: A New Spin, Unbounded Updatable Encryption from LWE and PCE
Get PDFUpdatable public-key encryption (UPKE) allows anyone to update a public key while simultaneously producing an update token, given which the secret key holder could consistently update the secret key. Furthermore, ciphertexts encrypted under the old public key remain secure even if the updated secret key is leaked -- a property much desired in secure messaging. All existing lattice-based constructions of UPKE update keys by a noisy linear shift. As the noise accumulates, these schemes either require super-polynomial-size moduli or an a priori bounded number of updates to maintain decryption correctness.
Inspired by recent works on cryptography based on the lattice isomorphism problem, we propose an alternative way to update keys in lattice-based UPKE. Instead of shifting, we rotate them. As rotations do not induce norm growth, our construction supports an unbounded number of updates with a polynomial-size modulus. The security of our scheme is based on the LWE assumption over hollow matrices -- matrices which generate linear codes with non-trivial hull -- and the hardness of permutation code equivalence. Along the way, we also show that LWE over hollow matrices is as hard as LWE over uniform matrices, and that a leftover hash lemma holds for hollow matrices
Dimensional eion: Improving the Attack with Decomposition in Higher Bases
No full textWe revisit the polynomial attack to the problem modulo from [BLLOR22]. Our new algorithm achieves a polynomial time solution in dimension , extending the range of dimensions for which a polynomial attack is known beyond the previous bound of .
We also combine our new algorithm with Wagner\u27s attack to improve the general attack complexity for some of the dimensions where a polynomial solution is still not known.
We implement our polynomial attack and break the one-more unforgeability of blind Schnorr signatures over 256-bit elliptic curves in a few seconds with 192 concurrent sessions
DFS: Delegation-friendly zkSNARK and Private Delegation of Provers
Get PDFZero-Knowledge Succinct Non-interactive Arguments of Knowledge (zkSNARKs) lead to proofs that can be succinctly verified but require huge computational resources to generate. Prior systems outsource proof generation either through public delegation, which reveals the witness to the third party, or, more preferably, private delegation that keeps the witness hidden using multiparty computation (MPC). However, current private delegation schemes struggle with scalability and efficiency due to MPC inefficiencies, poor resource utilization, and suboptimal design of zkSNARK protocols.
In this paper, we introduce DFS, a new zkSNARK that is delegation-friendly for both public and private scenarios. Prior work focused on optimizing the MPC protocols for existing zkSNARKs, while DFS uses co-design between MPC and zkSNARK so that the protocol is efficient for both distributed computing and MPC. In particular, DFS achieves linear prover time and logarithmic verification cost in the non-delegated setting. For private delegation, DFS introduces a scheme with zero communication overhead in MPC and achieves malicious security for free, which results in logarithmic overall communication; while prior work required linear communication. Our evaluation shows that DFS is as efficient as state-of-the-art zkSNARKs in public delegation; when used for private delegation, it scales better than previous work. In particular, for constraints, the total communication of DFS is less than KB, while prior work incurs GB, which is linear to the circuit size. Additionally, we identify and address a security flaw in prior work, EOS (USENIX\u2723)
Dynamic Decentralized Functional Encryption: Generic Constructions with Strong Security
Get PDFDynamic Decentralized Functional Encryption (DDFE) is a generalization of Functional Encryption which allows multiple users to join the system dynamically without interaction and without relying on a trusted third party. Users can independently encrypt their inputs for a joint evaluation under functions embedded in functional decryption keys; and they keep control on these functions as they all have to contribute to the generation of the functional keys.
In this work, we present new generic compilers which, when instantiated with existing schemes from the literature, improve over the state-of-the-art in terms of security, computational assumptions and functionality. Specifically, we obtain the first adaptively secure DDFE schemes for inner products in both the standard and the stronger function-hiding setting which guarantees privacy not only for messages but also for the evaluated functions. Furthermore, we present the first DDFE for inner products whose security can be proven under the LWE assumption in the standard model. Finally, we give the first construction of a DDFE for the attribute-weighted sums functionality with attribute-based access control (with some limitations). All prior constructions guarantee only selective security, rely on group-based assumptions on pairings, and cannot provide access control
Context-Dependent Threshold Decryption and its Applications
Get PDFIn a threshold decryption system a secret key is split across a number of
parties so that any threshold of them can decrypt a given ciphertext.
We introduce a new concept in threshold decryption called a decryption context, which is an additional argument that is used during decryption.
The context ensures that decryption shares that are generated for a ciphertext using different contexts are isolated from each other and cannot be jointly used to decrypt the ciphertext.
For example, suppose the decryption threshold is . Further, suppose that less than decryption shares are generated for a ciphertext under one context, and less than decryption shares are generated for under a different context. Then this set of shares is insufficient
to decrypt even if the total number of shares exceeds .
This new concept has several important applications, most notably for implementing an encrypted mempool in a consensus protocol.
We give two CCA-secure threshold decryption constructions that support context. One is based on ElGamal encryption, and the other is generic
showing how to add context to any CCA-secure threshold decryption system without changing the encryption algorithm