02329nas a2200133 4500008004100000245008800041210006900129260001400198520190700212100002402119700001602143700001502159856002102174 2023 eng d00aGeneralized Hybrid Search and Applications to Blockchain and Hash Function Security0 aGeneralized Hybrid Search and Applications to Blockchain and Has c11/7/20233 a
In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution D on Boolean functions, the probability an algorithm equipped with τc classical and τq quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most νD⋅(2τc−−√+2τq+1)2, where νD captures the average (over D) fraction of preimages of 1. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution D. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.
1 aCojocaru, Alexandru1 aGaray, Juan1 aSong, Fang uarXiv:2311.0372302355nas a2200169 4500008004100000245007400041210006900115260001300184300001300197490001000210520178100220100001902001700002202020700002302042700001502065856010502080 2020 eng d00aQuantum-Access-Secure Message Authentication via Blind-Unforgeability0 aQuantumAccessSecure Message Authentication via BlindUnforgeabili c5/1/2020 a788-817 0 v12-173 aFormulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition.
We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hash-and-MAC” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.
Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.
1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://quics.umd.edu/publications/quantum-access-secure-message-authentication-blind-unforgeability01127nas a2200145 4500008004100000245006400041210006200105260001500167490001000182520070300192100001800895700001600913700001500929856003700944 2018 eng d00aPseudorandom States, Non-Cloning Theorems and Quantum Money0 aPseudorandom States NonCloning Theorems and Quantum Money c2017/11/010 v109933 aWe propose the concept of pseudorandom states and study their constructions, properties, and applications. Under the assumption that quantum-secure one-way functions exist, we present concrete and efficient constructions of pseudorandom states. The non-cloning theorem plays a central role in our study—it motivates the proper definition and characterizes one of the important properties of pseudorandom quantum states. Namely, there is no efficient quantum algorithm that can create more copies of the state from a given number of pseudorandom states. As the main application, we prove that any family of pseudorandom states naturally gives rise to a private-key quantum money scheme.
1 aJi, Zhengfeng1 aLiu, Yi-Kai1 aSong, Fang uhttps://arxiv.org/abs/1711.0038502448nas a2200133 4500008004100000245006700041210006500108520202500173100001902198700002202217700002302239700001502262856003702277 2018 eng d00aQuantum-secure message authentication via blind-unforgeability0 aQuantumsecure message authentication via blindunforgeability3 aFormulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with 0 divulges the value of the function on an input that starts with 1. We then propose a new definition, which we call "blind-unforgeability" (or BU.) This notion matches "intuitive unpredictability" in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use "partially blinded" oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using "Bernoulli-preserving" hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment.
1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://arxiv.org/abs/1803.03761