PPRF
Puncturable Pseudorandom Function（可穿刺伪随机函数，PPRF）是一种特殊的伪随机函数（PRF），它允许生成一个“穿刺密钥”，该密钥可以在除了指定点之外的所有点上评估PRF。
定义
- 主密钥与穿刺密钥：PPRF有一个主密钥 ( k )，可以用来在定义域的所有点上评估PRF。而通过主密钥 ( k ) 和某个特定点 ( x )，可以生成一个穿刺密钥 ( k_x )，使用 ( k_x ) 无法评估PRF在点 ( x ) 上的值。
- 算法：PPRF由三个算法组成：
- Setup（初始化）：输入安全参数，输出PRF的主密钥。
- Puncture（穿刺）：输入主密钥和一个点 ( x )，输出一个穿刺密钥 ( k_x )。
- Eval（评估）：输入穿刺密钥 ( k_x ) 和一个点 ( x' )，如果 ( x' x )，则输出PRF在 ( x' ) 上的值；如果 ( x' = x )，则输出一个特殊符号（如 ()），表示无法评估。
举例
假设有一个可穿刺伪随机函数(F)，它的主密钥为(k)，可用于评估(F_k(x))。若想撤销在(x=01001011)点评估(F)的能力，可以生成一个和(x)相关的穿刺密钥(k^)，使得(F_k(x) = F_{k^}(x), x)且(F_k(x) F_{k^}(x), x = 01001011)。此外，(k^)不会泄露关于(x=01001011)处的(F_k(x))的任何信息。
安全性
PPRF的安全性要求即使攻击者获得了穿刺密钥 ( k_x )，也无法从 ( k_x ) 中推断出PRF在点 ( x ) 上的值。此外，PPRF还需要满足适应性安全性（Adaptive Security），即攻击者可以在获得穿刺密钥后动态选择挑战点。
应用
PPRF在密码学中有多种应用，包括： - 前向保密（Forward Secrecy）：通过穿刺密钥可以撤销对某些点的访问能力，从而保护过去的信息。 - 密钥撤销（Key Revocation）：可以撤销对特定数据的访问权限。 - 混淆（Obfuscation）：用于隐藏某些特定点的函数值。
PPRF的研究和应用是密码学中的一个重要方向，它结合了伪随机性和密钥管理的灵活性。
MPCitH
RSD
Regular Syndrome Decoding（RSD，规则综合解码）是综合解码问题（Syndrome Decoding Problem，SDP）的一个变体。以下是关于它的详细介绍：
定义
- 给定一个线性码的校验矩阵 ( _2^{(n-k) n}) 和一个向量（综合）( _2^{n-k})，RSD问题要求找到一个向量 ( _2^n)，其汉明重量为 (w)，并且满足 ( = )，同时 () 是规则的。
- 规则向量 () 的定义是：它可以被划分为 (w) 个连续的、等大小的块，每个块的汉明重量恰好为1。
特点
- 结构化错误分布：与普通的综合解码问题相比，RSD问题中的错误向量 () 具有特定的结构，即规则分布。这种结构化使得RSD问题在某些情况下可能比普通SDP更容易解决，但在其他情况下也可能更难。
- 应用广泛：RSD问题在密码学中有着重要应用，例如在多方计算（MPC）、零知识证明（ZK）以及伪随机相关生成器（PCG）等场景中。
研究进展
- 攻击方法：近年来，针对RSD问题的攻击方法不断涌现。例如，有研究提出了基于Gröbner基的攻击方法，还有研究通过改进信息集解码（ISD）技术来攻击RSD问题。
- 复杂度分析：对于RSD问题的复杂度，研究者们进行了深入分析。例如，某些特定参数下的RSD实例可以在多项式时间内解决，而另一些参数则会导致特别难解的实例。
与SDP的关系
- RSD问题是SDP的一个特殊变体，其主要区别在于错误向量的结构化要求。这种结构化可能会对问题的难度产生影响，但具体影响因参数而异。
总之，Regular Syndrome Decoding是一个具有特定结构的综合解码问题，它在密码学中具有重要应用，并且其安全性仍在不断研究中。
OMUF
OMUF 是密码学中的一个术语，通常指 One-More UnForgeability（一次性多不可伪造性）。这一概念主要用于描述某些签名方案或认证协议在面临多次挑战时的安全性，尤其是在攻击者能够进行多次查询的情况下，系统仍能保持不可伪造性。以下是详细解析：
1. OMUF 的核心定义
- 基本场景：攻击者（Adversary）可向签名预言机（Signing Oracle）发起多次签名请求，目标是伪造至少一个未被查询过的消息的合法签名。
- 安全性要求：即使攻击者获取了 ( n ) 个消息的签名，也无法生成第 ( n+1 ) 个有效签名。
- 类比模型：类似于“One-More 假设”（如 RSA 的 One-More 困难问题），要求攻击者必须付出与挑战次数成比例的计算资源。
2. 应用领域
- 数字签名方案：
例如，Schnorr 签名、BLS 签名等需证明在 OMUF 模型下安全，确保攻击者无法通过多次查询获得伪造能力。 - 盲签名协议：
在电子投票或匿名支付中，用户需对消息盲化后请求签名，OMUF 保证即使多次交互，签名者也无法伪造额外签名。 - 抗量子算法设计：
后量子签名方案（如基于哈希的签名）常需满足 OMUF 以抵御量子计算攻击。
3. 与其他安全模型的对比
| 安全模型 | 缩写 | 关键区别 |
|---|---|---|
| 选择性不可伪造性 | SUF | 攻击者需提前声明挑战消息 |
| 适应性不可伪造性 | EUF-CMA | 攻击者可自适应选择查询消息 |
| 一次性多不可伪造性 | OMUF | 攻击者在多次查询后仍需伪造额外签名 |
- OMUF 更强：相比 EUF-CMA（Existential Unforgeability under Chosen Message Attacks），OMUF 要求即使攻击者已获取多个签名，仍无法伪造新的签名，适用于动态多用户环境。
4. 典型构造与证明技术
- 基于零知识证明：
如 Fiat-Shamir 变换可将交互式协议转为非交互式，同时满足 OMUF（例如 Schnorr 签名）。 - 树形结构扩展：
在哈希树（Merkle Tree）中绑定多个签名状态，确保每次签名需“消耗”一个叶子节点，防止重放攻击。 - 随机预言机模型（ROM）：
多数 OMUF 证明依赖 ROM 假设，将哈希函数视为理想随机函数。
5. 实际攻击案例与防护
- 重放攻击：
若签名方案不满足 OMUF，攻击者可重复使用旧签名伪造新消息。
防护：添加时间戳或唯一 nonce。 - 密钥泄露：
前向安全（Forward Security）可增强 OMUF，即使长期密钥泄漏，历史签名仍安全。
实现：基于树状密钥演化（如 XMSS 签名）。
6. 总结
OMUF 是衡量密码协议在多次挑战下安全性的重要指标，尤其在多用户、高交互场景（如区块链或物联网）中至关重要。设计满足 OMUF 的方案需结合零知识证明、前向安全等技术，并在随机预言机或标准模型下严格证明其安全性。