2
$\begingroup$

Apologies in advance if the terminology I am using in the title of this question, is flawed.

I want an algorithm that will produce a ternary value (meaning from a set of three, as opposed to from a set of two as is the case with a 1 bit / binary value) given some message (of arbitrary length, much the same way message digest procedures accept such messages).

The required properties of the algorithm mirror requirements on cryptographically secure message digest algorithms:

  • The algorithm has to be deterministic with respect to input, producing same output for same input

  • The product of the algorithm must be irreversible to the original message. Arguably, reversing one single ternary bit into some message of any substantial length sounds akin to solving some intractable data compression problem, but just mentioning this for the requirements own sake.

  • The set of values the algorithm would produce must feature a sufficiently "random" distribution.

  • Every value would be present in quantities amounting to exactly 1/3 of the set, meaning the algorithm must also feature "fair" distribution of values.

To express this more plainly, perhaps, I am ultimately looking for a message digest algorithm which, instead of yielding some 128-, 256- or any other amount of bits worth of digest, yields one single ternary (as opposed to binary) value/number.

An algorithm that, by extension, turns a product of some existing traditional message digest (e.g. SHA-256) into a ternary value, would suffice, but I am not sure I can, for instance, just divide some 256-bit value by 3 to get me some sufficiently random value distribution. However, piggybacking on an existing, cryptographically secure message digest algorithm, could be a solution in general, I suppose.

$\endgroup$
4
  • $\begingroup$ Note: There's nothing special about the output having three possible values. An alternative formulation could simply have asked for the result to be an integer $i$ with $0\leq i < 3$. $\endgroup$ – SEJPM May 2 at 13:35
  • 1
  • $\begingroup$ Would there be modulo bias when using the number of set bits for the modulo 3 operation? I think not, because the number of set bits is random itself? $\endgroup$ – amn May 2 at 18:56
  • 2
    $\begingroup$ "Bit" literally is the contraction of "binary digit". You cannot have a ternary binary digit (but we get what you mean I suppose, so there is no need to call it a "tit"). $\endgroup$ – Maarten Bodewes May 2 at 20:02
3
$\begingroup$

Take the output $H$ of $\operatorname{SHA-256(M)}$ or any other hash of $b$ bits. Count the number $u$ of bits set in $H$ and output $u\bmod3$. This is optimally close to unbiased in $\{0,1,2\}$, for an ideal hash and the requirement to deterministically output a value for any $M$.

Counting the number of bits set can be fast. Sometimes there's even an instruction or compiler intrinsic for that. This popcount instruction was nicknamed NSA instruction on the (unverified) rumor it was added to mainframe computers subsided by the US government to help in some form of cryptanalysis based on Hamming distance.

There are equally good alternatives. E.g.: take all 32-bit words of the hash, add them (the total can require 35 bits), then reduce modulo $3$. Or: take all words of the hash reduced modulo $3$, add the results, reduce modulo $3$.


Argument: if we take a uniformly random integer $v$ in $[0,2^b)$ and reduce it modulo $n$, we obtain as $b$ grows a nearly uniformly random number in $[0,n)$, slightly biased towards $0$. With $n=3$, and $b$ even, $0$ has probability $\frac13+\frac1{3\,2^{b-1}}$, and both $1$ and $2$ have probability $\frac13-\frac1{3\,2^b}$. This bias is undetectable for $b\ge128$, and can't be lowered.

Noticing that $2^j\bmod3$ is $1$ for even $j$, and $2$ for odd $j$, we can compute $v\bmod3$ quickly from the binary expression of $v$, by counting the even-weight bits that are set in $v$, subtracting the number of odd-weight bits that are set in $v$, and reducing modulo $3$.

We'd get the same result by complementing the $\left\lfloor\frac b2\right\rfloor$ odd-weight bits, counting all the bits set, subtracting $\left\lfloor\frac b2\right\rfloor$, and reducing modulo $3$.

In our case, the polarity of the bits in $H$ is immaterial, thus we do not need to complement the odd-weight bits, and an offset is immaterial (it only changes the slightly favored outcome), thus we can remove the final subtract. And we reached the first paragraph's method.

$\endgroup$
3
  • 2
    $\begingroup$ NIST would call this the "simple modular method" with a security value $s=254$ in NIST SP 800-90A Rev. 1 (although that is about pseudo random number generation - which is similar for getting random values in a range). $\endgroup$ – Maarten Bodewes May 2 at 20:07
  • $\begingroup$ Is there a link for the unverified claim? Hacker's Delight is a book about bit and byte operations that includes such operations. The author claims that IBM 7030 Stretch (1961) has a pop_count instruction. $\endgroup$ – kelalaka May 2 at 22:56
  • 1
    $\begingroup$ @kelalaka: I added a link. $\endgroup$ – fgrieu May 3 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.