不可克隆聚合物及其密码学应用：(1,n)-时间程序的探索

### 不可克隆聚合物及其密码学应用：(1, n)-时间程序的探索 在密码学领域，保障信息安全和程序执行的可控性是至关重要的研究方向。本文将深入探讨(1, n)-时间程序这一创新的密码学应用，它借助消耗性令牌实现了对程序执行次数的有效限制，为软件保护和功能加密等领域带来了新的解决方案。 #### 1. 理论基础与(1, n)-时间程序概述 在特定条件下，存在一个重要的定理。对于 0 ≤γ ≤1，如果 f1, ..., fu 如前文所定义，那么协议 2 能够在 FCT -混合模型中，针对点函数族 I = {Ip,m|p ∈ P, m ∈ M} 安全地实现 FBP O，其中 nq = n 且 u 足够大。这里的 κ 包含了数字和生物安全参数，而敌手 A 具备执行计算算法和物理过程的能力，模拟器同样如此。该定理中的模拟器是计算型的，但依赖于 FCT，其模拟器涉及物理过程。通用组合（UC）安全的使用使得我们能够在具体和渐近意义上，获得针对所有物理/数字组合攻击的整体安全保证。 (1, n)-时间程序是消耗性令牌的一种新的密码学应用。对于这类程序，完整性要求诚实方最多只能运行一次程序，而可靠性则规定敌手最多能运行该程序 n 次。这一概念可以进一步推广，在保证诚实方和敌手能力差距的前提下，允许进行多次诚实查询。 #### 2. 动机与现有方案分析 一次（或 k 次）程序允许隐藏程序并将执行次数限制为一次（或 k 次）。它们可用于保护专有软件，支持密码学能力的临时转移。此外，k 次程序还能对可学习函数进行混淆，即那些可以通过多项式数量的查询来学习的函数。通过将 k 设为一个小常数，敌手可能无法学习该函数，从而使对这类函数的混淆变得有意义。 以往的研究提出了多种构建一次程序的方案。Goldwasser 等人将乱码电路与一次性存储设备相结合；Goyal 等人使用有状态的硬件令牌来增强安全性；Bellare 等人则提供了一个编译器，将任何程序编译成自适应安全的一次性版本。然而，这些方案大多假设存在防篡改硬件令牌，但缺乏具体的实现。Dziembowski 等人用一次性伪随机函数（PRF）取代了一次性存储设备，但他们的方案存在物理限制，实际实现的可行性存疑。Goyal 等人依靠区块链和见证加密避免了硬件令牌的使用，但将乱码电路存储在区块链上的做法并不实际。 我们研究消耗性令牌在构建有界执行程序中的适用性。鉴于这些令牌的有界查询能力，以及我们是实际构建这些令牌而非假设其存在，这是一个自然的研究方向。不过，诚实方和敌手之间的能力差距促使我们考虑(1, n)-时间程序这一稍作不同的概念。因此，像数字货币这类要求敌手只能在一个输入上执行的应用，无法使用(1, n)-时间程序实现；但允许 n 次敌手查询的应用，如混淆可学习函数，则可以采用我们的方案。 #### 3. 理想功能定义 我们定义了一个用于有界查询封装的理想功能 FBE。该功能与之前的 FBP O 类似，不同之处在于 FBE 隐藏的是任意电路，而不是点函数。诚实接收方可以对一个输入评估该电路，而敌手最多可以对 nq 个输入进行评估。 同时，任何实现 FBE 的有界查询混淆方案都需要满足效率属性。具体来说，存在一个多项式 p，对于所有 κ ∈ N，所有 C ∈ Cκ，以及所有输入 x ∈ {0, 1}∗，如果计算 C(x) 需要 t 个计算时间步骤，那么命令 (Evaluate, ·, x) 需要 p(t, κ) 个技术上可实现的时间步骤。 #### 4. 构建过程与安全分析 为了便于阐述，我们逐步介绍构建过程。首先是使用虚拟黑盒（VBB）混淆的初步尝试。 ##### 4.1 首次尝试：使用 VBB 在这个初始阶段，我们的目标是奠定构建的基本思路，而非追求效率优化。我们使用两个表 Tab1 和 Tab2。Tab1 将程序的输入空间 X 映射到令牌消息空间 M，该表是秘密的，将成为隐藏程序的一部分。Tab2 将 X 映射到令牌密钥空间 K，并且是公开的。 我们用 Prog 表示封装了目标电路或函数 f 的程序，我们希望将其转换为(1, n)-时间程序。Prog 由表 Tab : X → M、秘密密钥 sk 和 f 参数化，它有两条路径：陷门路径和常规路径。当检测到输入 m 中的隐藏触发条件时，陷门路径被激活，该输入可能包含程序输