Representing (masked) bits in rings

In cryptography it is often useful to represent bits in algebraic objects. I will specifically consider rings $Z_m$ of integers modulo $m$. If $m$ is a prime number this happens to also be a field, but the difference is not very important here.

Bits are elements of $\mathbb{B}=\{\text{T},\text{F}\}$, i.e. true and false, with the usual operations of not $\neg$, and $\wedge$, or $\vee$ and xor $\oplus$.

Given bit vectors $\vec{a},\vec{b}\in {\mathbb{B}}^n$ let the $\text{popcount}:{\mathbb{B}}^n\to [0,n]$ function return the number of $\text{T}$ values in a vector. We can then define the hamming distance function as $\text{hamming}(\vec{a},\vec{b})=\text{popcount}(\vec{a}\oplus \vec{b})$.

Masked bits are elements of $\mathbb{T}=\{\text{T},\text{F},\text{U}\}$, i.e. true, false, and unavailable. The operations are the same as for binary, except when one of the arguments is $\text{U}$, the result is always $\text{U}$.

We take $\text{popcount}$ to count the number of $\text{T}$'s and introduce $\text{count}$ to count the number of available entries i.e. either $\text{F}$ or $\text{T}$ but not $\text{U}$. We can then define a fractional hamming distance $\text{fhd}$ as

$$\text{fhd}(\vec{a},\vec{b})=\frac{\text{popcount}(\vec{a}\oplus \vec{b})}{\text{count}(\vec{a}\oplus \vec{b})}$$

The $\{0,1\}$ representation of bits

We represent $\text{F},\text{T}$ as $0,1$ respectively. The usual binary operations of not $\neg$, and $\wedge$, or $\vee$, xor $\oplus$, can respectively be represented using ring operations as

$$\begin{array}{rl}\neg a& =1-a\\ a\wedge b& =a\cdot b\\ a\vee b& =a+b-a\cdot b\\ a\oplus b& =a+b-2\cdot a\cdot b\end{array}$$

If we have a vector $\vec{a}\in {\mathbb{B}}^n$ we can represent it element wise in $Z_m^n$. This allows us to represent the $\text{popcount}$ function:

$$\begin{array}{rl}\text{popcount}(\vec{a})& =\text{vsum}(\vec{a})\mathrm{mod}m\end{array}$$

Observing that the sum over elementwise products is the dot product, we obtain the following useful identity:

$$\text{popcount}(\vec{a}\wedge \vec{b})=\vec{a}\cdot \vec{b}\mathrm{mod}m$$

This representation is reversible for any $m\ge 2$, except for $\text{popcount}$ which need $m\ge n$.

$$\text{hamming}(\vec{a},\vec{b})=\vec{a}\cdot \vec{a}+\vec{b}\cdot \vec{b}-2\cdot \vec{a}\cdot \vec{b}$$

The $\{1,-1\}$ representation of bits

We represent $\text{F},\text{T}$ as $1,-1$ respectively. The usual binary operations of not $\neg$, and $\wedge$, or $\vee$, xor $\oplus$, can respectively be represented using ring operations as

$$\begin{array}{rl}\neg a& =-a\\ a\wedge b& =?\\ a\vee b& =?\\ a\oplus b& =a\cdot b\end{array}$$

If we have a vector $\vec{a}\in {\mathbb{B}}^n$ we can represent it element wise in $Z_m^n$. This allows us to represent the $\text{popcount}$ function:

$$\begin{array}{rl}\text{popcount}(\vec{a})& =½\cdot (n-\text{vsum}(\vec{a}))\end{array}$$

Given a $m$ bit vectors ${\vec{a}}_i\in {\mathbb{B}}^n$ we can construct a matrix $\mathrm{A}\in {\mathbb{B}}^{n\times m}$ such tht ${\mathrm{A}}_{i,:}={\vec{a}}_i$. If we have a second matrix of hamming distances $\mathrm{D}\in [0,n{]}^{m\times m}$ such that ${\mathrm{D}}_{ij}=\text{hamming}({\vec{a}}_i,{\vec{a}}_j)$ then the following holds:

$$\mathrm{D}=½\cdot (n\cdot \mathrm{J}-\mathrm{A}\cdot {\mathrm{A}}^{\text{T}})$$

Where $\mathrm{J}$ is the matrix of all ones. Suppose we are given $\mathrm{D}$, we can compute ${\mathrm{D}}^{\prime }=n\cdot \mathrm{J}-2\cdot \mathrm{D}$ and solve the following quadratic system:

$$\begin{array}{rl}{\mathrm{D}}^{\prime }& =\mathrm{A}\cdot {\mathrm{A}}^{\text{T}}\\ \mathrm{J}& =\mathrm{A}\odot \mathrm{A}\end{array}$$

The $\{-1,0,1\}$ representation of masked bits

We represent $\text{F},\text{U},\text{T}$ as $-1,0,1$ respectively. The binary operations become

$$\begin{array}{rl}\neg a& =-a\\ a\wedge b& =½\cdot a\cdot b\cdot (1+a+b-a\cdot b)\\ a\vee b& =½\cdot a\cdot b\cdot (a\cdot b+a+b-1)\\ a\oplus b& =-a\cdot b\end{array}$$

Note that the formulas for $\wedge ,\vee$ can be evaluated using two multiplies in a depth-2 circuit.

Given a masked bitvector $\vec{a}\in {\mathbb{T}}^n$, we can define

$$\begin{array}{rl}\text{count}(\vec{a})& =\text{vsum}\left({\vec{a}}^{\odot 2}\right)\\ \text{popcount}(\vec{a})& =½\cdot \text{vsum}\left({\vec{a}}^{\odot 2}+\vec{a}\right)\end{array}$$

We can represent this on a suitably large (Q how large?) ring as $-1,0,1$ for $\text{F},\text{U},\text{T}$ respectively.

Note that squaring, ${\vec{a}}^{\odot 2}$, produces a regular $0,1$ bitvector that is $0$ whenever the value is $\text{U}$ and $1$ otherwise, i.e. it allows us to extract the mask as a regular bitvector. Similarly $½\cdot ({\vec{a}}^{\odot 2}+\vec{a})$ extracts the data bits: $1$ for $\text{T}$ and $0$ otherwise. The reverse mapping, converting data bits $\vec{b}$ and mask bits $\vec{m}$ to a masked bitvector is $\vec{m}-2\cdot \vec{b}\odot \vec{m}$. If the data bits are known to be $\text{F}$ in the in the unavailable region, then it simplifies to $\vec{m}-2\cdot \vec{b}\odot \vec{m}$.

In this representation and and or have awkward fourth degree expressions, though they can be evaluated using only two multiplies. The expressions for xor, $\text{count}$ and $\text{popcount}$ are quite nice considering that they correctly account for masks. This makes it a suitable system for computing fractional hamming distances.

This representation is reversible for any $m\ge 2$, except for $\text{popcount}$ which need $m\ge n$.

Fractional hamming distance

The fractional hamming weight of a masked bitvector $\vec{a}$ is defined as

$$\begin{array}{rl}\mathtt{fhw}(\vec{a})& =\frac{\text{popcount}(\vec{a})}{\text{count}(\vec{a})}\end{array}$$

and the fractional hamming distance between two masked bitvectors $\vec{a}$ and $\vec{b}$ as

$$\begin{array}{rl}\text{fhd}(\vec{a},\vec{b})& =\mathtt{fhw}(\vec{a}\oplus \vec{b})=\frac{\text{popcount}(\vec{a}\oplus \vec{b})}{\text{count}(\vec{a}\oplus \vec{b})}\end{array}$$

In the ring representation these can be computed as

$$\begin{array}{rlrl}\text{fhd}(\vec{a},\vec{b})& =\frac{½\cdot \text{vsum}\left((-\vec{a}\odot \vec{b}{)}^{\odot 2}-\vec{a}\odot \vec{b}\right)}{\text{vsum}\left((-\vec{a}\odot \vec{b}{)}^{\odot 2}\right)}& & =\frac{1}{2}-\frac{\text{vsum}\left(\vec{a}\odot \vec{b}\right)}{2\cdot \text{vsum}\left((\vec{a}\odot \vec{b}{)}^{\odot 2}\right)}\end{array}$$

Note that $(\vec{a}\odot \vec{b}{)}^{\odot 2}={\vec{a}}^{\odot 2}\odot {\vec{b}}^{\odot 2}$ and thus depends only on the masks of $\vec{a}$ and $\vec{b}$. Given the masks ${\vec{a}}_m$ and ${\vec{b}}_m$ it can be computed in binary as

$$\text{vsum}\left((\vec{a}\odot \vec{b}{)}^{\odot 2}\right)=\text{popcount}({\vec{a}}_m\wedge {\vec{b}}_m)$$