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.

[2]

The On-Line Encyclopedia of Integer Sequences. A001532.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[13]

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

[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.

[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.

[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.

[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. 

[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.

[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.

[20]

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

[21]

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

[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.

[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.

[24]

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

[25]

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

[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.

show all references

References:
[1]

The On-Line Encyclopedia of Integer Sequences. A000609.

[2]

The On-Line Encyclopedia of Integer Sequences. A001532.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[13]

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

[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.

[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.

[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.

[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. 

[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.

[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.

[20]

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

[21]

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

[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.

[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.

[24]

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

[25]

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

[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.

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

Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013
[8]

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
[9]

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

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 and Continuous Dynamical Systems, 2011, 30 (2) : 427-454. doi: 10.3934/dcds.2011.30.427
[11]

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
[12]

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

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
[17]

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

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
[19]

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
[20]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy