{'fraction_non_alphanumeric': 0.04505831550910045, 'fraction_numerical': 0.010876145122886314, 'mean_word_length': 4.241010998307953, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Designing Optimal Key Lengths and Control Laws for Encrypted Control Systems based on Sample Identifying Complexity and Deciphering Time

In the state-of-the-art literature on cryptography and control theory, there has been no systematic methodology of constructing cyber-physical systems that can achieve desired control performance while being protected against eavesdropping attacks. In this paper, we tackle this challenging problem. We first propose two novel notions referred to as sample identifying complexity and sample deciphering time in an encrypted-control framework. The former explicitly captures the relation between the dynamical characteristics of control systems and the level of identifiability of the systems while the latter shows the relation between the computation time for the identification and the key length of a cryptosystem. Based on these two tractable new notions, we propose a systematic method for designing the both of an optimal key length to prevent system identification with a given precision within a given life span of systems, and of an optimal controller to maximize both of the control performance and the difficulty of the identification. The efficiency of the proposed method in terms of security level and realtime-ness is investigated through numerical simulations. To the best of our knowledge, this paper first connect the relationship between the security of cryptography and dynamical systems from a control-theoretic perspective.

with respect to efficiency, reliability, and sustainability [1], [4]. Meanwhile, cyber-physical systems often face security threats in exchange for the advantages because, in general, they communicate with a public and untrustworthy computer, e.g., cloud, over insecure channels for decision making.
One of major security threats is the eavesdropping attack that tries to disclose confidential information of cyber-physical systems [5]. Once an adversary complete the attacks, more destructive and undetectable attacks can be designed based on a target system model learned by the disclosed information [6]. Therefore, it is crucial for realizing secure cyber-physical systems to prevent eavesdropping attacks.
To fulfill this objective, we definitely need a measure for quantifying the security level against the attacks. Some studies have employed information-theoretic measures, such as mutual information and directed information, for designing estimators and controllers with information leakage constraints under the presence of eavesdroppers [7]. Additionally, differential privacy [8], another well-known measure used in information community, has been adopted for private filtering and controls of dynamical systems [9], [10]. However, these existing measures are not suitable for dynamical systems because it is not clear that the systems should satisfy how the level of security. Furthermore, a controller design method based on the measures has an intrinsic trade-off between the security and quality of controls due to noise injection [7], [9]. It should be noted here that some recent papers have proposed controltheoretic security quantities [3], [11]- [15]. However, the quantities cannot measure the security level against eavesdropping attacks because they focus on other attacks.
Encrypted control [16] is the state-of-the-art technology for preventing eavesdropping attacks without noise injection. Contrary to the information-oriented methods, the performance degradation in encrypted control systems can be ignored by increasing a key length of cryptosystem [17]. Moreover, for a small key length, appropriate quantizers mitigate the quantization errors due to encryption [18], [19]. Thus, encrypted control is a promising framework for achieving the superior security and control performance of cyber-physical systems. In fact, various encrypted control methods have been developed recently by using partially, somewhat, and (leveled) fully homomorphic encryption [20]- [29]. Moreover, their feasibility has been verified through implementation to a drone [30], fog-computing environment [31], and field-programmable gate array [32]. However, the security level of encrypted control systems has not been analyzed and quantified.

B. Contribution
This study considers an attack scenario that an adversary eavesdrops and then identifies the system matrix of a stochastic closed-loop system with an encrypted controller by using collected encrypted-data. Under this scenario, we aim to answer the following quenstions: • What is the optimal controller to make the identification accuracy within a certain value, and subsequently, • what is the optimal key length needed to secure the closed-loop system within a life span of the system? To this end, we introduce two novel security quantities, sample identifying complexity and sample deciphering time. This type of quantification is not reported in any papers on cryptography.
The sample identifying complexity is derived as a lower bound for the total variance, i.e., the inverse of precision, of Bayesian estimation by an adversary. The sample deciphering time is computation time for breaking encrypted data without a secret key to obtain a data set for the estimation. The security in this study is defined based on these quantities. Roughly speaking, we say an encrypted control system is secure if the adversary cannot identify the system matrix with a certain precision within a life span of the system. The formal definition of the security will be described later.
The sample deciphering time is introduced in two cases with static-key encryption and dynamic-key encryption. Statickey encryption is traditional public-key encryption of which the key pair is identical throughout the communication. In contrast, a key pair in dynamic-key encryption [33] is updated at a short time interval, e.g., a sampling period. Although dynamic-key encryption would improve the security level of encrypted control systems, its security has not yet been proved. We extend the dynamic-key encryption scheme in [33] and provide a security proof of the extended scheme.
Using the security quantities, we formulate a design problem of optimal key length and controller. The optimal controller is designed to maximize the sample identifying complexity. In other words, the controller maximizes the difficulty of the system identification. More interestingly, such a controller is provided as the standard stochastic cheap controller improving the stability degree of a closed-loop system. This fact means, in controller design, there is no trade-off between the security level and the control performance.
After designing the optimal controller, we design the optimal key length to secure an encrypted control system. The optimal key length is obtained as the minimum key length to make the sample deciphering time longer than the system's life span. This key length is beneficial for reducing implementation costs of an encrypted control system while keeping the security level because the size of key length has a trade-off between ciphertext strength and computation costs of encryption and decryption algorithms.

C. Outline
Section II summarizes notations and a definition of homomorphic encryption. The ElGamal encryption, an example of a multiplicative homomorphic encryption scheme, is also introduced. Section III describes the attack scenario considered in this study. We define the security of encrypted control systems and formulate a design problem of the optimal key length and controller. Section IV proposes sample identifying complexity and sample deciphering time. They are used to understand the relationships among a key length, controller, and the number of samples for system identification. Section V provides the solution to the problem based on the security quantities. Additionally, we show how the security quantities can be used for other design problems in encrypted control systems. Section VI demonstrates the validity of the proposed method by numerical simulations. Section VII concludes this paper and presents some remarks on the results of this study.

A. Notation
The sets of real numbers, integers, security parameters, public keys, secret keys, plaintexts, and ciphertexts are denoted by R, Z, S, K p , K s , M, and C, respectively. We define the sets of integers Z + := {z ∈ Z | 0 ≤ z} and Z n := {z ∈ Z | 0 ≤ z < n}. The set of n-dimensional real column-vectors is denoted by R n , and that of m-by-n real-valued matrices is denoted by R m×n . The ith element of a vector v ∈ R n is denoted by v i , and the 2 norm and the maximum norm of v are denoted by v and v ∞ , respectively. The ith column vector and (i, j) entry of a matrix M ∈ R m×n are denoted by M i and M ij , respectively. The max norm and column stack vector of M are defined by M max := max i,j {|M ij |} and vec(M ) := [M 1 · · · M n ] , respectively. The cardinality of a set A is denoted by |A|. The Gaussian distribution with a mean µ and a variance-covariance matrix Σ is denoted by N (µ, Σ). The probability density function of N (µ, Σ) is denoted by f (x; µ, Σ).
Definition 1: Let A be a finite set and X be a random variable. If Pr(X = a) = 1/|A|, ∀a ∈ A, then we say X follows the discrete uniform distribution over A and is denoted as X ∼ U(A).
Definition 2 (negligible function [34]): We say a function : Z + \ {0} → R is negligible if for every positive integer c > 0 there exists N ∈ Z such that | (n)| < n −c holds for all n > N .

B. Homomorphic encryption and its example
This section describes the definition and example of homomorphic encryption to introduce the encrypted-control framework. One can refer [35] for the detailed survey of homomorphic encryption.
A public-key encryption scheme is a triplet (Gen, Enc, Dec), where Gen : S → K p × K s : k → (pk, sk) is a key generation algorithm, Enc : K p × M → C : (pk, m) → c is an encryption algorithm, Dec : K s × C → M : (sk, c) → m is a decryption algorithm, k is a security parameter, e.g., a key length, and (pk, sk) = Gen(k) is a pair of public key and secret key. Enc and Dec perform elementwise for a vector and a matrix. Public-key encryption schemes must satisfy Dec(sk, Enc(pk, m)) = m for all m ∈ M and (pk, sk) generated by Gen.
Definition 3: We say (Gen, Enc, Dec) is multiplicative homomorphic encryption if Dec(sk, c c ) = mm for all m, m ∈ M and c, c ∈ C satisfying Enc(pk, m) = c and Enc(pk, m ) = c , where : C × C → C is a binary operation over C. Similarly, additive homomorphic encryption is defined with : C × C → C.
An example of multiplicative homomorphic encryption includes the ElGamal encryption [36]. Its algorithms are Gen : k → (pk, sk) = ((p, q, g, h), s), Enc : (pk, m) → c = (g r mod p, mh r mod p), and Dec : (sk, (c 1 , c 2 )) → c 1 −s c 2 mod p, where q is a k bit prime, p = 2q + 1 is a safe prime, g is a generator of a cyclic group G := {g i mod p | i ∈ Z q } = M ⊂ Z p \{0} such that g q mod p = 1, h = g s mod p, C = G 2 , and r, s ∼ U(Z q ). Additionally, multiplicative homomorphism is Dec(sk, Enc(pk, m) * Enc(pk, m ) mod p) = mm mod p, where * is the Hadamard product.

III. ATTACK SCENARIO AND PROBLEM SETTING
Consider a plant described by the discrete-time stochastic linear system where t ∈ Z + is a time step, x ∈ R n is a state, u ∈ R m is an input, and w ∈ R n is an i.i.d. random variable following the Gaussian distribution N (0, L −1 ) with the zero vector 0 and a precision matrix L. Assume that (A p , B p ) is controllable, and the initial state is given by x 0 ∼ N (0, L −1 ). A state-feedback controller which is installed on a computer over a network, e.g., cloud, is employed for stabilizing (1), where a feedback gain F is to be designed. Note that output-feedback controllers can also be considered although we use a state-feedback controller for the simplicity of discussion. The networked control system with (1) and (2) has risks of eavesdropping attacks because the plant and controller communicate with each other via network links. This study considers encrypted control proposed in [20] as a secure control framework against the attacks. An encrypted control system includes an encrypter Enc and decrypter Dec in its feedback loop; see Fig. 1. Note that a sensor (encrypter) and an actuator (decrypter) in this study are assumed to be installed on a unified computer of plant side. An encrypted controller of (2) with multiplicative homomorphic encryption of Definition 3 is defined as where c F = Enc(pk, F ), and c xt = Enc(pk, x t ). An input is restored as and it approximately equals to an input of (2) if quantization errors caused by the encryption are sufficiently small. Thus, the dynamics of the encrypted control system is obtained as By using an encrypted-control framework, conventional controllers can be used while their gains and signals over network links are encrypted. We consider an attack scenario to identify the dynamics of the encrypted control system. The dynamics must be secret even though an adversary eavesdrops and deciphers the ciphertexts because he/she would exploit it as an initial step for executing more sophisticated attacks, such as stealth attacks. As a result, the total security level of encrypted control systems can be improved by preventing the identification attack. The worst scenario for a defender is Bayesian estimation of the dynamics, i.e., A in (3), with deciphered data because the estimation is the best in terms of the variance of estimator. This attack is formulated as follows: Definition 4: An adversary follows the protocol below: 1) Given T ∈ Z + , collect D Enc := {Enc(pk, x t )} T t=0 by eavesdropping attacks. based on his/her knowledge about a target control system. Then, estimate a posterior probability p(A|D) = f (vec(A);μ(T ),Λ −1 (T )) by Bayesian estimation with p(A) and D. An adversary aims to identify a system matrix A as a posterior probability p(A|D), and an estimationÂ is given by vec(Â) =μ(T ).
Is the encrypted control system secure under what conditions in these settings? In this paper, the system is said to be secure if identification of A with a certain precision is impossible within a given period. In particular, the security in the attack scenario is defined as follows, where we use the fact that the trace of a variance-covariance matrix can be used for a measure of the precision of the estimation since it represents the total variance: Definition 5: Let τ c be a life span that represents a period until the system (1) is replaced, and γ c be an acceptable variance against adversary's estimation. Define τ (T, k) := time for executing step 2) in Definition 4. The encrypted control system in Fig. 1 is said to be secure if there does not exist T ∈ Z + satisfying whereΛ(T ) is defined in Definition 4. If not, the system is said to be unsecure.
In Definition 5, τ c and γ c are the design parameters while the key length k and the controller F are the implicit decision variables. As τ c is taken larger for protecting the system during a longer period, the key length k would be longer [37]. Although the longer k is beneficial for ciphertext strength, it is not desirable in terms of implementation costs because the online computation costs of Enc and Dec with longer k has to be larger [38]. In other words, the choice of a longer key length increases economic costs since a high performance computer is required for keeping the real-time operation of the control system. Since there is such a trade-off, we will design F for making the key length as short as possible. Later we will show that the ease of identification relates to the stability of A in (3). This implies that the choice of a good controller F can make the key length k shorter while making the precision of identification is within the tolerance γ c . In this light, we consider the following design problem for ensuring the dynamical system security.
Problem 1: Consider the encrypted control system in Fig. 1 under the attack scenario in Definition 4. Find F and a minimum k ∈ (0, ∞) such that the system is secure defined in Definition 5.
An essential question behind Problem 1 is how the key length k, controller F , and the number of deciphered samples T relate to the security. The factors k and T are often taken into account in cryptography [34] and sample complexity of computational learning theory [39], respectively. Unlike to this, we have to explicitly consider the controller gain as well as those two factors because the system of our interest has dynamics. In view of this, Problem 1 lies in between cryptography, learning theory, and control theory. In the next section, we analyze the relation among k, T , F , and the security.
Remark 1: Additive homomorphic encryption can also be used instead of using multiplicative homomorphic encryption. In such a case, an encrypted controller is defined as (F, c xt ) → c ut = [F 11 c x1,t · · · F 1n c xn,t , · · · , F m1 c x1,t · · · F mn c xn,t ] , and an input is given by u t = Dec(sk, c ut ). Note that the encrypted controller has an unencrypted parameter F , unlike one with multiplicative homomorphic encryption.
Remark 2: Although most algorithms to recover D from D Enc would include integer operations rather than floating-point operations, the computational ability for integer operations in this study is assumed to be quantified by FLOPS.
Remark 3: So far we have assumed that an adversary can exactly recover D from D Enc without quantization errors caused by the encryption. In practice, Enc and Dec in Fig. 1 have to be equipped with an encoder Ecd : R → M and decoder Dcd : M → R that convert real numbers (F, x t ) to a plaintext space because the most existing homomorphic encryption schemes rely on arithmetic operations over integers. Therefore, quantization errors are always involved in the deciphered samples. However, for simplifying the following arguments, we do not consider the error, which is the worst case scenario for the defender. The details of the quantization error analysis is described in Appendix A.
Remark 4: An adversary of this study is assumed to estimate a system matrix A in (3). One may think that considering an estimation attack for a controller gain F in (2) is also important. The attack can be treated as solving simultaneous equations for F with N independet data sets of x and u. In such a case, the encrypted control system is said to be secure if τ (N, k) ≤ τ c is satisfied.

IV. SAMPLE IDENTIFYING-COMPLEXITY CURVE AND SAMPLE DECIPHERING-TIME CURVE
This section introduces two novel quantities referred to as sample identifying-complexity curve and sample decipheringtime curve to clearly understand the relationship among k, T , F , and the security.

A. Sample identifying-complexity curve
We introduce the following lemma that connects the notion of the security in Definition 5 to the dynamics of (3).
Lemma 1: Consider the system in Fig. 1 under the attack in Definition 4. Suppose A in (3) is Schur. Then, the parameters of a posterior probability p(A|D) in Definition 4 are described asΛ Besides, the following relations hold: Proof: See Appendix C. Note here that the term t i=0 A i L −1 (A i ) is the weighted finite-time controllability gramian of (3). Lemma 1 shows that the quantification E tr(Λ −1 (T )) in (4) can be bounded from below by using the trace of the gramian. We refer to the bound γ as sample identifying-complexity curve due to the acknowledge that the curve captures the complexity of the identification of vec(A) with |D| = T + 1 samples. It should be noted here that the system trajectory x t explicitly depends on the controller gain F . Thus, the curve is a function of T and F . We can see the following two observations from (8).
• Dependency of F : The sample identifying complexity is larger if F makes the stability degree measured by the trace of the controllability gramian smaller. This is natural because as the system more stable, the amount of information, i.e., the system output driven by the initial state and external input w, can be less, thereby making the identification more difficult. • Dependency of T : The sample identifying complexity is larger if the number of deciphered samples lesser. This implies that the identification is difficult for the adversary by decreasing leaked data samples. Fig. 2(a) depicts the schematic picture of the curve γ(T, F ).
Although F is an m-by-n matrix, in the figure larger F implies the one making A in (3) more stabilized.
When a sample size T is sufficiently large, the summation terms in (5) and (6) should be much larger than the terms Λ and Λµ, respectively. Then, the estimatesΛ andμ satisfy the following relation to an estimation error.
Proof: See Appendix D. The equalities (8) and (9) show that the sample identifying complexity is a lower bound of a type of estimation error with a sufficiently large samples. Thus, it is reasonable that the difficulty of identifying a system matrix is quantified by the sample identifying complexity.
For the following argument, we show a special case when L −1 = σ 2 I and the adversary has no prior information about the system, i.e., tr(Λ) = 0.
Then, the following corollary immediately follows from Lemma 1: (10) hold, then γ in (8) satisfies Proof: See Appendix E. The sample identifying-complexity curve connects the relationship between the sample complexity E tr(Λ −1 (T )) in Definition 5 and a pair (T, F ). Before showing how this is useful for solving Problem 1, we next show a different curve that connects the security to T and a key length k.
Remark 5: We have introduced the expectation of a lower bound ofΛ −1 because the computation of the inverse ofΛ, in general, requires a large number of computation resources, and it cannot be computed in advance of the control system's operation. A similar approach can be found in [40]- [43], and the studies employed the inverse of a trace of the Fisher information matrix as a lower bound of the precision of general unbiased estimator for dynamical systems. Unfortunately, the approach is not specialized in our attack scenario, i.e., it would give a loose lower bound of tr(Λ −1 ), and the lower bound cannot be computed without the system's operating data.

B. Sample deciphering-time curve
In this paper, we refer to τ (T, k) in (4) as sample deciphering-time curve due to the acknowledge that the curve captures the computation time for deciphering the T + 1 ciphertexts of D Enc . One might consider that the deciphering time does not depend on the number of samples. This is true in a traditional setup of public-key encryption, referred to as static-key encryption in this paper, where the keys used for encrypting all samples are identical [34]. On the other hand, when the keys of individual samples are completely different, in other words, dynamic-key encryption is used [33], the deciphering-time clearly depends on the number of samples. We show an explicit representation of τ (T, k) for each encryption scheme, and show an advantage of the dynamic case in terms of the security in Definition 5.
1) Static-key case: As a multiplicative homomorphic encryption scheme, this study uses the ElGamal encryption E described in Section II. The security of E, i.e., the difficulty of breaking the encryption, is based on the hardness of the discrete logarithm problem for G that is defined as follows: Definition 6 (discrete logarithm problem [44]): Let G be a group with a binary operation •. The discrete logarithm problem (DLP) for G is to determine, for any given elements g, h ∈ G, an integer x satisfying Additionally, the assumption that there does not exist a polynomial-time algorithm to solve the DLP is called the discrete logarithm assumption.
In the field of cryptography, the discrete logarithm assumption is widely believed to be satisfied. The ElGamal encryption achieves indistinguishability against chosen-plaintext attacks (IND-CPA) under the decisional Diffie-Hellman (DDH) assumption [34] that is a variant of the discrete logarithm assumption. The security level of IND-CPA means that an adversary can obtain no information about plaintexts from ciphertexts. Hence, an adversary must solve the DLP for G to obtain D from D Enc . The majority of algorithms for solving the DLP for a finite field F η with a modulus η are subexponentialtime algorithms of which computation time is described as where v and d are algorithm parameters [44]. For instance, the general number field sieve, the known fastest classical subexponential-time algorithm, has v = 1/3 and d = (64/9) 1/3 in (12) [37]. Thus, we use  as the computation time for deciphering a ciphertext of E with a key length k in the following. Note that G ⊂ F p , and L(k) satisfies L(k) ≤ L 1/3,(64/9) 1/3 (p) since p ∈ (2 k , 2 k+1 ). Therefore, (13) is stricter with a defender than (12). We next show the sample deciphering time of the static-key encryption. Since a single key pair is used for encrypting all the samples throughout a life span of the encrypted control system, the adversary has to break only one ciphertext for finding the secret key. Once the secret key is found, he/she can decrypt all ciphertexts of D Enc immediately. Thus, the sample deciphering time in this case can be described as where Υ is defined in Definition 4. For satisfying the second inequality of (4), the key length k will be long because even only one ciphertext cannot be broken during a given period τ c . Although it is natural from the ordinary manner in cryptography, the online computation costs of the associated Enc and Dec in Fig. 1 must be heavy, which is not desirable for real-time controls. Remark 6: The number field sieve is used for solving not only the DLP but also the prime factorization problem. Thus, (14) also enables to estimate the computation times for breaking other encryption schemes, such as RSA [45] and Paillier encryption [46]. Moreover, we can change L(k) according to any given encryption scheme such as the LLLalgorithm for lattice and fully homomorphic encryption, and, therefore, the sample deciphering time can be obtained for any encryption scheme as well.
2) Dynamic-key case: One way to reduce the online computational costs of Enc and Dec while keeping the sample deciphering time long is to regenerate a secret key at each sampling time. However, this approach is not suitable for realtime controls due to the high computational costs. As an alternative approach, we employ the dynamic-key encryption [33] that is an augmented concept of public-key encryption. The overview is as follows: First, give a key pair by Gen at the initial time. The secret key at time t + 1 is computed by a simple updating rule based on a modulus operation with a random number and the secret key at time t. At the same time, a public key and ciphertexts of controller parameters are also updated to keep the correctness, i.e., the property that a ciphertext is decrypted correctly, with the new secret key. Due to the time-dependency of this dynamic-key encryption, the adversary would have to break T + 1 ciphertexts to collect D from D Enc . However, the security proof of the dynamickey encryption has not yet been shown. Additionally, the dynamic-key encryption refreshes only the second element of ciphertext, and so, the first element remains the same value. In the following, we extend the dynamic-key encryption in [33] to update all components of ciphertext and provide the security proof of the scheme.
The dynamic ElGamal encryption in this study is constructed as follows: Definition 7: Dynamic ElGamal encryption is a tuple E dyn := (Gen, Enc, Dec, T K , T C ) with the transition maps T K : ((p, q, g, h), s) → ((p, q, g, hg s mod p), s+s mod q), where r , s ∼ U(Z q ).
Remark 7: The random number s needs to be shared secretly between a sensor an an actuator if they are installed on different places. This can be achieved by using a standard symmetric-key encryption scheme, such as AES. Similarly, a plant can transmit r and s to an encrypted controller secretly.
In Definition 7, T K and T C imply updating rules for a key pair and ciphertext, respectively. T C of the dynamic ElGamal encryption updates both c 1 and c 2 unlike to the scheme in [33]. We first show that the correctness and multiplicative homomorphism of our encryption scheme are satisfied even though the transition map is modified.
Proposition 1: Let k be a key length, (pk 0 , sk 0 ) = Gen(k), and c 0 = Enc(pk 0 , m). If (pk t+1 , sk t+1 ) = T K (pk t , sk t ) and c t+1 = T C (c t ), then Dec(sk t , c t ) = Dec(sk t , Enc(pk t , m)) = m mod p for all m ∈ M and t ∈ Z + . Furthermore, the multiplicative homomorphism Dec(sk t , c t * Enc(pk t , m ) mod p) = mm mod p is satisfied for all m, m ∈ M and t ∈ Z + .
Proof: See Appendix F. Due to the homomorphism, the dynamics of the encrypted control system in Fig. 1 with the dynamic-key encryption scheme E dyn can be regarded as (3) while the key pair and ciphertexts are dynamically updated.
We next show an explicit representation of the sample deciphering-time curve τ (T, k) when E dyn is used. To this end, we show a cryptographic property of the transition maps T K and T C .
Proposition 2: Let k be a key length, (pk 0 , sk 0 ) = Gen(k), m ∈ M, and c 0 = Enc(pk 0 , m). A key pair and ciphertext are updated by (pk t+1 , sk t+1 ) = T K (pk t , sk t ) and c t+1 = T C (c t ), respectively. Suppose an adversary knows pk t , sk t , and c t and can solve the DLP for G. There exists a negligible function (k) such that for all t ≥ 1, whereŝk t+1 andŝk t−1 are adversary's estimations of sk t+1 and sk t−1 , respectively.
Proof: See Appendix G. Proposition 2 implies that if we use the dynamic ElGamal cryptosystem, probability that an adversary can obtain the secret keys at time t + 1 and t − 1 is negligibly small even though he/she knows all information at time t including the information given by solving the DLP for G as long as the updates of a key pair and ciphertexts are performed secretly. This fact derives the following proposition on the security of our encryption scheme.
Proposition 3: E dyn satisfies IND-CPA at time t under the DDH assumption even though an adversary knows {pk i } t−1 i=0 and {sk i } t−1 i=0 . Proof: See Appendix H. From Propositions 2 and 3, an adversary cannot obtain any information about a secret key and plaintext for all time t even though he/she has secret keys at time t − 1 and t + 1. Thus, he/she must solve the DLP for G T + 1 times to collect D from D Enc . Therefore, the computation time for deciphering ciphertexts of D Enc is linearly increased from τ (0, k) as a sample size of D Enc increases if E dyn is used. Thus, the following lemma is derived: Lemma 2: A sample deciphering-time curve of the encrypted control system in Fig. 1 with E dyn in Definition 7 is given as where L(k) and Υ are defined in (13) and Definition 4, respectively.
Notice that the sample deciphering time of the static-key case corresponds to (15) with T = 0. It should be noted here that the curve τ (T, k) monotonically increases as either of T and k increases. A schematic picture of the sample deciphering-time curve is shown in Fig. 2(b).
In conclusion, for the encrypted control system in Fig. 1 with E dyn in Definition 7, we have introduced the two curves: • γ(T, F ) in (8) that characterizes the difficulty of identifying the system (3), and • τ (T, k) in (15) that quantifies the difficulty of deciphering encrypted samples.
In the next section, we show how these two curves are useful for solving Problem 1.

V. OPTIMAL KEY LENGTH AND CONTROLLER DESIGN
For simplifying the following discussion, we suppose that the assumptions in Corollary 2 hold. From Definition 5 and Corollary 2, the following immediately follows: Given k and F , if there does not exist T satisfying where γ and τ are respectively in (11) and (15), then the encrypted control system in Fig. 1 with E dyn in Definition 7 and (k, F ) is secure. An idea for designing a key length and controller based on the sample identifying-complexity curve γ and sample deciphering-time curve τ is as follows: • Controller design: Note from (11) that the identification variance monotonically decreases as the number of samples increases because the finite-time controllability gramian is positive definite. Thus, we should design the controller F that maximizes the minimum time step T satisfying γ(T , F ) < γ c . • Key length design: The computation time for deciphering |D Enc | = T + 1 ciphertexts is τ (T , k), and the time monotonically increases in a key length k. Considering that a key length is desirable to be as small as possible from the perspective of computational costs, it should be designed as the minimum key length k satisfying τ (T , k ) > τ c .
The pair (k , F ) is a solution to Problem 1 since there does not exists T satisfying (16) with (k , F ). Note here that the controller F simultaneously minimizes the trace of W t in (17) of (3). Hence, the controller also improves the stability of the control system, which will be discussed later. In the following, the concrete design processes of k and F are described.

A. Controller design
Following the controller design step, we design F so that the minimum time step T satisfying the first inequality of (16) is as large as possible. From (7), this design can be solved by making the cost function (18) as small as possible. Since this is a finite-horizon stochastic linear quadratic regulator (s-LQR) design problem, an optimal solution is given as follows: Lemma 3: Consider the system (3) and J T in (18). Assume that B p is full column rank. Then, the control sequence and P T = I.
Proof: See Appendix I. Although the control (19) is optimal, the resultant controller has to be time-varying. Unfortunately, time-varying controllers are difficult to be used in the encrypted-control framework because controller parameters must be encrypted and stored in advance before controller operation due to the difficulty of encrypted controller parameters update. On the other hand, as T → ∞, the control law converges to u t = F x t with where P > 0 is the solution to the discrete-time algebraic Riccati equation Hence, as a suboptimal solution to make J T as small as possible, we use the static feedback gain F in (2). It is interesting that the standard stochastic cheap control (19) is a good solution from the perspective of the security. This fact clearly connects the notion of the security and classical control theory. Moreover, the fact means no trade-off between the security and the control performance exists in controller design under the adversary of Definition 4. In other words, whenever the defender wants F in (20) for improving closed-loop damping performance, the controller is also a good solution in terms of the security. Once F is designed, the minimum time step T satisfying the first inequality of (16) can be uniquely determined as follows: where W t is defined in (17). An illustrative interpretation of this optimization is shown by the red line in Fig. 2(a). It should be noted here that T in (21) can be determined for any controller as long as A in (3) is Schur. However, T in this case will be larger than the one when F in (20) is used. This choice, as we will show later, induces a longer key length. For tractable computation of E(T ), we introduce the following proposition.
Algorithm 1 Optimal design of encrypted control system with dynamic-key encryption Input: A p , B p , n, γ c , τ c , and Υ. Output: F and k . # Controller design.
). end while # Solve optimization problem of (22).  (21) can be reduced to O(T ), which facilitates the optimization problem (21). The obtained T is used for designing the minimum key length design problem, which is described in the next section.

B. Key length design
Suppose that T is given by (21). Following the key length design step, we find a minimum key length k such that the second inequality of (16) does not hold. It follows from the second inequality of (16) and τ (T, k) in (15) that the key length minimization can be summarized as An illustrative interpretation of this optimization is shown by the red line in Fig. 2(b).
In conclusion, we have the following the theorem. Theorem 1: Consider Problem 1 with the assumptions in Corollary 2. The controller F and the minimum key length k are given by (20) and (22), respectively. Then, the encrypted control system in Fig. 1 with the dynamic-key encryption scheme E dyn in Definition 7 is secure.
Proof: See Appendix K. A pseudocode of the design algorithm is summarized as Algorithm 1.

C. Other design problems
The parameters of a sample identifying-complexity curve γ(T, F ) and a sample deciphering-time curve τ (T, k) are a time step T , controller F , and key length k. The optimal key length k in Problem 1 is derived under a given controller F . Similarly, by fixing T or k, the curves can be used for formulation of other design problems.
For example, a problem to design a controller gain F under a given key length k is a reverse problem of Problem 1. A degree of freedom in design of F in this problem is restricted by k through the minimum time step T satisfying τ (T , k) > τ c . That is, a defender wants to find F achieving a certain degree of stability of a control system, which is implicitly parameterized by k.
Furthermore, a problem to design F and k under the given time step T = τ c /T s is a variant of Problem 1, where T s is a sampling time. An adversary in the variant is weaker than one in Problem 1 because he/she uses all data within the life span for the estimation. Thus, a defender would be required to design a finite-horizon controller maximizing γ(T, F ) and smaller key length than the solution to Problem 1.

Consider (1) with
Let a controller F in (2) be given so that the poles of A in (3) are assigned to ±0.99. We first show how the Bayesian estimation in step 3) of Definition 4 performs. Let µ = 0 and Λ = I. For each T ∈ {1, . . . , 5000}, we perform the estimation by using a data set D. Fig. 3 shows the result, where the blue lines are the estimated mean values (Â 11 , . . . ,Â 22 ), and light-blue areas are the 95 % confidence intervals determined byΛ. The true values of A are denoted by the dashed lines. We can see from these figures that the precision of adversary's estimation improves as the number of samples increases. Fig. 4 depicts the sample identifying-complexity curves γ(T, F ) in (8) for different choices of the gains F that assigns the poles of A to ±0.99, and F in (20). Let the acceptable variance in (16) be chosen as γ c = 10 −6 , which is denoted by the dashed line in the figure. Then, the minimal time step T satisfying γ(T , F ) < γ c is 18586 while that for F is 384473. The time steps are denoted by T F and T F , respectively. This result shows that the stochastic cheap controller (20) improves sample identifying complexity of the closed-loop system.
We next compute the sample deciphering-time curves τ (T F , k) and τ (T F , k) in (15), and τ (0, k) in (14) for a comparison purpose. Note here that the first (resp. second) represents the time for deciphering T F + 1 (resp. T F + 1) ciphertexts of the dynamic ElGamal encryption E dyn in Definition 7 while the third represents that for deciphering any ciphertext of the normal ElGamal encryption E. Note that the third case is irrelevant to controllers because the encryption is static-key encryption. Fig. 5 illustrates those three curves for k. Let a life span and a computer performance be chosen  as τ c = 1.5768 × 10 9 s (50 years), which is denoted by the dashed line in the figure, and Υ = 442 × 10 15 FLOPS, which is the performance of Fugaku supercomputer 1 . Then, by solving (22), the optimal key length for each cases is determined to 641 bit, 734 bit, and 1091 bit. This result implies that the simultaneous use of the dynamic-key encryption and the s-LQR optimal controller can drastically reduce the key length while keeping the security level of the encrypted control system, thereby reducing its computation costs. Finally, we show how the differences of those three key lengths appear in the online computation times. All the computations are done by using MacBook Pro (macOS Big Sur, 2.3 GHz quad-core Intel Core i7, 32 GB 3733 MHz LPDDR4X) with C++. The results are shown in Table I. Fig. 6 depicts the average computation times of Enc, Dec, and T K , which are performed on a plant side. Their total times in E, E dyn with F , and E dyn with F were 2.24 ms, 0.94 ms, and 0.61 ms, respectively. This result confirms that the computation time is decreased according to reducing the optimal key length by using the dynamic-key encryption and the optimal controller. Although one may think that the resultant differences are not significant, the difference will be more significant for larger-dimensional systems. This is because an online computation of encrypted control systems includes n times of Enc and mn times of Dec on a plant side. Hence, for larger-dimensional systems, the proposed design methodology would be helpful for real-time controls while keeping the security level theoretically.

VII. CONCLUSION
This paper addressed a systematic design of encrypted control systems aginst eavesdropping attacks to construct secure cyber-physical systems. To quantify the security level of encrypted control systems, the novel security notions, sample identifying complexity and sample deciphering time, were proposed. The sample identifying complexity characterizes the difficulty of system identification by means of a controllability   gramian of a closed-loop system. Additionally, the sample deciphering time represents the computation time for breaking ciphertexts to collect a data set for the identification. Combining the notions, the optimal controller was obtained by the traditional stochastic cheap controller that simultaneously maximizes the stability degree of a closed-loop system and the difficulty of the identification. Furtermore, the optimal key length was determined as the minimum key length enough to prevent the identification with a given precision within a life span of the system. The numerical simulations demonstrated that the optimal key length and controller effectively reduced the implementation costs of encrypted control systems while keeping their security level. In our best knowledge, this paper is the first work to reveal the relationship between the cryptographic security and dynamical systems in a control-theoretic manner. One might think that some papers already related security level and properties of control systems [3], [11]- [15]. However, these studies considered only the control-theoretic aspect of the impact of cyber-attacks, namely resilience, performance degradation, and detectability. In contrast, our approach connected the effect of eavesdropping attacks and the characteristics of dynamical systems taking the feasibility of the attacks into consideration in terms of a computation time.
In this paper, the precision of adversary's estimation was evaluated based on a variance, i.e., the second moment about a mean. However, we did not consider the first moment about the origin of the estimation. In fact, although the estimator (6) is a consistent estimator, it is not a non-baiased estimator. Hence, the adversary would obtain the estimates including a bias with a precision evaluated by the second moment. This means the security evaluation of this paper is strict with a defender. We will modify the proposed method to consider both the first and second moments.
Moreover, the estimation of system and input matrices of (1) rather than a system matrix of (3) will be considered. This would be achievable by rewriting (1) as The equation is the same form of (3), and thus, the discussions in this paper would be extended directly. We will also consider extending the security concepts to be used for more general encrypted control systems, namely dynamic output-feedback controllers and nonlinear plants. This can be achieved, for example, by using the input-output history feedback controller representation [47] and the Koopman operator [48]. The controller representation realizes a dynamic controller as a matrixvector product form such as (2). The Koopman operator lifts a finite-dimensional nonlinear system to an infinite-dimensional linear system. The proposed scheme can be applied for such systems up to an error due to the truncation of the system dimension.

A. Quantization in encrypted control
This section describes the properties of quantization errors in encrypted control systems with a linear controller where Φ ∈ R α×β is a controller parameter matrix, ξ ∈ R β is a controller input vector, which consists of a controller state and plant output, and ψ ∈ R α is a controller output vector, which consists of a controller state update and plant input. In this case, an encrypted controller of (23) with the ElGamal encryption E = (Gen, Enc, Dec) is given as where c Φ = Enc(pk, m Φ ), c ξ = Enc(pk, m ξ ), c Ψij = c Φij * c ξj mod p, and m Φ and m ξ are plaintexts of Φ and ξ, respectively. For implementation of the encrypted controller (24), ξ and Φ must be encoded to plaintexts before encryption and be decoded to real numbers after decryption using an encoder and decoder because a plaintext space is not a set of real numbers. This study uses the following encoder Ecd ∆ : R → M and decoder Dcd ∆ : M → R with a sensitivity ∆ > 0: where R <0 := {x ∈ R | x < 0}, Z >q := {z ∈ Z | q < z}, and 1 A (·) is an indicator function that outputs 1 if its argument belongs to a set A; otherwise it outputs 0. Ecd ∆ and Dcd ∆ perform elementwise for a vector and matrix.
where d max is the maximum difference between two consecutive elements in the plaintext space. The inequality (25) implies that the quantization error decreases as ∆ decreases. Actually, the following propositions on the relationship between quantization errors and a sensitivity hold: Proposition 5: Given the ElGamal encryption E and f E in (24). Let (pk, sk) = Gen(k), m Φ = Ecd ∆Φ (Φ), m ξ = Ecd ∆ ξ (ξ), c Φ = Enc(pk, m Φ ), and c ξ = Enc(pk, m ξ ). Suppose an overflow and underflow do not occur, that is, where f = f + • f × , and the maps f × and f + are a multiplication and addition part of f in (23), respectively [20].
Proof: From the multiplicative homomorphism of E, we Regardless of the signs of Φ ij and ξ j , when an overflow and underflow do not occur, then the (i, j) entry of Proposition 6: Let k be a key length of the El-Gamal encryption. Suppose max{ Φ max , ξ ∞ } exists. Then, there exist seisitivities ∆ Φ (k) and ∆ ξ (k) satisfying By definition, every elements in a plaintext space of the ElGamal encryption are quadratic residues modulo p. The author of [49] shows that the number of consecutive quadratic non-residues modulo p is at most O(p  (1))(k+1) since p ∈ (2 k , 2 k+1 ), and lim k→∞ 2 Proposition 5 shows an output of f E exactly matches one of f × if the sensitivities are zero as long as Ecd ∆ and Dcd ∆ do not cause an overflow and underflow. Proposition 6 guarantees such sensitivities exist when a key length is sufficiently large. If a key length is relatively small, then quantization errors cannot be ignored. The quantization errors would degrade the precision of adversary's estimation of A in (3), that is, the number of data needs to be increased in order to keep the precision of the estimation.

B. Technical lemmas
This section introduces two technical lemmas used for proofs in the following appendices.
This completes the proof. Lemma 5: Let M ∈ R m×n be a full column rank matrix, and P ∈ R m×m be a positive definite matrix, then M P M is positive definite and invertible.
Proof: For any non-zero vector x ∈ R n , x (M P M )x = (M x) P (M x) > 0.
Therefore, M P M is positive definite, and this also means it is invertible.
This completes the proof.

D. Proof of Corollary 1
Proof: When a sample size T is sufficiently large, the estimatesΛ andμ are given bŷ This completes the proof.
IND-CPA 2 dyn is clearly the same as IND-CPA because the repetition of 5) to 7) does not affect the adversary's advantage. This fact concludes that the difference between adversary's advantages in IND-CPA 0 dyn and IND-CPA is negligible. In addition, the advantage in IND-CPA of the ElGamal encryption is negligible under the DDH assumption. From the above discussions, the dynamic ElGamal encryption satisfies IND-CPA at time t under the DDH assumption.

I. Proof of Lemma 3
Proof: The problem that minimizes J T in (18) is a form of the typical finite-horizon discrete-time stochastic linear quadratic regulator problem [51]. Hence, the optimal control sequence is given as u t = −(B p P t+1 B p ) −1 B p P t+1 A p x t if B p P t+1 B p is invertible, where P t = A p P t+1 A p − A p P t+1 B p (B p P t+1 B p ) −1 B p P t+1 A p + I, and P T = I. P T and P T −1 = A p {I − B p (B p B p ) −1 B p }A p + I are positive definite because B p B p is invertible from Lemma 5, and B p (B p B p ) −1 B p is a hat matrix whose eigenvalues consist of n ones and m − n zeros. Assume that P T −i > 0 for 1 ≤ i < T , then P T −i−1 = A p {P T −i − P T −i B p (B p P T −i B p ) −1 B p P T −i }A p + I, where B p P T −i B p is positive definite and invertible from Lemma 5. Additionally, Therefore, P T −i−1 is positive definite, and B p P t+1 B p is invertible for all t ∈ [0, T ).

J. Proof of Proposition 4
Proof: The cases of T = 1, 2 can be easily confirmed. This completes the proof.