## 3 Permute-Scatter-Gather Implementation
### Implementation
#### 3.3.2 Constant-Time Permutation  
We overcome the challenging problem by implementing _constant-time permutation_. It is a lookup-based technique that always has constant memory access pattern irrespective of the accessed index, thus revealing no information to adversaries. For the computational efficiency, the constant-time permutation is implemented in a x86 assembly. Since a memory access is a costly operation, the number of access needs to be minimized for the constant-time lookup procedure. We achieve this by utilizing only a single SSE load instruction. By doing so, the memory access time for the lookup can be confined to just a single CPU cycle in the case of the table being loaded to a L1 cache [26]. To load a permutation table into a SSE register by a single load instruction, we have to fit the size of the table within the width of the register. In most Intel x86 processors, SSE registers are 128 bits in length (Recent Intel processors support Advanced Vector Extension (AVX), in which the size of registers are more than 128 bits in length. For our technique to be widely deployed, we only consider SSE instructions in this paper). Please note that there are 32 multipliers in total, and thus the size of each index should be at least 5 bits in length. This indicates that a room of 160 bits is needed in the table to store all the indicies, which is larger than the size of the SSE register. We solve this problem in a way that the four leftmost bits of the index are stored in the table instead of all the bits being stored. This makes the four bits of the index to be permuted while the remaining rightmost bit is left unchanged during the permutation process. Figure 2 illustrates the process of constant-time permutation. We have PermTab, an array with a length of 128 bits, which is divided into two 64-bit permutation tables, PermTab\({}_{\text{H}}\) and PermTab\({}_{\text{L}}\). The address of PermTab is 16 bytes aligned so that a single load instruction can load both tables into a SSE register. Two pseudo-random permutations P\({}_{0}\) and P\({}_{1}\), which are generated independently in the Permute step, are set up to those tables respectively. Each table contains a permuted list of partial indices of 4 bits in its slots \(\mathsf{s}_{0},\mathsf{s}_{1},...,\mathsf{s}_{15}\) according to the permutation. In the permutation process, the value of the four leftmost bits of idx, denoted by X in Figure 2, is used to lookup the values of the corresponding slots in the tables simultaneously. For instance, the case of X = 2 would make concurrent lookups to PermTab\({}_{\text{H}}\) and PermTab\({}_{\text{L}}\) with the same slot \(\mathsf{s}_{2}\), resulting P\({}_{0}\)(X) and P\({}_{1}\)(X). The remaining rightmost bit of idx, denoted by Y, is used to select the one among them. As a result, the permuted index idx' is constructed from P\({}_{\text{Y}}\)(X) and Y, where P\({}_{\text{Y}}\in\{\mathsf{P}_{0},\mathsf{P}_{1}\}\) as shown in Figure 2. The memory location of the multiplier is then determined by the permuted index idx'. Listing 1 presents the implementation of the constant-time permutation. The source code is written in perlasm, a x86 assembly language in the form of a perl script. In lines 1-2, the 16 bytes array of PermTab, which comprises PermTabH and PermTabL, is loaded into a xmm1 register. In lines 3-9, the slots from PermTabH and PermTabL, corresponding to the four leftmost bits of the index idx (denoted by \(\$\)idx), are selected in the xmm1 register, and values in those slots are loaded to r10 and r11 registers, respectively. In lines 10-17, one of the values is chosen from r10 and r11 according to the rightmost bit of Sidx, and saved to rax register. Finally, in lines 18-20, the permuted index idx' is produced from the value in rax and the rightmost bit of idx, and then loaded into \(\$\)idx as an output.