# Barrel Shifter Physical Unclonable Function Based Encryption
## 3 Block Encryption Protocol
### Invertible and Commutative PUF  
Section 2 dictates invertibility and commutativity as encryption protocol requirements. PUF \(f\) must be a one-to-one function to achieve encryption and invertibility for decryption. Many classical PUFs, such as RO-PUFs [13; 14; 15; 16] and arbiter PUFs [17; 18], cluster the challenges into equivalence classes on a set of attributes resulting in the same response per challenge equivalence class. Arbiter PUF uses relative bit arrival time as the clustering attribute. RO PUF uses relative oscillator frequencies. The end result is that this makes these PUFs not invertible since the mapping is many-to-one. Further note that physical invertibility is distinct from logical invertibility. A mathematical one-to-one function has logical invertibility but may not be physically invertible. Physical invertibility is applicable to the PUF physical attribute measurement process. In the forward computation, inputs traverse the computation paths to the output; physical measurements may take place at various points along these paths. In the inverse computation, output bits travel to the inputs through the identical computation paths in reverse. The physical measurements of the same physical attribute occur in the inverse computation. These forward and inverse physical measurements need to be reproducible at all measurement points from input to output. Invertibility requires using a raw physical property such as delay. The reversible computation principle states that any information loss makes a process irreversible [19]. Many PUFs derive their response through the comparison of physical properties. Arbiter PUF uses a race between two paths. RO-PUF uses a frequency comparison. These comparisons provide reproducibility by including a wide margin of noise before comparison output changes, but information is lost. Permutation functions provide the necessary one-to-one relationship. Permutations create a nonlinear relationship from input bits to output bits. Due to this property, an adversary cannot create a useful mathematical model describing the input, output relationship. For \(n\) data bits, there exist \(N=n!\) permutations denoted by \(\pi_{0},\pi_{1},\ldots,\pi_{N-1}\). Each \(\pi_{i}\) captures some permutation \((i_{0},i_{1},\ldots,i_{n-1})\), where bit \(k\mapsto i_{k}\). In other words, the bit at 0 is routed to bit position \(i_{0}\) in the output. A key \(K\) is used to select this mapping. We call this a keyed PUF: \(R_{i,K}=f(K,C_{i})\). The PUF response is derived from the shift path delay. The protocol also requires the entanglement procedure to be commutative. Entanglement adds a bit from the delay of each path to the plaintext. Thus, entanglement is expressed as  
Figure 2: Cipher block chaining methods are used to encrypt (**a**) and decrypt (**b**) messages. This prevents the adversary from identifying plaintext patterns; it ensures identical blocks of plaintext encrypt to different ciphertexts. \(f(K_{Bob},P_{i})=P_{i}\oplus D_{Bob}\). This is commutative because '\(\oplus\)' is commutative. Note that the entanglement between the physical delay attribute and logical bits can occur at multiple points during the flight of message bits from input to output; each measurement point is also an entanglement point. The proposed PUF is based on a barrel shifter. Constructing it with precisely sized transmission gates makes its delay independent of bit state 0 or 1. Bit propagation delay for forward path and inverse path is remarkably stable and consistent regardless of bit state. This is due to symmetric physical structure of the MOSFET's source and drain. As we discuss in the following, physical commutativity and invertibility in our protocol is only achieved if the physical delay on the paths is a bit state independent. Step 5 of Figure 1, where [PERSON] computes \(f_{Bob}^{-1}\), is dealing with a different bit pattern at [PERSON]'s PUF output than was computed in Step 1 at [PERSON]'s PUF output.