International Association for Cryptologic Research

International Association
for Cryptologic Research


Boris Skoric


An efficient fuzzy extractor for limited noise
B. Skoric P. Tuyls
A fuzzy extractor is a security primitive that allows for reproducible extraction of an almost uniform key from a noisy non-uniform source. We analyze a fuzzy extractor scheme that uses universal hash functions for both information reconciliation and privacy amplification. This is a useful scheme when the number of error patterns likely to occur is limited, regardless of the error probabilities. We derive a sharp bound on the uniformity of the extracted key, making use of the concatenation property of universal hash functions and a recent tight formulation of the leftover hash lemma.
Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes
Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. For binary alphabets, $n$ users and a false accusation probability of $\eta$, a code length of $m\approx \pi^2 c_0^2\ln(n/\eta)$ is provably sufficient to withstand collusion attacks of at most $c_0$ colluders. This improves Tardos' construction by a factor of $10$. Furthermore, invoking the Central Limit Theorem we show that even a code length of $m\approx \half\pi^2 c_0^2\ln(n/\eta)$ is sufficient in most cases. For $q$-ary alphabets, assuming the restricted digit model, the code size can be further reduced. Numerical results show that a reduction of 35\% is achievable for $q=3$ and 80\% for~$q=10$.
Information-theoretic analysis of coating PUFs
Physical Uncloneable Functions (PUFs) can be used as a cost-effective means to store cryptographic key material in an uncloneable way. In coating PUFs, keys are generated from capacitance measurements of a coating containing many randomly distributed particles with different dielectric constants. We introduce a physical model of coating PUFs by simplifying the capacitance sensors to a parallel plate geometry. We estimate the amount of information that can be extracted from the coating. We show that the inherent entropy is proportional to $sqrt{n}(log n)^{3/2}$, where n is the number of particles that fit between the capacitor plates in a straight line. However, measurement noise may severely reduce the amount of information that can actually be extracted in practice. In the noisy regime the number of extractable bits is in fact a decreasing function of n. We derive an optimal value for n as a function of the noise amplitude, the PUF geometry and the dielectric constants.