As an example, if an error-correction code has (hypothetically) three bits of k and four bits of parity, chances are that parity completely reveals k. That’s because 23 = 8 possible values of k are mapped to 24 = 16 possible values of parity, resulting in a likely one-to-one mapping between k and parity (with some parity combinations unmapped).
Suppose (hypothetically) that four bits of k are mapped to three bits of parity, resulting in 16 possible values of k mapped to eight possible values of parity. In this case, parity information would likely narrow the search space of k from 16 down to two. This concept can be applied to error-correction codes of a higher order (larger blocks sizes as reflected by larger n).
To keep keys secret, it’s important to minimize the information leak via “helper” bits. There are numerous methods for doing so. One method encapsulates a conventional error-correction-code encoder in a syndrome encoder block, as well as a conventional error-correction-code decoder in a syndrome decoder block (Fig. 4).
Unlike an error-correction-code encoder that takes k bits input and outputs n-k bits, the syndrome encoder now takes n bits input and n-k bits output. On the decode side, instead of taking n bits input and outputs k bits, like the error-correction-code decoder, the syndrome decoder takes n bits input and outputs n bits. The end result of encapsulation is to produce helper (syndrome) bits that reveal much less information than plain-text parity bits.
Employing a properly designed Soft- PUF, such as one with Inter/Intra-PUF curves and NIST randomness test results like that in Figure 3, one could analyze randomness of a particular syndrome coding scheme given a certain sequence of parity bits. Columns 5 and 6 in the table show the results of applying randomness testing to syndrome bits. In this case, syndrome is generated using a more sophisticated syndrome coding scheme than the one just described.
Specifically, the 0th order “dc” sequence of all zeros and all ones and the first order “ac” sequence of alternating 1010s and 0101s were used as paritybit sequences. NIST Statistical Tests for Randomness analyzed the resulting syndrome from a properly designed syndrome encoder’s output.
Again, given the physical random nature of the PUF output in a properly designed Soft-PUF, syndrome bits from a properly designed syndrome encoder are reasonably random. This implies that it’s very difficult to infer information about parity (and, in turn, data bits k) from syndrome bits.
Custom correlation tests analyzing syndrome encoder input versus output confirm results from the earlier NIST randomness tests—over 95% of correlation results were within two standard errors of ideal uncorrelated value. In addition, the few present outliers didn't stray far from two standard errors away from ideal.