Dynamic Controller that Operates over Homomorphically Encrypted Data for Infinite Time Horizon

Under review for: IEEE Transactions on Automatic Control
Authors: Junsoo Kim, Hyungbo Shim, Kyoohyung Han
Abstract: In this paper, we present dynamic systems over encrypted data that compute the next state and the output using homomorphic properties of the cryptosystem, which has equivalent performance to the linear dynamic controllers over real-valued signals. Assuming that the input as well as the output of the plant is encrypted and transmitted to the system, the state matrix of the system is designed to consist of integers. This allows the proposed dynamic system to operate for infinite time horizon, without decryption or reset of the state. For implementation in practice, the use of cryptosystems based on Learning With Errors problem is considered, which allows both multiplication and addition over encrypted data. The effect of injecting errors during encryption is in turn controlled under closed-loop stability.

ArXiv version: available at https://arxiv.org/abs/1912.07362

Conference version: presented at IEEE Conference on Decision and Control (CDC), 2020
DOI: 10.1109/CDC42340.2020.9304509
Presentation Material: CDC2020_JunsooKim

Recorded video for presentation at CDC 2020

What is encrypted control?

Encrypted control is a recent approach for protecting control systems by encryption. It considers sensor measurements encrypted and transmitted to the controller, control operation directly performed over encrypted data, and the output transmitted to the actuator and decrypted for the plant.

Configuration of encrypted control system

By doing so, it can protect all control data in the network layer by encryption even when the operation is performed, and it operates without decryption key so that the secret key for decryption can be discarded from the controller, which leads to security enhancement.

How can it be realized?

Encrypted control can be realized with the use of homomorphic encryption. By homomorphic property of cryptosystem, it means there exist functions over ciphertexts such that their decryption outcome matches to the functions over plaintexts so that, it can perform arithmetic operation directly over encrypted messages.

In theory, any sort of operation can be performed for infinitely many times, thanks to the development of bootstrapping techniques of fully homomorphic encryption. However in practice, due to computational complexity of bootstrapping, the ability of addition and multiplication over encrypted data has been exploited for control operation.

Challenge: Implementing dynamic controllers using homomorphic encryption

Consider the following dynamic controller;

where $x(t)\in{\mathbb{R}^{\sf n}}$ is the state, $y(t)\in{\mathbb{R}^{\sf p}}$ is the input, and $u(t)\in{\mathbb{R}^{\sf m}}$ is the output. We assume that the closed-loop system is stable so that all signals are bounded. When it comes to recursive multiplication of the state $x(t)$ by non-integer state matrix $F$ , both the significant digits and the scale factor are recursively multiplied so that they both for the state increase as time goes by, even when the real state is bounded.

Increase of both significant digits and exponent (scale factor), due to recursive multiplication by non-integer numbers

And, without use of bootstrapping, it is not yet possible for encryption schemes to discard least significant digits, especially for infinitely many times. As a consequence, dynamic controllers implemented in this usual way have been incapable of running for an infinite time horizon.

This problem has been a common concern. Many results have considered only static or finite time operation. The use of bootstrapping has been considered but its computational complexity was a concern. And because of this problem, re-encryption for the state has been considered but it requires additional communication channel for the whole state to the actuator. And, periodic reset was considered, but it may result in performance degradation.

Conversion of state matrix: proposed method for encrypted dynamic control

Considering that the problem was due to recursive multiplication with non-integer numbers, we were motivated from systems having the state matrix as integers. For the controllers over quantized numbers with the state matrix consisting of integers without scaling, we observed that the scale factor for the state as well as its number of significant digits are fixed for the whole time, as long as the real state is bounded under closed-loop stability.

Motivation from systems having state matrix as integers

When the state matrix $F\in{\mathbb{R}^{{\sf n}\times{\sf n}}}$ consists of integers, there is no need of scale factor for the matrix $F$ unlike the other matrices. Then, despite the recursive multiplication by $F$ , the scale factor for the state and its number of significant digits do not increase as time goes by, as long as the real state $x(t)$ is bounded under stability. It means that it can operate without discarding least significant digits, so that in terms of encryption, it can be implemented using only addition and multiplication over encrypted data, to operate for an infinite time horizon.

With this motivation, our approach for encrypted dynamic control is to convert the given non-integer state matrix to integers, without use of scaling.

Proposed approach: Conversion of state matrix

First, considering the output equation $u(t)=Hx(t)$ , let’s add $-RHx(t)$ at the right hand side of the state update equation so that it converts the (outward) state matrix as $F-RH$ , and compensate the difference by the term $Ru(t)$ , which is considered as auxiliary input of system. Then, by coordinate transformation $z(t)=Tx(t)$ , we suggest that the state matrix be converted to the form $T(F-RH)T^{-1}$ . Now the question is: Is it always possible to have this converted matrix as integers?

Existence of (T,R) for converting state matrix

As the above Lemma, our answer is yes. Given any pair $(F,H)$ , there exist $(T,R)$ such that the converted state matrix $T(F-RH)T^{-1}$ can be set as integers. Then, how to find the matrices $(T,R)$ in practice?

First, without loss of generality, we may assume that the pair $(F,H)$ is observable. If it is not, we can consider Kalman observability decomposition for the controller and take the reduced observable sub-system which has the same input-output relation.

Next, with the observability, we can find the matrix R with pole-placement techniques such that the eigenvalues of $F-RH$ are all integers.

Finding the matrix R with pole-placement

Then, by transformation to Jordan canonical form we can obtain the converted matrix consisting of integers, since the eigenvalues appears at the diagonal. Hence, given any dynamic controller we can convert the state matrix to integers, without scaling.

The transformation T to Jordan canonical form yields the converted state matrix consisting of integers.

Now, we can apply the observation, for systems having state matrix as integers, to the converted controller as the same. With the state matrix converted to integers, the controller can operate with fixed scale for the whole time. Here, we note that the controller output as auxiliary input for the state update equation, which was mentioned as the term $Ru(t)$ while converting the state matrix, is regarded as an external input of the controller as well. It means that, in terms of encryption, it is regarded as a newly encrypted signal transmitted from the actuator.

Implemented dynamic controller over $({\mathbb{Z},+,\times})$ , where the term $\lceil {\sf s}^2 \cdot \overline u (t) \rfloor$ is regarded as external input

Implemented dynamic controller over $({\mathbb{Z},+,\times})$ , where the term $\lceil {\sf s}^2 \cdot \overline u (t) \rfloor$ is regarded as external input

Finally, we have the main theorem. Based on the conversion, linear dynamic controllers can be implemented over encrypted data to operate for an infinite time horizon with equivalent performance, without decryption, reset or bootstrapping for the state, using only addition and multiplication over ciphertexts.

Q. The proposed method still make use of re-encryption, doesn’t it?

Unfortunately, yes. However, one of the contribution of this work is that it make use of re-encryption of the controller output, rather than re-encrypting the controller state.

Re-encryption of state enables operation for infinite time horizon, but…

If re-encryption of the whole state were assumed, implementing dynamic controllers would be straightforward. The main problem was due to recursive operation for the encrypted state without decryption, but in case of decrypting and re-encrypting the whole state for each iteration, the operation of controller becomes non-recursive, in terms of the number of operations for each newly encrypted messages. However, we do not consider this as a solution, which is mainly because it heavily relies on the presence of decryption key, and it will increase network throughput proportionally to the state dimension.

Instead, we make use of re-encryption of controller output.

Instead, in this work, we have considered re-encryption of controller output. This is based on the rationale that transmission of the output to the decrypting device is necessary for the control, so that re-encrypting and transmitting back will be possible as long as the communication is bi-directional.

It would be better if the method does not use any re-encryption, but for this, we would like to leave a note that our next result for the next submission does not re-encrypt any portion of the state or the output.