Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Minimalist Model for Impossible Differentials
Get PDFThis paper introduces a new MILP modeling to find impossible differential (ID) distinguishers and attacks. Standard models for ID are negative models, in the sense that a differential is impossible if and only if the model has no solution. Our new modelling technique focuses on probable ID, differentials that are probably impossible. While this might lead to false positives, the main advantage is that searching for such probable ID can be achieved through a positive model. This facilitates the search for the best impossible differential attacks without first exhausting all possible ID distinguishers on a target. We also propose to simplify the modelling by only considering two possible states for internal cells: inactive and unknown. In this case there are no longer direct contradictions but only indirect ones, assuming that it is impossible that all cells are inactive.
With these two simple ideas, we are able to retrieve the longest impossible differentials distinguishers on MIDORI, SKINNY, PRESENT, SIMON, Simeck and SPECK. Furthermore, as the model looking for candidates is based on satisfiability, it can be incorporated in a larger model which looks directly for the best attacks in order to enumerate the distinguishers in the order of the complexity of the associated attacks, which we did for the AES, ARADI, SIMON and SKINNY
M&M: Secure Two-Party Machine Learning through Efficient Modulus Conversion and Mixed-Mode Protocols (Full Version)
No full textSecure two-party machine learning has made substantial progress through the use of mixed-mode protocols. Despite these advancements, existing approaches often suffer from efficiency bottlenecks due to the inherent mismatch between the optimal domains of various cryptographic primitives, such as Homomorphic Encryption and Oblivious Transfer. In response to these challenges, we introduce the \tNAME{} framework, which features an efficient modulus conversion protocol. This breakthrough enables seamless integration of the most suitable cryptographic subprotocols within their optimal modulus domains, allowing linear computations to be executed over a prime modulus and nonlinear computations over a two-power modulus, with a minimal modulus conversion overhead. We further establish new benchmarks for the performance of fundamental primitives, namely comparison and multiplication, across various two-party techniques, together with our practical optimizations to improve efficiency. By incorporating these techniques, \tNAME{} demonstrates significant performance enhancements over state-of-the-art solutions: \romannumeral1) we report a - improvement for approximated truncations with 1-bit error tolerance; \romannumeral2) an average of (resp. ) reduction in communication (resp. runtime) for machine learning functions; \romannumeral3) and a 25\%-99\% improvement in cost-efficiency for private inference of deep neural networks and 50\% improvement in private training of gradient boosting decision trees
Toward Crypto Agility: Automated Analysis of Quantum-Vulnerable TLS via Packet Inspection
Get PDFThe advancement of quantum computing threatens traditional public-key cryptographic algorithms such as RSA and ECC, both vulnerable to Shor’s algorithm.
As most Transport Layer Security (TLS) deployments still rely on these quantum-vulnerable algorithms for key exchange and digital signatures, the transition to Post-Quantum Cryptography (PQC), standardized by NIST, has become increasingly urgent.
Given the critical role of TLS in securing Internet communications, identifying and replacing these algorithms in operational deployments is a key priority for ensuring long-term security.
We present an automated method for analyzing TLS network packets to detect the use of quantum-vulnerable algorithms. Our approach combines hierarchical packet filtering, protocol-aware parsing, and a hybrid certificate extraction technique that enables analysis of encrypted TLS~1.3 certificates without full decryption. The framework achieved over 96\% detection accuracy, and our certificate parsing strategy improves overall throughput. Applying it to domestic and international TLS deployments revealed that domestic systems lag behind in quantum-readiness, underscoring the need for greater adoption of TLS~1.3, hybrid key exchanges (RSA/ECC with PQC), and short-lived certificates.
Beyond TLS, the underlying methodology can be extended to other secure communication protocols, offering a versatile foundation for post-quantum migration strategies.
These results highlight the practicality of our method for large-scale, real-time TLS assessments and its potential to guide PQC adoption
RBOOT: Accelerating Homomorphic Neural Network Inference by Fusing ReLU within Bootstrapping
Get PDFA major bottleneck in secure neural network inference using Fully Homomorphic Encryption (FHE) is the evaluation of non-linear activation functions like ReLU, which are inefficient to compute under FHE. State-of-the-art solutions approximate ReLU using high-degree polynomials, incurring significant computational overhead. We propose novel methods for functional bootstrapping with CKKS, and based on these methods we present RBOOT, an optimized framework that seamlessly integrates ReLU evaluation into CKKS bootstrapping, significantly reducing multiplication depth and boosting efficiency. Our key insight is that the EvalMod step in CKKS bootstrapping is composed of trigonometric functions, which can be transformed into various common non-linear functions. By co-optimizing these components, we can exploit such non-linearity to construct ReLU (and other non-linear functions) within the bootstrapping process itself, greatly reducing the computation overhead. Results on four widely used CNN models show that RBOOT achieves faster end-to-end inference and lower memory usage compared to previous polynomial approximation works, while maintaining comparable accuracy
Does the UC-Security Notion for PAKE Imply Game-Based Security?
Get PDFA Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographically strong key, in the setting where the only information shared in advance is a low-entropy password . The two standard security definitions for PAKE are the game-based one by Bellare, Pointcheval and Rogaway (BPR-security, EUROCRYPT 2000) and the Universally Composable (UC) one by Canetti et al. (EUROCRYPT 2005). It is well-known that UC-security implies BPR-security; however, there are a large number of variants of both definitions, and the relation between them is not entirely clear.
In this work, we thoroughly study a variant of BPR-security by Katz, Ostrovsky and Yung (KOY-security, JACM 2009):
1. We show, via a counterexample, that UC-security does \emph{not} imply KOY-security;
2. We then prove that a variant of UC-security, called implicit-only UC-security (Dupont et al., EUROCRYPT 2018), implies KOY-security.
Interestingly, we make the observation that KOY- and implicit-only UC-security essentially strengthen their standard counterparts in the same manner. We also present detailed explanations of all four security notions
Privacy-Preserving Federated Inference for Genomic Analysis with Homomorphic Encryption
Get PDFIn recent years, federated learning has gained significant momentum as a collaborative machine learning approach, particularly in the field of medicine. While the decentralized nature of federated learning boasts greater security guarantees compared to traditional machine learning methods, it is still susceptible to myriad attacks. Moreover, as federated learning becomes increasingly ubiquitous in medicine, its use for classification tasks is expected to increase; however, maintaining patient data confidentiality remains a significant challenge, especially for genetic data. In this work, we introduce a novel framework for secure federated inference on nucleotide-based genotype data and provide a gateway to private inference through fully homomorphic encryption. A federated model with five local clients was created and trained before being encrypted with the TFHE cryptosystem and placed for inference. This framework successfully identified promoter sequences encoded within given DNA sequences, showing its potential applications in secure genomic data analysis in a federated context. Our work represents a crucial step in privacy-preserving federated inference on nucleotide-based data
On the -Spreadness of Average-Case to Worst-Case Transformations
No full textAchieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as , (PKC 2023), and (TIFS 2023)—which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the \textit{-spreadness}, a critical factor in determining explicit rejection () or implicit rejection (), has not been established with rigorous proofs. Existing analyses of -spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the -spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called , , and , giving the corrected -spreaness for those PKE schemes with concrete parameters
Constraint-Friendly Map-to-Elliptic-Curve-Group Relations and Their Applications
Get PDFHashing to elliptic curve groups is a fundamental operation used in many cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, they are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs,
while BLS signatures are used in proof of stake protocols.
In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly such that one can efficiently generate succinct proofs of correctness. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs.
We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports non-deterministic map-to-curve choices making them more efficient in constraint programming frameworks and enabling efficient integration into zero-knowledge proofs. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM).
Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over fewer constraints than the best hash-to-elliptic-curve-group alternatives, and, enables - faster proving times at scale
Data Matching in Unequal Worlds and Applications to Smart Contracts
Get PDFSNARKs enable compact proofs that an NP statement is true and that the prover knows a valid witness. They have become a key building block in modern smart contract applications, including rollups and privacy-focused cryptocurrencies.
In the widely used Groth16 framework, however, long statements incur high costs.
A common workaround is to pass the statement’s hash to the SNARK and move the statement into the witness. The smart contract then hashes the statement first, and the circuit that is proven additionally checks consistency of the hash and the statement.
Unfortunately, virtually any hash function is expensive to call either in a smart contract (in terms of gas) or in the proven circuit (in terms of prover time).
We demonstrate a novel solution to this dilemma, which we call hybrid compression. Our method allows us to use two different hash functions—one optimized for the proof circuit, and another optimized for on-chain verification—thereby combining the efficiency advantages of both. We prove the security of this approach in the standard model under reasonable assumptions about the two hash functions, and our benchmarks show that it achieves near-optimal performance in both gas usage and prover time. As an example, compressing an 8 KB statement with our approach results in a 10-second prover time and a smart contract spending 270K gas, whereas the existing approaches either need a much longer proof generation (290 seconds for SHA-256 hashing) or a much more expensive contract (5M gas for Poseidon hashing).
Along the way, we develop a two-party protocol of independent interest in communication complexity: an efficient deterministic method for checking input equality when the two parties do not share the same hash function
There Is Always a Way Out! Destruction-Resistant Key Management: Formal Definition and Practical Instantiation
Get PDFA central advantage of deploying cryptosystems is that the security of large high-sensitive data sets can be reduced to the security of a very small key, i.e., a master key. The most popular way to manage the master key is to use threshold secret sharing schemes: a user splits and distributes her/his key among key servers, and can recover the key with the aid of any of them. However, it is vulnerable to device destruction: if all key servers and users\u27 devices break down, the key will be permanently lost. We propose a Destruction-Resistant Key Management scheme, dubbed DRKM, which ensures the key availability even if destruction occurs. In DRKM, a user utilizes her/his personal identification factors (PIFs) to derive a cryptographic key but can retrieve the key using any of the PIFs. As most PIFs can be retrieved by the user per se without requiring stateful devices, destruction resistance is achieved. With the integration of a threshold secret sharing scheme, DRKM achieves portable key access by invoking any key servers before destruction occurs. We prove the DRKM\u27s security, implement its prototype, and conduct a comprehensive performance evaluation to demonstrate its high efficiency