hlouiso/blind_MSS

# 盲 XMSS（目标和 WOTS+）与 ZKBoo（MPC-in-the-Head） 本项目在 **XMSS**（一种有状态的 Merkle 签名方案）上实现了一种**盲签名**，其叶子节点使用**目标和 WOTS+** 一次性签名，并采用 **ZKBoo / MPC-in-the-head** 风格的 ZK 证明，以证明其知道有效签名**但不泄露**任何秘密材料（承诺开启值、叶子索引或签名本身）。 它是基于 ZKBoo 对通用哈希盲签名构造的具体实例化：包含一个承诺方案、一个基于哈希的签名方案和一个 NIZK。这里的承诺方案是 **基于 GF(2¹²⁸) 的 Halevi–Micali**，签名方案是目标和 WOTS+/XMSS，而 NIZK 则是 ZKBoo。 ## 背景 这项工作是在我在[波尔多大学](https://mastercsi.labri.fr/)攻读**密码学与计算机安全**硕士学位的最后实习期间完成的。实习于 2025 年上半年在[UPC（巴塞罗那）](https://www.upc.edu/ca)进行，由 [Javier Herranz Sotoca](https://web.mat.upc.edu/javier.herranz/) 指导。 ## 构建 依赖要求： - 一个支持 OpenMP 的 C 编译器（GCC/Clang） - OpenSSL **libcrypto** - `make` ``` make # build everything make clean # remove binaries and intermediates ``` 生成的可执行文件：`CLIENT_blinding_message`、`SIGNER_XMSS_keygen`、`SIGNER_XMSS_sign`、`CLIENT_blind_sign`、`VERIFIER_verify`。 ## 参数 签名方案（`xmss.h`），与 Longfellow/Binius64 实例化保持一致： - `XMSS_H = 10` — Merkle 树高度（每对密钥可产生 `2^10 = 1024` 个签名） - `XMSS_WOTS_W = 4` — Winternitz 参数（2位坐标） - `XMSS_WOTS_LEN = 72` — WOTS+ 链的数量（目标和编码，无校验和） - `XMSS_TARGET_SUM = 132` — 72 个坐标所需满足的总和 - `XMSS_NODE_BYTES = 16` — 每个内部节点是 SHA-256 输出截断至 128 位的结果 - `XMSS_PK_SEED_BYTES = 16`，`XMSS_NONCE_LEN = 6` - 所有哈希均使用 SHA-256，采用 SPHINCS+ 风格的密钥化/微调（微调 `0x00` 链，`0x01` 树/pk，`0x02` 消息）。 Halevi–Micali 承诺（`commitment.h`）： - `HM_NONCES = 6`，`HM_LINES = 2`，域 `GF(2¹²⁸)` — 与基于 Longfellow 的实例化布局相同。 - 开启值 `(r, a)` 为 `96 + 192 = 288` 字节；承诺 `com = a‖b‖y` 为 `256` 字节。 ZKBoo（`shared.c`）： - `NUM_ROUNDS = 137` 次并行执行（可靠性误差 `(2/3)^137`）；若要达到 `2^-128`，请将其提升至 `219`。 - `INPUT_LEN = 1610`，`ySize = 191448`（每个视图的非线性门转录字）。 ## 文件与格式 所有十六进制数据均为**大写**且不含空格。 - **`XMSS_secret_key.txt`**（`SIGNER_XMSS_keygen`） - 第 1 行：`sk_seed` — 32 字节（64 个十六进制字符） - 第 2 行：`pk_seed` — 16 字节（32 个十六进制字符） - 第 3 行：`leaf_index` — 十进制（初始值为 `0`） - **`XMSS_public_key.txt`**（`SIGNER_XMSS_keygen`） - 第 1 行：`pk_seed` — 16 字节（32 个十六进制字符） - 第 2 行：XMSS root — 16 字节（32 个十六进制字符） - **`blinding_key.txt`**（`CLIENT_blinding_message`） — 秘密开启值 `(r, a)` - 第 1 行：nonces `r₁‖…‖r₆` — 96 字节（192 个十六进制字符） - 第 2 行：行矩阵 `a`（行优先 `a_{0,0..5} ‖ a_{1,0..5}`） — 192 字节（384 个十六进制字符） - **`blinded_message.txt`**（`CLIENT_blinding_message`） - 承诺 `com = a ‖ b ‖ y` — 256 字节（512 个十六进制字符）。签名者由此派生 `d = SHA256(com)`。 - **`XMSS_signature.txt`**（`SIGNER_XMSS_sign`） - 第 1 行：`leaf_index` — 十进制 - 第 2 行：`nonce` — 6 字节（12 个十六进制字符） - 接下来 `72` 行：WOTS+ 链值 — 每行 16 字节（32 个十六进制字符） - 接下来 `10` 行：XMSS 认证路径 — 每行 16 字节（32 个十六进制字符） - **`signature_proof.bin`**（`CLIENT_blind_sign`） - 二进制 ZKBoo 证明，证明在被承诺的消息上存在有效的 XMSS 签名。 ## 典型工作流 1. **签名者**生成密钥：`./SIGNER_XMSS_keygen` → `XMSS_secret_key.txt`、`XMSS_public_key.txt`。 2. **客户端**盲化消息：`./CLIENT_blinding_message`（提示输入 `m`） → `blinding_key.txt`（秘密开启值 `(r, a)`），`blinded_message.txt`（承诺 `com = a‖b‖y`）。客户端将 `(r, a)` 保密，并将 `com` 发送给签名者。 3. **签名者**对承诺进行签名：`./SIGNER_XMSS_sign`（读取 `XMSS_secret_key.txt`、`blinded_message.txt`；派生 `d = SHA256(com)`，对 `d` 进行签名，并使用公钥进行自检） → `XMSS_signature.txt`，并推进叶子索引。 4. **客户端**生成证明：`./CLIENT_blind_sign`（提示输入 `m`；读取 `blinding_key.txt`、`XMSS_signature.txt`、`XMSS_public_key.txt`）。它首先重新检查 XMSS 签名对于 `d = SHA256(a‖b‖y)` 是否有效，然后将 ZK 证明写入 `signature_proof.bin`。 5. **验证者**进行验证：`./VERIFIER_verify`（提示输入 `m`；读取 `XMSS_public_key.txt`、`signature_proof.bin`）。 ## 性能 消息长度仅影响原生的 `m̂ = SHA256(m)`，因此证明/验证时间与 `|m|` 无关。 ### 产物大小 | 产物 | 大小 | |---|---:| | 公钥（`pk_seed ‖ root`） | $32$ B | | 私钥（`sk_seed ‖ pk_seed ‖ leaf_index`） | $52$ B | | 承诺 `com = a ‖ b ‖ y` | $256$ B | | 原始 XMSS 签名（`leaf ‖ nonce ‖ 72 chains ‖ 10 path`） | $1.29$ KB | | **盲签名（ZKBoo 证明）** | $\approx 168.5$ MB | ### 耗时 | 阶段 | 平均时间 | |---|---:| | 承诺计算 | $< 1$ ms | | 密钥生成 | $\approx 130$ ms | | 签名 | $\approx 130$ ms | | 证明生成 | $\approx 1.7$ s | | 证明验证 | $\approx 0.9$ s | 由于 ZKBoo 的固有特性，证明体积非常庞大：`NUM_ROUNDS` 轮中的每一轮 都会序列化一份完整的逐视图非线性门转录，因此 ``` proof ≈ NUM_ROUNDS · (ySize·4 + 2·INPUT_LEN + sizeof(a) + 128) = 219 · (765792 + 3220 + 192 + 128) ≈ 168.5 MB ``` ## 参考文献 - [ZKBoo：更快的布尔电路零知识证明 — ePrint 2016/163](https://eprint.iacr.org/2016/163) - [基于对称密钥原语的后量子零知识与签名 — ePrint 2017/279](https://eprint.iacr.org/2017/279.pdf) - [原始 ZKBoo 实现（奥胡斯大学）](https://github.com/Sobuno/ZKBoo) - [XMSS — RFC 8391](https://datatracker.ietf.org/doc/html/rfc8391)

标签：后量子密码学, 哈希签名, 客户端加密, 密码学, 手动系统调用, 盲签名, 零知识证明