CHES 2024: Fast Transciphering Via Reconfigurable And Batched LUT Evaluation

Three weeks ago, the conference on Cryptographic Hardware and Embedded Systems (CHES) took place in Halifax, Canada. In this blog post, we give a high-level summary of the main contribution of the paper “Fast Transciphering Via Reconfigurable And Batched LUT Evaluation” that was presented by Leonard Schild at CHES 2024.

Lookup tables (LUTs) are multi-dimensional arrays, commonly used in both hardware and software to evaluate functions that may be difficult to compute otherwise. In a normal setting, the output of the LUT is simply induced by the digits or indices that are given as in input. However, the setting which we consider is one in which the digits are encrypted using a Fully Homomorphic Encryption (FHE) scheme.

As a brief reminder, FHE enables us to combine encrypted data using certain operations. E.g. given $c_0=\mathsf{Enc}(x),c_1=\mathsf{Enc}(y)$ , we are able to compute $c_3=\mathsf{Enc}(x+y)$ or $c_4=\mathsf{Enc}(3\cdot x)$ without decrypting either $c_0$ or $c_1$. Furthermore, the class of FHE schemes we work with has a special blind-rotation procedure that works as follows

• $\mathsf{BlindRotate}(c_0,C_1)$: Given ciphertexts
  • $c_0=\mathsf{Enc}(m),m\in \{0,\dots ,2^k-1\}$,
  • $C_1=\mathsf{Enc}(P),P\in {\mathbb{Z}}_q[X]/(X^N+1)$
• Output $$C=\mathsf{Enc}((-1{)}^{m_k}\cdot P^{\prime }),P_i^{\prime }=P_{i–m(\mathrm{mod}N)}$$ where $m_k$ is the $k$-th bit of $m$

In other words, if the $k$-th bit of $m$ is 0, the procedure outputs a ciphertext containing $P$ rotated by $m$ slots and otherwise outputs the same value, multiplied by -1. We note that transforming an encryption of a polynomial into an encryption of one of its coefficients and vice-versa is feasible without decryption, and referred to as sample-extraction and ciphertext packing respectively.

We will see next how to use the previous concepts to evaluate (simple) lookup tables.

Background on LUT Evaluation

Let us consider a lookup table $F:{\mathbb{Z}}_{2^{k-1}}\mapsto {\mathbb{Z}}_{2^{k-1}}$ that we aim to evaluate using $\mathsf{Enc}(m)$. This is the simplest setting, often called functional or programmable bootstrapping, and, provided that $k<6$, can be performed efficiently:

• Start by encoding the $F$ into the coefficients of a polynomial, i.e. $P_i=F(i)$
• Run $C=\mathsf{Enc}(P^{\prime })\leftarrow \mathsf{BlindRotate}(\mathsf{Enc}(m),\mathsf{Enc}(P))$
• The result is $c_0=\mathsf{Enc}(P_0^{\prime })$

As $m$ ranges from 0 to $2^k–1$ but the LUT only takes inputs up to $2^{k-1}-1$, the most significant bit of $m$ must be 0. Hence, no sign flip occurred and $P^{\prime }$ is simply a rotation of $P$ and $P_0^{\prime }=F(m)$

We’ve just seen how to evaluate one dimensional lookup tables. Extending this methodology to multiple input dimensions is possible and was done in the work “Revisiting the functional bootstrap in TFHE” by Guimarães et al. To give an intuition of this approach, consider a LUT $F:{\mathbb{Z}}_{2^{k-1}}^l\mapsto {\mathbb{Z}}_{2^{k-1}}$ that is a $l$-dimensional LUT. As in the one dimensional case, we can now encode $F$ into a matrix, or for higher dimensions a tensor, of polynomials. Then, we can use the blind-rotation procedure to rotate each dimension so that the LUT value will finally be in the $0^l$-th slots of the resulting encrypted tensor.

Faster LUT Evaluation

The previous approaches had some shortcomings. In the 1D case, we have to limit the size of the encrypted digits for performance reasons. In the higher dimensional case, this limit can be circumvented by splitting a digit into multiple. However, it is easy to see that the number of blind-rotations is exponential in $l$ (or at least a multiple of $l$ using more sophisticated approaches). Furthermore, if the number of output values is greater than 1, the entire procedure needs to be repeated. Finally, in all cases we have seen so far, there was an implicit requirement that the most significant bit of $m$ must be 0.

We now come to the actual contribution of the paper we are summarizing. Consider the case in which we have a have lookup table $F:{\mathbb{Z}}_2^l\mapsto {\mathbb{Z}}_2^l$ where $l$ may range from $8-10$. One such example is the AES SBOX. This means that the digits consist of bits and are given as $c_i=\mathsf{Enc}(m_i{2}^{k-1})$. This setting is particularly interesting, as giving any $c_i$ as input to the blind-rotation procedure will not actually perform any rotation and only a sign flip depending on $m_i$, as that is the $k$-th bit. We now describe the method that allows us to evaluate such a LUT using only $l$ blind-rotations while obtaining all output bits at once.

First, we select a set of $\omega$ bits that we homomorphically compose into a single integer. Let $P=2^{j-1}\cdot \sum _i{X}^i$ and perform $c_i^{\prime }=\mathsf{Enc}(P^{\prime })\leftarrow \mathsf{BlindRotate}(c_i,\mathsf{Enc}(P))$ for some $c_i,i<\omega$. As we mentioned in the last paragraph, no rotation will take place and we’ll have that $P^{\prime }=(-1{)}^{m_i}P$. Then, adding $2^{j–1}$ to every slot, we have that $P_0^{\prime }+2^{j–1}=m_i{2}^j$. In other, we have just seen how to shift an encrypted most significant bit into any other bit slot. By repeating this procedure for any bit slot, and adding all resulting ciphertexts we obtain $\overline{c}=\mathsf{Enc}(\sum _{i=0}^{k-1}{m}_i{2}^i)$.

The ciphertext $\overline{c}$ contains information about the first $\omega$ bits, but not the remaining $l-\omega$ bits. Now, let us consider $F_j^{\prime }(x_0,\dots ,x_{\omega -1})=F(x_0,\dots ,x_{\omega -1},0,\dots ,0{)}_j$ which equals our previous LUT $F$, except that we fix the last $l–\omega$ inputs to zero and focus on the $j$-th output bit. We could evaluate this $F_j^{\prime }$ using the 1D procedure described earlier, but we will actually evaluate $F_j^{\prime }$ for all values of $j$ and combinations of possible inputs for the last $l–\omega$ bits. Note that this only requires a single blind-rotation as one can use an optimization introduced in “New techniques for multi-value input homomorphic evaluation and application” by Carpov et al. Once all such LUTs have been evaluated, we can combine them into several encrypted polynomials. In practice, the polynomial dimension will be so large that a single polynomial will suffice to pack all values into it.

The final step of the method will be used to actually select the correct group of outputs from the pool of candidates. To this end, we rely again on the sign-flipping ability of the blind-rotation procedure. Consider the following expression: $$C=2^{-1}\cdot (\mathsf{Enc}(P_0)+\mathsf{Enc}(P_1)+\mathsf{BlindRotate}(c_i,\mathsf{Enc}(P_0)–\mathsf{Enc}(P_1)))$$ Going through both cases of the value $m_i$ in $c_i$, we can observe that $C=\mathsf{Enc}(P_0)$ if $m_i=0$ and $C=\mathsf{Enc}(P_1)$ otherwise. Therefore, we are able to select the final, correct output by repeatedly applying the previous equation.

We have now described the entire method. It is worth pointing out that if the number of digits $l$ increases drastically, the amount of blind-rotation may no longer be equal to $l$. However, many optimizations that can be applied to the method by Guimarães also benefit the novel approach, but need to be explored in future work.