# American Institute of Mathematical Sciences

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:

show all references

##### References:
Distribution of delays obtained via circuit simulation
Comparison of entropies up to $n = 10$
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]$
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}$
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...
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
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] 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] 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 [5] 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 [6] Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2020  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] 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 - A, 2011, 30 (2) : 427-454. doi: 10.3934/dcds.2011.30.427 [9] 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 [10] 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, 2020  doi: 10.3934/amc.2020095 [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] 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 [13] 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 [14] Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201 [15] 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, 2020  doi: 10.3934/amc.2020056 [16] Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565 [17] Mourad Choulli. Local boundedness property for parabolic BVP's and the Gaussian upper bound for their Green functions. Evolution Equations & Control Theory, 2015, 4 (1) : 61-67. doi: 10.3934/eect.2015.4.61 [18] João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465 [19] Ana-Maria Acu, Laura Hodis, Ioan Rasa. Multivariate weighted kantorovich operators. Mathematical Foundations of Computing, 2020, 3 (2) : 117-124. doi: 10.3934/mfc.2020009 [20] Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables