Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Exploring Kaneko’s bound: On multi-edges, loops and the diameter of the supersingular -isogeny graph
Get PDFWe strengthen Kaneko\u27s bound to prove that, away from the -invariant , edges of multiplicity at least three can occur in the supersingular -isogeny graph only if the base field\u27s characteristic satisfies . Further we prove a diameter bound for , while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko\u27s bound to deduce that the distance of and in is at least one fourth of the graph\u27s diameter if . We also study other phenomena in with Kaneko\u27s bound and provide data to demonstrate that the resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal\u27 classical modular polynomial in positive characteristic
Shred-to-Shine Metamorphosis in Polynomial Commitment Evolution
Get PDFPolynomial commitment schemes (PCSs) enable verifying evaluations of committed polynomials. Multilinear (ML) PCSs from linear codes are favored for their prover time. Distributed MLPCSs further reduce it by enabling multiple provers to distribute both commitment and proof generation.
We propose , an FRI-based MLPCS that unites the linear prover time of PCSs from encodable codes with the compact proofs and fast verification of Reed–Solomon (RS) PCSs. By cutting FFT and hash overhead for both committing and opening, runs faster in prover than the RS-based DeepFold (Usenix Security\u2725) while retaining competitive proof size and verifier time, and beats Orion (Crypto\u2722) from linear codes by -fold in prover speed while reducing proof size and verification time by -fold.
Its distributed version delivers the first code-based distributed SNARK for arbitrary circuits over a single polynomial, and further achieves accountability. outperforms DeVirgo (CCS\u2722)---the only prior code-based distributed MLPCS, limited to data-parallel circuits and lacking accountability---by in prover time and in communication, with the same number of provers.
A central insight in both constructions is the shred-to-shine technique. It further yields a group-based MLPCS of independent interest, with shorter structured reference string and faster opening time than multilinear KZG (TCC\u2713)
Breaking the Twinkle Authenticated Encryption Scheme and Analyzing Its Underlying Permutation
Get PDFThis paper studies the Twinkle family of low-latency symmetric key schemes designed by Wang et al. (CiC 2024). In particular, it presents cryptanalysis of both the mode and the underlying primitive. Twinkle is a PRF-based design, and an authenticated encryption scheme Twinkle-AE is specified based on a dedicated PRF called Twinkle-PRF. To achieve low latency, Twinkle-PRF uses a large key and state to produce sufficient randomness in a single step. Twinkle-AE uses a 1024- or 512-bit key for authentication and generates a -bit tag, where . It claims to provide bits of integrity.
Several Twinkle-AE parameter sets claim higher confidentiality than integrity. In this setup, for any ciphertext, an adversary can obtain the message after decryption attempts by guessing the tag, allowing attacks in the chosen-ciphertext setting. We show that a 1024- or 512-bit authentication key can be recovered using only queries. The recovered authentication key enables the generation of valid ciphertexts for arbitrary plaintexts, thus achieving universal forgery.
In the second part of the paper, we perform cryptanalysis on reduced-round variants of the 1280-bit public permutation Twinkle-P, which serves as a core component of Twinkle-PRF.
We investigate impossible differential, zero-correlation linear, integral, and differential-linear distinguishers by developing automated analytic tools. We provide practical distinguishers for up to 5 rounds, and the longest distinguisher reaches 6 rounds with a complexity of . This surpasses the round bounds evaluated by the designers. We stress that our attacks on mode exploits the gap between the claimed confidentiality and integrity levels, thus have no impact on the parameter sets having the same security level.
Our attacks on the permutation do not have any significant impact on the whole specifications. Moreover, we note that Twinkle-AE-512b/Twinkle-AE-1024b and Twinkle-PA remain secure, and the versions we attacked would also be secure if the claimed confidentiality level matched the integrity level
Picking up the Fallen Mask: Breaking and Fixing the RS-Mask Countermeasure
Get PDFPhysical attacks pose a major challenge to the secure implementation of cryptographic algorithms. Although significant progress has been made in countering passive attacks such as side-channel analysis (SCA), protection against fault attacks is still less developed. One reason for this is the broader and more complex nature of fault attacks, which makes it difficult to create standardized fault evaluation methodologies for countermeasures like those used for SCA. This makes it easier to overlook potential vulnerabilities that attackers could exploit. RS-Mask, published at HOST 2020, is such a countermeasure that has been affected by the absence of a systematic analysis method. The fundamental concept behind the countermeasure is to maintain a uniform distribution of variables, regardless of whether they are faulty or correct. This property is particularly effective against Statistical Ineffective Fault Attacks (SIFA), which exploit the dependency between fault propagation and the secret data.
In this work, we present several fault scenarios involving single fault injections on the AES implementation protected with RS-Mask, where the fault propagation depends on the secret data. This happens because the random space mapping used in RS-Mask countermeasure retains a dependency on the secret data, as it is derived based on the S-box input. To address this, we propose a new countermeasure based on the core concept of RS-Mask, implementing a single mapping for all S-box inputs, involving an intrinsic duplication. Next, we evaluate the effectiveness of the new countermeasure against fault attacks by comparing the fault detection rate across all possible fault locations and values for every input. Additionally, we examine the output differences between faulty and correct outputs for each input. Our results show that the detection rate is uniform for each input, which ensures security against statistical attacks utilizing both effective and ineffective faults. Moreover, the output differences being uniform for each input ensures security against differential fault attacks
A note on the security of the BitVM3 garbling scheme
Get PDFWe provide minimal counterexamples for the security of the BitVM3 garbling scheme: our attack allows the evaluator to forge input and output wires. Then we use the same idea to exhibit an attack on the forward label propagation garbling scheme proposed in a more recent paper. In both cases, the authenticity property of the garbling scheme is broken
On Weak NIZKs, One-way Functions and Amplification
Get PDFAn -weak non-interactive zero knowledge (NIZK) argument has soundness error at most and zero-knowledge error at most . We show that as long as is hard in the worst case, the existence of an -weak NIZK proof or argument for with implies the existence of one-way functions. To obtain this result, we introduce and analyze a strong version of universal approximation that may be of independent interest.
As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO\u2724] showed that -weak NIZK proofs (with and constants such that ) can be amplified to make their errors negligible, but needed to assume the existence of one-way functions. Our results can be used to remove the additional one-way function assumption and obtain NIZK amplification theorems that are (almost) unconditional; only requiring the mild worst-case assumption that if , then
Batch Decryption without Epochs and its Application to Encrypted Mempools
Get PDFSuppose Alice holds a secret key in a public key encryption scheme. For a given set of ciphertexts, Alice wants to create a short pre-decryption key that lets anyone decrypt this exact set of ciphertexts and nothing else. This problem is called batch decryption. When the secret key is shared among a number of decryption parties the problem is called batch threshold decryption. This question comes up in the context of an encrypted mempool where the goal is to publish a short pre-decryption key that can be used to decrypt all ciphertexts in a block. Prior work constructed batch threshold decryption with some limitations.
In this work, we construct three new batch decryption and batch threshold decryption schemes. We first observe that a key-policy ABE (KP-ABE) scheme directly gives a batch decryption scheme. However, the best KP-ABE schemes, which happen to be lattice-based, lead to relatively long public keys and ciphertexts. We then use very different techniques to construct a new lattice-based batch decryption scheme with shorter parameters. Our construction employs a recent preimage sampler due to Waters, Wee, and Wu. Finally, for completeness, we show that a trilinear map leads to a highly efficient threshold batch decryption scheme
Note: Full-round distinguisher for Synergy
Get PDFIn this note we study the proposed cipher Synergy and describe a full round differential with probability . The claims have been experimentally verified
RoK and Roll – Verifier-Efficient Random Projection for -size Lattice Arguments
No full textSuccinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors\u27\u27 (RPS) [ASIACRYPT\u2724] and hinges on two key innovations, presented as reductions of knowledge (RoKs):
- Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes , i.e. independent of the original witness length.
- Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients ) be sent in plain, as in LaBRADOR [CRYPTO\u2723]. We observe, however, that the strategy from prior works to immediately lift the projection claim to , and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to while maintaining a succinct verification time.
These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity and succinct verification for structured linear relations
Foundations of Single-Decryptor Encryption
Get PDFSingle decryptor encryption (SDE) is public key encryption (PKE) where the decryption key is an unclonable quantum state. Coladangelo, Liu, Liu, and Zhandry (CRYPTO 2021) realized the first SDE assuming subexponentially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), along with the polynomial hardness of the learning with errors (LWE) assumption. Since then, SDE has played a pivotal role in recent advances in quantum cryptography. However, despite its central importance in unclonable cryptography, many fundamental questions about SDE remain unanswered. For example, a line of works has proposed various security notions for SDE, but their relationships have hardly been discussed. Moreover, while many subsequent works have adopted the construction methodology of Coladangelo et al., none have explored its improvement, leaving the possibility of a more efficient approach to SDE.
In this work, we address these fundamental questions concerning SDE. Our contributions are threefold.
New security notion: We introduce a strengthened indistinguishability-based security notion for SDE, which we call CPA+ anti-piracy security. We show that CPA+ security unifies the existing security notions for SDE, as detailed in the third item.
New construction: We present an SDE scheme that satisfies CPA+ anti-piracy security, based solely on polynomially secure iO and OWFs. In addition to relying on weaker and more general assumptions, our SDE scheme offers a significant advantage over the scheme of Coladangelo et al., as both the construction and its security proof are much simpler.
Relationships among security notions: We demonstrate that CPA+ anti-piracy security implies all existing security notions for SDE, with the sole exception of identical challenge ciphertext security proposed by Georgiou and Zhandry (EPRINT 2020). Although we do not establish a direct implication from CPA+ anti-piracy security to identical challenge ciphertext security, we provide a generic transformation from an SDE scheme satisfying the former to one achieving the latter in the quantum random oracle model. Additionally, we establish various relationships among different security notions for SDE. By combining these results with our SDE construction, we derive several new feasibility results