An official website of the United States government
Advances in quantum computing have urged the need for cryptographic algorithms that are low-power, low-energy, and secure against attacks that can be potentially enabled. For this post-quantum age, different solutions have been studied. Code-based cryptography is one feasible solution whose hardware architectures have become the focus of research in the NIST standardization process and has been advanced to the final round (to be concluded by 2022–2024). Nevertheless, although these constructions, e.g., McEliece and Niederreiter public key cryptography, have strong error correction properties, previous studies have proved the vulnerability of their hardware implementations against faults product of the environment and intentional faults, i.e., differential fault analysis. It is previously shown that depending on the codes used, i.e., classical or reduced (using either quasi-dyadic Goppa codes or quasi-cyclic alternant codes), flaws in error detection could be observed. In this work, efficient fault detection constructions are proposed for the first time to account for such shortcomings. Such schemes are based on regular parity, interleaved parity, and two different cyclic redundancy checks (CRC), i.e., CRC-2 and CRC-8. Without losing the generality, we experiment on the McEliece variant, noting that the presented schemes can be used for other code-based cryptosystems. We perform error detection capability assessments and implementations on field-programmable gate array Kintex-7 device xc7k70tfbv676-1 to verify the practicality of the presented approaches. To demonstrate the appropriateness for constrained embedded systems, the performance degradation and overheads of the presented schemes are assessed.
more »
« less
CRC-Oriented Error Detection Architectures of Post-quantum Cryptography Niederreiter Key Generator on FPGA
Providing error detection constructions for Internet of nano-Things in constrained applications is of prominent importance. The Niederreiter cryptosystem falls into the category of code-based public-key cryptography. It is a relatively well-established scheme, but its key size and performance overheads have traditionally hindered its efficiency to be utilized for traditional computers. However, with the arrival of quantum computers, the Niederreiter cryptosystem is believed to be secure against attacks enabled by such computers, even though it has been previously shown that it is still vulnerable to fault injection and natural hardware defects. In this paper, we present fault detection schemes for the different blocks in the key generation of the Niederreiter cryptosystem using binary Goppa codes. These blocks perform finite field operations such as addition, multiplication, squaring, and inversion. The schemes are derived for different parameter sizes in order to have more flexibility and be able to choose according to the overheads to be tolerated and the required level of security. Moreover, we implement our fault detection schemes on Xilinx field-programmable gate array (FPGA) family Kintex UltraScale+ (device xcku5p-ffvd900-1-i) to benchmark the overhead induced of the proposed approaches.
more »
« less
- Award ID(s):
- 1801512
- PAR ID:
- 10468115
- Publisher / Repository:
- IEEE
- Date Published:
- Subject(s) / Keyword(s):
- Fault detection, field-programmable gate array (FPGA), Niederreiter cryptosystem, post-quantum cryptography.
- Format(s):
- Medium: X
- Location:
- Oslo, Norway
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Parallel operations are important for both near‐term quantum computers and larger‐scale fault‐tolerant machines because they reduce execution time and qubit idling. This study proposes and implements a pairwise‐parallel gate scheme on a trapped‐ion quantum computer. The gates are driven simultaneously on different sets of orthogonal motional modes of a trapped‐ion chain. This work demonstrates the utility of this scheme by creating a Greenberger‐Horne‐Zeilinger (GHZ) state in one step using parallel gates with one overlapping qubit. It also shows its advantage for circuits by implementing a digital quantum simulation of the dynamics of an interacting spin system, the transverse‐field Ising model. This method effectively extends the available gate depth by up to two times with no overhead when no overlapping qubit is involved, apart from additional initial cooling. This scheme can be easily applied to different trapped‐ion qubits and gate schemes, broadly enhancing the capabilities of trapped‐ion quantum computers.more » « less
-
Exascale computing must simultaneously address both energy efficiency and resilience as power limits impact scalability and faults are more common. Unfortunately, energy efficiency and resilience have been traditionally studied in isolation and optimizing one typically detrimentally impacts the other. To deliver the promised performance within the given power budget, exascale computing mandates a deep understanding of the interplay among energy efficiency, resilience, and scalability. In this work, we propose novel methods to analyze and optimize costs of resilience techniques including checkpoint-restart and forward recovery for large sparse linear system solvers. In particular, we present experimental and analytical methods to analyze and quantify the time and energy costs of recovery schemes on computer clusters. We further develop and prototype performance optimization and power management strategies to improve energy efficiency. Experimental results show that recovery schemes incur different time and energy overheads and optimization techniques significantly reduce such overheads. This work suggests that resilience techniques should be adaptively adjusted to a given fault rate, system size, and power budget.more » « less
-
Motivated by the rise of quantum computers, existing public-key cryptosystems are expected to be replaced by post-quantum schemes in the next decade in billions of devices. To facilitate the transition, NIST is running a standardization process which is currently in its final Round. Only three digital signature schemes are left in the competition, among which Dilithium and Falcon are the ones based on lattices. Besides security and performance, significant attention has been given to resistance against implementation attacks that target side-channel leakage or fault injection response. Classical fault attacks on signature schemes make use of pairs of faulty and correct signatures to recover the secret key which only works on deterministic schemes. To counter such attacks, Dilithium offers a randomized version which makes each signature unique, even when signing identical messages. In this work, we introduce a novel Signature Correction Attack which not only applies to the deterministic version but also to the randomized version of Dilithium and is effective even on constant-time implementations using AVX2 instructions. The Signature Correction Attack exploits the mathematical structure of Dilithium to recover the secret key bits by using faulty signatures and the public-key. It can work for any fault mechanism which can induce single bit-flips. For demonstration, we are using Rowhammer induced faults. Thus, our attack does not require any physical access or special privileges, and hence could be also implemented on shared cloud servers. Using Rowhammer attack, we inject bit flips into the secret key s1 of Dilithium, which results in incorrect signatures being generated by the signing algorithm. Since we can find the correct signature using our Signature Correction algorithm, we can use the difference between the correct and incorrect signatures to infer the location and value of the flipped bit without needing a correct and faulty pair. To quantify the reduction in the security level, we perform a thorough classical and quantum security analysis of Dilithium and successfully recover 1,851 bits out of 3,072 bits of secret key $$s_{1}$$ for security level 2. Fully recovered bits are used to reduce the dimension of the lattice whereas partially recovered coefficients are used to to reduce the norm of the secret key coefficients. Further analysis for both primal and dual attacks shows that the lattice strength against quantum attackers is reduced from 2128 to 281 while the strength against classical attackers is reduced from 2141 to 289. Hence, the Signature Correction Attack may be employed to achieve a practical attack on Dilithium (security level 2) as proposed in Round 3 of the NIST post-quantum standardization process.more » « less
-
Fault-tolerant quantum computation with bosonic qubits often necessitates the use of noisy discrete-variable ancillae. In this work, we establish a comprehensive and practical fault-tolerance framework for such a hybrid system and synthesize it with fault-tolerant protocols by combining bosonic quantum error correction (QEC) and advanced quantum control techniques. We introduce essential building blocks of error-corrected gadgets by leveraging ancilla-assisted bosonic operations using a generalized variant of path-independent quantum control. Using these building blocks, we construct a universal set of error-corrected gadgets that tolerate a single-photon loss and an arbitrary ancilla fault for four-legged cat qubits. Notably, our construction requires only dispersive coupling between bosonic modes and ancillae, as well as beam-splitter coupling between bosonic modes, both of which have been experimentally demonstrated with strong strengths and high accuracy. Moreover, each error-corrected bosonic qubit is comprised of only a single bosonic mode and a three-level ancilla, featuring the hardware efficiency of bosonic QEC in the full fault-tolerant setting. We numerically demonstrate the feasibility of our schemes using current experimental parameters in the circuit-QED platform. Finally, we present a hardware-efficient architecture for fault-tolerant quantum computing by concatenating the four-legged cat qubits with an outer qubit code utilizing only beam-splitter couplings. Our estimates suggest that the overall noise threshold can be reached using existing hardware. These developed fault-tolerant schemes extend beyond their applicability to four-legged cat qubits and can be adapted for other rotation-symmetrical codes, offering a promising avenue toward scalable and robust quantum computation with bosonic qubits.more » « less
