Search

Several cryptographic systems depend upon the computational difficulty of reversing cryptographic hash functions. Robust hash functions transform inputs to outputs in such a way that the inputs cannot be later retrieved in a reasonable amount of time even if the outputs and the function that created them are known. Consequently, hash functions can be cryptographically secure, and they are employed in encryption, authentication, and other security methods. It has been suggested that such cryptographically-secure hash functions will play a critical role in the era of post-quantum cryptography (PQC), as they do in conventional systems. In this work, we introduce a procedure that leverages the principle of reversibility to generate circuits that invert hash functions. We provide a proof-of-concept implementation and describe methods that allow for scaling the hash function inversion approach. Specifically, we implement one manifestation of the algorithm as part of a more general automated quantum circuit synthesis, compilation, and optimization toolkit. We illustrate production of reversible circuits for crypto-hash functions that inherently provide the inverse of the function, and we describe data structures that increase the scalability of the hash function inversion approach., Comment: 12 pages, 9 figures, 1 table

Physically unclonable functions (PUFs) are designed to act as device 'fingerprints.' Given an input challenge, the PUF circuit should produce an unpredictable response for use in situations such as root-of-trust applications and other hardware-level cybersecurity applications. PUFs are typically subcircuits present within integrated circuits (ICs), and while conventional IC PUFs are well-understood, several implementations have proven vulnerable to malicious exploits, including those perpetrated by machine learning (ML)-based attacks. Such attacks can be difficult to prevent because they are often designed to work even when relatively few challenge-response pairs are known in advance. Hence the need for both more resilient PUF designs and analysis of ML-attack susceptibility. Previous work has developed a PUF for photonic integrated circuits (PICs). A PIC PUF not only produces unpredictable responses given manufacturing-introduced tolerances, but is also less prone to electromagnetic radiation eavesdropping attacks than a purely electronic IC PUF. In this work, we analyze the resilience of the proposed photonic PUF when subjected to ML-based attacks. Specifically, we describe a computational PUF model for producing the large datasets required for training ML attacks; we analyze the quality of the model; and we discuss the modeled PUF's susceptibility to ML-based attacks. We find that the modeled PUF generates distributions that resemble uniform white noise, explaining the exhibited resilience to neural-network-based attacks designed to exploit latent relationships between challenges and responses. Preliminary analysis suggests that the PUF exhibits similar resilience to generative adversarial networks, and continued development will show whether more-sophisticated ML approaches better compromise the PUF and -- if so -- how design modifications might improve resilience., Comment: 14 pages, 8 figures

Physically unclonable functions (PUFs) identify integrated circuits using nonlinearly-related challenge-response pairs (CRPs). Ideally, the relationship between challenges and corresponding responses is unpredictable, even if a subset of CRPs is known. Previous work developed a photonic PUF offering improved security compared to non-optical counterparts. Here, we investigate this PUF's susceptibility to Multiple-Valued-Logic-based machine learning attacks. We find that approximately 1,000 CRPs are necessary to train models that predict response bits better than random chance. Given the significant challenge of acquiring a vast number of CRPs from a photonic PUF, our results demonstrate photonic PUF resilience against such attacks., Comment: 6 pages, 4 figures

Quantum algorithms provide an exponential speedup for solving certain classes of linear systems, including those that model geologic fracture flow. However, this revolutionary gain in efficiency does not come without difficulty. Quantum algorithms require that problems satisfy not only algorithm-specific constraints, but also application-specific ones. Otherwise, the quantum advantage carefully attained through algorithmic ingenuity can be entirely negated. Previous work addressing quantum algorithms for geologic fracture flow has illustrated core algorithmic approaches while incrementally removing assumptions. This work addresses two further requirements for solving geologic fracture flow systems with quantum algorithms: efficient system state preparation and efficient information extraction. Our approach to addressing each is consistent with an overall exponential speed-up., Comment: 13 pages, 12 figures, LA-UR-23-31328

The quantum computer has become contemporary reality, with the first two-qubit machine of mere decades ago transforming into cloud-accessible devices with tens, hundreds, or -- in a few cases -- even thousands of qubits. While such hardware is noisy and still relatively small, the increasing number of operable qubits raises another challenge: how to develop the now-sizeable quantum circuits executable on these machines. Preparing circuits manually for specifications of any meaningful size is at best tedious and at worst impossible, creating a need for automation. This article describes an automated quantum-software toolkit for synthesis, compilation, and optimization, which transforms classically-specified, irreversible functions into both technology-independent and technology-dependent quantum circuits. We also describe and analyze the toolkit's application to three situations -- quantum read-only memories, quantum random number generators, and quantum oracles -- and illustrate the toolkit's start-to-finish features, from the input of classical functions to the output of technology-dependent quantum circuits. Furthermore, we illustrate how the toolkit enables research beyond circuit synthesis, including comparison of synthesis and optimization methods and deeper understanding of even well-studied quantum algorithms. As quantum hardware continues to develop, such quantum circuit toolkits will play a critical role in realizing its potential., Comment: 48 pages, 23 figures, 20 tables

Several prominent quantum computing algorithms--including Grover's search algorithm and Shor's algorithm for finding the prime factorization of an integer--employ subcircuits termed 'oracles' that embed a specific instance of a mathematical function into a corresponding bijective function that is then realized as a quantum circuit representation. Designing oracles, and particularly, designing them to be optimized for a particular use case, can be a non-trivial task. For example, the challenge of implementing quantum circuits in the current era of NISQ-based quantum computers generally dictates that they should be designed with a minimal number of qubits, as larger qubit counts increase the likelihood that computations will fail due to one or more of the qubits decohering. However, some quantum circuits require that function domain values be preserved, which can preclude using the minimal number of qubits in the oracle circuit. Thus, quantum oracles must be designed with a particular application in mind. In this work, we present two methods for automatic quantum oracle synthesis. One of these methods uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits. For each method, we describe known quantum circuit use cases, and illustrate implementation using an automated quantum compilation and optimization tool to synthesize oracles for a set of benchmark functions; we can then compare the methods with metrics including required qubit count and quantum circuit complexity., Comment: 18 pages, 10 figures, SPIE Defense + Commercial Sensing: Quantum Information Science, Sensing, and Computation XV

Random number generators (RNG) are essential elements in many cryptographic systems. True random number generators (TRNG) rely upon sources of randomness from natural processes such as those arising from quantum mechanics phenomena. We demonstrate that a quantum computer can serve as a high-quality, weakly random source for a generalized user-defined probability mass function (PMF). Specifically, QC measurement implements the process of variate sampling according to a user-specified PMF resulting in a word comprised of electronic bits that can then be processed by an extractor function to address inaccuracies due to non-ideal quantum gate operations and other system biases. We introduce an automated and flexible method for implementing a TRNG as a programmed quantum circuit that executes on commercially-available, gate-model quantum computers. The user specifies the desired word size as the number of qubits and a definition of the desired PMF. Based upon the user specification of the PMF, our compilation tool automatically synthesizes the desired TRNG as a structural OpenQASM file containing native gate operations that are optimized to reduce the circuit's quantum depth. The resulting TRNG provides multiple bits of randomness for each execution/measurement cycle; thus, the number of random bits produced in each execution is limited only by the size of the QC. We provide experimental results to illustrate the viability of this approach., Comment: 15 pages, 7 figures, SPIE Defense + Commercial Sensing: Quantum Information Science, Sensing, and Computation XV

Emerging quantum algorithms that process data require that classical input data be represented as a quantum state. These data-processing algorithms often follow the gate model of quantum computing--which requires qubits to be initialized to a basis state, typically $\lvert 0 \rangle$--and thus often employ state generation circuits to transform the initialized basis state to a data-representation state. There are many ways to encode classical data in a qubit, and the oft-applied approach of basis encoding does not allow optimization to the extent that other variants do. In this work, we thus consider automatic synthesis of addressable, quantum read-only memory (QROM) circuits, which act as data-encoding state-generation circuits. We investigate three data encoding approaches, one of which we introduce to provide improved dynamic range and precision. We present experimental results that compare these encoding methods for QROM synthesis to better understand the implications of and applications for each., Comment: 14 pages, 9 figures, and 13 tables

Solving large systems of equations is a challenge for modeling natural phenomena, such as simulating subsurface flow. To avoid systems that are intractable on current computers, it is often necessary to neglect information at small scales, an approach known as coarse-graining. For many practical applications, such as flow in porous, homogenous materials, coarse-graining offers a sufficiently-accurate approximation of the solution. Unfortunately, fractured systems cannot be accurately coarse-grained, as critical network topology exists at the smallest scales, including topology that can push the network across a percolation threshold. Therefore, new techniques are necessary to accurately model important fracture systems. Quantum algorithms for solving linear systems offer a theoretically-exponential improvement over their classical counterparts, and in this work we introduce two quantum algorithms for fractured flow. The first algorithm, designed for future quantum computers which operate without error, has enormous potential, but we demonstrate that current hardware is too noisy for adequate performance. The second algorithm, designed to be noise resilient, already performs well for problems of small to medium size (order 10 to 1000 nodes), which we demonstrate experimentally and explain theoretically. We expect further improvements by leveraging quantum error mitigation and preconditioning., Comment: 20 pages, 12 figures

Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.