Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
New Techniques for Analyzing Differentials with Application to AES
Get PDFDifferential cryptanalysis is one of the most powerful attacks on modern block ciphers. After many year of research, we have very good techniques for showing that the probability that an input difference leads to an output difference (i.e., the probability of a differential) is either significantly higher, or lower than expected, and such large deviations lead to attacks.
On the other hand, modern techniques cannot estimate with high accuracy the probability of a differential that spans many rounds of the cipher. Therefore, these techniques are sufficient to argue only limited resistance against differential cryptanalysis.
In particular, for the AES, Keliher and Sui proved in 2005 that any 4-round differential has probability at most (about) , under the assumption that the round-keys are chosen independently. This establishes limited security arguments against classical differential cryptanalysis. Stronger bounds are only known when considering thousands of AES rounds, whereas at most 14 rounds are used in practice by AES-256.
In this paper, we propose new techniques for estimating the probability of a differential under the assumption that the round-keys of the cipher are chosen independently. We apply our techniques to AES, and show that the probability of every differential in 8-round AES is within an additive factor of from the expected value of .
We further apply our techniques to prove that 8-round AES is at most -close to a pairwise independent permutation, while 40-round AES is at most -close. The latter result improves upon the work of Liu, Tessaro and Vaikuntanathan [CRYPTO 2021], who proved a similar bound for 9000-round AES.
To obtain our results, we develop and adapt a variety of techniques for analyzing differentials using functional analysis. We expect these techniques to be useful for analyzing differentials in additional block ciphers besides the AES
FunBic-CCA: Function Secret Sharing for Biclusterings Applied to Cheng and Church Algorithm (Extended Version)
Get PDFHigh-throughput technologies (e.g., the microarray) have fostered the rapid growth of gene expression data collection. These biomedical datasets, increasingly distributed among research institutes and hospitals, fuel various machine learning applications such as anomaly detection, prediction or clustering. In particular, unsupervised classification techniques based on biclustering like the Cheng and Church Algorithm (CCA) have proven to adapt particularly well to gene expression data. However, biomedical data is highly sensitive, hence its sharing across multiple entities introduces privacy and security concerns, with an ever-present threat of accidental disclosure or leakage of private patient information. To address such threat, this work introduces a novel, highly efficient privacy-preserving protocol based on secure multiparty computation (MPC) between two servers to compute CCA. Our protocol performs operations relying on an additive secret sharing and function secret sharing, leading us to reformulate the steps of the CCA into MPC-friendly equivalents. Leveraging lightweight cryptographic primitives, our new technique named FunBic-CCA is first to exploit the efficiency of function secret sharing to achieve fast evaluation of the CCA biclustering algorithm
Barely Doubly-Efficient SimplePIR
Get PDFA Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size . The breakthrough work of Lin-Mook-Wichs (STOC’23) presented the first DEPIR construction from the Ring-LWE assumption. This remains essentially the only known construction to date, and realizing DEPIR from alternative foundations, particularly from plain LWE, has remained elusive.
In this work, we present a simple LWE-based construction of DEPIR in the CRS model. Our construction is inspired by SimplePIR (USENIX’23) and leverages the matrix–vector multiplication preprocessing of Williams (SODA’07). While our construction is only barely doubly-efficient, with server computation of , it was previously unknown whether even such modest sublinear efficiency could be achieved from unstructured, plain LWE
Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness
No full textA zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. \u2794] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message).
Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is game-based instead of simulation-based.
Our construction builds on the work of Kuykendall and Zhandry [TCC \u2720] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlák\u27s 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert\u27s second problem (and, hence, also Gödel\u27s incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC
A Novel Partial Key Exposure Attack on Common Prime RSA
Get PDFWe propose a novel partial key exposure attack on common prime RSA by leveraging lattice-based techniques. In common prime RSA, the primes and are defined as and for a common prime . Recently, Zheng introduced the first partial key exposure attack on this scheme; however, it is limited to instances where . In contrast, our work investigates deeper into partial key exposure attacks by presenting a unified generic case that targets one consecutive unknown block of the private key. By employing a lattice-based solving strategy for trivariate integer polynomials, we can effectively identify additional weak private keys that are vulnerable to partial exposure. Extensive numerical experiments validate the correctness and practicality of our proposed attack on common prime RSA
Threshold Structure-Preserving Signatures with Randomizable Key
Get PDFWhile digital signatures serve to confirm message integrity
and the identity of the signer, the inherent link between the public key
and the signer’s identity can pose challenges in anonymized networks or
applications focused on preserving privacy. Signatures with randomiz-
able keys aim to disentangle the signer’s identity from their public key,
thus preserving the signature’s validity. This approach ensures that the
signature, even with a randomized key, maintains its verifiability without
linking it to the signer’s identity.
Although signatures with randomizable keys effectively maintain privacy,
additional structural improvements are necessary in specialized signature
schemes for complex cryptographic frameworks. Threshold structure-
preserving signatures offer a way to construct modular protocols while
retaining the benefits of structure-preserving properties. Thus, the ran-
domizable key version of it is essential for a wide range of applications,
making it the foundation of this work. In this study, signatures with ran-
domizable key principles combined with threshold structure-preserving
signatures to build a strong cryptographic base for privacy-preserving
applications. This foundation makes sure that signatures are valid while
also being modular and unlinkable.
An earlier version of this work appeared in the 22nd International Con-
ference on Security and Cryptography(SECRYPT 2025) [6]; the present
article extends that study by adding the formal security proofs of the
introduced protocols
Applications Of Zero-Knowledge Proofs On Bitcoin
Get PDFThis paper explores how zero-knowledge proofs can enhance Bitcoin\u27s functionality and privacy. First, we consider Proof-of-Reserve schemes: by using zk-STARKs, a custodian can prove its Bitcoin holdings are more than a predefined threshold X, without revealing addresses or actual balances. We outline a STARK-based protocol for Bitcoin UTXOs and discuss its efficiency. Second, we examine ZK Light Clients, where a mobile or lightweight device verifies Bitcoin\u27s proof-of-work chain using succinct proofs. We propose a protocol for generating and verifying a STARK-based proof of a chain of block headers, enabling trust-minimized client operation. Third, we explore Privacy-Preserving Rollups via BitVM: leveraging BitVM, we design a conceptual rollup that keeps transaction data confidential using zero-knowledge proofs. In each case, we analyze security, compare with existing approaches, and discuss implementation considerations. Our contributions include the design of concrete protocols adapted to Bitcoin\u27s UTXO model and an assessment of their practicality. The results suggest that while ZK proofs can bring powerful features (e.g., on-chain reserve audits, trustless light clients, and private layer-2 execution) to Bitcoin, each application requires careful trade-offs in efficiency and trust assumptions
Efficient Full Domain Functional Bootstrapping from Recursive LUT Decomposition
Get PDFFully Homomorphic Encryption over the Torus (TFHE) enables efficient evaluation of arbitrary lookup tables (LUT) over encrypted data, allowing complex functions to be computed without decryption. However, in TFHE, only lookup tables with a negacyclic structure can be homomorphically evaluated, which limits the range of functions that can be supported. To overcome this limitation and enable the evaluation of arbitrary functions, the notion of full-domain functional bootstrapping (FDFB) was introduced. However, existing FDFB methods require at least two consecutive bootstrapping operations to evaluate a single function, resulting in significant latency and overhead.
In this work, we present a novel FDFB scheme that supports arbitrary lookup tables by decomposing them into multiple small negacyclic LUTs and one compact full-domain LUT. This structure allows most computations to be handled by fast negacyclic bootstrapping, significantly reducing the computational cost.
To address the need for maintaining distinct evaluation keys for each LUT length, we apply Extended Bootstrapping (PKC 2021), which enables all operations to run within a fixed ring dimension. Combined with Extended Bootstrapping, our method nearly halves the bootstrapping cost compared to prior FDFB approaches while maintaining a constant key size, negligible parameter overhead, and strong scalability.
Finally, we implement our algorithm using the TFHE-go library and evaluate its performance across various settings. Our method achieves up to a 3.41× speedup over previous FDFB schemes without increasing key size, and retains up to a 1.91× advantage even when Extended Bootstrapping is applied to both
Compressing steganographic payloads with LLM assistance
Get PDFSteganography is the practice of concealing messages or information within other non-secret text or media to avoid detection. A central challenge in steganography is balancing payload size with detectability and media constraints—larger payloads increase the risk of detection and require proportionally larger or higher-capacity carriers. In this paper, we introduce a novel approach that combines Huffman coding, suitable dictionary identification, and large language models (LLMs) rephrasing techniques to significantly reduce payload size. This enables more efficient use of limited-capacity carriers, such as images, while minimizing the visual or statistical footprint. Our method allows for the embedding of larger payloads into fixed-size media, addressing a key bottleneck in traditional steganographic systems. By optimizing payload compression prior to encoding, we improve both the stealth and scalability of steganographic communication
Improved Key-recovery Attacks on ARADI
Get PDFARADI is a low-latency block cipher introduced by the U.S. National Security
Agency (NSA), targeting secure and efficient memory encryption. However, unlike
most academic cipher proposals, the design rationale behind ARADI has not been made
public, leaving its security to be only assessed through independent analysis. In this
work, we present improved key-recovery attacks on up to 12 out of 16 rounds of ARADI
in the single-key setting — advancing the best known attacks by two rounds. Our
techniques build upon the ZeroSum distinguisher framework and leverage the Fast
Hadamard Transform (FHT). A central insight in our attacks is that the linear layer
of ARADI exhibits weak diffusion. This structural property allows partial decryption
with only a subset of the round keys, significantly reducing the key-guessing space