 Award ID(s):
 1839805
 NSFPAR ID:
 10295505
 Date Published:
 Journal Name:
 Journal of Mathematical Cryptology
 Volume:
 15
 Issue:
 1
 ISSN:
 18622984
 Page Range / eLocation ID:
 143 to 156
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 ﬁxing a priori a suﬃciently 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 postquantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Speciﬁcally, 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 (HermiteSVP) 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 latticebased PoW would help explore often complex optimization spaces.more » « less

Abstract We study the performance scaling of three quantum algorithms for combinatorial optimization: measurementfeedback coherent Ising machines (MFBCIM), discrete adiabatic quantum computation (DAQC), and the Dürr–Høyer algorithm for quantum minimum finding (DHQMF) that is based on Grover’s search. We use M
ax Cut problems as a reference for comparison, and timetosolution (TTS) as a practical measure of performance for these optimization algorithms. For each algorithm, we analyze its performance in solving two types of Max Cut problems: weighted graph instances with randomly generated edge weights attaining 21 equidistant values from −1 to 1; and randomly generated Sherrington–Kirkpatrick (SK) spin glass instances. We empirically find a significant performance advantage for the studied MFBCIM in comparison to the other two algorithms. We empirically observe a subexponential scaling for the median TTS for the MFBCIM, in comparison to the almost exponential scaling for DAQC and the proven scaling for DHQMF. We conclude that the MFBCIM outperforms DAQC and DHQMF in solving M$$\widetilde{{{{\mathcal{O}}}}}\left(\sqrt{{2}^{n}}\right)$$ $\stackrel{\u0303}{O}\left(\sqrt{{2}^{n}}\right)$ax Cut problems. 
We present the first nearlineartime algorithm that computes a (1+ε)approximation of the diameter of a weighted unitdisk graph of n vertices. Our algorithm requires O(n log^2 n) time for any constant ε>0, so we considerably improve upon the nearO(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 unitdisk 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{allpairs boundedleg 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 nearcubic preprocessing time bound given by Roditty and Segal (2011).more » « less

In this article, we introduce an innovative hybrid quantum search algorithm, the Robust Nonoracle 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 nonoracular 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.

Kiltz, E. (Ed.)The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, spacetime, cumulative space) necessary to evaluate a function f with a static datadependency graph G. Of particular interest in the field of cryptography are dataindependent memoryhard 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 bruteforce 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 spacetime 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 NoDeletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible spacetime complexity of several important graphs: Line Graphs, Argon2iA, Argon2iB, and DRSample. Specifically, (1) we show that a line graph of size N has reversible spacetime complexity at most O(N^{1+2/√logN}). (2) We show that any (e, d)reducible DAG has reversible spacetime complexity at most O(Ne+dN2^d). In particular, this implies that the reversible spacetime complexity of Argon2iA and Argon2iB are at most O(N^2 loglogN/√logN) and O(N^2/(log N)^{1/3}), respectively. (3) We show that the reversible spacetime complexity of DRSample is at most O((N^2loglog N)/log N). We also study the cumulative pebbling cost of reversible pebblings extending a (nonreversible) pebbling attack of Alwen and Blocki on depthreducible graphs.more » « less