Signal Processing for Cryptography and Security Applications - Signal Processing Systems - page 233

More elaborate error-correction techniques can be applied to transform a noisy
measurement value into a reliable bit string. In the syndrome construction [ 19 ] the
syndrome, instead of the offset, of a linear block code is used, which reduces the
communication overhead. In [ 51 ] , it is shown that certain fuzzy secrets produce
soft-decision information , which allows the use of soft-decision error-correcting
techniques. This allows to extract a longer and hence more secure key from the
same fuzzy secret.
All these techniques uses a public communication to establish a noise-free secret
from a noisy secret. The data that is passed through this channel, W is called helper
data . It is clear that the publishing of W decreases the uncertainty an adversary may
have about the value of X . In fact, for the code-offset construction it can be shown
that the min-entropy of X is reduced from H ∞ ( X ) to H ∞ ( X ) − n + k ,i.e.thatthe

helper data induces a min-entropy loss .
To conclude, the now noise-free secret with limited min-entropy needs to be
transformed into a uniformly distributed key K . In order to do this, randomness
extractors are used. Randomness extractors succeed in extracting uniform ran-
domness from non-uniformly distributed variables [ 10 , 13 ] . It is obvious that the
output domain of a randomness extractor is smaller than the input, hence they are
compression functions. In fact, the min-entropy of a random variable X is a measure
for the maximum number of uniform bits an ideal randomness extractor can extract
from X . After error correction with the code-offset technique, the fuzzy secret X can
hence contribute at most H ∞ (

k uniformly random bits. Generic randomness
extractors can be constructed relatively easy by using so-called universal hash
functions :if

X ) − n +

H is a universal hash family, the process that selects a random function

h σ ←H can again

be published as helper data to allow reconstruction of K at later times, this time
however without additional loss in min-entropy.

and calculates K = h σ ( X ) is a randomness extractor. The seed σ

5 Conclusion

The purpose of this chapter is to illustrate the usage of signal processing techniques
into the design and implementation of cryptographic and security applications. This
is only the beginning and by no means complete. New directions are being explored.
One example is the exploration of signal processing in the encrypted domain, which
is the topic of the SPEED project [ 65 ] .

Acknowledgements This work is supported in part by the IAP Programme P6/26 BCRYPT of the
Belgian State, by the European Commission under contract numbers ICT-2007-216676 ECRYPT
NoE phase II and ICT-2007-238811 UNIQUE, and by the Research Council K.U.Leuven: GOA
11/007 TENSE. Benedikt Gierlichs is a Postdoctoral Fellow of the Fund for Scientific Research -
Flanders (FWO).