Sep 29, 2015 - II outlines our system model and the underlying assumptions upon which the security of our system is based. In Section. III we discuss ...

4 downloads 27 Views 398KB Size

Physical-Layer Cryptography Through Massive MIMO

arXiv:1310.1861v2 [cs.IT] 29 Sep 2015

Thomas R. Dean, Member, IEEE, and Andrea J. Goldsmith, Fellow, IEEE

Abstract—We propose the new technique of physical-layer cryptography based on using a massive MIMO channel as a key between the sender and desired receiver, which need not be secret. The goal is for low-complexity encoding and decoding by the desired transmitter-receiver pair, whereas decoding by an eavesdropper is hard in terms of prohibitive complexity. The decoding complexity is analyzed by mapping the massive MIMO system to a lattice. We show that the eavesdropper’s decoder for the MIMO system with M-PAM modulation is equivalent to solving standard lattice problems that are conjectured to be of exponential complexity for both classical and quantum computers. Hence, under the widely-held conjecture that standard lattice problems are hard to solve in the worst-case, the proposed encryption scheme has a more robust notion of security than that of the most common encryption methods used today such as RSA and Diffie-Hellman. Additionally, we show that this scheme could be used to securely communicate without a pre-shared secret and little computational overhead. Thus, by exploiting the physical layer properties of the radio channel, the massive MIMO system provides for low-complexity encryption commensurate with the most sophisticated forms of application-layer encryption that are currently known. Index Terms—Cryptography, Lattices, MIMO, Quantum Computing

I. I NTRODUCTION The decoding of massive MIMO systems forms a complex computational problem. In this paper, we exploit this complexity to form a notion of physical-layer cryptography. The premise of physical-layer cryptography is to allow the transmission of confidential messages over a wireless channel in the presence of an eavesdropper. We present a model where a given transmitter-receiver pair is able to efficiently encode and decode messages, but an eavesdropper who has a physically different channel must perform an exponential number of operations in order to decode. This allows for confidential messages to be exchanged without a shared key or key agreement scheme. Rather, the encryption exploits physical properties of the massive MIMO channel. Our MIMO wiretap channel model for communication is shown in Figure 1. Here, a parallel channel decomposition allows for two users, Alice and Bob, to communicate with an overhead of only performing linear precoding and receiver shaping of their MIMO channel, assumed known to both of them. To an eavesdropper, Eve, who has a different channel, this decomposition does not aid in the ability to decode the channel with linear complexity. In particular, we prove that T. Dean is supported by the Fannie and John Hertz Foundation. This work was supported in part by the NSF Center for Science of Information. The authors are with the Department of Electrical Engineering, Stanford University, 350 Serra Mall, Stanford, CA 94305 (e-mail: [email protected]; [email protected]).

Figure 1. A MIMO wiretap channel model, defined by a channel gain matrix A = UΣVH , where A is known to both Alice and Bob. This allows Bob to efficiently decode Alice’s message. If Eve is not physically co-located, then knowledge of A, which we call the channel state information key, does not aid her in decoding the message with low complexity. Through the use of reductions we show that the complexity of Eve decoding Alice’s message to Bob is at least as hard as worst-case standard lattice problems. Hence, this complexity is conjectured to be exponentially hard in the number of transmitter antennas Alice uses. In particular, no existing algorithms, including those of a quantum computer, have been shown to solve such problems in sub-exponential time

it is exponentially hard1 for the eavesdropper to gain any knowledge of Alice’s transmitted vector in our system model even if it knows the channel between Alice and Bob. We refer to the channel encryption key as a Channel State Informationor CSI-key. The model requires both the transmitter and receiver to have perfect knowledge of the channel, but this knowledge does not need to be kept secret. For decoding by Eve to be hard, our model requires a maximum on the SNR that Eve maintains and that Alice and Bob use a large constellation size, where the required constellation size is related to the number of transmit antennas. To characterize the hardness of decoding MIMO systems, we use the method of reductions found in the computational study of cryptography. A brief description of this method will be provided below, while a more detailed overview of this approach to cryptography can be found in [1]. In the method of reductions, we suppose that we have access to an oracle, i.e., a black box which, given a channel and a received vector, returns the proper transmitted vector in a single operation. If the existence of such an oracle would imply efficient solutions (i.e., ones whose runtime is bounded to within a polynomial factor of the length of the input) to problems which are known (or conjectured) to be hard (i.e., ones whose runtime is bounded to within an exponential factor of the length of the input), then it follows that such an oracle cannot (or is conjectured to not) exist. We show in this work that under proper conditions, the complexity of decoding MIMO systems by an eavesdropper can be related to solving standard lattice problems. The con1 More precisely, we prove that it is at least as hard as solving standard lattice problems in the worst case, which are conjectured to be exponentially hard.

2

nection between MIMO and lattices is not new: for example, see Damen et al. [2], where the maximum-likelihood decoder is related to solving the Closest Vector Problem. Problems on lattices have been widely studied in cryptography and other fields and many standard lattice problems are conjectured to be hard ([3]–[13]). Lattice problems are also conjectured to be hard even when solved using quantum computers when they exist ([3], [13]). Creating efficient cryptosystems that achieve security given the presence of quantum computers is currently an active area of research, since most cryptosystems today, such as RSA (a public-key algorithm named after its inventors, Rivest, Shimir, and Adleman, [14]) or the Diffie-Hellman key exchange (see [15]), could efficiently be broken by a quantum computer ([16]–[18]). Our physical-layer cryptosystem provides quantum-resistant cryptography by exploiting the hardness associated with the eavesdropper’s decoding in a massive MIMO system. The idea of exploiting properties of the physical layer to achieve secrecy is not new and dates back to Shannon’s notion of information theoretic secrecy [19] and Wyner’s wiretap channel [20] (for a survey on the subject see [21]). In information theoretic secrecy, the goal is to communicate in a manner such that legitimate users may communicate at a positive rate, while the mutual information between the eavesdropper and the sender is negligibly small. Note that since in our model Bob and Eve have statistically-identical channels, information theoretic secrecy is not possible without a key rate, coding, or using properties of Alice’s and/or Bob’s channel in the transmission strategy. Along these lines, Shimizu et al. [22], have suggested using properties of the radio propagation channel to achieve information theoretic secrecy. These notions all differ from ours as we consider encryption based on computational complexity at the eavesdropper’s decoder rather than through equivocation at the eavesdropper related to entropy and mutual information. We believe this work makes significant progress in addressing some of the challenges that have been identified in applying physical layer security to existing and future systems [23]. The remainder of this paper is organized as follows. Section II outlines our system model and the underlying assumptions upon which the security of our system is based. In Section III we discuss lattices, lattice problems, and lattice-based cryptography in order to provide the background for our main result, which is stated in Section IV and proved in Appendix A. In Section V we discuss additional notions of security for our model, including how to achieve security under adversarial models commonly considered by cryptographers. II. P ROBLEM F ORMULATION A. The Wiretap Model Consider an n × m real-valued MIMO system consisting of n transmit antennas and m receive antennas: y = Ax + e,

(1)

where x ∈ Rn , and A ∈ Rn×m is the channel gain matrix. Each entry of the channel gain matrix is drawn i.i.d. from the Gaussian distribution with zero mean and standard deviation

√ k/ 2π. This distribution is henceforth written Ψk . The vector e ∈ Rm is the channel noise with each entry i.i.d. Ψα . It is assumed that A is known to both the transmitter and receiver. If we constrain the vector x to use a discrete, periodic constellation, then the set of received points becomes analogous to points on a lattice, perturbed by a Gaussian random variable. We assume that the vector x has a constrained average transmitted power, such that E [kxk] = P . We assume that there are an arbitrary number of receive antennas, restricted to an amount within a polynomial factor of the number of transmit antennas, n. By making this assumption, we are considering the advantage an eavesdropper would gain by having an arbitrarily large number of receive antennas, but we are assuming that building a receiver with an exponential number of antennas relative to those at the legitimate user’s transmitter would be prohibitively expensive. Assuming that certain requirements on SNR and constellation size are met, as described below, the security of the system can be quantified soley by the number of transmit antennas. This number plays the role of the security parameter commonly used by cryptographers in designing cryptosystems. Essentially, we are saying that decoding the system requires a number of operations that is exponential in n and we parameterize the remaining variables in our system based on n. We consider real systems with the transmitted signal constellation, X , defined as the set of integers [0, M ). Lattices can easily be scaled and shifted, so we use this constellation without loss of generality over all possible M-PAM constellations. Our analysis assumes channels with a zero-mean gain, but this is for simplicity of exposition as the proof given in Appendix A can easily be generalized to systems with nonzero mean. We consider uncoded systems, but our results can be extended to coded systems as we discuss in Section III. Let the vector ai ∈ Rn denote the gains between the transmitter and the ith receive antenna, let ei denote the noise sample at this antenna, and let x represent the transmitted vector which is drawn from X n . The ith receive antenna gets a noisy, random inner-product of the form yi = hai , xi + ei .

(2)

Our work can easily be extended to complex channels, where the real and imaginary portions of the channel gain matrix and noise are drawn independently, and M-QAM symbols are sent, using an equivalent constellation as in the real case. Let user A have n transmit antennas which are used to send a message to user B who has a number of receive antennas that is within a polynomial factor of n. Let the channel between A and B be represented by A, where each entry is i.i.d. Gaussian Ψk . The noise at each receive antenna is drawn from ΨMα . The results in this paper show that MIMO decoding can be related to solving standard lattice problems in the worst case when a certain minimum noise level and constellation size are met. If the noise power is below the required level, efficient decoding methods such as the zero-forcing decoder could be applied to our system. In other words, if these conditions are

3

not met, then our results provide no insight on the complexity of decoding, and hence on the security of the MIMO wiretap channel. Specifically, for some arbitrary m > 0, we require the following constraints on the transmission from user A to user B: Minimum Noise: mα/k 2 >

√ n

(3)

0.4 0.3 10

Constellation Size: M > m 2n log log n/ log n

0.2

(4)

y ˜ = BVx + ˜ e.

5

0.1

where the parameter m may be chosen by a user or system designer in order to trade off the SNR requirement for the size of the constellation. Now consider an eavesdropper, EVE, which has poly(n) receive antennas, and receives message x with channel represented by B, where each entry is again i.i.d. Ψk . Let the channel have noise be drawn from ΨMβ , where β ≥ α. In other words, the eavesdropper must meet at least the minimum noise requirement stated above. Discussion on how to ensure this requirement is met is also provided in Section V. In order to send message x to user B, user A performs a linear precoding as described in [25]. Let the singular value decomposition of A be given as A = UΣVH . A now sends ˜ = Vx. Upon receiving a transmission from user A, user B x ˜ = UH y. It is easy to show that this expands to computes y y ˜ = Σx + ˜ e. Since Σ, representing the singular values of A, is a diagonal matrix, B can efficiently estimate x with linear complexity in n. Notice that U is unitary so kek = k˜ ek. Now consider the message received by EVE: (5)

Note that V consists of the right singular vectors of A, which is independent of B and unitary. Gaussian random matrices are orthogonally invariant [26], so since V is unitary, multiplying by V returns the matrix to an identical, independent distribution. In other words, the entries of BV are i.i.d., following the same distribution as B. As the main result of this work, we will prove that the computational complexity for EVE to efficiently recover x can be mapped to the problem of solving standard lattice problems which are conjectured to be computationally hard. B. Definitions The following definitions will be used in the proofs of our results. We define a negligible amount in n, denoted negl. (n) as any amount being asymptotically smaller than n−c for any c > 0. Similarly a non-negligible amount is one that is at least n−c for some c > 0. We define a polynomial amount, denoted as poly(n), as an amount that is at most nc for some c > 0. An expression is exponentially small in n when it is at most 2−Ω(n) , and exponentially close to 1 when it is 1 − 2−Ω(n) . A probability is overwhelming if it holds with probability 1−n−c for some c > 0. An algorithm is efficient or efficiently computable if its run time is within some polynomial factor of the parameter n. An algorithm is hard if its run time is at least 2n . We assume that, as input, algorithms accept c real numbers approximated to within 2−n for some c > 0.

0.0 - 10

0 -5 -5

0 5

10

Figure 2.

- 10

A Gaussian distribution on a two-dimensional lattice

Z represents the set of all integers and Zq represents the set of integers modulo q. Given two probability density functions φ1 , φ2 on Rn , we define the total variational distance as ˆ 1 |φ1 (x) − φ2 (x)| dx. (6) ∆(φ1 , φ2 ) = 2 Rn C. MIMO Signal Distributions In this subsection, we define various distributions which are used in our problem. Specifically, we discuss distributions of lattice points and distributions which can be empirically related to received MIMO signals. Further, we formally define the standard lattice problems that we relate to our MIMO decoding problem. First, in the proof of our work, we will need to generate lattice points according to a Gaussian distribution. Since a lattice is a discrete set of points, we define a discrete Gaussian distribution, DA,α , for any countable set A and parameter α as Ψα (x) . (7) ∀x ∈ A, DA,α (x) = Ψα (A) We now define two distributions, AM,α,k and Rα,ψ , both on Rn × R. The distribution AM,α,k is the distribution of channel gains and the received signal from a single antenna in a MIMO system for an arbitrarily distributed transmitted vector, with a fixed second moment. This distribution is defined for a single antenna so a MIMO system with m receive antennas would get m samples from this distribution. The distribution Rα,ψ is constructed to be empirically identical to the distribution AM,α,k , but lacks the underlying structure. These distributions are the input to the MIMO decoding problems which we will define in this section. For some arbitrary x ∈ X n , we define the distribution AM,α,k as the distribution on Rn × R given by drawing a as defined above, choosing ei ∼ ΨMα and outputting (ai , yi = hai , xi + ei ). We could alternatively express our system as drawing ei ∼ Ψα and outputting

4

(ai , yi = hai , xi /M + ei ), which would result in the same received SNR. We define the distribution Rα,ψ as the distribution on Rn ×R given by drawing ai as before and outputting (ai , ψ). Here ψ is a zero-mean Gaussian distribution. We choose the second moment of ψ properly, derived in the next paragraph, so that Rα,ψ is empirically distributed identically to AM,α,k but lacks the underlying structure. In the distribution AM,α,k , each y is the inner product of a Gaussian variable with an arbitrary vector, summed with a second Gaussian vector. The resulting distribution of y will be Gaussian, with a second moment related to the transmitted power level as well as the channel gain variance. We now consider the appropriate distribution for ψ. Instead of considering samples drawn of the form ha, xi+e, we define a variable h which is drawn according to Ψα/P . We then note that the distribution of ha + h, xi is identical to that of ha, xi + e. Now note that a + h is drawn from Ψ√k2 +(α/P )2 . Taking the inner product of this distribution with x results in a distribution of Ψ√(kP )2 +α2 . ψ is drawn according to this Ψ√(kP )2 +α2 . D. MIMO Decoding Problems Given these distributions, we now precisely define MIMO decoding for the eavesdropper in the MIMO wiretap channel. We define two separate but closely related problems: a search problem and a decision problem. The search variant of the problem asks us to recover the transmitted vector x without error. This implies that the eavesdropper may be able to determine that a MIMO transmission is taking place even if this transmission cannot be decoded. The decision variant asks us for a yes or no answer as to whether the received samples were transmitted from a MIMO system or were random Gaussian noise. This implies that the eavesdropper cannot even discern that a transmission is taking place, and is very closely related to cryptographers’ notions of indistinguishability and semantic security, which we discuss in Section V. Defining search and decision variants of the problem is a standard practice in the study of computational complexity and aids us in meeting the strong notions of security commonly considered by cryptographers. In Section V, we discuss cryptographers’ notions of security and how they can be acheived. In Appendix A, we prove that the search problem is as hard as solving certain lattice problems in the worst case. We do not present a proof for the hardness of the decision problem, and leave it as an open question as to whether or not this problem is hard. We use the term “MIMO decoding problem” to refer to the search problem. We wish to show that the MIMO decoding problem, i.e., the MIMO-Search problem defined below, is hard to solve, i.e., that this decoding is of exponential complexity in the number of transmit antennas. We say that an algorithm solves this problem if it returns the correct answer with a probability greater than 1 − n−c , for some c > 0. Problem Definition 1. MIMO − SearchM,α,k . Let M ≥ 2, α ∈ (0, 1), k ∈ R, n > 0. Given a polynomial number of samples of AM,α,k , output x.

We also define below the decision variant of the search problem, which simply asks whether or not received samples are transmitted from a MIMO system (with known channel gain matrix) or are generated from a Gaussian distribution. As described above and in more detail in Section V, this decoding problem is related to robust cryptographic notions of security. Problem Definition 2. MIMO − DecisionM,α,k . Let M ≥ 2, α ∈ (0, 1), k ∈ R, n > 0. Given a polynomial number of samples, distinguish between samples of AM,α,k and samples of Rα,ψ . The MIMO search problem above will be related to solving standard lattice problems (discussed in Section III) through standard reductions. In Section III and Appendix B we will also discuss the complexity of solving these lattice problems. The result of our reduction implies that the complexity of decoding a MIMO system grows exponentially in the number of transmit antennas, i.e., MIMO decoding is at least as hard as the lattice problems to which we relate them. More precisely, we state this in a contrapositive manner below. This contrapositive statement allows us to conjecture a lower bound on the complexity of solving the MIMO decoding problems, based on the conjectured hardness of solving lattice problems. Main Result. Let M > m 2n log log n/ log n √ for some m > 0, α ∈ R, and k ∈ R be such that mα/k 2 > n. Given access to an efficient algorithm that can solve MIMO − SearchM,α,k , there exist efficient classical and quantum solutions to standard lattice problems, which are conjectured to be hard. E. Assumptions In this work we offer a proof of security by showing that breaking our cryptosystem is at least as hard as solving wellknown lattice problems in the worst case. These problems are conjectured to require exponential running time. This conjecture and the large body of research behind it is discussed in the following section. For a more through treatment of the hardness of these problems, see [3]–[12]. Our proof is also based upon the following assumptions: • We assume that the Gaussian channel noise has suffi√ ciently large power so that mα/k 2 > n. If the noise is too small, it is in fact possible to use a subexponential algorithm to recover the message, as described [27]. One possible way to ensure this requirement is met is to add noise at the transmitter. This intentionally degrades the communication SNR for a trade-off of security. A further discussion and characterization of our system in terms of received SNR is found in Section V. • We assume that the constellation size of the system is large relative to the number of transmit antennas. Specifically, in order for the proof of Theorem 1 to hold, we require that M > m 2n log log n/ log n . Unlike the noise requirement, it is unclear that sub-exponential decoding immediately follows if this bound is not strictly met; it is an open problem as to whether or not this requirement is needed. • We assume that each entry in the channel gain matrix is independent and Gaussian. More importantly, we

5

• •

assume that the two receivers of Bob and Eve, have independent channels. The fact that channels between different antennas are independent is well justified in most scattering environments. For example, in a uniform scattering environment, it has been shown that channels are independent over a distance of 0.4λ, see e.g. [28] or [29]. This independence analysis is extended to MIMO channels in [30] and [31]. In our model we consider static channel gains. Timevarying channels are discussed in Section V. We assume that the norm of the transmitted message is exactly P . We discuss the importance of this assumption and how it can be relaxed in Section V. III. L ATTICES

We now provide an overview of lattices and lattice-based cryptography. This section contains all of the concepts used in the cryptography literature that are required in the proof of our main result. We first define several problems on lattices which are all conjectured to be hard to solve and are all used in the proof of our main result to show that MIMO decoding is at least as hard as solving standard lattice problems. We next provide a discussion on the complexity of solving these lattice problems, followed by a discussion on the Learning With Errors (LWE) problem. The Learning With Errors problem has a striking similarity to the problem of MIMO decoding. We follow a very similar approach to show the hardness of MIMO decoding as is used to show the hardness of LWE decoding. Lattice-based cryptography has generated much research interest in recent years. Cryptographers’ interest in lattices largely began with the surprising result of Ajtai [5] which created a connection between the average-case and worstcase complexity of lattice problems. Cryptographers have used these results to create a wide variety of cryptographic constructions which enjoy strong proofs of security. Important to this paper is the work of Micciancio and Regev [34] which explores Gaussian measures on lattices. The Learning With Errors problem, first introduced by Regev [13], shows that recovering a point that is perturbed by a small Gaussian amount from a random integer lattice can be related to approximating solutions to standard lattice problems. This problem is discussed more thoroughly below. The hardness reduction in this work very closely follows the work in [13]. For a survey on lattice-based cryptography, see [3]. A lattice is a discrete periodic subgroup of Rn that is closed under addition. Alternatively, a lattice can be defined as the set of all integer combinations of n linearly independent vectors, known as a basis, ) ( n X n . (8) xi Ai : x ∈ Z L(A) = Ax = i=1

A lattice is not defined by a unique set of basis vectors. Any basis A multiplied by a unimodal matrix results in an alternative basis representation of the same lattice. We can define a set of vectors, whose length we denote as λ1 (A), . . . , λn (A), as the shortest vectors that exist in the lattice defined by the

basis A. These vectors are known as the minima.

successive

˜ ˜ It is easy to show that λ1 (A) ≥ mini A i , where A is the shortest possible basis for the lattice. The dual of a lattice L(A) ∈ Rn , L∗ (A), is the lattice given by all y ∈ Rn such that for every x ∈ L(A), hx, yi ∈ Z. Since A is full rank, L((AT )−1 ) is a dual of the lattice L(A). A. Lattice Problems. This section considers a set of standard problems on lattices which are conjectured to be computationally hard. These problems will be used in the characterization of the computational complexity of MIMO decoding. These problems are defined with an approximation factor, γ(n) ≥ 1, and input given in the form of an arbitrary basis. The precise definition of the approximation factor varies for each problem, but is precisely stated in each definition below. The approximation factor plays an important role in the computational complexity required to solve a given problem. In general, for very large approximation factors, the following lattice problems can be efficiently computed. For small approximation factors, the problems are conjectured to require exponential running time. The problem of MIMO decoding will be related to solving lattice problems with an approximation factor of γ = n/α, which is conjectured to be hard. The relation between the approximation factor and the complexity of solving the problem is discussed in detail in Appendix B. For a survey on the hardness of these problems, see [3] or [4]. The first problem we describe is the shortest vector problem. In general, these problems can be efficiently solved if γ is at least O (2n ), but are conjectured to require exponential run time for exact solutions or even for polynomial approximation factors. A close variant of this problem, the decision Shortest Vector Problem (GapSVP), asks whether or not the shortest vector generated by the lattice is shorter than some distance d. In general, for an arbitrary basis, short vectors are hard to find. Definition 1. GapSVPγ is defined as follows: given an ndimensional lattice L(A) and a number d > 0, output YES if λ1 (A) ≤ d or NO if λ1 (A) > γ(n) · d. The following problem, the shortest independent vectors problem (SIVP), is often referred to as a lattice basis reduction. Definition 2. SIVPγ is defined as follows: given by an ndimensional lattice L(A), output a set of n linearly independent basis vectors of length at most γ(n) · λn (A). One well-known algorithm for finding approximate solutions to the SIVP probelm is the Lentra-Lentra-Lovász (LLL) lattice basis reduction algorithm, which creates an “LLLreduced” basis in polynomial time. For large values of n, the LLL algorithm returns a basis that is exponentially larger than the shortest possible basis of the lattice. It is generally conjectured that no polynomial time algorithm could approximate SIVP to within a polynomial factor of n. For a more in-depth discussion of lattice basis reduction algorithms and their complexity, see [3]. The following two lattice problems are important in the reduction given in this paper. They are also used by Regev

6

in [13] in his proof of the security of LWE. The first problem, the Bounded Distance Decoding (BDD) problem, is equivalent to decoding a linear code, where the received vector is at most some distance d from the nearest codeword. Exact solutions to this problem are conjectured to require exponential run time. By requiring d < λ1 /2, we ensure that the closest vector is unique. The Closest Vector Problem (CVP) is idential to this problem but without a bounding distance; it is also decoding a linear code. Definition 3. The BDDL(A),d problem is defined as follows: given by an n-dimensional lattice L(A), a distance 0 < d < λ1 (A)/2, and a point x ∈ Rn which is at most distance d from a point in L(A), output the unique closest vector in L(A) Informally, we can relate MIMO decoding to BDD (or more generally to the Closest Vector Problem), as follows. Linear precoding is well known to simplify encoding and decoding of a MIMO system to be of linear complexity in n. In terms of lattice problems, we say that this linear precoding transforms the lattice basis into one in which the Closest Vector Problem is easy to solve. This is very closely related to the cryptographic notion of the trapdoor function: a function that is easy to compute in one direction, but computationally infeasible to invert without a key (which serves as the “trapdoor”) [15]. The linear precoding transformation applied to the MIMO channel effectively creates a spatially-varying trapdoor in that it allows the MIMO channel to be efficiently inverted only at Bob’s location. In our model, both communicators must have knowledge of the channel in order to perform the parallel decomposition via a singular value decomposition (SVD) associated with linear precoding. The eavesdropper may also learn this channel and hence learn the “key”, but this does not allow it to decode the message with lower complexity. We finally define the discrete Gaussian sampling problem (DGS), which, for small values of r, can be reduced to solving GapSVP and SIVP. See [13] for this reduction. This problem asks us to √ sample a Gaussian distribution, with standard deviation r/ 2π, with support over a lattice. Definition 4. The DGSr problem is defined as follows: given by an n-dimensional lattice L(A) and a number r, output a sample from DL,r , the discrete distribution defined in Section II.3. We borrow the following claim from [33], which gives an efficient algorithm to solve DGSr for large r. Intuitively, solving DGSr for small values of r becomes a computationally harder task because it reveals information about the short vectors in the lattice. We use the following claim in the proof of our main theorem, as our main theorem requires sampling Gaussian distributions on lattices. Claim 1. [33, Theorem 4.1]. There exists a probabilistic polynomial-time algorithm that, given an n-dimensional lattice √ L(A), and a number r > λn (L(A)) · ω log n , outputs a sample from a distribution that is within negligible distance of DL(A),r .

B. Learning With Errors We now give an overview of the Learning With Errors problem. The reader may note the similarities between this problem and the problem of MIMO decoding. In particular, the Learning with Errors problem is very similar to the problem presented in this paper except that Learning with Errors is set entirely over integer fields, whereas MIMO decoding is set in the reals. We take advantage of the results related to the Learning with Errors problem to show the hardness of MIMO decoding. The Learning with Errors (LWE) problem was first presented by Regev in [13]. The problem allows one to have an arbitrary number of samples of “noisy random inner products” of the form (a, y = ha, xi + e) , (9) where a ∈ Znq , x ∈ Znq , and e ∈ Zq . Each a is random from the uniform distribution over Znq , and each e is drawn from a discrete Gaussian distribution with a small second moment (relative to q). This problem is an extension of the classic learning-parity with noise problem of machine learning. As with many hard problems, the LWE problem has two variants: the search and decision variants. These two problems are related in complexity. In the search variant of the problem, the goal is to recover the vector x; whereas the decision variant asks us to distinguish between samples of y and a random distribution. If we fix the number of samples to which one has access, the LWE problem becomes analogous to finding the closest vector in an integer lattice. In [13], Regev proves that the LWE problem is at least as hard as solving GapSVPn/c and SIVPn/c in the worst case, but requires the use of a quantum computer. Peikert in [24] demonstrates a reduction that does not require a quantum computer for the case where q = O (2n ). If we fix the number of samples available to the receiver, then this problem becomes equivalent to decoding a random linear code. Consider the case where we take a random generator matrix A ∈ Zm×n , a vector t = Ax + e ∈ Zm q q and we wish to recover the vector x. If we restrict m < poly(n), and provide the proper distribution on e, then decoding this code is as hard as solving worst-case lattice problems to within a factor of γ < n/c. We briefly summarize Regev’s reduction as follows. If an efficient algorithm exists to solve LWE, then this can be used to construct an efficient algorithm that solves the BDD problem for any n-dimensional lattice. This step is somewhat surprising as it allows us to use the LWE algorithm, which operates on an integer lattice reduced modulo q, to solve BDD for any real lattice. How this step is accomplished is not entirely intuitive, but requires one to convert a single instance of BDD into an arbitrary number of samples of the distribution defined in the LWE problem. This step also requires as an input samples of a number of lattice points drawn from a discrete Gaussian distribution with a large second moment. With an efficient algorithm to solve BDD, it is possible to generate a distribution of lattice points which has a smaller second moment than input in the previous step. The above process can now be iterated with this new distribution of lattice points to solve BDD with a

7

larger bounding distance than before. Repeating this step will eventually result in a distribution of lattice points with a very small second moment, which will reveal information about the shortest vectors of the lattice, allowing us to approximate solutions to GapSVP and SIVP. This step, using an LWE algorithm to solve any instance of the BDD problem, turns out to be extremely useful to characterize the hardness of MIMO decoding. In particular, we will show that if we have an efficient algorithm for MIMO decoding, then this algorithm can be used to efficiently to solve instances of the BDD problem. Then, with an efficient BDD algorithm, Regev’s quantum reductions to worst-case lattice problems follow. Additionally for large M , Peikert’s classical reduction follows. C. Lattice-Based Cryptography In recent years, lattice-based cryptography has become a very attractive field for cryptographers for a number of reasons. The security guarantees provided by many latticebased schemes far exceeds that of many modern schemes such as RSA and Diffie-Hellman, since lattice problems enjoy an average-to-worst case connection, as discussed in Appendix B. Lattice problems also appear to be resistant to quantum computers. The creation of such computers poses a significate challenge to the state of modern cryptography, since a quantum computer could break most modern number-theoretic schemes. In addition, many proposed lattice schemes are competitive with, or better than, many modern number-theoretic schemes in terms of both key size and the computational efficiency of encryption and decryption [37]. For these reasons, a number of lattice-based cryptography standards are being developed or have been developed recently by both the IEEE and the financial industry ([38], [39]). Lattice-based cryptography provides cryptographers with a wide variety of tools to create many different cryptographic constructions. We here reference some of these constructions as it is possible that some of them could be applied to the MIMO decoding problem or even that the MIMO decoding construction could inspire entirely new cryptographic constructions. Importantly, the LWE problem can be extended to cyclotomic rings ([40]), which can improve the efficiency (in terms of key size and complexity of the encryption and decryption operations) of cryptosystems based on LWE. In [13], a system which is secure against Chosen-Plaintext Attack (CPA-secure) is presented and in [24] a Chosen-Ciphertext Attack secure (CCA-secure) system is presented. In addition, the LWE problem has been used to create a wide range of useful cryptographic primitives such as identity-based encryption ([41]), oblivious transfer ([42]), zero-knowledge systems ([43]), and pseudorandom functions ([44]). The LWE problem was also used to construct a fully homomorphic cryptosystem [45], solving a long-standing open problem in cryptography. IV. M AIN T HEOREM In this section we state our main theorem regarding the computational hardness of MIMO − SearchM,α,k . We show that given an efficient algorithm which can solve this problem,

Figure 3. A map of reductions relating MIMO decoding (the MIMO-search problem) to solving standard lattice problems and the LWE problem. If there exists an efficient algorithm to solve the MIMO-Search problem, then this implies solutions to standard lattice problems. Since lattice problems are conjectured to be hard, this conjecture follows for the hardness of the MIMOsearch problem. In this figure, M refers to the constellation size used in the MIMO system.

there exist efficient solutions to the problems of GapSVPn/α and SIVPn/α . The reduction is based off the work of [13] and involves a step using a quantum computer. In [24] this step is removed, but the hardness is only related to the GapSVP problem. The relation between the reductions used to show the hardness of MIMO decoding and the reductions used to show the hardness of LWE is shown in Figure 3. Examples of parameters which meet the requirements stated in Theorem 1 are shown in Table I. The proof of this theorem is found in Appendix A. Theorem 1. MIMO − SearchM,α,k to GapSVPn/α and SIVPn/α . Let m > 0, α √ ∈ R, k ∈ R, M > m 2n log log n/ log n , 2 be such that mα/k > n. Assume we have an efficient algorithm that solves MIMO − SearchM,α,k , given a polynomial number of samples from Ax,α,k . Then there exists an efficient quantum algorithm that, given an n-dimensional lattice L(A), solves the problems GapSVPn/α and SIVPn/α . Hence, since GapSVPn/α and SIVPn/α are conjectured to be hard, it is also conjectured that MIMO-Search is hard. An outline of the reductions is shown in Figure 3. Figure 3 also relates the work of Regev and Peikert to our work. The steps used to prove the theorem are outlined as follows: An instance of • We first show that, given the MIMO oracle as described in Section II, we can solve problems where the coefficients of the channel gain matrix are instead drawn from a discrete Gaussian distribution as described in Lemma 1 in Appendix A. • We begin by reducing a lattice basis A by using the Lensta-Lensta-Lovász (LLL) lattice-basis reduction algorithm. We then, using the procedure described in [33], create a discrete Gaussian distribution on this lattice, with a second moment around the length of the largest vector given in the reduced basis. We use this as the starting point for the iterative portion of the algorithm. • The main step in the proof is given in Lemma 7, where we use this MIMO decoding oracle to solve the BDD problem given access to a DGS oracle. This allows us to directly

8

Table I M AXIMUM SNR S n log2 M SNR (dB) 80 33.7 87.1 128 51.3 139.2 196 75.4 210.7 256 96 272.2 Example sets of parameters for various numbers of transmit antennas. In order for the security proofs contained in this paper, the system must meet these minimum constellation size and maximum SNR values. Here we set m = 1.

•

•

use the results from Regev [13] and Peikert [24]. In Lemma 8, from [13], the BDD oracle is used to (quantumly) solve DGSL∗ ,√n/(√2d) , that is return samples of DL∗ ,r . Note that we can efficiently sample from DL,r for r√> ηǫ (L). √ If in Lemma 7 we set parameters so that 2d > n, then we can reduce the value of r to below the value for which we could previously efficiently sample, that is we can construct a distribution that is more narrow than previously possible. The BDD and DGS oracles can now be applied iteratively, shrinking the second moment of the discrete Gaussian distribution with each iteration. Eventually, the distribution becomes narrow enough to reveal information about the shortest vectors of the lattice, thereby solving the GapSVPn/α and SIVPn/α problems.

V. S ECURITY AND THE MIMO W IRETAP C HANNEL In the previous sections we have shown that the MIMO wiretap model is secure in the sense that the decoding complexity of any eavesdropper is exponential in the number of transmit antennas. In this section, we relate this notion of security for our system to other notions of security used by information theorists and cryptographers. Until this section, we have refered to the third user on Alice and Bob’s public channel to be an eavesdropper. This implies that the eavesdropper is passive and has no ability but to receive and decode information. In practice, this model is limited and, in order to provide more practical and robust notions of security, a more powerful adversarial model should be considered. The need for using more robust security models in the study of physical-layer security was recently discussed in [23]. In this work the author suggests bridging the gap between notions of security in information theory and cryptography in order to make physical-layer schemes more widely accepted by the security community. Considering an adversary which, for example, has the ability to manipulate, inject, alter or duplicate information is considered essential when a cryptographer develops and designs a cryptosystem, but is rarely, if ever, considered in information-theortic settings. In this section, we discuss stronger adversarial models which are commonly considered in cryptography and show how to use the hardness result derived in Section IV in order to construct secure schemes under these models. We note that there are many other adversarial models studied in the field of cryptography which we do not discuss here. A more complete discussion of these models is provided in [1]. Unfortunately, in the main result of this work we do not show that the decision variant (i.e. Eve distinguishing

between Alice’s signal and a random variable) is as hard as the search variant (i.e. Eve decoding Alice’s signal). As a result, constructing cryptosystems which are provably secure under common adversarial models, using only the assumptions outlined in Section II, is not apparent. We instead rely on an additional conjecture that the decision problem is hard and use this conjecture to construct systems which demonstrate the desired notions of security. We discuss the validity of this conjecture both in the following subsections and in Appendicies B and C. We believe that the schemes proposed based on this conjecture are practical and that applying these notions of security in the context of physical-layer security is not only novel, but makes substantial progress in bridging ideas from information-theoretic security and cryptography, as discussed in [23]. A. Information-Theoretic Security We have shown that it is hard for Eve to decode Alice’s message. However, we defined decoding as exactly recovering the message without error. This is not the same as stating that, information-theoretically, Eve receives no information about the message. Consider that Eve applies some suboptimal decoder that runs in polynomial time (for example, successive interference cancellation or zero-forcing decoding). Eve would then get some estimate for Alice’s message with some bit error rate that is potentially less than half. In some sense, this is insecure as it implies that Eve in fact receives information about Alice’s message. In this section, we provide a means to use our system in a manner that is in fact secure under cryptographic notions of security rather than informationtheoretic ones. Under the widely accepted conjecture that lattice problems cannot efficiently be approximated to even subexponential factors, Eve can at best recover a constellation point that is exponentially far away from Alice’s transmitted vector. Effectively, this means that for a single channel use, Eve can reduce the number of possible transmitted vectors from M n to 2n . Cryptographically, this relates exactly to the notion of leaky keys presented in [46]. We could use this result in an information-theoretic sense along with our hardness result to say that there is now a positive secrecy rate in the wiretap channel, which could be accomplished through either a key rate, coding, or using a transmission strategy that takes into account the channel characteristics of Bob and/or Eve (e.g. puts a null in the direction of Eve). While this approach would extend existing results on information-theoretic secrecy, it is different from our approach in two main aspects, as we now describe. First, assume that the average received SNR at Bob’s location is identical to the average received SNR at Eve’s location and, at both locations, the sufficient conditions of our hardness result holds. Since the channel gain matrices between Alice and Bob and Alice and Eve have the same distribution, on average they have the same number of spatial streams that can be supported and at the same SNR. In other words, the mutual information between the channel input and the output at Bob and at Eve is the same, unless the input is encoded

9

in a manner that allows Bob to decode whereas Eve cannot. This will reduce the mutual information between Alice and Eve, possibly to zero. On the other hand, our approach shows that there is (likely) no efficient algorithm that allows Eve to decode, and thus, practically, if Eve is subject to complexity constraints she will receive less information than Bob. To our knowledge, this notion of information exchange, based on the conjectured complexity of decoding, is novel. Second, relying on the information theoretic secrecy argument does not provide a constructive result. By this we mean that it merely shows the existence of a scheme that allows for Alice and Bob to reliably and securely communicate, rather than actually providing such a scheme, as is the case for most information-theoretic results. In contrast, the cryptographic notion of security that we use in fact gives a practical scheme for secure communication. B. Secret Key Transmission and Computational Secrecy Capacity We now proceed to describe a secret key transmission protocol. In the context of our model in Figure 1, such a protocol allows Alice to transmit a “secret” to Bob in the form of bits undecodable by Eve. Information-theoretic protocols which achieve this secret key transmission based on equivocation at the eavesdropper are known, for example [48]. Here we present a protocol in which the key is kept secret under computational rather than information-theoretic assumptions. We call the number of bits Alice can securely transmit to Bob per channel use under computational assumptions the Computational Secrecy Capacity. As discussed above, we must accept an additional conjection for this scheme to be provably secure. This conjecture is widely accepted to be true (see [3], for example) and discussed in more detail in Appendix B: Conjecture 1. There is no polynomial time algorithm which can reduce approximate SIVP to within polynomial factors. Alice transmits a message m ∈ [0, M )n chosen uniformly at random through her channel. This message has n log M bits of entropy. Eve receives this message through her channel and can apply her favorite lattice-basis reduction algorithm to decoding the message, but is unable to obtain a lattice basis that is within a polynomial factor of the shortest basis. She can use this shorter basis along with Babai’s nearest plane algorithm [49] to recover a vector, m′ , that is a super-polynomial distance away from m, that is km − m′k > 2ω(log n) . The fact that Eve can recover this vector m′ implies that Eve can in fact learn a non-negligible amount of information about Alice’s message. Here we argue that this information is in fact useless unless Eve can violate our computational assumptions. In order to more precisely determine the length of the basis which Eve can practically find, one can consider the current state-of-the-art for lattice basis reduction algorithms, For a study on limits of lattice basis reduction algorithms, see [50], for a more general overview see [3]. In [3], the authors suggest that the closest Eve can decode relative to the original message (given a realistic amount of computational resources)

Table II C OMPUTATIONAL S ECRECY C APACITY n log2 M SNR (dB) Computational Secrecy Capacity 80 33.7 87.1 12.4 128 51.3 139.2 19.4 196 75.4 210.7 29.1 256 96 272.2 37.6 For unit channel gain variance, the minimum constellation size, and the minimum SNR that meets the noise requirements for the hardness condition to hold. Computational Secrecy Capacity gives the number of bits Alice can securely transmit to Bob per channel use using Algorithm 1. √

is bounded by km − m′ k > 22 n log M log 1.01 . According to [3], this is still conservative, and we claim that it would require either an infeasible amount of computational resources or a substantial advancement in lattice-basis reduction algorithms for Eve to learn more about the original message than this bound indicates. Achieving this bound in terms of Eve’s ability to decode the transmitted message implies that √ the entropy associated with Eve’s estimate of m is at least 2 n log M log 1.01. By applying the leftover hash √ lemma [51], it follows that Alice can transmit to Bob 2 n log M log 1.01 bits of information per message without Eve learning any (non-negligible) amount of information about the message. Thus, the security of the bits transmitted via the scheme described in Algorithm 1 √ immediately holds. The quantity 2 n log M log 1.01 is the Computational Secrecy Capacity of our model in Figure 1. Table II gives examples of the computational secrecy capacity for various parameters. Algorithm 1 requires the use of a universal hash function, which we briefly define as a function which takes an arbitrarysized input and returns a fixed-size output (the hash value). A universal hash is constructed so that there is a low expectation that two inputs chosen randomly hash to the same value (collide). The leftover hash lemma [51] essentially states that using a universal hash function allows us to extract randomness from a source from which an adversary has partial information, such that the adversary is left almost no information about the output of the hash function. Algorithm 1 Key-Agreement Scheme Alice wishes to send Bob η secret√bits. Alice generates some number c = c(n), such that 2c n log M log 1.01 > η, of random messages m ∈ [0, M )n and sends them to Bob over the MIMO channel with channel parameters meeting the constraints in Theorem 1. Alice and Bob ensure that the message is exchanged without error for example through channel coding. Alice and Bob then hash the message (after decoding if channel coding is used), using a universal hash which outputs η bits and use the result as their secret.

C. Symmetric-Key Algorithm with Chosen-Plaintext Security In this subsection, we define the concept of chosen plaintext (CPA) security and provide motivation to the importance of CPA security in the context of our model presented in Figure 1. Succinctly, the condition necessary to achieve CPA security

10

is that an adversary must be unable (without violating our computational hardness assumptions) to match up pairs of plaintext (unencrypted data) and ciphertext (encrypted data). There are many reasons why such a notion of security is needed. For example, consider that an adversary knows that a user communicates with only a known small subset of possible messages. If the adversary can match plaintext and ciphertext, then the adversary can exhaustively search over the possible transmitted messages and learn the message. The concept of CPA security was formally introduced in [52]. We illustrate the value of this notion of security with an example from our model in Figure 1. Sending non-random messages, or messages from a source with a small entropy, could be problematic from a security perspective. Consider, for example, that Alice is casting a vote in an election which she sends to the election official, Bob. In the election, there are a small number, v, of candidates. Alice votes by sending some message xi , for i ∈ [0, v), which is predefined, and publically known, for each candidate. Eve could receive y = Bxi + e, and compute the l2 norm between y and each possible {Bx0 , . . . , Bxv−1 } and tell with some certainty which candidate received Alice’s vote. If instead Alice transmits her vote using a scheme that is CPA secure, receiving the vector y will convey no information about Alice’s vote to Eve. It is not immediately apparent how to achieve CPA security for the system in Figure 1 without a result giving evidence that the decision variant of the MIMO decoding problem is hard. In this subsection, we show that if the decision variant is hard this can be used to construct a CPA secure symmetrickey encryption scheme. A symmetic-key encryption scheme uses the same key for both the encryption of the plaintext and decryption of the ciphertext. The hardness of the decision variant would follow if we could show the hardness of the search variant for small M , given the equivalence of the two problems that result from the lemmas presented in Appendix C. We proceed under this conjecture in order to demonstrate the construction of CPA secure physical-layer cryptosystem and highlight why it is a useful notion in the more general context of physical-layer security. We state the additional conjecture as follows: Conjecture 2. The decision variant of the MIMO decoding problem is as hard as the search variant. The scheme for CPA security outlined in this section requires, in addition to Conjecture 2, that we have time-varying channels with finite coherence times. Most MIMO channels are in fact time-varying due to mobility of the transmitter, receiver, or their environment. It is assumed in MIMO channel modeling that after a time period larger than the channel coherence time, Tc , each entry of the channel gain matrix will have no correlation to prior values. We constrain Alice to transmit at a rate no greater than 1/Tc. Now, each channel gain matrix between Alice and Eve

will be independent.2 Our proposed CPA-secure cryptosystem is described in Algorithm 2. In Algorithm 2, the sum and difference operations are performed modulo M . We provide a proof of CPA security under Conjecture 2 in Appendix C. Algorithm 2 Symmetric-Key Encryption Scheme Alice and Bob both know M log n bits which are unknown to Eve (these could be exchanged using Algorithm 1, for example). These bits are used to construct the vector s ∈ ZnM . Alice sends Bob the message m ∈ {0, 1}m by transmitting 2 −1 H V(s + M U y-s), 2 m). Bob decodes by computing M (Σ and rounding each entry to the nearest {0, 1}. D. Computational Attacks We wish to briefly note the importance of maintaining the security parameters as stated in Theorem 1. When the minimum noise requirement is not met, it is apparent that attacks follow on our system. By attack, we mean that an adversary could, by applying a sub-exponential algorithm, recover a non-negligible amount of information about the secret (i.e. the resulting key in Algorithm 1 or m in Algorithm √ 2). Specifically, if the requirement that mα/k 2 > n is not met, it is likely that the eavesdropper may apply the (subexponential) attack given in [27] and learn most, if not all, of the secret, without error. As an additional example, in [47], the authors show an attack on a version of our system with security parameters not meeting those defined in Theorem 1. Finally, we note that it is not apparent that an attack follows immediately for smaller values of M than required in Theorem 1, but we leave it as an open question as to whether or not it can be shown that Eve can successfully decode with nonexponential complexity for smaller values of M, or if a smaller bound on the requirement for M can be found that still entails decoding to be hard for Eve. VI. C ONCLUSION We have demonstrated that the complexity of an eavesdropper decoding a large-scale MIMO systems with M-PAM modulation can be related to solving lattice problems in the worst-case. This suggests that the complexity of solving these problems grows exponentially with the number of transmitter antennas. The complexity argument presented in this paper is in fact more robust than the arguments underlying the most common encryption methods used today such as RSA and Diffie-Hellman, as it is based on a worst-case rather than an average-case hardness arguments. Furthermore, it is believed that the underlying lattice problems are hard to solve using a quantum computer, and thus this scheme presents a practical solution to post-quantum cryptography. It is not new to exploit properties of a communication channel to achieve security; however, to our knowledge, this is the first scheme which uses physical properties of the 2 Note that if Alice transmits m copies of the same message x , this is no i different than Eve having m-times more receivers. Thus, our model accounts for the retransmission of messages, however we must require that a single message is not sent an exponential number of times (in regards to n).

11

channel to achieve security based on computational complexity arguments. Indeed, the notion of the channel is not typically considered by cryptographers. We thus describe our system as a way of achieving physical-layer cryptography. Further novel to our scheme is the role that the channel gain matrix plays in decoding. A transmitted message can only be decoded by a user with the corresponding channel gain matrix. The channel gain matrix, or more specifically the precoding of the message using the right-singular vectors of the channel gain matrix, essentially plays the role of a secret key in that it allows for efficient decoding at the receiver. However, this value does not need to be kept secret, nor does it play the traditional role of a public key. We term this type of key as the Channel State Information- or CSI-key. In cryptography terminology, this system is a trapdoor function, for which the trapdoor varies both spatially and temporally. The fact that this is a new type of cryptographic primitive suggests the possibility of entirely new cryptographic constructions. We have used the hardness result, in conjunction with a new notion of computational secrecy capacity, to construct a method in which two users can perform a key-agreement scheme, without a pre-shared secret. Given an additional conjecture, we also describe how our results can be used to construct a symmetric cipher system which achieves chosen plaintext security, effectively meaning that an eavesdropper cannot match plaintext and ciphertext pairs. We relate the parameters required to maintain security to SNR requirements and constellation size and show that they are practical to achieve assuming a system with enough transmitter antennas and the corresponding number of receivers, and relatively large constellation sizes.

P ROOF

A PPENDIX A OF M AIN T HEOREM

Theorem 1. MIMO − DecisionM,α,k to GapSVPn/α and SIVPn/α . Let α > 0, m > 0 , k > 0 be such that √ mα/k 2 > n, and M > m 2n log log n/ log n . Assume we have access to an oracle that solves MIMO − DecisionM,α,k , given a polynomial number of samples from Ax,α,k . Then there exists an efficient quantum algorithm that given an n-dimensional lattice L(A), solves the problems GapSVPn/α and SIVPn/α . Additionally, there exists a classical solution to GapSVPn/α . Proof: The lemmas required to prove this theorem are given below. We summarize the proof of the main theorem as follows. 1) We first show that, given the MIMO oracle as described in Section II, we can solve problems where the coefficients of the channel gain matrix are instead drawn from a discrete Gaussian distribution as described in Lemma 1. 2) We begin with an arbitrary lattice basis A and apply the LLL algorithm. We then create a discrete Gaussian distribution on this lattice, with a second moment around the length of the largest vector given in the reduced basis. We use this as the starting point for the iterative portion of the algorithm.

3) In Lemma 7, we use this MIMO decoding oracle to solve the BDD problem. The input to this problem is an (arbitrary) n-dimensional lattice L(A), a number √ r > 2ηǫ (L(A)), √ and a target point y within distance d < M σα/k 2 r 2 (the bounding distance) of L(A). We take this instance of a BDD problem and, using a number of samples from the distribution DL∗ ,r , we are able to construct a number of samples in the form of (A, y = ha, xi + e), in the exact form of distribution expected by MIMO decoding oracle using Lemma 1. Here, returning the correct vector x solves the BDD problem. We now have an oracle which solves the BDD problem for arbitrary lattices. 4) In Lemma 8, from [13], the BDD oracle is used to (quantumly) solve DGSL∗ ,√n/(√2d) , that is return samples of DL∗ ,r . Note we can efficiently sample from DL,r for r√> ηǫ (L).√If, in Lemma 7 we set parameters so that 2d > n, then we can reduce the value of r to below the value for which we could previously efficiently sample, that is we can construct a distribution that is more narrow than previously possible. 5) In [13], the steps of Lemma 7 and 8 are iteratively applied, resulting in a more narrow distribution of lattice points. Eventually, this distribution becomes narrow enough to reveal information about the shortest vectors of the lattice, solving the GapSVPn/α and SIVPn/α . We refer the reader to [13] for the rigorous treatment of this process. 6) We refer the reader to [24] for the classical reduction, which requires an oracle to solve the BDD problem. Replacing Regev’s LWE-based BDD oracle with our MIMObased BDD oracle, the classical reduction follows.

A. Smoothing Parameter. Before we prove the main theorem, we review the smoothing parameter and state some of its properties that we will require in our proof. The smoothing parameter was introduced in [34] and is an important property of the behavior of a discrete Gaussian distribution on lattices. It is precisely defined as follows. Definition 5. For an n-dimensional lattice L(A) and a real ǫ > 0, the smoothing parameter, ηǫ (L(A)), is the smallest α such that Ψ1/α (L∗ (A)\ {0}) ≤ ǫ. The smoothing parameter defines the smallest standard deviation such that, when the inverse is sampled over the dual L∗ (A), all but a negligible amount of weight is on the origin. More intuitively, it is the width at which a discrete Gaussian measure begins to behave as a continuous one. The motivation for√the name ‘smoothing parameter’ is given in [34]. For α > 2ηǫ (L), if we sample lattice points from DL,α then add Gaussian noise Ψα , then the resulting distribution is at most distance 4ǫ from Gaussian. We borrow the following two technical claims from [34]. Claim 2. [34, Lemma 3.2]. For any n-dimensional lattice √ L(A), ηǫ (L) ≤ n/λ1 (L∗ (A)) where ǫ = 2−n .

12

More generally, we can characterize the smoothing parameter for any ǫ. Claim 3. [34, Lemma 3.3]. For any n-dimensional lattice L(A) and ǫ > 0, r ln(2n(1 + 1/ǫ)) ηǫ (L) ≤ · λn (A). (10) π Equivalently, p for any superlogarithmic function ω (log n), ηǫ (L) ≤ ω (log n) · λn (A). We will also note the following property of the smoothing parameter, which follows from the linearity of lattices. If we scale the basis of a lattice, then all of the successive minima will scale by the same amount: Claim 4. For any n-dimensional lattice L(A),ǫ > 0, and c > 0,ηǫ (L (c · A)) = c · ηǫ (L (A)). B. Preliminary Lemmas Before we can proceed with the main part of the proof showing the reduction from standard lattice problems to the MIMO decoding problem, we require several preliminary lemmas. We will first show, in Lemma 1, that it is sufficient to solve the MIMO decoding from a discrete Gaussian distribution rather than a continuous one. This distribution is used as input to the MIMO oracle in Lemma 7. We define the distribution DM,α,k , which is the discrete analog of the distribution √ AM,α,k . Given an arbitrary lattice L(A), and a number r > 2ηǫ (L(A)), we first sample a vector a from the distribution DL(A),r , and a point e from the distribution ψα . We now output: ka ka ,y = , x /M + e (11) r r Lemma 1. Continuous-to-Discrete Samples. Given an oracle which can solve MIMO − DecisionM,α,k , there exists an efficient algorithm to recover x given samples from DM,α,k . Proof: We first claim that every point in the distribution DL(A),r is proportional to ψr , to within a negligible amount. This effectively follows from the fact that we choose r to be larger than the square root of two times the smoothing parameter of the lattice (formally, see equation 11 of [13, Claim 3.9]). We now create a unitary transformation that can be applied e and y e , so that the support of e to both a and y, creating a a is effectively Rn . W do not have to actually cover all of Rn , nor do we in fact have to come close to doing so. Our algorithms, by assumption, can only approximate points in Rn to within c a factor of 2−n , for some c > 0. Thus, we only need to have c a support in which no point is more than a distance of 2−n away from any point in Rn . Then, by the fact that we choose a unitary transformation, all norms and inner products will be preserved, and we will achieve our desired result. We describe an appropriate transformation as follows. Take two samples from the discrete distribution, call them (ai , yi ) and (aj , yj ). Now generate two numbers ci , cj ∈ Z2nc , uniformly, and output ci ai + cj aj ci yi + cj yj = , ci + cj ci + cj

ci ai + cj aj , ci + cj

ci e i + cj e j ci ai + cj aj ,x + ci + cj ci + cj

since each e is generated i.i.d., it is not hard to see that the noise has the correct distribution. Similarly, since each a is c a +c a i.i.d., moments of the quantity i cii +cjj j will be unchanged, and this quantity will be proportional to the desired Gaussian distribution. We have now increased the support of the districj ci bution. Indeed, the support of the quantities ci +c and ci +c j j covers every point in the interval [0, 1) to within a factor of c 2−n , and this new distribution will be indistinguishable from the distribution expected by the MIMO oracle. We next state the following claim which is proven in [13] and shows that a small change in α results in a small change in the distribution of Ψα . This claim is required in the proofs of Lemmas 2 and 3. Claim 5. [13, Claim 2.2]. For any 0 < β < α ≤ 2β, α −1 . ∆(Ψα , Ψβ ) ≤ 9 β

(12)

We next show that given a vector x, it is easy to verify whether or not it is the correct solution to the MIMO-Search problem: Lemma 2. Verifying solutions of MIMO − SearchM,α,k . There exists an efficient algorithm that, given x′ and a polynomial number of samples from Ax,α,k , for an unknown x, outputs whether x = x′ with overwhelming probability. Proof: Let ξ be the distribution on y − ha, x′ i. The same distribution can be obtained by sampling e ∼ Ψα and outputting e + ha, x − x′ i. In the case x = x′ , this reduces to e, and the distribution on ξ is exactly Ψα . In the case where x 6= x′ , kx − x′ k > 1 by the restriction on our choices of x. The inner product of ha, x − x′ i is Gaussian with zero mean √ and the standard and a standard deviation of at least k/ 2π, √ √ deviation on e + ha, x − x′ i must be at least α2 + k 2 / 2π. We now must distinguish between the random variables of Ψα and Ψ√α2 +k2 . Assuming that k 2 is non-negligible in n, then given an arbitrary number of samples within a polynomial factor of n, we can distinguish between the two distributions with overwhelming probability by estimating the sample standard deviation. The following lemma is used from [13, Lem. 3.7]. In [13], the lemma applies to the case of LWE over an integer field, this proof is repeated in this appendix in order to demonstrate that it follows for the case of MIMO channels, given Lemma 7. Specifically, this lemma shows that if we can solve the MIMO problems with noise parameter α, then we can solve the problems given samples with noise drawn according to Ψβ for any β ≤ α. Lemma 3. [13, Lem 3.7]. Error Handling for β ≤ α. Assume we have access to an oracle which solves MIMO − SearchM,α,k by using a polynomial number of samples. Then there exists an efficient algorithm that given samples from Ax,β,k for some (unknown) β ≤ α, outputs x with overwhelming probability.

13

Proof: Assume we have at most nc samples for some c > 0. Let Z be the set of all integer multiples of n−2c α2 between 0 and α2 . For each γ ∈ Z, do the following n times. For each sample, add a small amount of noise sampled from Ψ√γ , which creates samples in the form Ax,√β 2 +γ,k . Apply the oracle and recover a candidate x′ . Use Lemma 2 and check whether x′ = x. If yes, output x′ , otherwise continue. We now show the correctness of this algorithm. By Lemma 2, a result can be verified to be a correct solution of MIMO − SearchM,α,k with probability exponentially close to 1. Thus we must only show that in one iteration of the algorithm, we output samples that are close to Ax,α,k . Consider the smallest γ ∈ Z such that γ ≥ α2 − β 2 . Then γ ≤ α2 − β 2 + n−2c α2 . And p p α ≤ β 2 + γ ≤ α2 + n−2c α2 ≤ 1 + n−2c α. And by Claim 5, ∆ Ψα , Ψ√β 2 +γ ≤ 9n−2c , which is negligible in n. Standard lattice problems are formulated with coefficient vectors that span all integers. In our definition, we have limited our constellation size. Regev in [13] introduces a variant on (M) BDDL(A),d , which we designate as BDDL(A),d . This problem is identical to the BDDL(A),d problem, with the exception that the coefficient vectors of the solution are reduced modulo M , for arbitrary M . Regev shows that if we can solve this variant of the problem in polynomial time, there in fact exists a polynomial time algorithm which solves BDDL(A),d in the general case. Thus for further lemmas, we can ignore the effect of the limited constellation size. Lemma 4. [13, Lem. 3.5]. Finding coefficients modulo M is sufficient. Given a lattice L(A), a number d < λ1 (L(A)/2, and an integer M ≥ 2, access to an oracle which solves (M) BDDL(A),d , there exists an efficient algorithm that solves BDDL(A),d . The following lemma shows that when sufficient noise is added to a discrete Gaussian variable, it behaves like a continuous one. This establishes a formal notion of the structure of the lattice being ‘statistically hidden’ by the noise. This lemma is used to show that the distribution constructed in the proof of the main theorem is negligibly close to the distribution required by the MIMO − Decision oracle. Lemma 5. [13, Cor. 3.10]. For a lattice L(A), vectors n z, u q ∈ R , and two reals r, α > 0. Assume that 2 1/ 1/r2 + (P/α) ≥ ηǫ (A) for some ǫ < 12 . Then the distribution of hz, vi + e, where v is distributed according to DL+u,r , the norm of z is constrained to P , and e is a√normal variable with zero mean and standard deviation α/ 2π, is within total variational distance 2ǫp of a normal variable with √ zero mean and standard deviation (rP )2 + α2 / 2π.

We now state the following claim about a polynomial-time lattice basis reduction algorithm, the LLL algorithm, given in [32] and improved by Schnorr in [36].

Claim 6. [32], [36]. For some L (A), we apply Schnorr’s variant of the LLL algorithm, and obtain a new, shorter basis

e The norms of the new basis vectors in this for this lattice A. lattice, given by σ1 , ..., σn , are bounded by: σn < 2n log log n/ log n λn

(13)

σ1 < 2n log log n/ log n λ1

(14)

and The rest of this proof proceeds with the following assumption: 1≤

λn < 2n log log n/ log n λ1

(15)

The lower bound is evident from Minkowski’s bound, and the upper bound comes from the fact that we have reduced the basis by applying the LLL algorithm. While no such upper bound would exist on an arbitrary lattice, were this ratio to be bigger than this bound, then the LLL algorithm would have returned exactly the shortest basis and we would have already exactly solved the GapSVP and SIVP problems. C. Reducing MIMO Decoding to Standard Lattice Problems We now begin the main procedure of the reduction. We begin by taking the basis and applying the LLL algorithm. Lemma 6. We start with an arbitrary lattice L(A), and apply the LLL algorithm to the basis A. We now the use procedure given in [33] and Schnorr’s variant of LLL to get a distribution DL,r , for some r > 2n log log n/ log n λn The following lemma is the main mathematical contribution of this work, and allows the MIMO oracle to be used in place of the LWE oracle in the framework of Regev’s reduction for LWE. From Figure 3, this replacement implies that an efficient solution of the MIMO decoding problem would also provide an efficient solution for standard lattice problems. Lemma 7. MIMO − SearchM,α,k to BDDL,r . Let α > 0, k > 0, m > 0, and M > m 2n log log n/ log n . Assume we have access to an oracle that, for all β ≤ α, finds x given a polynomial number of samples from Ax,β,k (without knowing β). Then there exists an efficient algorithm √ that given an n-dimensional and a target point y lattice L(A), a number r > 2η(L(A)), √ within distance d < M σα/ k 2 r 2 of L(A), where σ is the smallest eigenvalue of AT A, returns the unique x ∈ L(A) closest to y with overwhelming probability. Proof: We describe a procedure that, given y, outputs a polynomial number of samples from the distribution of Dx,β,k . Then, using the MIMO-Search oracle returns the closest point x = As. First, using Claim 1, sample a vector v ∈ L∗ (A) from DL∗ ,r . We now output

kv/r, k v, A−1 y /rM + ke/r (16) We note that the right-hand side is equal to

k v, A−1 y /rM + ke/r =

hkv/r, si /M + k v, A−1 δ /rM + ke/r

14

We are guaranteed that kδk < d. We first note that the quantity k v, A−1 δ /r is distributed according to DkL∗ /r,ξ , where ξ < kd/σ. We note that σ relates to the maximum ‘skew’ that results from inverting the Gaussian matrix A. Since A−1 δ is fixed for all samples, this ‘skew’ is also fixed, meaning the inner product v, A−1 δ is symmetric since the distribution on v is symmetric. √ We now add some noise e from the distribution α/ 2 so that the discrete nature of DkL∗ /r,ξ is effectively washed out and we are left with a distribution that is essentially Gaussian as expected by the MIMO oracle. That is the distribution of the noisep is within negligible total variational distance of ψβ for β = ξ 2 + α2 /2 < α. This condition will be true precisely when the condition given in Lemma 5 is met. We can see that this holds: q √ √ 1/ (1/k 2 + ( 2ξ/M α)2 ) ≥ k/ 2 > ηǫ (L ∗ (kA/r)) (17) Therefore, the distribution in equation 15 is the distribution expected by the MIMO oracle and we can recover the vector x. In order to relate the MIMO problem to standard lattice problems, we need the following lemma, given in [13], which uses a quantum computer.

Lemma 8. [13, Lem. 3.14]. BDDL,α,k to DL∗ ,√n/(√2d) . There exists an efficient quantum algorithm that, given any ndimensional lattice L, a number d < λ1 (A)/2, and an oracle that solves BDDL,d , outputs a sample from DL∗ ,√n/(√2d) . √ In √order for the reduction to hold, we must have d > n/ 2, or the Gaussian distribution will actually grow in each iteration of the procedure. We show this in the following claim. √ √ √ Claim 7. The inequality M σα/ k 2 r 2 > n/ 2 is true given the constraints stated in Theorem 1. √ Proof: We first set the constraint that mα/k 2 > n, and thus we only require that M σ/mr > 1. We can see this is true: Mσ 2n log log n/ log n σ 2n log log n/ log n λ1 >1 > > mr r λn

(18)

Here, the first step simply applies the bound given on M/m in Theorem 1, and the second step follows from applying the bounds on r and σ from Lemma 7 and Claim 6. The final step follows from applying the bound in equation 13 on the quantity λn /λ1 . Finally, we require the following lemma from [13, Sec. 3.3], which uses both the BDD and DGS oracles iteratively √ to solve standard lattice problems. By setting d = M σα/ k 2 r 2 , we can iterate between the BDD and the DGS oracles, shrinking the Gaussian distribution with each step, to a limit, and the stated standard lattice problems. Lemma 9. DGSL,√n/(√2d) to standard lattice problems. For n-dimensional √ lattice L(A), α > 0, m > 0, k ∈ R such that mα/k 2 > n, and M > m 2n log log n/ log n . Given an oracle which solves BDDL∗ ,d and DGSL,√n/(√2d) , then there exists an

efficient algorithm that given an n-dimensional lattice L(A), solves the problems GapSVPn/α and SIVPn/α . A PPENDIX B C OMPLEXITY OF L ATTICE P ROBLEMS The security of any lattice-based cryptosystem is based on the presumed hardness of lattice problems. In this subsection we limit our discussion to the GapSVPγ and SIVPγ problems. One well-known algorithm for solving lattice problems is the LLL algorithm [32]. The algorithm solves SIVPγ and can be adapted to solving many other lattice problems as well. The algorithm runs in polynomial time but only achieves an approximation factor of O (2n ). There have been a number of improvements to this algorithm, such as Schnorr’s algorithm [36] but none that achieve small approximation factors (to within even a polynomial factor of n) that run in polynomial time. All known algorithms that return exact solutions to lattice problems in fact require a running time on the order of 2n , see for example [11] or [12]. The hardness of these problems leads to the following conjecture, stated in [3, Conj. 1.1]: Conjecture 1. There is no polynomial time algorithm that approximates lattice problems to within an approximation factor that is within a polynomial factor of n. Within certain approximation factors, the complexity class of solving lattice problems is known. It is NP-Hard to approximate GapSVP √ to within constant factors [5], [8]–[10]. For a factor of n, it belongs to the class NP∩CoNP [6], [7]. It should be noted that our results are based on an approximation factor of n/c. While such a strong hardness result is not known for this regime, constructing algorithms to achieve such approximation factors within polynomial time seems to be out of reach. These results are summarized in Table III. Table III H ARDNESS RESULTS FOR STANDARD LATTICE PROBLEMS γ O (1) √ n<γ

2n log log n/ log n

Hardness NP-Hard NP∩CoNP – P

Reference [5],[8],[9],[10] [6],[7] [13],[35], This work [32],[36]

Another interesting result related to the hardness of lattice problems considers quantum computation. If a quantum computer were to be realized, this could have profound implications for the field of cryptography. A quantum computer could efficiently factor numbers and solve the discrete-logarithm problem, which would allow for virtually all key-exchange protocols to be broken in polynomial time [18]. In addition, algorithms such as Grover’s search algorithm could improve exhaustive searches by a factor of a square root, weakening the security of systems like AES (the Advanced Encryption Standard, based on the Rijndael cipher) [17]. There are currently no known quantum algorithms that perform significantly better than the best known classical algorithms. However, it should be noted that quantum algorithms are far less understood and studied than classical algorithms, and thus we have less assurance that such an algorithm does not exist. We will still

15

state the following conjecture, given in [3, Conj. 1.2], but note that this is a weaker conjecture than Conjecture 1: Conjecture 2. There is no polynomial time quantum algorithm that approximates lattice problems to within polynomial factors. Since we show in our main result that the hardness of decoding MIMO is based on lattice problems, this implies that MIMO decoding cannot be performed any faster on a quantum computer. In more general terms, this means that latticebased cryptography currently provides promise for efficient constructions of classical cryptosystems that are secure against quantum computers. Besides being conjectured to be hard, many lattice problems have an additional property that makes them attractive to cryptographers: for certain problems, there are connections between the average-case and worst-case complexities. This allows for the construction of systems which are based on robust proofs of security. This property and its significance is described next. The worst-case complexity refers to the complexity of solving the problem for the worst possible input of a fixed size; whereas average-case complexity of a problem refers to the average complexity of solving a problem given some underlying distribution of inputs of a fixed size (typically uniformly random over all possible inputs). A worst-to-average case reduction gives a distribution of inputs for which the average complexity of solving a problem is as hard as the worst case complexity (potentially of a different problem). The connections between worst- and average-case complexity of certain lattice problems was first found by Ajtai [5]. Ajtai constructed a function that is one-way (that is, it can be computed in polynomial time, but is hard to invert) on average based on the worst-case hardness of lattice problems. This result was used by Ajtai and Dwork to construct a cryptosystem [35]. These worst-to-average case reductions were extended by many, but most important to this paper is the reduction found in [34]. Basing cryptographic systems on problems where a worstto-average case reduction exists is an extremely strong guarantee of security. It means that it is at least as hard to break the cryptosystem as it is to solve any instance of the related problems. Such a strong guarantee is not provided by most cryptosystems today. For example, breaking a cryptosystem that is based on factoring (e.g. RSA) only implies a solution to factoring numbers of a specific form; namely, the specific form used to generate RSA keys and not a solution to worstcase factoring problems. Because a worse-case to average-case connection exists for the cryptosystem proposed in this paper, we can say that it is at least as hard for Eve to decode the message transmitted from Alice to Bob in Figure 1 as it is to solve all instances of the underlying lattice problems. The worst-to-average connection in our work is entirely a result of basing it on previous results, notably [13] and [34].

A PPENDIX C CPA S ECURITY AND S MALL M In our reduction, the requirement for large M in the MIMO reduction comes from the fact that the problem is not reduced modulo M as is the case in the LWE problem. In [24], Peikert shows that the hardness result for the decision variant of the LWE problem still holds for large M , but this result cannot by applied here as it relies on the fact that the inner product in the LWE distribution is reduced modulo q. It is entirely possible that the fact that the MIMO problem does not contain a modulo reduction makes the decision variant easy. In this appendix, we show that for small M , the search and decision variants of the MIMO problem are equivalent. If one could prove Lemma 7 above for small M or prove the lemma below without the requirement for small M , then Conjecture 2 in Section V would not be needed, and the CPA security of Algorithm 2 would only rely on the assumption that SIVP and GapSVP are hard to approximate in the worst case. Lemma 10. Decision to Search. Given access to an oracle that, given a polynomial number of inputs, solves MIMO − DecisionM,α,k , there exists an efficient algorithm which can solve MIMO − SearchM,α,k . Proof: Generate a value e a from Ψk , and let l = e a − a1 . e has the Let e a = a + (l, 0, 0, . . . , 0). It is not hard to see that a same distribution as a. Choose a guess, m, for the first entry of x and calculate ye = y +l·m. Input this (e a, ye) into the decision oracle. In the case m = x1 , the transformation will be in the proper form of ye = e ax + e and the oracle will output YES. In the case m 6= x1 , the resulting y will be perturbed from e ax by e1 + a1 (x − m), or an additional factor of a1 (x − m) from the distribution expected by the oracle. The norm of this new vector x is a factor of n+1 n times larger than before, and the distribution of y is now normally distributed with a standard q √ n+1 2 kP n + α2 / 2π. Using Claim 5, we can deviation of show that this distribution has a total variational distance of q 2 + α2 kP n+1 n p ∆ ≤ 9 − 1 ≤ 9n−c 2 2 (kP ) + α

for some c > 0 from the expected distribution on Rα,ψ . This is negligible in n, and so it is arbitrarily close to the original random distribution and the oracle will output a NO. If we have M < poly(n), we can efficiently try every possible m for each entry in x. We note that this proof does not follow for the case that a1 = 0. However, since we assume that we can precisely sample from a Gaussian distribution, and that we can approximate c all real numbers to a factor of within 2−n , the probability of c drawing a value less than 2−n is exponentially close to zero, thus we ignore this case. Finally we must apply Lemma 2 from Appendix A to verify that a recovered vector is in fact the properly decoded MIMO vector, as required by the above algorithm. We outline two ways which one can show that Algorithm 2 is CPA secure. First, we can show that the existance of an oracle which can distinguish between (m, A (s + m) + e) and

16

(m, ψ) could solve the MIMO − Decision problem (and for small M the MIMO − Search problem). To accomplish this, the adversary could subtract the quantity Am from A (s + m)+e and is left with the exact input of for the MIMO − Decision problem. It is an open problem to rigorously show that the framework of [33] and [46] can be used in conjunction with , Conjecture 1 of Section V to show CPA security, i.e. whether we can say that the quantity As + e acts as a pseudorandom generator which statistically hides the quantity Am, assuming the entropy of message m is less than the computational secrecy capacity. The methodology used in the construction of these schemes follows the ideas of providing cryptosystems secure under the presence of leakage, first provided by [53] and [54]. ACKNOWLEDGEMENT The authors would like to thank Dan Boneh for his discussions on lattice-based cryptography, Martin Hellman for his comments on a preliminary version of this work, Shlomo Shamai for discussions regarding information-theoretic secrecy in the context of our model, and Mainak Chowdhury for discussions on algorithms for MIMO decoding and linear codes. R EFERENCES [1] J.Katz, and Y. Lindell, Introduction to Modern Cryptography. New York: Chapman & Hall/CRC, 2007. [2] M. O. Damen, H. El Gamal, and G. Caire, "On maximum likelihood detection and the search for the closest lattice point", IEEE Trans. Inf. Theory, vol. 49, no. 10, pp.2389–2402, 2003. [3] D. Micciancio and O. Regev, “Lattice-based Cryptography,” in PostQuantum Cryptography, Berlin, German: Springer Berlin/Heidelberg, pp. 147–191, 2009. [4] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective. Boston, MA: Kluwer Academic Publishers, Mar. 2002. [5] M. Ajtai, “Generating hard instances of lattice problems”, Complexity of computations and proofs, vol. 13 of Quad. Mat., pp. 1–32, 2004. Preliminary version in STOC 1996. [6] O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540563, 2000. Preliminary version in STOC 1998. [7] D. Aharonov and O. Regev. Lattice problems in NP intersect coNP. Journal of the ACM, 52(5):749–765, 2005. Preliminary version in FOCS 2004. [8] S. Khot. Hardness of approximating the shortest vector problem in lattices. In Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 126–135, 2004. [9] I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proc. 39th ACM Symp. on Theory of Computing (STOC), pp. 469–477, 2007. [10] D. Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM journal on Computing, 30(6): 2008–2035, 2001. [11] D. Micciancio, and P. Voulgaris, Faster exponential time algorithms for the shortest vector problem. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1468–1480, 2010. [12] M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the ACM Symposium on the Theory of Computing, number 33, pages 601-610, 2001. [13] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, Proc. 37th ACM Symp. on Theory of Computing (STOC), pp. 84–93, 2005. [14] R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21 (2): 120–126, 1978. [15] W. Diffie, and M. Hellman, "New directions in cryptography". IEEE Transactions on Information Theory 22 (6): 644–654, 1976.

[16] M. A. Nielson and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge, MA: Cambridge Univ. Press, 2000. [17] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79(2):325, 1997. [18] P. W. Shor. Polynomial-time algorithsm for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp., 26(5):1484– 1509, 1997. [19] C. E. Shannon, "Communication theory of secrecy systems", Bell Syst. Tech. J., vol. 28, pp.656–715, 1949. [20] A. D. Wyner, "The wire-tap channel", Bell Syst. Tech. J., vol. 54, pp.1355–1387, 1975. [21] A. Mukherjee, S. A. A. Fakoorian, J. Huang and A. L. Swindlehurst, “Principles of physical-layer security in multiuser wireless networks: survey”, Commun. Surveys Tuts, 16 (3): 1550–1573, 2010. [22] T. Shimizu , H. Iwai , H. Sasaoka and A. Paulraj, "Secret key agreement based on radio propagation characteristics in two-way relaying systems", Proc. 2010 IEEE Global Commun. Conf., pp.1–6, 2010. [23] W. Trappe, “The Challenges Facing Physical Layer Security,” IEEE Commun. Mag., pp. 16–20, June, 2015. [24] C. Peikert, “Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem”, Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 333–342, 2009. [25] A. Goldsmith, Wireless Communications. Cambridge, MA: Cambridge Univ. Press, 2004. [26] A. Edelman and N. Rao, "Random matrix theory", Acta Numerica, vol. 14, pp.233–297, 2005. [27] S. Arora, and R. Ge, "New algorithms for learning in presence of errors." In Automata, Languages and Programming, pages 403–415, 2011. [28] R. H. Clarke, “A statistical theory of mobile radio reception,” Bell Systems Tech. J., pp. 957–1000, July/August 1968. [29] W. C. Jakes, Jr., Microwave Mobile Communications, Wiley, New York, 1974. [30] Y. Mohasseb and M. P. Fitz, “A 3-D spatio-temporal simulation model for wireless channels,” IEEE J. Sel. Areas Commun., pages 1193–1203, August 2002. [31] R. Ertel, P. Cardieri, K. W. Sowerby, T. Rappaport, and J. H. Reed, “Overview of spatial channel models for antenna array communication systems,” IEEE Per. Commun. Mag., pp. 10–22, February, 1998. [32] A. Lenstra, H. Lenstra, Jr., and L. Lovasz, “Factoring polynomials with rational coefficients”, Math. Ann., vol. 261, no. 4, pp. 515–534, 1982. [33] C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions”, Proc. 38th Annual ACM Symp. on Theory of Computing (STOC), pages 197–206, 2008. [34] D. Micciancio and O. Regev, “Worst-case to average-case reductions based on Gaussian measures”, SIAM Journal of Computing, vol. 37,no. 1, pp. 267–302, 2007. [35] M. Ajtai and C. Dwork. “A public-key cryptosystem with worstcase/average-case equivalence”, Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pp. 284–293, 1997. [36] C. P. Schnorr. “Factoring integers and computing discrete logarithms via Diophantime approximation”, Advances in comptutational complexity, pages 171–182, 1987. [37] R. El Bansarkhan, and J. Buchmann. "Improvement and efficient implementation of a lattice-based signature scheme," Selected Areas in Cryptography–SAC 2013. Springer Berlin Heidelberg, 2014. 48–67. [38] IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices, 1363.1-2008 - 2009. [39] Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry, ANSI X9.98-2010, 2010. [40] V. Lyubashevsky, C. Peikert, and O. Regev. "On ideal lattices and learning with errors over rings", Advances in Cryptology–EUROCRYPT 2010. Springer, Heidelberg, pp. 1–23, 2010. [41] D. Boneh, E. Goh, and X. Boyen, “Hierarchical Identity Based Encryption with Constant Size Ciphertext”, Proc. of Eurocrypt ’05, LNCS 3493, pages 440–456, 2005. [42] C. Peikert, V. Vaikuntanathan, and B. Waters, “A framework for efficient and composable oblivious transfer”, in Proc. of CRYPTO, 2008, pp. 554–571. [43] D. Micciancio, and S. P. Vadhan. “Statistical zero-knowledge proofs with efficient provers: Lattice problems and more”. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282–298. Springer, Heidelberg (2003). [44] A. Banerjee, C. Peikert, and A. Rosen. “Pseudorandom functions and lattices”, EUROCRYPT 2012: 719-737. [45] C. Gentry, “A fully homomorphic encryption scheme,” Ph.D. dissertation, Dept. of Comp. Sci., Stanford Univ., Stanford, CA, 2009.

17

[46] S. Goldwasser, Y. Kalai, C. Peikert, and V. Vaikuntanathan. “Robustness of the Learning with Errors Assumption”, In ICS. 2010. [47] R. Steinfeld and A. Sakzad. On Massive MIMO Physical Layer Cryptosystem. Preprint, arXiv:1507.08015, 2015. [48] R. Ahlswede and I. Csiszàr. “Common Randomness in Information Theory and Cryptography–Part I: Secret Sharing”. IEEE Trans. Inf. Theory vol. 39, no. 4, pp.1121–1132, 1993. [49] L. Babai. On Lovasz’ lattice reducition and the nearest lattice point problem. Combinatorica, 6(1):1–13, 1986. [50] N. Gama and P. Q. Nguyen. Predicting lattice reduction. In Advances in Cryptology – Proc. Eurocrypt ’08, Lecture Notes in Computer Science. Springer, 2008. [51] R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random generation from one-way functions (extended abstract). In STOC, pages 12–24, 1989. [52] S. Goldwater and S. Micali. Probabilistic encryption. Journal of computer and system sciences, no. 2, pages 270–299, 1984. [53] Y. Ishai, Amit Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO, pages 463–481, 2003. [54] S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In TTC, pages 278–297, 2004.