FFS（Feige-Fiat-Shamir）身份鉴别方案
证明者（Prover）可以向验证者（Verifier）证明自己拥有某个秘密，而无需透露该秘密的任何信息。它基于大整数分解的数学难题来保证安全性。
简化版FFS方案
单次交互有50%的概率被攻击者欺骗
1. 初始化阶段：生成密钥
- 选择模数：证明者选择一个模数 $ n $，它是两个大素数的乘积。
- 生成秘密：随机选择一个秘密数字 $ s $，它与 $ n $ 互质。
- 计算公钥：计算 $ v = s^{-2} \mod n $（即 $ s^2 $ 的模逆元）。
- 公布密钥：公钥为 $ (n, v) $，私钥为 $ s $ 需妥善保管。
2. 交互阶段：证明身份
证明者（Alice）向验证者（Bob）证明自己拥有私钥 $ s $：
- 承诺 (Commitment)：Alice 随机选取一个数 $ r $，计算承诺值 $ x = r^2 \mod n $，并将 $ x $ 发送给 Bob。
- 挑战 (Challenge)：Bob 随机生成一个挑战位 $ e \in {0, 1} $，发送给 Alice。
- 响应 (Response)：Alice 根据挑战计算响应值 $ y $：
- 若 $ e = 0 $，则 $ y = r $。
- 若 $ e = 1 $，则 $ y = r \cdot s \mod n $。
- 验证 (Verification)：Bob 收到 $ y $ 后，验证等式 $ y^2 \equiv x \cdot v^e \pmod{n} $ 是否成立：
- 若 $ e=0 $：验证 $ y^2 \equiv r^2 \equiv x \pmod{n} $，成立。
- 若 $ e=1 $：验证 $ y^2 \equiv (r \cdot s)^2 \equiv r^2 \cdot s^2 \equiv x \cdot v^{-1} \pmod{n} $。由于 $ v = s^{-2} $，所以 $ x \cdot v^{-1} \equiv x \cdot s^2 $，验证通过。
若等式成立，Bob 相信 Alice 知道 $ s $，但无法从中获取 $ s $ 的任何信息。
3. 安全性分析
单次验证，攻击者有50%的概率猜对挑战 $ e $ 并伪造响应。为了降低风险，通常会将协议重复执行 $ t $ 次，将欺骗概率降至 $ (1/2)^t $
完整版FFS方案
- 密钥生成：证明者选择一个Blum整数 $ n = p \cdot q $。然后选择 $ k $ 个随机数 $ s_1, s_2, ..., s_k $ 和 $ k $ 个随机比特 $ c_1, c_2, ..., c_k $，计算 $ v_i = (-1)^{c_i} \cdot s_i^{-2} \mod n $。公钥为 $ (n, v_1, ..., v_k) $，私钥为 $ (s_1, ..., s_k) $。
- Alice选择一个随机数 $ r $ 计算 $ x = r^2 \mod n $，发送给 Bob。
- 发送所有挑战：Bob 为每一轮生成一个挑战向量 $ (b_{1}, ..., b_{k}) $，其中每个 $ b_{j} $ 是随机比特，然后一次性发送给 Alice。
- 发送所有响应：Alice 计算响应 $ y = r \cdot \prod_{j=1}^{k} s_j^{b_{j}} \mod n $，并一次性发送给 Bob。
- 批量验证：Bob 验证等式 $ x \equiv y^2 \cdot \prod_{j=1}^{k} v_j^{b_{j}} \pmod{n} $ 是否成立。全部通过，则验证成功。