August  2020, 14(3): 491-505. doi: 10.3934/amc.2020060

Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem

1. 

LTCI, Telecom Paris, Institut Polytechnique de Paris, 75013 Paris, France

2. 

Secure-IC S.A.S., 35510 Cesson-Sévigné, France

3. 

Texas A & M University, 23874 Doha, Qatar

* Corresponding author: Alexander Schaub

Received  November 2018 Revised  December 2018 Published  January 2020

Motivated by a security application on physically unclonable functions, we evaluate the probability distributions and Rényi entropies of signs of scalar products of i.i.d. Gaussian random variables against binary codewords in $ \{\pm1\}^n $. The exact distributions are determined for small values of $ n $ and upper bounds are provided by linking this problem to the study of Boolean threshold functions. Finally, Monte-Carlo simulations are used to approximate entropies up to $ n = 10 $.

Citation: Alexander Schaub, Olivier Rioul, Jean-Luc Danger, Sylvain Guilley, Joseph Boutros. Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem. Advances in Mathematics of Communications, 2020, 14 (3) : 491-505. doi: 10.3934/amc.2020060
References:
[1]

The On-Line Encyclopedia of Integer Sequences. A000609. Google Scholar

[2]

The On-Line Encyclopedia of Integer Sequences. A001532. Google Scholar

[3]

I. G. Abrahamson, Orthant probabilities for the quadrivariate normal distribution, The Annals of Mathematical Statistics, 35 (1964), 1685-1703.  doi: 10.1214/aoms/1177700391.  Google Scholar

[4]

H. L. Chang and S. S. Sapatnekar, Statistical timing analysis considering spatial correlations using a single pert-like traversal, Proceedings of the 2003 IEEE/ACM International Conference on Computer-aided Design, ICCAD '03, Washington, DC, USA, IEEE Computer Society, (2003), 621–625. Google Scholar

[5]

Z. H. Cherif, J.-L. Danger, S. Guilley and L. Bossuet, An easy-to-design PUF based on a single oscillator: The Loop PUF, 15th Euromicro Conference on Digital System Design (DSD), IEEE, (2012), 156–162. doi: 10.1109/DSD.2012.22.  Google Scholar

[6]

T. M Cover, Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE Transactions on Electronic Computers, 14 (1965), 326-334.  doi: 10.1109/PGEC.1965.264137.  Google Scholar

[7]

J.-L. Danger, S. Guilley, P. Nguyen and O. Rioul, PUFs: Standardization and evaluation, Proc. 2nd IEEE Workshop on Mobile System Technologies (MST 2016), Milano, Italy, (2016), 12–18, http://perso.telecom-paristech.fr/~rioul/publis/201609dangerguilleynguyenrioul.pdf, http://dx.doi.org/10.1109/MST.2016.11. Google Scholar

[8]

J. Delvaux, D. Gu and I. Verbauwhede, Upper bounds on the min-entropy of RO Sum, Arbiter, Feed-Forward Arbiter, and S-ArbRO PUFs, Hardware-Oriented Security and Trust (AsianHOST), IEEE Asian, (2016), 1–6. doi: 10.1109/AsianHOST.2016.7835572.  Google Scholar

[9]

Y. DodisK. Pietrzak and D. Wichs, Key derivation without entropy waste, Advances in Cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8441 (2014), 93-110.  doi: 10.1007/978-3-642-55220-5_6.  Google Scholar

[10]

Y. Dodis and Y. Yu, Overcoming weak expectations, Theory of Cryptography, Springer, (2013), 1–22. doi: 10.1109/ITW.2012.6404636.  Google Scholar

[11]

B. Gassend, D. Clarke, M. Van Dijk and S. Devadas, Delay-based circuit authentication and applications, Proceedings of the 2003 ACM Symposium on Applied Computing, (2003), 294–301. doi: 10.1145/952532.952593.  Google Scholar

[12]

N. Gruzling, Linear separability of the vertices of an n-dimensional hypercube, Master's thesis, University of Northern British Columbia, 2008. doi: 10.24124/2007/bpgub464.  Google Scholar

[13]

J.-C. Hausmann, Counting polygon spaces, Boolean functions and majority games, Preprint, (2015), arXiv: 1501.07553. Google Scholar

[14]

R. Maes and I. Verbauwhede, Physically unclonable functions: A study on the state of the art and future research directions, Towards Hardware-Intrinsic Security, Springer, (2010), 3–37. doi: 10.1007/978-3-642-14452-3_1.  Google Scholar

[15]

M. Majzoobi, F. Koushanfar and M. Potkonjak, Lightweight secure PUFs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, (2008), 670–673. doi: 10.1109/ICCAD.2008.4681648.  Google Scholar

[16]

S. MurogaT. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Transactions on Computers, 100 (1970), 818-825.  doi: 10.1109/T-C.1970.223046.  Google Scholar

[17]

A. Rényi, On measures of entropy and information, 1961 Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Univ. California Press, Berkeley, Calif, 1 (1961), 547-561.   Google Scholar

[18]

O. Rioul, P. Solé, S. Guilley and J.-L. Danger, On the entropy of physically unclonable functions, IEEE International Symposium on Information Theory (ISIT), (2016), 2928–2932. doi: 10.1109/ISIT.2016.7541835.  Google Scholar

[19]

A. Schaub, J.-L. Danger, S. Guilley and O. Rioul, An improved analysis of reliability and entropy for delay PUFs, 21st Euromicro Conference on Digital System Design, DSD 2018, Prague, Czech Republic, (2018), 553–560. Google Scholar

[20]

M. Skorski, Key derivation for squared-friendly applications: Lower bounds, IACR Cryptology ePrint Archive, 157 (2016). Google Scholar

[21]

T. J. Stieltjes, Extrait d'une lettre adressée à M. Hermite, Bulletin of Science and Mathematics, 2nd Series, 13 (1889), 170-172.   Google Scholar

[22]

S. Tajik, E. Dietz, S. Frohmann, J.-P. Seifert, D. Nedospasov, C. Helfmeier, C. Boit and H. Dittrich, Physical characterization of arbiter PUFs, International Workshop on Cryptographic Hardware and Embedded Systems, (2014), 493–509. doi: 10.1007/978-3-662-44709-3_27.  Google Scholar

[23]

R. O. Winder, Single stage threshold logic, Switching Circuit Theory and Logical Design, SWCT 1961. Proceedings of the Second Annual Symposium on, (1961), 321–332. Google Scholar

[24]

R. O. Winder, Enumeration of seven-argument threshold functions, IEEE Transactions on Electronic Computers, (1965), 315–325. doi: 10.1109/PGEC.1965.264136.  Google Scholar

[25]

M.-D. Mandel Yu and S. Devadas, Recombination of physical unclonable functions, 35th Annual GOMACTech Conference, (2010). Google Scholar

[26]

Y. A Zuev, Methods of geometry and probabilistic combinatorics in threshold logic, Discrete Mathematics and Applications, 2 (1992), 427-438.  doi: 10.1515/dma.1992.2.4.427.  Google Scholar

show all references

References:
[1]

The On-Line Encyclopedia of Integer Sequences. A000609. Google Scholar

[2]

The On-Line Encyclopedia of Integer Sequences. A001532. Google Scholar

[3]

I. G. Abrahamson, Orthant probabilities for the quadrivariate normal distribution, The Annals of Mathematical Statistics, 35 (1964), 1685-1703.  doi: 10.1214/aoms/1177700391.  Google Scholar

[4]

H. L. Chang and S. S. Sapatnekar, Statistical timing analysis considering spatial correlations using a single pert-like traversal, Proceedings of the 2003 IEEE/ACM International Conference on Computer-aided Design, ICCAD '03, Washington, DC, USA, IEEE Computer Society, (2003), 621–625. Google Scholar

[5]

Z. H. Cherif, J.-L. Danger, S. Guilley and L. Bossuet, An easy-to-design PUF based on a single oscillator: The Loop PUF, 15th Euromicro Conference on Digital System Design (DSD), IEEE, (2012), 156–162. doi: 10.1109/DSD.2012.22.  Google Scholar

[6]

T. M Cover, Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE Transactions on Electronic Computers, 14 (1965), 326-334.  doi: 10.1109/PGEC.1965.264137.  Google Scholar

[7]

J.-L. Danger, S. Guilley, P. Nguyen and O. Rioul, PUFs: Standardization and evaluation, Proc. 2nd IEEE Workshop on Mobile System Technologies (MST 2016), Milano, Italy, (2016), 12–18, http://perso.telecom-paristech.fr/~rioul/publis/201609dangerguilleynguyenrioul.pdf, http://dx.doi.org/10.1109/MST.2016.11. Google Scholar

[8]

J. Delvaux, D. Gu and I. Verbauwhede, Upper bounds on the min-entropy of RO Sum, Arbiter, Feed-Forward Arbiter, and S-ArbRO PUFs, Hardware-Oriented Security and Trust (AsianHOST), IEEE Asian, (2016), 1–6. doi: 10.1109/AsianHOST.2016.7835572.  Google Scholar

[9]

Y. DodisK. Pietrzak and D. Wichs, Key derivation without entropy waste, Advances in Cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8441 (2014), 93-110.  doi: 10.1007/978-3-642-55220-5_6.  Google Scholar

[10]

Y. Dodis and Y. Yu, Overcoming weak expectations, Theory of Cryptography, Springer, (2013), 1–22. doi: 10.1109/ITW.2012.6404636.  Google Scholar

[11]

B. Gassend, D. Clarke, M. Van Dijk and S. Devadas, Delay-based circuit authentication and applications, Proceedings of the 2003 ACM Symposium on Applied Computing, (2003), 294–301. doi: 10.1145/952532.952593.  Google Scholar

[12]

N. Gruzling, Linear separability of the vertices of an n-dimensional hypercube, Master's thesis, University of Northern British Columbia, 2008. doi: 10.24124/2007/bpgub464.  Google Scholar

[13]

J.-C. Hausmann, Counting polygon spaces, Boolean functions and majority games, Preprint, (2015), arXiv: 1501.07553. Google Scholar

[14]

R. Maes and I. Verbauwhede, Physically unclonable functions: A study on the state of the art and future research directions, Towards Hardware-Intrinsic Security, Springer, (2010), 3–37. doi: 10.1007/978-3-642-14452-3_1.  Google Scholar

[15]

M. Majzoobi, F. Koushanfar and M. Potkonjak, Lightweight secure PUFs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, (2008), 670–673. doi: 10.1109/ICCAD.2008.4681648.  Google Scholar

[16]

S. MurogaT. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Transactions on Computers, 100 (1970), 818-825.  doi: 10.1109/T-C.1970.223046.  Google Scholar

[17]

A. Rényi, On measures of entropy and information, 1961 Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Univ. California Press, Berkeley, Calif, 1 (1961), 547-561.   Google Scholar

[18]

O. Rioul, P. Solé, S. Guilley and J.-L. Danger, On the entropy of physically unclonable functions, IEEE International Symposium on Information Theory (ISIT), (2016), 2928–2932. doi: 10.1109/ISIT.2016.7541835.  Google Scholar

[19]

A. Schaub, J.-L. Danger, S. Guilley and O. Rioul, An improved analysis of reliability and entropy for delay PUFs, 21st Euromicro Conference on Digital System Design, DSD 2018, Prague, Czech Republic, (2018), 553–560. Google Scholar

[20]

M. Skorski, Key derivation for squared-friendly applications: Lower bounds, IACR Cryptology ePrint Archive, 157 (2016). Google Scholar

[21]

T. J. Stieltjes, Extrait d'une lettre adressée à M. Hermite, Bulletin of Science and Mathematics, 2nd Series, 13 (1889), 170-172.   Google Scholar

[22]

S. Tajik, E. Dietz, S. Frohmann, J.-P. Seifert, D. Nedospasov, C. Helfmeier, C. Boit and H. Dittrich, Physical characterization of arbiter PUFs, International Workshop on Cryptographic Hardware and Embedded Systems, (2014), 493–509. doi: 10.1007/978-3-662-44709-3_27.  Google Scholar

[23]

R. O. Winder, Single stage threshold logic, Switching Circuit Theory and Logical Design, SWCT 1961. Proceedings of the Second Annual Symposium on, (1961), 321–332. Google Scholar

[24]

R. O. Winder, Enumeration of seven-argument threshold functions, IEEE Transactions on Electronic Computers, (1965), 315–325. doi: 10.1109/PGEC.1965.264136.  Google Scholar

[25]

M.-D. Mandel Yu and S. Devadas, Recombination of physical unclonable functions, 35th Annual GOMACTech Conference, (2010). Google Scholar

[26]

Y. A Zuev, Methods of geometry and probabilistic combinatorics in threshold logic, Discrete Mathematics and Applications, 2 (1992), 427-438.  doi: 10.1515/dma.1992.2.4.427.  Google Scholar

Figure 1.  Distribution of delays obtained via circuit simulation
Figure 2.  Comparison of entropies up to $ n = 10 $
Table 1.  Summary of Notations
Notation Explanation
$ n $ number of delay elements in a PUF
$ X_i $ Gaussian random variable representing the delay difference of the $ i $-th delay element ($ i \in [1, n] $)
$ X $ $ X = (X_1, X_2, \ldots, X_n) $
$ x_i $ realization of $ X_i $
$ M $ number of challenges
$ C $ challenge code, a matrix defined by its rows $ (c_i)_{i\in[1, M]} $
$ \text{sgn} $ $ \text{sgn}(x) = 1 $ if $ x> 0 $, $ \text{sgn}(x) = -1 $ if $ x< 0 $, and $ \text{sgn}(0) = 0 $.
$ B_i $ $ B_i = \text{sgn}(c_i \cdot X) $
$ B $ $ B =(B_1, B_2, \ldots, B_M) $
$ b_i $ realization of $ B_i $
$ b $ realization of $ B $
$ \mathbb{P}_b $ $ \mathbb{P}_b = \mathbb{P}[B=b] $
Notation Explanation
$ n $ number of delay elements in a PUF
$ X_i $ Gaussian random variable representing the delay difference of the $ i $-th delay element ($ i \in [1, n] $)
$ X $ $ X = (X_1, X_2, \ldots, X_n) $
$ x_i $ realization of $ X_i $
$ M $ number of challenges
$ C $ challenge code, a matrix defined by its rows $ (c_i)_{i\in[1, M]} $
$ \text{sgn} $ $ \text{sgn}(x) = 1 $ if $ x> 0 $, $ \text{sgn}(x) = -1 $ if $ x< 0 $, and $ \text{sgn}(0) = 0 $.
$ B_i $ $ B_i = \text{sgn}(c_i \cdot X) $
$ B $ $ B =(B_1, B_2, \ldots, B_M) $
$ b_i $ realization of $ B_i $
$ b $ realization of $ B $
$ \mathbb{P}_b $ $ \mathbb{P}_b = \mathbb{P}[B=b] $
Table 2.  Distribution for $ n = 3 $
Size of equivalence class Probability per element
8 $ \frac{1}{8} -3 \frac{\arcsin \frac{1}{3}}{4\pi} $
6 $ \frac{\arcsin \frac{1}{3}}{\pi} $
Size of equivalence class Probability per element
8 $ \frac{1}{8} -3 \frac{\arcsin \frac{1}{3}}{4\pi} $
6 $ \frac{\arcsin \frac{1}{3}}{\pi} $
Table 3.  Exact entropies for $ n\leq 4 $
$ n $ 1 2 3 4
$ H(n) $ 1 2 3.6655... 6.2516...
$ H_0(n) $ 1 2 3.8073... 6.7004...
$ H_2(n) $ 1 2 3.54615... 5.71049...
$H_\infty(n) $ 1 2 3.20858... 4.58496...
$ n $ 1 2 3 4
$ H(n) $ 1 2 3.6655... 6.2516...
$ H_0(n) $ 1 2 3.8073... 6.7004...
$ H_2(n) $ 1 2 3.54615... 5.71049...
$H_\infty(n) $ 1 2 3.20858... 4.58496...
Table 4.  Non-zero probabilities for $ n = 1 $ to $ 10 $
$ n $ Non-zero probabilities Proportion among challenges max-entropy
1 2 1 1
2 4 1 2
3 14 0.875 3.8073
4 104 0.40625 6.7004
5 1882 0.0287 10.8780
6 94572 $ 2.202 \cdot 10^{-5} $ 16.5291
7 15 028 134 $ 8.147 \cdot 10^{-13} $ 23.8411
8 8 378 070 864 $ 2.462\cdot 10^{-29} $ 32.9640
9 17561539552946 $ 1.517\cdot 10^{-64} $ 43.997
10 144130531453121108 $ 1.075\cdot 10^{-137} $ 57.000
$ n $ Non-zero probabilities Proportion among challenges max-entropy
1 2 1 1
2 4 1 2
3 14 0.875 3.8073
4 104 0.40625 6.7004
5 1882 0.0287 10.8780
6 94572 $ 2.202 \cdot 10^{-5} $ 16.5291
7 15 028 134 $ 8.147 \cdot 10^{-13} $ 23.8411
8 8 378 070 864 $ 2.462\cdot 10^{-29} $ 32.9640
9 17561539552946 $ 1.517\cdot 10^{-64} $ 43.997
10 144130531453121108 $ 1.075\cdot 10^{-137} $ 57.000
Table 5.  Estimated Entropies for $ n = 1 $ to $ n = 10 $
$ n $ Equivalence classes Shannon entropy Collision entropy
1 1 1 1
2 1 2 2
3 2 3.665 3.545
4 3 6.250 5.708
5 7 10.015 8.456
6 21 15.189 11.600
7 135 21.956 14.890
8 2470 30.564 18.548
9 175428 41.038 22.231
10 52980624 53.47 26.06
$ n $ Equivalence classes Shannon entropy Collision entropy
1 1 1 1
2 1 2 2
3 2 3.665 3.545
4 3 6.250 5.708
5 7 10.015 8.456
6 21 15.189 11.600
7 135 21.956 14.890
8 2470 30.564 18.548
9 175428 41.038 22.231
10 52980624 53.47 26.06
[1]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

[2]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[3]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[4]

Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316

[5]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[6]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[7]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (120)
  • HTML views (359)
  • Cited by (0)

[Back to Top]