Affine maps over a finite field form a pairwise independent hash family

Fix distinct inputs $x,x^{\mathrm{\prime }}\in F$ and target outputs $y,y^{\mathrm{\prime }}\in F$. Because $x-x^{\mathrm{\prime }}\mathrm{\ne }0$, [L1] gives $a=(y-y^{\mathrm{\prime }})\mathrm{/}(x-x^{\mathrm{\prime }})$. Then $b:=y-ax$ is forced, and these values satisfy $ax+b=y$ and $a{x}^{\mathrm{\prime }}+b=y^{\mathrm{\prime }}$. Thus there is at least one pair $(a,b)$ producing the target output pair.

If $(a,b)$ and $(a^{\mathrm{\prime }},b^{\mathrm{\prime }})$ both satisfy those two equations, then subtracting them yields $(a-a^{\mathrm{\prime }})(x-x^{\mathrm{\prime }})=0$. Since $x-x^{\mathrm{\prime }}\mathrm{\ne }0$, [L1] gives $a=a^{\mathrm{\prime }}$, and then $b=b^{\mathrm{\prime }}$. So the pair from step 1.1 is unique.

The family $\mathcal{H}$ has $\mathrm{\mid }F{\mathrm{\mid }}^2$ members, and step 2.1 shows that exactly one of them maps $(x,x^{\mathrm{\prime }})$ to $(y,y^{\mathrm{\prime }})$. Therefore the probability in [L2] is $1\mathrm{/}\mathrm{\mid }F{\mathrm{\mid }}^2$, proving pairwise independence.