在本篇文章中将梳理 [ZCF23] 论文中给出的 IOPP soundness 证明思路，其与 [BKS18] 中关于 FRI 协议的 soundness 证明类似。其中用到了二叉树的方式来分析 Prover 可能作弊的点，这个思想也在 [BGKS20] DEEP-FRI 协议的 soundness 证明中出现过。
IOPP 协议 ¶ 在前面第 2 篇文章中已经详细介绍了 IOPP 协议，为了后文的分析，这里简单罗列下 IOPP 协议，它是 FRI 协议的一个扩展，在理解协议的过程中，完全可以带入 FRI 协议，commit 阶段和 query 阶段都是一致的。
协议 1 [ZCF23, Protocol 2] IOPP.commit
输入 oracle：π d ∈ F n d \pi_d \in \mathbb{F}^{n_d} π d ∈ F n d ( π d − 1 , … , π 0 ) ∈ F n d − 1 × ⋯ × F n 0 (\pi_{d-1}, \ldots, \pi_0) \in \mathbb{F}^{n_{d-1}} \times \cdots \times \mathbb{F}^{n_0} ( π d − 1 , … , π 0 ) ∈ F n d − 1 × ⋯ × F n 0
对于 i i i d − 1 d-1 d − 1 Verifier 从 F \mathbb{F} F α i ← $ F \alpha_i \leftarrow \$ \mathbb{F} α i ← $ F 对于每一个索引 j ∈ [ 1 , n i ] j \in [1, n_i] j ∈ [ 1 , n i ] f ( X ) : = i n t e r p o l a t e ( ( d i a g ( T i ) [ j ] , π i + 1 [ j ] ) , ( d i a g ( T i ′ ) [ j ] , π i + 1 [ j + n i ] ) ) f(X) := \mathrm{interpolate}((\mathrm{diag}(T_i)[j], \pi_{i+1}[j]), (\mathrm{diag}(T'_i)[j], \pi_{i+1}[j+n_i])) f ( X ) := interpolate (( diag ( T i ) [ j ] , π i + 1 [ j ]) , ( diag ( T i ′ ) [ j ] , π i + 1 [ j + n i ])) π i [ j ] = f ( α i ) \pi_i[j] = f(\alpha_i) π i [ j ] = f ( α i ) Prover 输出 oracle π i ∈ F n i \pi_i \in \mathbb{F}^{n_i} π i ∈ F n i 协议 2 [ZCF23, Protocol 3] IOPP.query
输入 oracles：( π d − 1 , … , π 0 ) ∈ F n d − 1 × … × F n 0 (\pi_{d-1}, \ldots, \pi_0) \in \mathbb{F}^{n_{d-1}} \times \ldots \times \mathbb{F}^{n_0} ( π d − 1 , … , π 0 ) ∈ F n d − 1 × … × F n 0
Verifier 采样 μ ← $ [ 1 , n d − 1 ] \mu \leftarrow \$ [1, n_{d-1}] μ ← $ [ 1 , n d − 1 ] 对于 i i i d − 1 d-1 d − 1 查询 oracle π i + 1 [ μ ] , π i + 1 [ μ + n i ] \pi_{i+1}[\mu], \pi_{i+1}[\mu + n_i] π i + 1 [ μ ] , π i + 1 [ μ + n i ] 计算 p ( X ) : = i n t e r p o l a t e ( ( d i a g ( T i ) [ μ ] , π i + 1 [ μ ] ) , ( d i a g ( T i ′ ) [ μ ] , π i + 1 [ μ + n i ] ) ) p(X) := \mathrm{interpolate}((\mathrm{diag}(T_i)[\mu], \pi_{i+1}[\mu]), (\mathrm{diag}(T'_i)[\mu], \pi_{i+1}[\mu + n_i])) p ( X ) := interpolate (( diag ( T i ) [ μ ] , π i + 1 [ μ ]) , ( diag ( T i ′ ) [ μ ] , π i + 1 [ μ + n i ])) 检查 p ( α i ) = π i [ μ ] p(\alpha_i) = \pi_i[\mu] p ( α i ) = π i [ μ ] 如果 i > 0 i > 0 i > 0 μ > n i − 1 \mu > n_i - 1 μ > n i − 1 μ ← μ − n i − 1 \mu \leftarrow \mu - n_{i - 1} μ ← μ − n i − 1 如果 π 0 \pi_0 π 0 G 0 \mathbf{G}_0 G 0 accept，否则输出 reject。 分析思路 ¶ IOPP soundness 分析的就是对于任意的一个 Prover，其可能会作弊，在这种情况下，Verifier 输出 accept 的概率最多是多少，我们希望这个概率足够的小，这样这个协议才比较安全。当然这个概率肯定和协议中的一些参数相关，在实际中，我们希望其达到一个提前给定的安全参数 λ （例如取 λ 为 128 或 256 ），意思是这个概率要小于 2 − λ 2^{-\lambda} 2 − λ
我们现在来看看 IOPP 协议中对于作弊的 Prover ，有哪些地方可以钻漏洞使得 Verifier 输出 accept 。我们注意到，有两个地方 Verifier 引入了随机数。
在 IOPP.commit 阶段，协议第 1 步，Verifier 会从 F \mathbb{F} F α i \alpha_{i} α i π i + 1 \pi_{i+1} π i + 1 π i \pi_{i} π i 在 IOPP.query 阶段，协议的第 1 步，Verifier 就会从 [ 1 , n d − 1 ] [1, n_{d-1}] [ 1 , n d − 1 ] 假设初始作弊的 Prover 给出的 π d \pi_{d} π d C d C_{d} C d π 0 \pi_{0} π 0 C 0 C_0 C 0
Prover 非常幸运，Verifier 选取的随机数 α i \alpha_{i} α i π i + 1 \pi_{i+1} π i + 1 π i \pi_{i} π i C i C_{i} C i accept 。为什么说对于这种情况 Prover 非常幸运呢？因为这是 Proximity Gaps 告诉我们的结论，意思是说发生这种情况的概率非常非常的小（假设该概率为 ε ），小到发生这种情况就相当于 Prover 中了彩票。
Prover 没有情况 1 所说的那么幸运了，这时用随机数折叠之后的消息 π i \pi_{i} π i μ ← $ [ 1 , n d − 1 ] \mu \leftarrow \$ [1,n_{d-1}] μ ← $ [ 1 , n d − 1 ] π i \pi_{i} π i a a a δ 0 \delta_{0} δ 0 Δ ( a , C ) > δ \Delta(a, C) > \delta Δ ( a , C ) > δ a [ i ] a[i] a [ i ] c [ i ] c[i] c [ i ]
由于 Δ ( a , C ) > δ \Delta(a, C) > \delta Δ ( a , C ) > δ a a a
如果 Verifier 查询 l l l ( 1 − δ ) l (1 - \delta)^{l} ( 1 − δ ) l
综合上述两种情况，Prover 作弊成功的概率不超过
ϵ + ( 1 − δ ) l (1) \epsilon + (1 - \delta)^{l} \tag{1} ϵ + ( 1 − δ ) l ( 1 ) 这是一个整体分析的思路，具体的表达式与 ( 1 ) (1) ( 1 )
IOPP Soundness 定理 ¶ 定理 1 [ZCF23, Theorem3] (可折叠的线性编码的 IOPP Soundness) 令 C d C_d C d ( c , k 0 , d ) (c, k_0, d) ( c , k 0 , d ) ( G 0 , … , G d ) (G_0, \ldots, G_d) ( G 0 , … , G d ) C i C_i C i 0 ≤ i < d 0 \le i < d 0 ≤ i < d G i G_i G i i ∈ [ 0 , d − 1 ] i \in [0, d-1] i ∈ [ 0 , d − 1 ] Δ C i ≥ Δ C i + 1 \Delta C_i \ge \Delta C_{i+1} Δ C i ≥ Δ C i + 1 γ > 0 \gamma > 0 γ > 0 δ : = min ( Δ ∗ ( π d , C d ) , J γ ( J γ ( Δ C d ) ) ) \delta := \min(\Delta^*(\pi_d, C_d), J_{\gamma}(J_{\gamma}(\Delta_{C_d}))) δ := min ( Δ ∗ ( π d , C d ) , J γ ( J γ ( Δ C d ))) Δ ∗ ( π d , C d ) \Delta^*(\pi_d, C_d) Δ ∗ ( π d , C d ) v \mathbf{v} v C d C_d C d π d − 1 , … , π 0 \pi_{d-1}, \ldots, \pi_0 π d − 1 , … , π 0 ℓ \ell ℓ accept 的概率至多为 ( 1 − δ + γ d ) ℓ (1 - \delta + \gamma d)^{\ell} ( 1 − δ + γ d ) ℓ
定理中提到的出现的 J γ ( J γ ( Δ C d ) ) J_{\gamma}(J_{\gamma}(\Delta_{C_d})) J γ ( J γ ( Δ C d ))
定义 1 [ZCF23, Definition 4] (Johnson Bound) 对于任意的 γ ∈ ( 0 , 1 ] \gamma \in (0,1] γ ∈ ( 0 , 1 ] J γ : [ 0 , 1 ] → [ 0 , 1 ] J_{\gamma}: [0,1] \rightarrow [0,1] J γ : [ 0 , 1 ] → [ 0 , 1 ]
J γ ( λ ) : = 1 − 1 − λ ( 1 − γ ) . J_{\gamma}(\lambda) := 1 - \sqrt{1 - \lambda(1 - \gamma)} . J γ ( λ ) := 1 − 1 − λ ( 1 − γ ) . 相对陪集最小距离(relative coset minimum distance) 的定义如下。
定义 2 [ZCF23, Definition 5] (Relative Coset Minimum Distance) 令 n n n C C C [ n , k , d ] [n,k,d] [ n , k , d ] v ∈ F n \mathbf{v} \in \mathbb{F}^{n} v ∈ F n c ∈ C c \in C c ∈ C v \mathbf{v} v c c c Δ ∗ ( v , c ) \Delta^*(\mathbf{v},c) Δ ∗ ( v , c )
Δ ∗ ( v , c ) = 2 ∣ { j ∈ [ 1 , n / 2 ] : v [ j ] ≠ c [ j ] ∨ v [ j + n / 2 ] ≠ c [ j + n / 2 ] } ∣ n . \Delta^*(\mathbf{v},c) = \frac{2 |\{ j \in [1, n/2]: \mathbf{v}[j] \neq c[j] \vee \mathbf{v}[j + n/2] \neq c[j + n/2] \} |}{n}. Δ ∗ ( v , c ) = n 2∣ { j ∈ [ 1 , n /2 ] : v [ j ] = c [ j ] ∨ v [ j + n /2 ] = c [ j + n /2 ]} ∣ . 这个定义和 [BBHR18] 中证明 soundness 用到的 Block-wise 距离定义([BBHR18, Definition 3.2])是类似的，它是相对最小 Hamming 距离的一个替代版本。将 { j , j + n / 2 } \{j,j+n/2\} { j , j + n /2 } { j , j + n / 2 } \{j,j+n/2\} { j , j + n /2 } n = 8 n = 8 n = 8 ω 8 = 1 \omega^8 = 1 ω 8 = 1 x ↦ x 2 x \mapsto x^2 x ↦ x 2 { 1 , 5 } \{1,5\} { 1 , 5 } { 2 , 6 } \{2,6\} { 2 , 6 } { 3 , 7 } \{3,7\} { 3 , 7 } { 4 , 8 } \{4,8\} { 4 , 8 }
Δ ∗ ( v , c ) \Delta^*(\mathbf{v},c) Δ ∗ ( v , c ) v \mathbf{v} v c c c
令 Δ ∗ ( v , C ) : = min c ∈ C Δ ∗ ( v , c ) \Delta^*(\mathbf{v},C) := \min_{c \in C}\Delta^*(\mathbf{v},c) Δ ∗ ( v , C ) := min c ∈ C Δ ∗ ( v , c ) Δ ( v , C ) ≤ Δ ∗ ( v , C ) \Delta(\mathbf{v},C) \le \Delta^*(\mathbf{v},C) Δ ( v , C ) ≤ Δ ∗ ( v , C )
尽管多了这些不同的定义和 Johnson 函数，但是 IOPP Soundness 的证明思路与前面说的分析思路还是一致的，分两种情况讨论。我们的目的是分析作弊的 Prover 最后能够通过 Verifier 的检查，最终输出 accept 的概率。证明的思路是：
情况 1 : Prover 非常幸运，由于 Verifer 选取随机数 α i \alpha_i α i i ∈ [ 0 , d − 1 ] i \in [0, d-1] i ∈ [ 0 , d − 1 ]
Δ ( f o l d α i ( π i + 1 ) , C i ) ≤ min ( Δ ∗ ( π i + 1 , C i + 1 ) , J γ ( J γ ( Δ C d ) ) ) − γ \Delta(\mathrm{fold}_{\alpha_i}(\pi_{i+1}), C_i) \le \min(\Delta^*(\pi_{i+1}, C_{i+1}), J_{\gamma}(J_{\gamma}(\Delta_{C_d}))) - \gamma Δ ( fold α i ( π i + 1 ) , C i ) ≤ min ( Δ ∗ ( π i + 1 , C i + 1 ) , J γ ( J γ ( Δ C d ))) − γ 用反证法通过 Correlated Agreement 定理（其能推导出对应的 Proximity Gaps 定理）可以证明发生“坏”的事件的概率是比较小的，证明得到其概率最多为 2 d γ 3 ∣ F ∣ \frac{2d}{\gamma^3 |\mathbb{F}|} γ 3 ∣ F ∣ 2 d
情况 2 : 假设 Prover 没有那么幸运了，也就是情况 1 中的“坏”的事件没有发生，那么Verifier 在 IOPP.query 阶段会选取 μ ← $ [ 1 , n d − 1 ] \mu \leftarrow \$ [1, n_{d-1}] μ ← $ [ 1 , n d − 1 ] l l l ( 1 − δ + γ d ) l (1 - \delta + \gamma d)^{l} ( 1 − δ + γ d ) l
综合 1 和 2 就得到了对于可折叠的线性编码(Foladable Linear Codes)的 IOPP Soundness ，至少为
s − ( δ ) = 1 − ( 2 d γ 3 ∣ F ∣ + ( 1 − δ + γ d ) l ) . \mathbf{s}^-(\delta) = 1 - \left(\frac{2d}{\gamma^3 |\mathbb{F}|} + \left(1 - \delta + \gamma d \right)^l \right) . s − ( δ ) = 1 − ( γ 3 ∣ F ∣ 2 d + ( 1 − δ + γ d ) l ) . 也就证得了定理 1 。
情况 1 的证明 ¶ 下面的推论 1 证明了对于某一次 i i i C i C_i C i B ( i ) B^{(i)} B ( i ) 2 γ 3 ∣ F ∣ \frac{2}{\gamma^3 |\mathbb{F}|} γ 3 ∣ F ∣ 2 B i B_i B i B i B_i B i
Pr [ ⋃ i = 0 d − 1 B ( i ) ] ≤ ∑ i = 0 d − 1 Pr [ B ( i ) ] ≤ 2 d γ 3 ∣ F ∣ . \Pr\left[\bigcup_{i = 0}^{d-1} B^{(i)} \right] \le \sum_{i = 0}^{d-1} \Pr[B^{(i)}] \le \frac{2d}{\gamma^3 |\mathbb{F}|}. Pr [ i = 0 ⋃ d − 1 B ( i ) ] ≤ i = 0 ∑ d − 1 Pr [ B ( i ) ] ≤ γ 3 ∣ F ∣ 2 d . 我们具体来看看推论 1。
推论 1 [ZCF23, Corollary 1] 固定任意的 i ∈ [ 0 , d − 1 ] i \in [0, d-1] i ∈ [ 0 , d − 1 ] γ , δ > 0 \gamma, \delta > 0 γ , δ > 0 δ ≤ J γ ( J γ ( Δ C d ) ) \delta \le J_{\gamma}(J_{\gamma}(\Delta_{C_d})) δ ≤ J γ ( J γ ( Δ C d )) Δ ∗ ( v , C i + 1 ) > δ \Delta^*(\mathbf{v}, C_{i+1}) > \delta Δ ∗ ( v , C i + 1 ) > δ
Pr α i ← $ F [ Δ ( f o l d α i ( v ) , C i ) ≤ δ − γ ] ≤ 2 γ 3 ∣ F ∣ . (2) \Pr_{\alpha_i \leftarrow \$ \mathbb{F}}[\Delta(\mathrm{fold}_{\alpha_i}(\mathbf{v}), C_i) \le \delta - \gamma] \le \frac{2}{\gamma^3 |\mathbb{F}|}. \tag{2} α i ← $ F Pr [ Δ ( fold α i ( v ) , C i ) ≤ δ − γ ] ≤ γ 3 ∣ F ∣ 2 . ( 2 ) 其中的 f o l d α i ( ⋅ ) \mathrm{fold}_{\alpha_i}(\cdot) fold α i ( ⋅ ) u , u ′ ∈ F n i \mathbf{u},\mathbf{u'} \in \mathbf{F}^{n_i} u , u ′ ∈ F n i
π i + 1 = ( u + d i a g ( T i ) ∘ u ′ , u + d i a g ( T i ′ ) ∘ u ′ ) \pi_{i+1} = (\mathbf{u} + \mathrm{diag}(T_i) \circ \mathbf{u}', \mathbf{u} + \mathrm{diag}(T_i') \circ \mathbf{u}') π i + 1 = ( u + diag ( T i ) ∘ u ′ , u + diag ( T i ′ ) ∘ u ′ ) 那么 f o l d α i ( π i + 1 ) \mathrm{fold}_{\alpha_i}(\pi_{i+1}) fold α i ( π i + 1 )
f o l d α i ( π i + 1 ) : = u ′ + α i u . \mathrm{fold}_{\alpha_i}(\pi_{i+1}) := \mathbf{u}' + \alpha_i \mathbf{u}. fold α i ( π i + 1 ) := u ′ + α i u . 这其实就是对 π i + 1 \pi_{i+1} π i + 1 α i \alpha_i α i
推论 1 将 [BKS18] 的推论 7.3 的结果推广到了一般的可折叠的线性编码。
推论 1 证明思路： α i \alpha_i α i 2 γ 3 ∣ F ∣ \frac{2}{\gamma^3 |\mathbb{F}|} γ 3 ∣ F ∣ 2 U = { u + x u ′ : x ∈ F } U = \{\mathbf{u} + x \mathbf{u'} : x \in \mathbb{F}\} U = { u + x u ′ : x ∈ F } C i C_i C i T T T w , w ′ ∈ C i \mathbf{w}, \mathbf{w'} \in C_i w , w ′ ∈ C i u , u ′ \mathbf{u}, \mathbf{u'} u , u ′ T T T w , w ′ \mathbf{w}, \mathbf{w'} w , w ′ c w c_{w} c w C i + 1 C_{i+1} C i + 1 Δ ∗ ( v , C i + 1 ) \Delta^{*}(\mathbf{v}, C_{i+1}) Δ ∗ ( v , C i + 1 )
情况 2 的证明 ¶ 想要证明调用 IOPP.query l l l accept 的概率不超过 ( 1 − δ + γ d ) l (1 - \delta + \gamma d)^l ( 1 − δ + γ d ) l reject 的概率至少为 δ − γ d \delta - \gamma d δ − γ d
用二叉树的思想来进行证明，首先定义一个“坏”的节点 ( i , μ ) (i,\mu) ( i , μ ) i ∈ [ 0 , d − 1 ] i \in [0, d-1] i ∈ [ 0 , d − 1 ] μ ∈ [ n i ] \mu \in [n_i] μ ∈ [ n i ]
p ( X ) : = i n t e r p o l a t e ( ( d i a g ( T i ) [ μ ] , π i + 1 [ μ ] ) , ( d i a g ( T i ′ ) [ μ ] , π i + 1 [ μ + n i ] ) ) p(X) := \mathrm{interpolate}((\mathrm{diag}(T_i)[\mu], \pi_{i+1}[\mu]), (\mathrm{diag}(T'_i)[\mu], \pi_{i+1}[\mu + n_i])) p ( X ) := interpolate (( diag ( T i ) [ μ ] , π i + 1 [ μ ]) , ( diag ( T i ′ ) [ μ ] , π i + 1 [ μ + n i ])) 接着检查 IOPP.query 协议的第 3 步，发现
p ( α i ) ≠ π i [ μ ] p(\alpha_i) \neq \pi_i[\mu] p ( α i ) = π i [ μ ] 这时我们说节点 ( i , μ ) (i,\mu) ( i , μ )
下面考虑 i i i d − 1 d-1 d − 1 μ ∈ [ 1 , n d − 1 ] \mu \in [1, n_{d-1}] μ ∈ [ 1 , n d − 1 ] n 0 n_{0} n 0
如果在其中有一个 ( i , μ ) (i,\mu) ( i , μ ) d − 1 d-1 d − 1 i + 1 i +1 i + 1 d − 1 d-1 d − 1 i + 1 i+1 i + 1 i i i ( i , u ) (i,u) ( i , u ) i + 1 i+1 i + 1 d − 1 d-1 d − 1 β i \beta_i β i i i i i i i β i \beta_i β i ∑ i = 0 d − 1 β i \sum_{i=0}^{d-1}\beta_i ∑ i = 0 d − 1 β i β i : = Δ ( π i , f o l d α i ( π i + 1 ) ) \beta_i := \Delta(\pi_i, \mathrm{fold}_{\alpha_i}(\pi_{i+1})) β i := Δ ( π i , fold α i ( π i + 1 )) π i + 1 \pi_{i+1} π i + 1 π i \pi_i π i
那么剩下的任务就是估计 ∑ i = 0 d − 1 β i \sum_{i=0}^{d-1}\beta_i ∑ i = 0 d − 1 β i β i \beta_i β i
**命题 1 ** [ZCF23, Claim 2] 对任意的 i ∈ [ 0 , d ] i \in [0, d] i ∈ [ 0 , d ] δ ( i ) : = min ( Δ ∗ ( π i , C i ) , J γ ( J γ ( Δ C d ) ) ) \delta^{(i)} := \min(\Delta^*(\pi_i, C_i), J_{\gamma}(J_{\gamma}(\Delta_{C_d}))) δ ( i ) := min ( Δ ∗ ( π i , C i ) , J γ ( J γ ( Δ C d ))) i ∈ [ 0 , d − 1 ] i \in [0, d-1] i ∈ [ 0 , d − 1 ]
β i ≥ δ ( i + 1 ) − δ ( i ) − γ . \beta_i \ge \delta^{(i+1)} - \delta^{(i)} - \gamma . β i ≥ δ ( i + 1 ) − δ ( i ) − γ . 那么根据 soundness 中的条件，δ = δ ( d ) \delta = \delta^{(d)} δ = δ ( d ) Δ ∗ ( π 0 , C 0 ) = Δ ( π 0 , C 0 ) = 0 \Delta^{*}(\pi_0, C_0) = \Delta(\pi_0, C_0) = 0 Δ ∗ ( π 0 , C 0 ) = Δ ( π 0 , C 0 ) = 0 δ ( 0 ) = 0 \delta^{(0)} = 0 δ ( 0 ) = 0
δ = δ ( d ) − δ ( 0 ) = ∑ i = 0 d − 1 δ ( i + 1 ) − δ ( i ) ≤ ∑ i = 0 d − 1 β i + γ d , \delta = \delta^{(d)} - \delta^{(0)} = \sum_{i = 0}^{d-1} \delta^{(i+1)} - \delta^{(i)} \le \sum_{i = 0}^{d-1} \beta_i + \gamma d, δ = δ ( d ) − δ ( 0 ) = i = 0 ∑ d − 1 δ ( i + 1 ) − δ ( i ) ≤ i = 0 ∑ d − 1 β i + γ d , 从而得证 ∑ i = 0 d − 1 β i ≥ δ − γ d \sum_{i = 0}^{d-1} \beta_i \ge \delta - \gamma d ∑ i = 0 d − 1 β i ≥ δ − γ d B B B δ − γ d \delta - \gamma d δ − γ d
References ¶ [BBHR18] Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018. Available online as Report 134-17 on Electronic Colloquium on Computational Complexity. [BGKS20] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: sampling outside the box improves soundness. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 5:1–5:32. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. [BKS18] Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. “Worst-Case to Average Case Reductions for the Distance to a Code”. In: Proceedings of the 33rd Computational Complexity Conference. CCC ’18. San Diego, California: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. isbn: 9783959770699. [ZCF23] Hadas Zeilberger, Binyi Chen, and Ben Fisch. “BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes.” Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2024.
