33、可证明安全的后量子签名方案解析

可证明安全的后量子签名方案解析

在当今数字化时代，签名方案的安全性至关重要，尤其是在量子计算逐渐发展的背景下，后量子签名方案的研究变得尤为关键。本文将详细介绍一种基于多项式同构（Isomorphism of Polynomials）的可证明安全的后量子签名方案，包括其基本原理、构造过程以及安全性证明。

量子随机预言机与引理

在量子计算的背景下，量子随机预言机是一个重要的概念。对于量子随机预言机 $O$，可以以 $\sum \alpha_x|x\rangle$ 的形式进行查询，并得到 $\sum \alpha_x|H(x)\rangle$ 作为答案。这里有一个重要的引理：
- 引理 2 ：设 $A$ 是一个可以访问预言机 $O$ 的量子算法，$|\phi\rangle = \sum_{x\in{0,1}^n} \alpha_x|x\rangle$ 是对 $O$ 的一个查询，且存在 $x \in {0, 1}^n$ 使得 $|\alpha_x|^2 \leq \epsilon$。如果将 $O$ 修改为预言机 $O’$，使得对查询 $|\phi\rangle$ 的答案被修改为对应于对 $|x\rangle$ 的预言机答案的量子态独立采样，那么从 $O$ 和 $O’$ 得到的答案测量结果之间的统计距离至多为 $4\sqrt{\epsilon}$。

基于 IP2S 的签名方案构造

该签名方案基于 Santoso 提出的并行版本的身份识别方案，并通过 Fiat - Shamir 变换转化为签名方案。

基本身份识别方案

• 参数设置与密钥生成