标题： 关于一次性签名、量子与经典绑定以及置换的混淆 显示英文标题

标题： On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations

摘要： 单次签名（OSS）由Amos、Georgiou、Kiayias和Zhandry（STOC'20）定义。 这些签名允许仅对一条消息进行签名，之后签名密钥会自我销毁，防止任何第二条消息被签名。 虽然在经典情况下这种对象是不可能的，但Amos等人观察到，通过利用不可克隆原理，可以使用量子签名密钥实现OSS。 自那时起，OSS已成为一个重要的概念工具，在去中心化环境以及具有经典通信的量子密码学中有许多应用。 OSS还与后量子哈希和承诺中经典绑定和坍缩绑定之间的分离密切相关。 不幸的是，由于Amos等人提出的唯一已知的OSS构造仅在经典预言机模型中得到了验证，并且他们的验证最终被发现包含一个致命的错误。 因此，即使在经典理想化模型中OSS的存在性也一直未被解决。 我们给出了第一个标准模型下的OSS，假设（次指数）不可区分混淆（iO）和LWE具有可证明的安全性。 这也首次在标准模型下实现了经典绑定和坍缩绑定后量子承诺/哈希之间的分离，解决了十年来的一个开放问题。 在此过程中，我们还给出了第一个相对于经典预言机具有无条件安全性的构造。 为了实现我们的标准模型构造，我们开发了一种可交换伪随机置换（可交换PRPs）的概念，并展示了它们如何用于将涉及随机置换的预言机证明转换为基于混淆的证明。 特别是，混淆可交换PRPs可以得到一个陷阱门单向置换，即\emph{全域}，解决了另一个十年-old的问题，即从（次指数）iO和单向函数构造这个对象。 显示英文摘要

摘要： One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open. We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is \emph{full-domain}, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.