11 research outputs found
A Faster Algorithm for Finding Closest Pairs in Hamming Metric
No full textWe study the Closest Pair Problem in Hamming metric, which asks to find the pair with the smallest Hamming distance in a collection of binary vectors. We give a new randomized algorithm for the problem on uniformly random input outperforming previous approaches whenever the dimension of input points is small compared to the dataset size. For moderate to large dimensions, our algorithm matches the time complexity of the previously best-known locality sensitive hashing based algorithms. Technically our algorithm follows similar design principles as Dubiner (IEEE Trans. Inf. Theory 2010) and May-Ozerov (Eurocrypt 2015). Besides improving the time complexity in the aforementioned areas, we significantly simplify the analysis of these previous works. We give a modular analysis, which allows us to investigate the performance of the algorithm also on non-uniform input distributions. Furthermore, we give a proof of concept implementation of our algorithm which performs well in comparison to a quadratic search baseline. This is the first step towards answering an open question raised by May and Ozerov regarding the practicability of algorithms following these design principles
MiRitH: Efficient Post-Quantum Signatures from MinRank in the Head
No full textSince 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.
MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.
At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management
New Time-Memory Trade-Offs for Subset Sum -- Improving ISD in Theory and Practice
No full textWe propose new time-memory trade-offs for the random subset sum problem defined on over .
Our trade-offs yield significant running time improvements for every fixed memory limit . Furthermore, we interpolate to the running times of the fastest known algorithms when memory is not limited.
Technically, our design introduces a pruning strategy to the construction by Becker-Coron-Joux (BCJ) that allows for an exponentially small success probability. We compensate for this reduced probability by multiple randomized executions. Our main improvement stems from the clever reuse of parts of the computation in subsequent executions to reduce the time complexity per iteration.
As an application of our construction, we derive the first non-trivial time-memory trade-offs for Information Set Decoding (ISD) algorithms. Our new algorithms improve on previous (implicit) trade-offs asymptotically as well as practically. Moreover, our optimized implementation also improves on running time, due to reduced memory access costs. We demonstrate this by obtaining a new record computation in decoding quasi-cyclic codes (QC-3138). Using our newly obtained data points we then extrapolate the hardness of suggested parameter sets for the NIST PQC fourth round candidates McEliece, BIKE and HQC, lowering previous estimates by up to 6 bits and further increasing their reliability
Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing
No full textDue to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantum-secure signature proposal LegRoast. However, its security is not yet extensively studied.
The Legendre PRF computes for a key on input the Legendre symbol in some finite field \F_p. As standard notion, PRF security is analysed by giving an attacker oracle access to . Khovratovich\u27s collision-based algorithm recovers using in time with constant memory. It is a major open problem whether this birthday-bound complexity can be beaten.
We show a somewhat surprising wide-ranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting.
More precisely, we present a small memory multiple-key attack on Legendre keys in time , i.e. with amortized cost per key. This multiple-key attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker\u27s profit.
Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public only -- and not on a key . Namely, an attacker may compute e.g. in precomputation time a hint of size . On receiving access to in an online phase, the attacker then uses the hint to recover the desired key in time only . Thus, the attacker\u27s online complexity again beats the birthday-bound.
In addition, our precomputation attack can also be combined with our multiple-key attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking keys one may spend time in the precomputation phase for constructing a hint of size . In an online phase, one then finds {\em all keys in total time} only .
Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy key-independent precomputation pays off
Practical cryptanalysis of code-based crypto schemes
No full textDiese Dissertation analysiert die praktische Sicherheit von Code-basierten Kryptoverfahren. Dazu dienen zwei Hauptresultate, zum einem eine Implementierung der asymptotisch schnellsten Algorithmen des Syndrome-Dekodier-Problems, mit der verschiedene kryptanalytische Instanzen Code-basierter Verfahren gebrochen wurden, um daraus die Sicherheit Kryptographischer Instanzen zu extrapolieren. Und zum anderen wird ein neuer Time-Memory Tradeoff der besten Syndrome-Dekodier-Algorithmen vorgestellt. Dieser neue Tradeoff wird zunächst als Algorithmus für das Subset Sum Problems (Teilsummen-Problem), einem fundamentalen Problem der theoretischen Informatik, eingeführt. In diesem Kontext wird die Landschaft der Time-Memory Tradeoffs deutlich vereinfacht. Darüber hinaus wird ein neuer Algorithmus zum lösen des Nearest-Neighbour-Problem in der Hamming-Metrik vorgestellt. Dieser löst das Problem optimal und darüber hinaus ist im Gegensatz zu den vorherigen bekannten Algorithmen implementierbar
McEliece needs a Break -- Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD
No full textWith the recent shift to post-quantum algorithms it becomes increasingly important to provide precise bit-security estimates for code-based cryptography such as McEliece and quasi-cyclic schemes like BIKE and HQC. While there has been significant progress on information set decoding (ISD) algorithms within the last decade, it is still unclear to which extent this affects current cryptographic security estimates.
We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938).
Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST\u27s standardization process.
For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC.
For the proposed McEliece round-3 parameter sets of 192 and 256 bit, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired
LESS is Even More: Optimizing Digital Signatures from Code Equivalence
No full textLESS is a signature scheme based on the code equivalence problem that has advanced to the second round of the NIST PQC standardization process. While promising, the scheme suffers from relatively large signatures and moderate to slow signing and verification times. Chou, Santini, and Persichetti recently introduced a variant of LESS relying on canonical forms to significantly reduce signature sizes. However, the overall performance impact of this approach remained largely unclear. In this work, we provide the first implementation of the new LESS variant and show that, in its original form, it performs poorly due to the overhead of computing canonical forms in a naïve way. We then introduce a series of algorithmic and implementation-level optimizations that reduce this overhead to about 10%, showing that the signature size reduction comes at minor cost. In addition, we present further improvements to the signature scheme as a whole, as well as a re-parameterization. The resulting scheme achieves speedups of 2.5x to 10x over the Round 1 NIST submission, while maintaining the reduced signature sizes
LESS is Even More: Optimizing Digital Signatures from Code Equivalence
No full textLESS is a signature scheme based on the code equivalence problem that has advanced to the second round of the NIST PQC standardization process. While promising, the scheme suffers from relatively large signatures and moderate to slow signing and verification times. Chou, Santini, and Persichetti recently introduced a variant of LESS relying on canonical forms to significantly reduce signature sizes. However, the overall performance impact of this approach remained largely unclear. In this work, we provide the first implementation of the new LESS variant and show that, in its original form, it performs poorly due to the overhead of computing canonical forms in a naïve way. We then introduce a series of algorithmic and implementation-level optimizations that reduce this overhead to about 10%, showing that the signature size reduction comes at minor cost. In addition, we present further improvements to the signature scheme as a whole, as well as a re-parameterization. The resulting scheme achieves speedups of 2.5× to 10× over the Round 1 NIST submission, while maintaining the reduced signature sizes
: a Software Library for Cryptographic Hardness Estimation
No full textThe estimation of the computational complexity of hard problems is essential for determining secure parameters for cryptographic systems. To date, those estimations are often performed in an ad-hoc manner. This led to a scattered landscape of available estimation scripts, with multiple scripts for the same problem with varying outputs. Overall, this complicates the task of reaching consensus on the hardness of cryptographic problems. Furthermore, for designers it makes it difficult to gather precise information on the concrete difficulty of the underlying problems. Especially in the light of the still ongoing NIST PQC standardization effort and the upcoming call for post-quantum secure digital signature schemes there is a pressing need for a reliable point of access for concrete security estimates.
In this work we present the first open-source software library entirely dedicated to cryptographic hardness estimation, the library. In contrast to most previous estimators, this library follows a modern object-oriented software architecture, which provides a wide variety of features. Overall the design is optimized to ease extending existing estimators by new algorithms and makes it simple to integrate completely new estimators.
In this work we further specify the algorithmic cost model underlying the estimators. In order to provide a starting point for the project, we gathered and integrated estimators for six different hardness assumptions, including the syndrome decoding problem, the multivariate quadratic problem, the code equivalence problem, the permuted kernel problem and different flavors thereof. In our effort of gathering those estimation scripts, we also normalized those estimates to fit into the cost model and to measure the same unit operations
MiRitH: Efficient Post-Quantum Signatures from MinRank in the Head
No full textSince 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new post-quantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.
MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm. At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speed-up of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management
