论文标题
关于量词后世界中连续工作的证据的安全性
On the Security of Proofs of Sequential Work in a Post-Quantum World
论文作者
论文摘要
顺序工作的证明（POSW）使众者可以说服一个由资源的验证者说服供资，以表明供众投入了大量的顺序时间来执行一些基本的计算。 POSW有许多应用程序，包括时间戳记，区块链设计和普遍可验证的CPU基准。 Mahmoody，Moran和Vadhan（ITCS 2013）在随机Oracle模型中首次构造了POSW，尽管结构依赖于昂贵的深度刺激图。在最近的突破中，科恩和彼得斯克（Eurocrypt 2018）提供了有效的POSW结构，不需要昂贵的深度射击图。 在经典的并行随机甲骨文模型中，很容易说任何成功的POSW攻击者都必须产生一个长$ \ nathcal {h} $ - 序列，并且任何在顺序时间$ t-1 $中运行的恶意派对都不会产生$ \ nathcal {h} $ - 长度$ t $的序列$ t $ ting $ t $ aft $ t $ c $ aft $ t $ aft $ t $ aft $ t $ aft $ t $ aft $ t $ aft $ t $ copience $ t $ cobsibaliable。在本文中，我们证明，在顺序时间内运行的任何量子攻击者$ t-1 $都不会产生$ \ MATHCAL {H} $ - 序列 - 即使攻击者在每个回合中都提交了大量的量子查询，否则可能会产生$ \ MATHCAL {H} $序列。证明更具挑战性，并突出了Zhandry最近的压缩甲骨文技术的力量（Crypto 2019）。我们进一步扩展了这一结果，以建立通过将菲亚特·萨米尔转换应用于科恩和彼得扎克的有效建筑（Eurocrypt 2018）获得的非相互作用POSW的量子后安全性。
A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long $\mathcal{H}$-sequence and that any malicious party running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence of length $T$ except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence except with negligible probability -- even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry's recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak's efficient construction (EUROCRYPT 2018).
