American Institute of Mathematical Sciences

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

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

Alexander Schaub 1,, , Olivier Rioul 1, , Jean-Luc Danger 1, , Sylvain Guilley 2, and  Joseph Boutros 3,

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  August 2020 Early access  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 $.

Keywords: Multivariate Gaussian distribution, entropy, Boolean threshold functions.
Mathematics Subject Classification: Primary: 94A17, 94C10.
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. Dodis, K. 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. Muroga, T. 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. Dodis, K. 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. Muroga, T. 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 Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Comparison of entropies up to $ n = 10 $
Figure Options

Download full-size image

Download as PowerPoint slide

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] $
Table Options

Download as excel

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} $
Table Options

Download as excel

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...
Table Options

Download as excel

$ 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
Table Options

Download as excel

$ 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
Table Options

Download as excel

$ 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]

Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335
[2]

René Henrion. Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 655-668. doi: 10.3934/naco.2012.2.655
[3]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[4]

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[5]

Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061
[6]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[7]

Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
[8]

Rui Zhang, Sihong Su. A new construction of weightwise perfectly balanced Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021020
[9]

Katayun Barmak, Eva Eggeling, Maria Emelianenko, Yekaterina Epshteyn, David Kinderlehrer, Richard Sharp, Shlomo Ta'asan. An entropy based theory of the grain boundary character distribution. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 427-454. doi: 10.3934/dcds.2011.30.427
[10]

Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2020, 14 (4) : 651-676. doi: 10.3934/amc.2020036
[11]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[12]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
[13]

Thomas W. Cusick, Younhwan Cheon. The weight recursions for the 2-rotation symmetric quartic Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021011
[14]

Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095
[15]

Suman Dutta, Subhamoy Maitra, Chandra Sekhar Mukherjee. Following Forrelation – quantum algorithms in exploring Boolean functions' spectra. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021067
[16]

Sanjit Kumar Mohanty, Rajani Ballav Dash. A quadrature rule of Lobatto-Gaussian for numerical integration of analytic functions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021031
[17]

Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113
[18]

Bingxin Wang, Sihong Su. A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020115
[19]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121
[20]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (392)
  • HTML views (369)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy