More Like this

1. Lattice-Based Proof-of-Work for Post-Quantum Blockchains

   Rouzbeh Behnia, Eamonn W. (October 2021, 5th International Workshop on Cryptocurrencies and Blockchain Technology - CBT 2021 (with ESORICS 2021))

   Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover’s search algorithm gives an asymptotic quadratic advantage to quantum machines over classical machines. In this paper, as a step towards a fuller understanding of post-quantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Specifically, for a lattice of rank n sampled from a particular class, our protocol provides as the PoW an instance of the Hermite Shortest Vector Problem (Hermite-SVP) in the Euclidean norm, to a small approximation factor. Asymptotically, the best known classical and quantum algorithms that directly solve SVP type problems are heuristic lattice sieves, which run in time 20.292n+o(n) and 2 0.265n+o(n) respectively. We discuss recent advances in SVP type problem solvers and give examples of where the impetus provided by a lattice-based PoW would help explore often complex optimization spaces. 

   more » « less
2. Approximate shortest paths and distance oracles in weighted unit-disk graphs

   https://doi.org/10.20382/jocg.v10i2  

   Chan, Timothy M.; Skrepetos, Dimitrios (January 2019, Journal of computational geometry)

   We present the first near-linear-time algorithm that computes a (1+ε)-approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O(n log^2 n) time for any constant ε>0, so we considerably improve upon the near-O(n^{3/2})-time algorithm of Gao and Zhang (2005). Using similar ideas we develop (1+ε)-approximate \emph{distance oracles} of O(1) query time with a likewise improvement in the preprocessing time, specifically from near O(n^{3/2}) to O(n log^3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1+ε)-approximate \emph{all-pairs bounded-leg shortest paths\/} (apBLSP) problem for a set of n planar points. Our data structure requires O(n^2 log n) space, O(loglog n) query time, and nearly O(n^{2.579}) preprocessing time for any constant ε>0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal (2011). 

   more » « less
3. Shallow-Depth Quantum Circuit for an Unstructured Database Search

   https://doi.org/10.3390/quantum6040037  

   Zhan, Junpeng (October 2024, Quantum Reports)

   Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits. 

   more » « less
4. \({\ell_0}\) Optimization with Robust Non-Oracular Quantum Search

   https://doi.org/10.3390/technologies11050148  

   Zhang , Tianyi; Ke, Yuan (October 2023, Technologies)

   In this article, we introduce an innovative hybrid quantum search algorithm, the Robust Non-oracle Quantum Search (RNQS), which is specifically designed to efficiently identify the minimum value within a large set of random numbers. Distinct from the Grover’s algorithm, the proposed RNQS algorithm circumvents the need for an oracle function that describes the true solution state, a feature often impractical for data science applications. Building on existing non-oracular quantum search algorithms, RNQS enhances robustness while substantially reducing running time. The superior properties of RNQS have been demonstrated through careful analysis and extensive empirical experiments. Our findings underscore the potential of the RNQS algorithm as an effective and efficient solution to combinatorial optimization problems in the realm of quantum computing. 

   more » « less
5. The Parallel Reversible Pebbling Game: Analyzing the Post-quantum Security of iMHFs

   Blocki, Jeremiah; Holman, Blake; Lee, Seunghoon (December 2022, Theory of Cryptography Conference (TCC 2022))

   Kiltz, E. (Ed.)

   The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function f with a static data-dependency graph G. Of particular interest in the field of cryptography are data-independent memory-hard functions fG,H which are defined by a directed acyclic graph (DAG) G and a cryptographic hash function H. The pebbling complexity of the graph G characterizes the amortized cost of evaluating fG,H multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain X, i.e., given y∈{0,1}∗ find x∈X such that fG,H(x)=y. While a classical attacker will need to evaluate the function fG,H at least m=|X| times a quantum attacker running Grover’s algorithm only requires O(m−−√) blackbox calls to a quantum circuit CG,H evaluating the function fG,H. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit CG,H. We first observe that a legal black pebbling strategy for the graph G does not necessarily imply the existence of a quantum circuit with comparable complexity—in contrast to the classical setting where any efficient pebbling strategy for G corresponds to an algorithm with comparable complexity for evaluating fG,H. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. Specifically, (1) we show that a line graph of size N has reversible space-time complexity at most O(N^{1+2/√logN}). (2) We show that any (e, d)-reducible DAG has reversible space-time complexity at most O(Ne+dN2^d). In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most O(N^2 loglogN/√logN) and O(N^2/(log N)^{1/3}), respectively. (3) We show that the reversible space-time complexity of DRSample is at most O((N^2loglog N)/log N). We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs. 

   more » « less