34 research outputs found
A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers
No full textQuantum computing enabled cryptanalytic techniques are able to concretely reduce the security margin of existing cryptographic primitives. While this reduction is only polynomial for symmetric cryptosystems, it still provides a reduction in their security margin.
In this work, we propose a detailed quantum circuit designed to cryptanalyze both the Data Encryption Standard (DES) cryptosystem, and its successor Triple-DES (3DES), currently
standardized in ISO/IEC 18033-3, and still widely employed in satellite data and bank card encryption. To do so, we introduce the first quantum circuit implementation of the 8 substitution tables (a.k.a. S-boxes), applying a bitslicing strategy, which is currently the most efficient classical combinatorial circuit design in terms of number of two inputs Boolean gates. Secondly, we present the complete quantum circuits required to attack
both DES and 3DES leveraging Grover’s algorithm. We provide finite regime, closed form equations, delineating the circuits complexities in terms of the number of qubits, gates, depth and number of qubits multiplied by depth. The complexity analysis is based on two distinct gate sets: a NOT-CNOT-Toffoli (NCT) extended with the Hadamard gate; and the fault-tolerant Clifford+T. Finally, akin to the classical attack to the 3DES, we introduce a meet-in-the-middle strategy relying on an exponential amount of Quantum Random Access Memory. Our findings show that the 3DES with keying option 2, the most widely
employed variant of 3DES, can be attacked with a circuit depth of approximately 2^{67} and less than a thousand qubits. This is close to the 2^{64} value suggested by NIST for the depth achievable sequentially by a single quantum computer in a decade. Our technique can be further sped up parallelizing the approach onto multiple devices, pointing to the practicality of cryptanalyzing 3DES in such a scenario
Improving the Efficiency of Quantum Circuits for Information Set Decoding
No full textThe NIST Post-Quantum standardization initiative, that entered its fourth round, aims to select asymmetric cryptosystems secure against attacker equipped with a quantum computer. Code-based cryptosystems are a promising option for Post-Quantum Cryptography (PQC), as neither classical nor quantum algorithms provide polynomial time solvers for its underlying hard problems. Indeed, to provide sound alternatives to lattice-based cryptosystems, NIST advanced all round 3 code-based cryptosystems to round 4. We present a complete implementation of a quantum circuit based on the Information Set Decoding (ISD) strategy, the best known one against code-based cryptosystems, providing quantitative measures for the security margin achieved with respect to the quantum-accelerated key recovery on AES, targeting both the current state-of-the-art approach and the NIST estimates. Our work improves the state-of-the-art, reducing the circuit depth from 219 to 230 for all the parameters of the NIST selected cryptosystems. We further analyse recently proposed optimizations, showing that the overhead introduced by their implementation overcomes their asymptotic advantages. Finally, we address the concern brought forward in the latest NIST report on the parameters choice for the McEliece cryptosystem, showing that the parameter choice yields a computational effort which is slightly below the required target level
A Complete Quantum Circuit to Solve the Information Set Decoding Problem
No full textProviding strong security margins against cryptanalytic attackers equipped with quantum computers is a major research direction fostered by the US National Institute of Standards and Technology (NIST) Post-quantum Cryptography Standardization process. Among the viable candidates, code-based asymmetric cryptosystems are one of the prominent approaches. In this work, we propose the first fully detailed quantum circuit to compute the solution to the Information Set Decoding problem, the main cryptanalytic tool against such cryptosystems. We evaluate the cryptanalytic effort with our circuit design on actual parameters from cryptosystems admitted to the final stage of the NIST standardization process and compare it with the previous conservative asymptotic estimates. We show that the actual computational effort of our solution is smaller than the one estimated via asymptotics by a factor of 24. We also perform a comparison of our results with the quantum-computational effort of breaking the AES cipher, following the guidelines of the US NIST in evaluating the security of the ciphers. To do this, we translate our design on gates of the Clifford+T gate set only, one of the most promising candidate for fault-tolerant quantum computation, and report that the parameter choices for Classic McEliece and BIKE, two candidates admitted to the final round of the NIST standardization process provide an adequate security margin with respect to our ISD solution technique
InfraRed Thermography proposed for the estimation of the Cooling Rate Index in the remote survey of rock masses
No full textDIURNAL CYCLING OF INSULIN SENSITIVITY IN TYPE 2 DIABETES: EVIDENCE FOR DEVIATION FROM PHYSIOLOGY AT AN EARLY STAGE
No full textUnlabelled: The aim of this study was to establish the contribution of insulin resistance to the morning (a.m.) versus afternoon (p.m.) lower glucose tolerance of people with type 2 diabetes (T2D). Eleven subjects with T2D (mean [SD] diabetes duration 0.79 [0.23] years, BMI 28.3 [1.8] kg/m2, A1C 6.6% [0.26%] [48.9 (2.9) mmol/mol]), treatment lifestyle modification only) and 11 matched control subjects without diabetes were monitored between 5:00 and 8:00 a.m. and p.m. (in random order) on one occasion (study 1), and on a subsequent occasion, they underwent an isoglycemic clamp (a.m. and p.m., both between 5:00 and 8:00, insulin infusion rate 10 mU/m2/min) (study 2). In study 1, plasma glucose, insulin, C-peptide, and glucagon were higher and insulin clearance lower in subjects with T2D a.m. versus p.m. and versus control subjects (P < 0.05), whereas free fatty acid, glycerol, and β-hydroxybutyrate were lower a.m. versus p.m. However, in study 2 at identical hyperinsulinemia a.m. and p.m. (∼150 pmol/L), glucose Ra and glycerol Ra were both less suppressed a.m. versus p.m. (P < 0.05) in subjects with T2D. In contrast, in control subjects, glucose Ra was more suppressed a.m. versus p.m. Leucine turnover was no different a.m. versus p.m. In conclusion, in subjects with T2D, insulin sensitivity for glucose (liver) and lipid metabolism has diurnal cycles (nadir a.m.) opposite that of control subjects without diabetes already at an early stage, suggesting a marker of T2D. Article highlights: In people with type 2 diabetes (T2D), fasting hyperglycemia is greater in the morning (a.m.) versus the afternoon (p.m.), and insulin sensitivity for glucose and lipid metabolism is lower a.m. versus p.m. This pattern is the reverse of the physiological diurnal cycle of people without diabetes who are more insulin sensitive a.m. versus p.m. These new findings have been observed in the present study in people without obesity but with recent-onset T2D, with good glycemic control, and in the absence of confounding pharmacological treatment. It is likely that the findings represent a specific marker of T2D, possibly present even in prediabetes before biochemical and clinical manifestations
A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems
No full textThe significant interest in cryptographic primitives providing sound security margins when facing attacks with quantum computers is witnessed by the ongoing USA National Institute of Standards and Technology Post-quantum Cryptography Standardization process. Sound and precise evaluation of the amount of computation required to break such cryptographic primitives by means of quantum computers is required to be able to choose the cryptosystem parameters.
We present a full description of a quantum circuit to accelerate the computation of the solution of the Information Set Decoding problem , which is currently the best known non-structural attack against code-based cryptosystems. We validate our design running it on small instances of error correction codes, which allowed a complete validation on the AtoS QLM quantum computer simulator. We detail the circuit accelerating the exponential complexity search phase in the Lee and Brickell variant of the ISD solver, and provide its computational complexity for cryptographically relevant parameters taken from the third round candidates in the USA post-quantum standardization process
paper-codes/2023-TQuantum: Submission release
No full textCode made available for the latest round of review
Design and development of a quantum circuit to solve the information set decoding problem
No full textLAUREA MAGISTRALENegli ultimi anni i crittosistemi basati su codici lineari sono stati oggetto
di studi sempre più approfonditi data la loro maggior resistenza ad attacchi
tramite calcolatori quantistici. La sicurezza di questo tipo di crittosistemi
si basa sulla difficoltà di ricavare il valore di una parola di codice corretta
a partire da una affetta da errore dato un codice lineare con una struttura
apparentemente casuale.
In questo lavoro abbiamo progettato e implementato diversi circuiti
quantistici in grado di risolvere il problema noto come Information Set
Decoding, che è attualmente il più efficace tipo di attacco a tali
crittosistemi. Basati sull'algoritmo di Grover, gli algoritmi quantistici
proposti si sono dimostrati in grado di identificare l'errore originale con
un'elevata percentuale di affidabilità, durante la loro validazione tramite
simulatore di calcolatore quantistico.
Abbiamo esplorato due tipi di attacchi diversi: il primo, basato su un algoritmo
di ricerca esaustiva tradizionale, è puramente quantistico; il secondo, basato
sull'algoritmo di Lee-Brickell, è un algoritmo ibrido classico-quantistico.
In entrambi i casi, sono state utilizzate e comparate modalità di esecuzione
diverse, dimostrando come un'attenta preparazione dello stato iniziale del
sistema possa ridurre drasticamente il numero di iterazioni rispetto
all'utilizzo di una versione base dell'algoritmo di Grover.
In questo lavoro abbiamo inoltre fornito una misura quantitativa della complessità
di calcolo di entrambi gli algoritmi proposti in termini di numero di
quantum gates e numero complessivo di qubit.Cryptosystems based on linear codes are gaining momentum due to their stronger
resistance to quantum attacks. They rely on the hardness of finding a
minimum-weight codeword in a large linear code with an apparently random
structure.
In this work we designed and implemented several quantum circuits to
specifically solve the Information Set Decoding problem, which is currently
the most effective attack against code-based cryptoschemes. Relying on
Grover's algorithm, the proposed algorithms were shown capable of
effectively recover the original error vector simulating the computation of a
quantum computer. Both an exhaustive search and a variant of Lee-Brickell's
algorithm are proposed, with the former relying only on a quantum circuit and
the latter using a hybrid classic-quantum approach. In both cases, two variants
have been analyzed and compared, showing how a proper preparation of the initial
state of the system can drastically reduce the number of iterations with respect
to the uniform superposition of the classic Grover's algorithm.
We provide, for the proposed algorithms, a quantitative evaluation of their
computational complexity in terms of the number of involved quantum gates and
required storage in qubits
