Additive Delay Model

The Additive Delay Model [GCvDD02] can be used to model Arbiter PUFs as well as Arbiter PUF-based constructions, such as the XOR Arbiter PUF, the Lightweight Secure PUF, the Permutation PUF, and the Interpose PUF. It can be extended by a noise model based on Gaussian random variables, which has been shown to highly accurate [DV13].

This module contains LTFArray, a simulation implementation of the Additive Delay Model, as well as NoisyLTFArray, an implementation of the Additive Delay Model with Gaussian noise.

Note

pypuf’s implementation of the Additive Delay Model uses \(\{-1,1\}\) to represent bit values both for challenges and responses.

Note

All simulations based on the Additive Delay Model in pypuf use numpy.int8 to represent bit values, i.e. for each challenge or response bit, one byte of memory is allocated. While inefficient in terms of required memory, this provides faster evaluation performance than storing one logical bit in one bit of memory.

Modeling of Delay Values

Todo

Add derivation of Additive Delay Model from circuit

Implementation of the Additive Delay Model

class pypuf.simulation.base.LTFArray(weight_array: ndarray, transform: str | Callable, combiner: str | Callable = 'xor', bias: ndarray | None = None)

Highly optimized, numpy-based implementation that can batch-evaluate functions as found in the Additive Delay Model of Arbiter PUFs, i.e. functions \(f\) of the form

\[\begin{split}f: \{-1,1\}^n \to \{-1,1\}, f(c) &= \text{sgn } \hat{f}(c), \\ \hat{f}: \{-1,1\}^n \to \mathbb{R}, \hat{f}(x) &= \prod_{l=1}^k (b_l + \sum_{i=1}^n W_{l,i} \cdot x_i ),\end{split}\]

where \(n, k\) are natural numbers (positive int) specifying the size of the LTFArray, \(W \in \mathbb{R}^{k \times n}\) are the weights of the linear threshold functions, and \(b_i, i \in [k]\) are the biases of the LTFs.

For performance reasons, the evaluation interface of LTFArray is specialized for evaluating a list of challenges with each call, returning a list of responses of same length; this length will often be referred to as \(N\).

Todo

Detail on weight distribution.

Two generalizations of \(f\) are supported. First, modifying the challenge input has been extensively studied in the literature [Lightweight Secure PUF, Permutation PUF]. In LTFArray, this is implemented as input transformation. Second, using a function different from XOR to combine the individual results into a final result, which is less studied and is known to LTFArray as combiner function (in reference to LFSRs). We detail on both below.

Input Transformations. An input transformation can be understood as a list of functions \(\lambda_1,...,\lambda_k\), where \(\lambda_i:\{-1,1\}^n \to \{-1,1\}^n\) generates the input for the \(i\)-th LTF in the LTFArray. In order to use input transformations with LTFArray, implement a Python function that maps a list of challenges challenges given as ndarray of shape \((N, n)\) and the number of LTFs given as a positive int k to a list of list of sub-challenges to the individual LTFs (sub_challenges), returned as ndarray of shape \((N, k, n)\), where for all \(i \in [N]\) and \(l \in [k]\)

\[\mathtt{sub\_challenges}_{i, l} = \lambda_l(\mathtt{challenges}_i).\]

Given such a function, LTFArray will evaluate

\[\begin{split}f: \{-1,1\}^n \to \{-1,1\}, f(c) &= \text{sgn } \hat{f}(c), \\ \hat{f}: \{-1,1\}^n \to \mathbb{R}, \hat{f}(x) &= \prod_{l=1}^k (b_l + \langle W_l, \lambda_l(x) \rangle ).\end{split}\]

Warning

In above definition, the \(\lambda_i\) are different from preprocessing functions implemented in hardware. This is due to the nature of the Arbiter PUF Additive Delay Model: in order to accurately model the behavior of an Arbiter PUF without additional challenge processing on a given hardware input \(c \in \{-1,1\}^n\), the Arbiter PUF needs ot be modeled as function

\[f(c) = \text{sgn } \prod_{l=1}^k b_l + \sum_{i=1}^n W_{l,i} \cdot c_i c_{i+1} \cdots c_n,\]

i.e. \(\lambda_1 = \cdots = \lambda_k\) with \(\lambda_1(c)_i = c_i c_{i+1} \cdots c_n\). This function is implemented in LTFArray as att; its inverse is att_inverse.

Combiner Function. The combiner function replaces the product of linear thresholds in the definition of \(\hat f\). Setting the combiner parameter to a Callable my_combiner taking a shape \((N, k)\) array of sub-responses and returning an array of shape \((N,)\), will compute the function

\[f(c) = \text{sgn } \mathtt{my\_combiner} \left( b_l + \sum_{i=1}^n W_{l,i} \cdot c_i c_{i+1} \cdots c_n \right).\]

To instanciate an LTFArray, provide the following parameters:

Parameters:

weight_array – weights of the LTFs in this array, ndarray of floats with shape \((k, n)\)
transform – input transformation as described above, given as callable function or string s identifying a member function of this class with name s or f’transform_{s}’.
combiner – optional combiner function as described above, given as callable function or string s identifying a member function of this class with name s or f’combiner_{s}’, defaults to xor, i.e. the partity function.
bias – optional ndarray of floats with shape \((k,)\), specifying the bias values \(b_l\) for \(l \in [k]\), defaults to zero bias.

To create an LTFArray containing just one function, the majority vote function of four inputs, use

>>> from pypuf.simulation import LTFArray
>>> from numpy import array, ones
>>> my_puf = LTFArray(ones(shape=(1, 4)), transform='id')
>>> my_puf.eval(array([[1, 1, -1, 1]]))
array([1])
>>> my_puf.eval(array([[1, -1, -1, -1]]))
array([-1])

eval(challenges: ndarray, block_size: int | None = 1000000) → ndarray

Evaluate the PUF on a list of given challenges.

Parameters:: challenges – List of challenges to evaluate on. Challenges must be given as ndarray of shape (\(N\), challenge_length), where \(N\) is the number of challenges to be evaluated. Evaluating many challenges at once may have performance benefits, to evaluate a single challenge, provide an ndarray with shape (1, challenge_length). In cases where challenge_length = 0, an empty array with shape (\(N\), 0) needs to be provided to determine the number of responses requested.
Returns:: ndarray, shape (\(N\), response_length), listing the simulated responses to the challenges in order they were given.

Modeling of Noise

Todo

Add overview of NoisyLTFArray.