Quantum-safe & quantum cryptography

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle f = fU depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P x⟩ = π(x)⟩, as well as random alternating-basis phase unitaries F2 · H n · F1. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries x⟩ αx x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing SN and $U(N)$ yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).

We demonstrate a method to generate application-ready truly random bits from a magnetic tunnel junction driven by a Field-Programmable Gate Array (FPGA). We implement a real-time feedback loop that stabilizes the switching probability near 50% and apply an XOR operation, both on the FPGA, to suppress short-term correlations, together mitigating long-term drift and bias in the bitstream. This combined approach passes the NIST Statistical Test Suite for random bit generation at 5 Mb/s without post-processing, providing a practical hardware solution for fast and reliable true random number generation. Beyond cryptographic applications, these capabilities open opportunities for stochastic hardware accelerators, probabilistic computing, and large-scale modeling where real-time access to unbiased randomness is essential.

We study the error correcting properties of Haar random codes, in which a $K$-dimensional code space C CN is chosen at random from the Haar distribution. Our main result is that Haar random codes can approximately correct errors up to the quantum Hamming bound, meaning that a set of $m$ Pauli errors can be approximately corrected so long as mK ≪ N. This is the strongest bound known for any family of quantum error correcting codes (QECs), and continues a line of work showing that approximate QECs can significantly outperform exact QECs [LNCY97, CGS05, BGG24]. Our proof relies on a recent matrix concentration result of Bandeira, Boedihardjo, and van Handel.

We review two magnetic tunnel junction (MTJ) approaches for compact, low-power, CMOS-integrated true random number generation (TRNG). The first employs passive-read, easy-plane superparamagnetic MTJs (sMTJs) that generate thermal-fluctuation-driven bit streams at $0.5$--$1$~Gb/s per device. The second uses MTJs with magnetically stable free layers, operated with stochastic write pulses to achieve switching probabilities of about $0.5$ (\emph{i.e.}, write error rates of ≃ 0.5), achieving 0.1~Gb/s per device; we refer to these as stochastic-write MTJs (SW-MTJs). Randomness from both approaches has been validated using the NIST~SP800 test suites. The sMTJ approach uses a read-only cell with low power and can be compatible with most advanced CMOS nodes, while SW-MTJs leverage standard CMOS MTJ process flows, enabling co-integration with embedded spin-transfer torque magnetic random access memory (STT-MRAM). Both approaches can achieve deep sub-0.01~$μ$m² MTJ footprints and offer orders-of-magnitude better energy efficiency than CPU/GPU-based generators, enabling placement near logic for high-throughput random bit-streams for probabilistic computing, statistical modeling, and cryptography. In terms of performance, sMTJs generally suit applications requiring very high data-rate random bits near logic processors, such as probabilistic computing or large-scale statistical modeling. By contrast, SW-MTJs are an attractive option for edge-oriented microcontrollers, providing entropy sources for computing or cryptographic enhancement. We highlight the strengths, limitations, and integration challenges of each approach, emphasizing the need to reduce device-to-device variability in sMTJs -- particularly by mitigating magnetostriction-induced in-plane anisotropy -- and to improve temporal stability in SW-MTJs for robust, large-scale deployment.

Perpendicular magnetic tunnel junctions (pMTJs) actuated by nanosecond pulses are emerging as promising devices for true random number generation (TRNG) due to their intrinsic stochastic behavior and high throughput. In this work, we demonstrate the tunability and quality of random number distributions generated by pMTJs operating at a frequency of 104 MHz. First, changing the pulse amplitude is used to systematically vary the probability bias. The variance of the resulting bitstreams closely matches the expected binomial distribution, demonstrating consistency with an underlying sequence of Bernoulli trials. Second, the quality of uniform distributions of 8-bit random numbers generated with a probability bias of 0.5 is considered. A reduced chi-square analysis of these data shows that only two XOR operations are sufficient to achieve this distribution with p-values greater than 0.05. Finally, we show that there is a correlation between long-term probability bias variations and pMTJ resistance. These findings suggest that variations in the characteristics of the pMTJ underlie the observed variation of probability bias. Our results highlight the potential of stochastically actuated pMTJs for high-speed, tunable TRNG applications, showing the importance of the stability of pMTJ device characteristics in achieving reliable, long-term performance.

The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse U. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

Abstract Consider a sequential process in which each step outputs a system Ai A i and updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs A1, …, An A 1, ⋯, A n conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) (Dupuis et al. in Commun Math Phys 379: 867–913, 2020), which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition. Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. As examples, we give the first multi-round security proof for blind randomness expansion and a simplified analysis of the E91 QKD protocol. The proof of our generalised EAT relies on a new variant of Uhlmann’s theorem and new chain rules for the Rényi divergence and entropy, which might be of independent interest.

Random reversible and quantum circuits form random walks on the alternating group Alt(2ⁿ) and unitary group SU(2ⁿ), respectively. Known bounds on the spectral gap for the $t$-th moment of these random walks have inverse-polynomial dependence in both $n$ and $t$. We prove that the gap for random reversible circuits is Ω(n⁻³) for all t≥ 1, and the gap for random quantum circuits is Ω(n⁻³) for t ≤ Θ(2n/2). These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to n⁻¹/polylog(n, t) for t≤ 2Θ(n), which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with O(n⁴ t) gates form multiplicative-error $t$-wise independent (even) permutations for all t≥ 1; for t ≤ Θ(2n/6.1), we show that O(n² t) gates suffice. 2) Random quantum circuits with O(n⁴ t) gates form multiplicative-error unitary $t$-designs for t ≤ Θ(2n/2); for t≤ Θ(22n/5), we show that O(n²t) gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``PFC ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.

A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptographic assumption). Such protocols play a crucial role in the certification of quantum devices. Existing single-round protocols (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. As such, current proofs of quantumness are out of reach for near-term devices. In this work, we construct efficient single-round proofs of quantumness based on existing knowledge assumptions. While knowledge assumptions have not been previously considered in this context, we show that they provide a natural basis for separating classical and quantum computation. Specifically, we show that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning With Errors (LWE) can be "compiled" into single-round protocols using a knowledge-of-exponent assumption or knowledge-of-lattice-point assumption, respectively. We also prove an adaptive hardcore-bit statement for a family of claw-free functions based on DDH, which might be of independent interest. Previous approaches to constructing single-round protocols relied on the random oracle model and thus incurred the overhead associated with instantiating the oracle with a cryptographic hash function. In contrast, our protocols have the same resource requirements as their multi-round counterparts without necessitating mid-circuit measurements, making them, arguably, the most efficient single-round proofs of quantumness to date. Our work also helps in understanding the interplay between black-box/white-box reductions and cryptographic assumptions in the design of proofs of quantumness.

We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS '18), Bartusek et al. (CRYPTO '22) also constructed a succinct classical argument system for QMA. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP*=RE in quantum complexity.

Nanoscale magnetic tunnel junction (MTJ) devices can efficiently convert thermal energy in the environment into random bitstreams for computational modeling and cryptography. We recently showed that perpendicular MTJs actuated by nanosecond pulses can generate true random numbers at high data rates. Here, we explore the dependence of probability bias—the deviations from equal probability (50/50) 0/1 bit outcomes—of such devices on temperature, pulse amplitude, and duration. Our experimental results and device model demonstrate that operation with nanosecond pulses in the ballistic limit minimizes variation of probability bias with temperature to be far lower than that of devices operated with longer-duration pulses. Furthermore, operation in the short-pulse limit reduces the bias variation with pulse amplitude while rendering the device more sensitive to pulse duration. These results are significant for designing true random number generator MTJ circuits and establishing operating conditions.

Large quantities of random numbers are crucial in a wide range of applications. We have recently demonstrated that perpendicular nanopillar magnetic tunnel junctions (pMTJs) can produce true random bits when actuated with short pulses. However, our implementation used high-end and expensive electronics, such as a high-bandwidth arbitrary waveform generator and analog-to-digital converter, and was limited to relatively low data rates. Here, we significantly increase the speed of true random-number generation of our stochastic actuated pMTJs (SMART-pMTJs) using field-programmable gate arrays (FPGAs), demonstrating the generation of over10¹²bits at rates exceeding 10 Mb/s. The resulting bitstreams pass the NIST Statistical Test Suite for randomness with only onexoroperation. In addition to a hundred-fold reduction in the setup cost and a thousand-fold increase in bitrate, the advancement includes simplifying and optimizing random bit generation with a custom-designed analog daughterboard to interface an FPGA and SMART-pMTJ. The resulting setup further enables FPGA at-speed processing of MTJ data for stochastic modeling and cryptography.

Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. We prove this by constructing strong forms of pseudoentanglement in a public-key setting, where the circuits used to prepare the states are public knowledge. In particular, we construct two families of quantum circuits which produce volume-law vs near area-law entangled states, but nonetheless the classical descriptions of the circuits are indistinguishable under the Learning with Errors (LWE) assumption. Indistinguishability of the circuits then allows us to translate our construction to Hamiltonians. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.

Nanoscale magnetic tunnel junction (MTJ) devices can efficiently convert thermal energy in the environment into random bitstreams for computational modeling and cryptography. We recently showed that perpendicular MTJs activated by nanosecond pulses can generate true random numbers at high data rates. Here, we explore the dependence of probability bias-the deviations from equal probability (50/50) 0/1 bit outcomes-of such devices on temperature, pulse amplitude, and duration. Our experimental results and device model demonstrate that operation with nanosecond pulses in the ballistic limit minimizes variation of probability bias with temperature to be far lower than that of devices operated with longer-duration pulses. Further, operation in the short-pulse limit reduces the bias variation with pulse amplitude while rendering the device more sensitive to pulse duration. These results are significant for designing TRNG MTJ circuits and establishing operating conditions.

True random number generators (TRNGs) are fundamental building blocks for many applications, such as cryptography, Monte Carlo simulations, neuromorphic computing, and probabilistic computing. While perpendicular magnetic tunnel junctions (pMTJs) based on low-barrier magnets (LBMs) are natural sources of TRNGs, they tend to suffer from device-to-device variability, low speed, and temperature sensitivity. Instead, medium-barrier magnets (MBMs) operated with nanosecond pulses - denoted, stochastic magnetic actuated random transducer (SMART) devices - are potentially superior candidates for such applications. We present a systematic analysis of spin-torque-driven switching of MBM-based pMTJs (Eb ~ 20 - 40 kBT) as a function of pulse duration (1 ps to 1 ms), by numerically solving their macrospin dynamics using a 1-D Fokker-Planck equation. We investigate the impact of voltage, temperature, and process variations (MTJ dimensions and material parameters) on the switching probability of the device. Our findings indicate SMART devices activated by short-duration pulses (< 1 ns) are much less sensitive to process-voltage-temperature (PVT) variations while consuming lower energy (~ fJ) than the same devices operated with longer pulses. Our results show a path toward building fast, energy-efficient, and robust TRNG hardware units for solving optimization problems.

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries $U$ such that no quantum polynomial-time oracle algorithm Af can implement $U$, even approximately, if it only makes one (quantum) query to $f$. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

Machine learning methods, particularly neural networks trained on large datasets, are transforming how scientists approach scientific discovery and experimental design. However, current state-of-the-art neural networks are limited by their uninterpretability: Despite their excellent accuracy, they cannot describe how they arrived at their predictions. Here, using an "interpretable-by-design" approach, we present a neural network model that provides insights into RNA splicing, a fundamental process in the transfer of genomic information into functional biochemical products. Although we designed our model to emphasize interpretability, its predictive accuracy is on par with state-of-the-art models. To demonstrate the model's interpretability, we introduce a visualization that, for any given exon, allows us to trace and quantify the entire decision process from input sequence to output splicing prediction. Importantly, the model revealed uncharacterized components of the splicing logic, which we experimentally validated. This study highlights how interpretable machine learning can advance scientific discovery.

The goal of quantum key distribution (QKD) is to establish a secure key between two parties connected by an insecure quantum channel. To use a QKD protocol in practice, one has to prove that a finite size key is secure against general attacks: no matter the adversary's attack, they cannot gain useful information about the key. A much simpler task is to prove security against collective attacks, where the adversary is assumed to behave identically and independently in each round. In this work, we provide a formal framework for general QKD protocols and show that for any protocol that can be expressed in this framework, security against general attacks reduces to security against collective attacks, which in turn reduces to a numerical computation. Our proof relies on a recently developed information-theoretic tool called generalised entropy accumulation and can handle generic prepare-and-measure protocols directly without switching to an entanglement-based version.

State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.

Magnetic tunnel junctions (MTJs), which are the fundamental building blocks of spintronic devices, have been used to build true random number generators (TRNGs) with different trade-offs between throughput, power, and area requirements. MTJs with high-barrier magnets (HBMs) have been used to generate random bitstreams with 200~Mb/s throughput and pJ/bit energy consumption. A high temperature sensitivity, however, adversely affects their performance as a TRNG. Superparamagnetic MTJs employing low-barrier magnets (LBMs) have also been used for TRNG operation. Although LBM-based MTJs can operate at low energy, they suffer from slow dynamics, sensitivity to process variations, and low fabrication yield. In this paper, we model a TRNG based on medium-barrier magnets (MBMs) with perpendicular magnetic anisotropy. The proposed MBM-based TRNG is driven with short voltage pulses to induce ballistic, yet stochastic, magnetization switching. We show that the proposed TRNG can operate at frequencies of about 500~MHz while consuming less than 100~fJ/bit of energy. In the short-pulse ballistic limit, the switching probability of our device shows robustness to variations in temperature and material parameters relative to LBMs and HBMs. Our results suggest that MBM-based MTJs are suitable candidates for building fast and energy-efficient TRNG hardware units for probabilistic computing.

True random number generators are of great interest in many computing applications, such as cryptography, neuromorphic systems, and Monte Carlo simulations. Here, we investigate perpendicular magnetic-tunnel-junction nanopillars (pMTJs) activated by short-duration (nanosecond) pulses in the ballistic limit for such applications. In this limit, a pulse can transform the Boltzmann distribution of initial free-layer magnetization states into randomly magnetized down or up states, i.e., a bit that is 0 or 1, easily determined by measurement of the tunnel resistance of the junction. It is demonstrated that bit streams with millions of events: (1) are very well approximated by a normal distribution; (2) pass multiple statistical tests for true randomness, including all the National Institute of Standards and Technology tests for random number generators with only one xor operation; (3) can be used to create a uniform distribution of 8-bit random numbers; and (4) can have no drift in the bit probability with time. The results presented here show that pMTJs operated in the ballistic regime can generate true random numbers at around 50-MHz bit rates, while being more robust to environmental changes, such as their operating temperature, compared to other stochastic nanomagnetic devices.

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.

Summary Machine learning methods, particularly neural networks trained on large datasets, are transforming how scientists approach scientific discovery and experimental design. However, current state-of-the-art neural networks are limited by their uninterpretability: despite their excellent accuracy, they cannot describe how they arrived at their predictions. Here, using an “interpretable-by-design” approach, we present a neural network model that provides insights into RNA splicing, a fundamental process in the transfer of genomic information into functional biochemical products. Although we designed our model to emphasize interpretability, its predictive accuracy is on par with state-of-the-art models. To demonstrate the model’s interpretability, we introduce a visualization that, for any given exon, allows us to trace and quantify the entire decision process from input sequence to output splicing prediction. Importantly, the model revealed novel components of the splicing logic, which we experimentally validated. This study highlights how interpretable machine learning can advance scientific discovery.

We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC '20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle. At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS '18). We give a self-contained, modular proof of security for Mahadev's protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier's first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including - Succinct arguments for QMA (given multiple copies of the witness), - Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and - Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).

Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation. The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared n uniformly random BB84 states (up to a change of basis on his space). While previous approaches could only certify one- or two-qubit states, our protocol allows for the certification of an n-fold tensor product of BB84 states. Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent n random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.

A major difficulty in quantum rewinding is the fact that measurement is\ndestructive: extracting information from a quantum state irreversibly changes\nit. This is especially problematic in the context of zero-knowledge simulation,\nwhere preserving the adversary's state is essential.\n In this work, we develop new techniques for quantum rewinding in the context\nof extraction and zero-knowledge simulation:\n (1) We show how to extract information from a quantum adversary by rewinding\nit without disturbing its internal state. We use this technique to prove that\nimportant interactive protocols, such as the Goldreich-Micali-Wigderson\nprotocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are\nzero-knowledge against quantum adversaries.\n (2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero\nknowledge using a simulator that can be seen as a natural quantum extension of\nthe classical simulator.\n Our results achieve (constant-round) black-box zero-knowledge with negligible\nsimulation error, appearing to contradict a recent impossibility result due to\nChia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution:\n (3) We introduce coherent-runtime expected quantum polynomial time, a\ncomputational model that (a) captures all of our zero-knowledge simulators, (b)\ncannot break any polynomial hardness assumptions, and (c) is not subject to the\nCCLY impossibility. In light of our positive results and the CCLY negative\nresults, we propose coherent-runtime simulation to be the right quantum\nanalogue of classical expected polynomial-time simulation.\n

Abstract In device-independent quantum key distribution (DIQKD), an adversary prepares a device consisting of two components, distributed to Alice and Bob, who use the device to generate a secure key. The security of existing DIQKD schemes holds under the assumption that the two components of the device cannot communicate with one another during the protocol execution. This is called the no-communication assumption in DIQKD. Here, we show how to replace this assumption, which can be hard to enforce in practice, by a standard computational assumption from post-quantum cryptography: we give a protocol that produces secure keys even when the components of an adversarial device can exchange arbitrary quantum communication, assuming the device is computationally bounded. Importantly, the computational assumption only needs to hold during the protocol execution—the keys generated at the end of the protocol are information-theoretically secure as in standard DIQKD protocols.

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). At the heart of our proof is a new measure-and-repair quantum rewinding procedure that achieves asymptotically optimal knowledge error.

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

Despite the success of neural networks at solving concrete physics problems, their use as a general-purpose tool for scientific discovery is still in its infancy. Here, we approach this problem by modeling a neural network architecture after the human physical reasoning process, which has similarities to representation learning. This allows us to make progress towards the long-term goal of machine-assisted scientific discovery from experimental data without making prior assumptions about the system. We apply this method to toy examples and show that the network finds the physically relevant parameters, exploits conservation laws to make predictions, and can help to gain conceptual insights, e.g., Copernicus' conclusion that the solar system is heliocentric.

We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results: - A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE). - A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed technique that we call simulation via teleportation, which may be useful in other settings. In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model, including an impossibility result for a natural class of simulators, and a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation. Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.

An affine determinant program ADP: {0,1}^n → {0,1} is specified by a tuple (A,B_1,…,B_n) of square matrices over?_q and a function Eval:?_q → {0,1}, and evaluated on x ∈ {0,1}^n by computing Eval(det(A + ∑_{i∈[n]} x_i B_i)). In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation. As a proof-of-concept, we give a candidate ADP-based construction of indistinguishability obfuscation (i?) for all circuits along with a simple witness encryption candidate. We provide cryptanalysis demonstrating that our schemes resist several potential attacks, and leave further cryptanalysis to future work. Lastly, we explore practically feasible applications of our witness encryption candidate, such as public-key encryption with near-optimal key generation.

A conjunction is a function f(x1,…,xn) = i ∈ S li where S [n] and each li is xi or xi. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where |S| ≥ 0.226n. While conjunction obfuscation is known from LWE [31, 47], these constructions rely on substantial technical machinery.

Physically unclonable cryptographic primitives are promising for securing the rapidly growing number of electronic devices. Here, we introduce physically unclonable primitives from layered molybdenum disulfide (MoS 2) by leveraging the natural randomness of their island growth during chemical vapor deposition (CVD). We synthesize a MoS 2 monolayer film covered with speckles of multilayer islands, where the growth process is engineered for an optimal speckle density. Using the Clark–Evans test, we confirm that the distribution of islands on the film exhibits complete spatial randomness, hence indicating the growth of multilayer speckles is a spatial Poisson process. Such a property is highly desirable for constructing unpredictable cryptographic primitives. The security primitive is an array of 2048 pixels fabricated from this film. The complex structure of the pixels makes the physical duplication of the array impossible (i.e., physically unclonable). A unique optical response is generated by applying an optical stimulus to the structure. The basis for this unique response is the dependence of the photoemission on the number of MoS 2 layers, which by design is random throughout the film. Using a threshold value for the photoemission, we convert the optical response into binary cryptographic keys. We show that the proper selection of this threshold is crucial for maximizing combination randomness and that the optimal value of the threshold is linked directly to the growth process. This study reveals an opportunity for generating robust and versatile security primitives from layered transition metal dichalcogenides.

Development of physical cryptographic primitives for generating strong security keys is central to combating security threats such as counterfeiting and unauthorized access to electronic devices. We introduce a new class of physical cryptographic primitives from layered molybdenum disulfide (MoS2) which leverages the unique properties of this material system. Using chemical vapor deposition, we synthesize a MoS2 monolayer film covered with speckles of multilayer islands, where the growth process is engineered for an optimal speckle density. The physical cryptographic primitive is an array of 2048 pixels fabricated from this film. Using the Clark-Evans test, we confirm that the distribution of islands on the film exhibits complete spatial randomness, making this cryptographic primitive ideal for security applications. A unique optical response is generated by applying an optical stimulus to the structure. The basis for this unique response is the dependence of the photoemission on the number of MoS2 layers which by design is random throughout the film. The optical response is used to generate cryptographic keys. Standard security tests confirm the uniqueness, reliability, and uniformity of these keys. This study reveals a new opportunity for generating strong and versatile nano-engineered security primitives from layered transition metal dichalcogenides.

All known multilinear map candidates have suffered from a class of attacks known as “zeroizing” attacks, which render them unusable for many applications. We provide a new construction of polynomial-degree multilinear maps and show that our scheme is provably immune to zeroizing attacks under a strengthening of the Branching Program Un-Annihilatability Assumption (Garg et al., TCC 2016-B).

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

Recent advances in lattice cryptography, mainly stemming from the development of ring-based primitives such as ring-LWE, have made it possible to design cryptographic schemes whose efficiency is competitive with that of more traditional number-theoretic ones, along with entirely new applications like fully homomorphic encryption. Unfortunately, realizing the full potential of ring-based cryptography has so far been hindered by a lack of practical algorithms and analytical tools for working in this context. As a result, most previous works have focused on very special classes of rings such as power-of-two cyclotomics, which significantly restricts the possible applications. We bridge this gap by introducing a toolkit of fast, modular algorithms and analytical techniques that can be used in a wide variety of ring-based cryptographic applications, particularly those built around ring-LWE. Our techniques yield applications that work in arbitrary cyclotomic rings, with no loss in their underlying worst-case hardness guarantees, and very little loss in computational efficiency, relative to power-of-two cyclotomics. To demonstrate the toolkit’s applicability, we develop a few illustrative applications: two variant public-key cryptosystems, and a “somewhat homomorphic ” symmetric encryption scheme. Both apply to arbitrary cyclotomics, have tight parameters, and very efficient implementations. 1