Thales UK has identified Synthetic Aperture Radar (SAR) as a promising candidate for the application of Homomorphic Encryption (HE). It is proposed that the data collected from SAR can be protected throughout its processing up to the formation of image products. SAR data can be processed in many ways to produce different types of images; the simplest of which is the Single Look Complex Image. The main challenge of implementing the Single Look Complex Image algorithm in the encrypted domain is that of implementing the Fourier Transform.

#### Discrete Fourier Transform

Consider the Discrete Fourier Transform (DFT) for a
sequence of complex numbers $x_0, x_1, \ldots, x_{N-1}$:

$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{ -\frac{2\pi
i k n} {N} } , \quad k=0,\ldots, N-1$

This is a linear transform; it requires
only the summation of sequence samples and multiplication by scalar values $e^{-\frac{2\pi
i k n}{N} }$ (sometimes called

*twiddle factors*). We usually implement this via a Fast Fourier Transform (FFT) which reduces the computational complexity by the use of a few mathematical tricks.#### Paillier Cryptosystem

The Paillier cryptosystem [1]
encrypts plaintext messages $m\in \mathbb{Z}_n$, where $n$ is the
product of two large prime numbers, to a ciphertext $c\in
\mathbb{Z}^*_{n^2}$. Let $\text{Enc}$
and $\text{Dec}$ denote the encryption and decryption
processes respectively. It can be shown that the Paillier cryptosystem
satisfies the two following properties:

1) For
two plaintext messages $m_1, m_2\in \mathbb{Z}_n$

$\text{Dec}( \text{Enc}(m_1) \cdot \text{Enc}(m_2) \text{ mod } n^2)$ $ = m_1 + m_2 \text{ mod } n$.

$\text{Dec}( \text{Enc}(m_1) \cdot \text{Enc}(m_2) \text{ mod } n^2)$ $ = m_1 + m_2 \text{ mod } n$.

2) For
a plaintext $m$ and any constant integer $k$

$\text{Dec}
( \text{Enc}(m)^k \text{ mod } n ) = km \text{ mod } n^2$.

Properties 1 and 2 allow us to add any
two plaintexts and multiply any plaintext by an integer constant in the
encrypted domain; these operations are sufficient to implement the Fourier Transform
(DFT/FFT).

#### The Fourier Transform under Paillier Encryption

There
are two major challenges in the implementation of a Fourier Transform
under Paillier encryption:

1) Paillier
encrypts and allows operations only on integer values modulo $n$.
We must convert our sequence samples $x_0, x_1, \ldots, x_{N-1}$, and twiddle
factors $e^{-\frac{2\pi ikn}{N} }$, into integers modulo $n$. We achieve this
by multiplying by two appropriately chosen scale factors; one for the sequence
samples and one for the twiddle factors. These scale factors must be dealt with
throughout the Fourier Transform.

2) The
homomorphic addition and scalar multiplication operations result in plaintext
values modulo $n$. That is, if we wish to sum two plaintext
values $m_1, m_2$ in the encrypted domain we must ensure
the resulting plaintext is no greater than $n-1$. Otherwise, we can say nothing
about the magnitude of $m_1 + m_2$. Since we wish to perform many additions and scalar
multiplications throughout the Fourier Transform, we require $n$ to
be large enough to cope with the growth from all of these operations.

These two challenges have been discussed in [2]. Challenge 1 means that we need to deal with the quantisation scale factors when performing operations. The analysis of challenge 2 in [2] results in the following lower bound for the word length $n_p$ of the modulus $n$ after radix-2 FFT operations:

$n_p \geq v + (v-2) n_2 + n_1 + 3$

Where:

$v = \log_2 (N)$

$n_1 = b_1-1$, where $b_1$
is the number of bits of precision in the sequence samples

$n_2 = \left\lceil b_2 - \dfrac{v}{2} + \dfrac{1}{2} \right\rceil$
where $b_2$ is the hardware register size in an
equivalent plaintext implementation of the Fourier Transform. Equivalently, $n_2$
is the number of bits of precision required in the twiddle
factors to ensure the same precision in the result of the Fourier Transform as
a standard (in clear) hardware implementation.

Typical SAR applications perform multiple FFT operations, as well as other multiplications. For example, the Single Look Complex Image processing employs four 2-dimensional FFTs and 3 Hadamard products. Using the inequality above for one (1-dimensional) FFT operation, our analysis of the Single Look Complex Image processing results in a lower bound:

$n_p \geq 8v + 8(v-2) n_2 + n_1 + 3(n_3-1) + 24$

for the modulus word length, where $n_3$
is the word length associated with each of the inputs to the Hadamard
products. We expect values of the order $v=13$, $n_1 = 7$, $n_2=10$,
$n_3=16$, giving a lower bound of $n_p\geq
1060$. It is likely that the modulus word length is required to be
larger than this bound for security reasons so there is plenty of scope to perform Single Look Complex Image processing.

#### References

[1] Paillier,
"Public-Key
Cryptosystems Based on Composite Degree Residuosity Classes", EUROCRYPT,
Springer. pp. 223–238 (1999).

[2] Bianchi, T.,
Piva, A., Barni, M, "On the Implementation of the Discrete Fourier
Transform in the Encrypted Domain", IEE Transaction on Information and
Security , 86-97 (2009).

## No comments:

## Post a Comment