@article{Ueno_Kazumori_Homma_2020, title={Rejection Sampling Schemes for Extracting Uniform Distribution from Biased PUFs}, volume={2020}, url={https://tches.iacr.org/index.php/TCHES/article/view/8678}, DOI={10.13154/tches.v2020.i4.86-128}, abstractNote={<p>This paper presents an efficient fuzzy extractor (FE) construction for secure cryptographic key generation from physically unclonable functions (PUFs). The proposed FE, named acceptance-or-rejection (AR)-based FE, utilizes a new debiasing scheme to extract a uniform distribution from a biased PUF response. The proposed debiasing scheme employs the principle of rejection sampling, and can extract a longer debiased bit string compared to those of conventional debiasing schemes. In addition, the proposed AR-based FE is extended to ternary PUF responses (<em>i.e.</em>, ternary encoding of a PUF response). These responses can be derived according to cell-wise reliability of the PUF and are promising for extraction of stable and high-entropy responses from common PUFs. The performance of the AR-based Fes is evaluated through an experimental simulation of PUF-based key generation and compared with conventional FEs. We confirm that the proposed AR-based FE can achieve the highest efficiency in terms of PUF and nonvolatile memory (NVM) sizes for various PUF conditions among the conventional counterparts. More precisely, the AR-based FE can realize a 128-bit key generation with up-to 55% smaller PUF size or up-to 72% smaller NVM size than other conventional FEs. In addition, the ternary AR-based FE is up to 55% more efficient than the binary version, and can also achieve up-to 63% higher efficiency than conventional counterparts. Furthermore, we show that the AR-based FE can be applied to PUFs with local biases (<em>e.g.</em>, biases depending on cell location in SRAM PUFs), unlike all the conventional schemes, for which only global (or identical) biases are assumed.</p>}, number={4}, journal={IACR Transactions on Cryptographic Hardware and Embedded Systems}, author={Ueno, Rei and Kazumori, Kohei and Homma, Naofumi}, year={2020}, month={Aug.}, pages={86–128} }