Research proof index

A word u is relatively close to a code C within an relative error bound δ if and only if it is relatively close within the equivalent absolute error bound ⌊δ * n⌋.

A word u is within the uniqueDecodingRadius of a code C if and only if there exists exactly one codeword v in C that is that close.

A word u is close to a code C within the absolute unique decoding radius if and only if it is close within the relative unique decoding radius.

Binding ≤ keyed-CR (standard model): for any binding adversary A against the hash-based commitment scheme H.toCommitment, the binding advantage is bounded by the keyed-CR advantage of H against the natural reduction adversary bindingAdv_toCRAdv A. A binding-game win has m₁ ≠ m₂ together with both openings verifying: `H k (m₁, s₁) = c = H k (...

ROM Collision Resistance birthday bound: for any t-query ROM-CR adversary A over a hash range Y, the advantage is bounded by (t+2) * (t+1) / (2 * |Y|) (a vacuous bound when |Y| = 0). The two extra queries account for the experiment's verification queries, which share the adversary's cache.

Definition 4.11.2 Combine(d*, r, (f_0, d_0), …, (f_{m-1}, d_{m-1}))(x) := if (r * φ(x)) = 1 then sum_{i < m} r_i * f_i(x) * (dstar - degree + 1) else sum_{i < m} r_i * f_i(x) * (1 - r * φ(x)^(dstar - degree + 1)) / (1 - r * φ(x))