Remark: has at most one sibling per input on average
ProvedLevin2003.hashPair_siblings_le_oneRemark (Levin 2003, Section 4.3, p. 102). Inputs of have siblings on average for any length-preserving and .
Here a sibling of an input is a different input with the same image, and the average is over all inputs. Formally, for and any function on the field , the number of ordered pairs of distinct inputs with the same image under is at most the number of inputs, .
The point of the Remark is that raw one-way functions are hard to use: 'To be useful, owfs need other properties, e.g. low Renyi entropy', and the hashing is proposed as a way to obtain it, the low average collision count being exactly the required entropy bound. The paper's accompanying Conjecture — that is one-way for any one-way , with the same security up to a polynomial factor — is not part of this statement.
The count is in fact exact: for distinct , the equation determines uniquely as , so there are ordered sibling pairs, slightly fewer than the inputs.
import Definitions.Def_Levin2003_tiling_expansion
namespace Levin2003
/-- **Remark (Levin 2003, §4.3).** For every function `f` on the field with
`2 ^ n` elements, the map `g (a, x) = (a, f x + a * x)` has at most one sibling
per input on average: the number of ordered pairs of distinct inputs with the
same image is at most the number of inputs. -/
theorem hashPair_siblings_le_one (n : ℕ) (hn : n ≠ 0)
(f : GaloisField 2 n → GaloisField 2 n) :
{pq : (GaloisField 2 n × GaloisField 2 n) × (GaloisField 2 n × GaloisField 2 n) |
pq.1 ≠ pq.2 ∧ hashPair f pq.1 = hashPair f pq.2}.ncard
≤ Nat.card (GaloisField 2 n × GaloisField 2 n) := by
sorry
end Levin2003
Read-back
What the Lean code literally says, in plain math · Aristotle (Harmonic) — non-blind, authored by the drafting agent
Non-blind read-back — not independent testimony. This read-back was written by the same agent that drafted the Lean statements in this proposal, at the explicit instruction of the proposal's owner. It was therefore not produced blind by an independent auditor: its author knew the source text, the intended meaning and the mission's aims while writing it. A reviewer must not treat it as an independent cross-check of faithfulness; it is at best a careful restatement by an interested party, and any discrepancy it fails to surface may simply reflect the author's own assumptions about what the code was meant to say.
Fix a natural number assumed to be nonzero, and let denote the Galois field with elements as constructed in Mathlib. Let be an arbitrary function from to — no computability, additivity, injectivity or other property is assumed — and let be the map on sending to , using the field operations of .
The statement bounds the size of one set by the size of another. The set in question consists of ordered pairs of elements of — so pairs of inputs to — subject to two conditions: , and . Its size is measured by the cardinality-of-a-set operator that returns for an infinite set (here the ambient type is finite, so this is the ordinary cardinality). The claim is that this number is at most the number of elements of , i.e. at most .
In other words, summed over all inputs, the number of other inputs sharing an input's image is at most the number of inputs — the average number of siblings per input is at most one. Note that pairs are ordered, so a colliding unordered pair is counted twice, and that the bound is non-strict. The hypothesis is stated but excludes only the degenerate one-element case.