
-
Previous Article
Isogeny formulas for Jacobi intersection and twisted hessian curves
- AMC Home
- This Issue
-
Next Article
On perfect poset codes
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 |
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 $.
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. |


Notation | Explanation |
number of delay elements in a PUF | |
Gaussian random variable representing the delay difference of the |
|
realization of |
|
number of challenges | |
challenge code, a matrix defined by its rows |
|
realization of |
|
realization of |
|
Notation | Explanation |
number of delay elements in a PUF | |
Gaussian random variable representing the delay difference of the |
|
realization of |
|
number of challenges | |
challenge code, a matrix defined by its rows |
|
realization of |
|
realization of |
|
Size of equivalence class | Probability per element |
8 | |
6 |
Size of equivalence class | Probability per element |
8 | |
6 |
1 | 2 | 3 | 4 | |
1 | 2 | 3.6655... | 6.2516... | |
1 | 2 | 3.8073... | 6.7004... | |
1 | 2 | 3.54615... | 5.71049... | |
1 | 2 | 3.20858... | 4.58496... |
1 | 2 | 3 | 4 | |
1 | 2 | 3.6655... | 6.2516... | |
1 | 2 | 3.8073... | 6.7004... | |
1 | 2 | 3.54615... | 5.71049... | |
1 | 2 | 3.20858... | 4.58496... |
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 | 16.5291 | |
7 | 15 028 134 | 23.8411 | |
8 | 8 378 070 864 | 32.9640 | |
9 | 17561539552946 | 43.997 | |
10 | 144130531453121108 | 57.000 |
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 | 16.5291 | |
7 | 15 028 134 | 23.8411 | |
8 | 8 378 070 864 | 32.9640 | |
9 | 17561539552946 | 43.997 | |
10 | 144130531453121108 | 57.000 |
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 |
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
Other articles
by authors
[Back to Top]