Efficient Fuzzy Extractors Based on Ternary Debiasing Method for Biased Physically Unclonable Functions

This paper proposes a new debiasing method and its application to fuzzy extractors (FEs) for stable and efficient extraction of uniform random binary responses from biased physically unclonable functions (PUFs). The proposed method handles PUF responses as ternary responses assuming that an unstable response bit is the third value, and stably extracts uniform random binary responses from them. In this paper, we evaluate the stability and effectiveness of the proposed method via two experiments with simulated and actual responses of latch PUFs. We demonstrate that the proposed method can obtain longer debiased random binary responses than the conventional method. In addition, we apply the debiasing method to the construction of FEs; in an experimental evaluation, we show the advantages of the proposed FE in terms of needed PUF size and authentication success rate. The results show the advantage of the proposed method to other conventional methods. In particular, the needed PUF sizes in the proposed FE were 34%-38% shorter than those in the conventional binary method under the condition that the authentication success rates are sufficient.