Quantum-Access-Secure Message Authentication via Blind-Unforgeability
Quantum-Access-Secure Message Authentication via Blind-Unforgeability
复制标题
DOI：
10.1007/978-3-030-45727-3_27
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
G. Alagic;Christian Majenz;A. Russell;F. Song
中科院分区：
文献类型：
--
作者：
G. Alagic;Christian Majenz;A. Russell;F. Song
在具有量子查询访问的攻击者在场的情况下，制定和设计经典消息的认证一直是一个长期存在的挑战，因为熟悉的不可伪造性的经典概念不能直接转化为在量子环境中有意义的概念。一个特别的困难是，当敌手可以在量子叠加中查询时，如何公平地捕捉“预测未查询的值”的概念。我们提出了对抗量子对手的不可伪造性的自然定义，称为盲不可伪造性。这个概念定义了一个函数是可预测的，如果存在一个对手，该对手可以使用“部分盲目的”先知访问来预测盲区中的值。我们用一系列技术成果支持这项提议。我们首先建立了这个概念在经典设置下与EUF-CMA重合，然后通过一些简单的指导性例子，例如随机函数和量子查询安全伪随机函数，证明了这个概念是满足的。然后，我们证明了盲不可伪造性对于支持规范构造和约简的适用性。根据定义，我们证明了Hash-and-MAC范例和Lamport一次性数字签名方案确实是不可伪造的。为了支持我们的分析，我们还定义和研究了一种新的量子安全哈希函数，称为Bernoulli保持。最后，我们证明了盲不可伪造性严格强于Boneh和Zhandry[Eurocrypt‘13，Crypto’13]的先前定义，并通过构造一个可伪造但满足该定义的显式函数族来解决先前定义中的一个公开问题。
Formulating 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 calledblind 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 calledBernoulli-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.