无导电性高效可测试电路解析

# 无导电性高效可测试电路解析 在数字电路的设计与测试领域，如何构建高效可测试的电路一直是研究的重点。本文将深入探讨一种无导电性高效可测试电路的相关构建与特性。 ## 1. 单层压缩的构建 ### 1.1 Sm,d 压缩小工具 Gn,λ,d 小工具由 λ 层组成，每层定义为子小工具 Sm,d（参数 m 可变）。单层压缩小工具 Sm,d 能将 m 位输入压缩为 $\frac{m}{d}$ 位输出，测试过程中还需 d 条额外输入线，这些线的值为均匀随机位。为便于分析，通常让 m 是 d 的倍数，若不是则可添加 $m - \lfloor \frac{m}{d} \rfloor$ 条设为 0 的备用输入线到 Sm,d 单层小工具中。有时在上下文 m 明确时，也将 Sm,d 简记为 Sd。 Sm,d 接收 m + d 条线作为输入，其中 d 条是由均匀随机位组成的额外输入，输出 $\frac{m}{d}$ 条线。其工作过程如下： 1. 将输入序列（如 $z_1, z_2, \cdots, z_m$）划分为 $\frac{m}{d}$ 个长度为 d 的块：$(z_1, \cdots, z_d), (z_{d + 1}, \cdots, z_{2d}), \cdots, (z_{(\frac{m}{d} - 1)d + 1}, \cdots, z_{(\frac{m}{d} - 1)d + d})$。 2. 利用 d 位额外输入序列 $r_1, \cdots, r_d$，输出每个长度为 d 的 z 块与额外序列的内积值。更正式地，对于给定输入线 $(z_1, \cdots, z_m)$ 和额外输入线 $(r_1, \cdots, r_d)$，Sm,d 输出 $\frac{m}{d}$ 位： $Sm,d ((z_i)_{i = 1, \cdots, m}, (r_i)_{i = 1, \cdots, d}) = \left( \sum_{j = 1, \cdots, d} z_{id + j} \cdot r_j \right)_{i = 0, \cdots, \frac{m}{d} - 1}$ ### 1.2 构建模块 Sm,d 的构建需要两种类型的小工具： - **复制树（△m′）**：以单条线为输入，输出 m′ 条线，在未被篡改的计算中，这些输出线是输入线的副本。它通过一个有 m′ 个叶子节点的完全二叉树实现，根节点为输入，叶子节点为输出，所有内部节点都是 COPY 门，计算方向从根到叶子。 - **异或树（▷d）**：接收 d 条线作为输入，输出 1 条线，在未被篡改的电路中，该输出是所有输入的异或。它通过一个有 d 个叶子节点的完全二叉树实现，叶子节点为输入，根节点为输出，所有节点都是 XOR 门，计算方向从叶子到根。 ### 1.3 Sm,d 的特性 对于具有 m 条输入线和 d 条用于随机性的额外输入线的 Sm,d 小工具，有以下特性： |特性|描述| | ---- | ---- | |输出线数量|$\frac{m}{d}$| |深度|小于 $\log \frac{m}{d} + \log d + 1 = \log m + 1$| |总门数|小于 $d \cdot \frac{m}{d} + n + \frac{m}{d} \cdot d = 3m$（复制树中的门数、乘法门数和异或树中的门数之和）| ## 2. 层的组合 Gn,λ,d 的完整构建是通过简单添加 λ 层 Sm,d 小工具实现的，每层的参数 m 会根据层的不同而变化。第一层 S 接收小工具 G 的输入线作为输入，后续层接收前一层的输出作为输入，依次类推。每层都会将输出线的数量减少 d 倍，且每层都会得到 d 条额外输入线，这些线的值为均匀随机位。 ### 2.1 Gn,λ,d 的特性 若 Gn,λ,d 接收长度为 $n = m \cdot d^{\lambda}$ 的序列作为输入进行压缩，则有以下特性： |特性|描述| | ---- | ---- | |输出位数|m| |所需辅助随机位数|$\lambda \cdot d$| |深度|有界于 $\lambda \cdot (\log n + 1)$| |总门数|不大于 $\sum_{i = 0}^{\lambda - 1} 3 \frac{n}{d^i} = 3n \frac{d - d^{1 - \lambda}}{d - 1}$| ### 2.2 直觉理解 在命题 3 中表明，任何非平凡的篡改都会导致标准输出线出现错误或辅助输出线（即压缩小工具 G 的输入线）出现信息丢失。这里重点关注第二种情况，若对应值 $z_i$ 的输入线出现错误（由信息丢失暗示），有望它能在 λ 层 Sd 中留存，因为该特定线上的值有时会改变相应内积的值，有时则不会，且这仅取决于某些 $r_j$ 的值。 ## 3. 信息丢失元组 ### 3.1 引入原因 在计算中，输入值和篡改可能会被对手以某种方式选择，使得单个计算错误消失。例如，Gn,λ,d 中的一条线在未被篡改的测试输入评估中几乎总是被评估为 0，对手篡改后将其值翻转为 1，然后可能通过另一个常量篡改来撤销该错误评估。因此，我们关注信息丢失，即确保某条线在两次评估中分别为 0 和 1，且其中一次评估出现错误。 ### 3.2 定义 引入信息丢失元组的概念，将信息丢失的概念与整个电路的评估过程分离。设 $X_i$ 表示电路 C 中 n 条线的诚实评估，$Y_i$ 表示相同线的篡改评估。若存在 $i, j, k$ 使得 $(X_i[k] \neq X_j[k]) \land (Y_i[k] = Y_j[k])$，则称 $(X_1, \cdots, X_m; Y_1, \cdots, Y_m)$（一个 $Z_2$ 上的 n 元向量元组）为信息丢失元组，三元组 $(i, j, k)$ 称为该元组的信息丢失见证。 ## 4. 线上的代数值 ### 4.1 代数表示 在篡改实现的 Gn,λ,d 中，电路的线不仅携带 $Z_2$ 中的元素，还携带 $Z_2$ 上的多元多项式环中的元素。该环的不定元与电路的输入线相关联，用小写字母表示，有时也会使用辅助不定元。计算 val 函数的结果时，只需将 G 中的函数外推到该环。从现在起，提及线上的值时，允许其为环中的元素。 ### 4.2 篡改对值的影响 - **复制树（△）**：设 △τ 以 r 为输入，r′ 为其任意输出，则 $r′ \in \{0, 1, r, r + 1\}$。复制树的每个输出要么是常量、被翻转，要么是其单条输入线的原始值，这取决于从复制树的根到输出线的路径上的翻转或常量篡改的数量。 - **异或树（▷）**：设 $a_1, \cdots, a_d$ 是 ▷τ 的输入值，p 是其输出，则 $p = \beta + \sum_{i = 1, \cdots, d} \alpha_i a_i$，其中 $\alpha_i, \beta \in \{0, 1\}$。异或树的单个输出是其输入的线性组合，若从某个输入线到输出线的路径上存在常量篡改，则该输入值 $a_i$ 的系数 $\alpha_i$ 设为 0，系数 $\beta$ 取决于翻转篡改的数量和常量篡改的值。 - **乘法门**：设 $(z_i, r_i)$ 是 Sτ 中某个乘法门的一对输入线，multi 表示该乘法门的输出值，则 $multi = \alpha_i(z_i) r_i + \beta_i(z_i)$，其中 $\alpha_i, \beta_i$ 是 $Z_2$ 上的线性函数。对于固定的 τ，乘法门的输出值 $m_i$ 可描述为 $r_i$ 的线性函数。 - **单层压缩小工具**：设 $p_m$ 是 Sτd 构建中 ▷τ 小工具的输出值，该小工具以 $z_{md + 1}, z_{md + 2}, \cdots, z_{md + d}, r_1, r_2, \cdots, r_d$ 为输入，则 $p_m = \beta(z_{md + 1}, \cdots, z_{md + d}) +