extfieldsofstudy:
Computer Science
Mathematics

text:
Feedback Enhances Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels

In this report, the fundamental limits of simultaneous information and energy transmission in the two-user Gaussian multiple access channel (G-MAC) with and without feedback are fully characterized. All the achievable information and energy transmission rates (in bits per channel use and energy-units per channel use, respectively) are identified. Thus, the information-energy capacity region is defined in both cases. In the case without feedback, an achievability scheme based on power-splitting and successive interference cancelation is shown to be optimal. Alternatively, in the case with feedback (G-MAC-F), a simple yet optimal achievability scheme based on power-splitting and Ozarow's capacity achieving scheme is presented. Three of the most important observations in this work are: (a) The information-energy capacity region of the G-MAC without feedback is a proper subset of the information-energy capacity region of the G-MAC-F and (b) Feedback can at most double the energy rate for a fixed information rate.

Introduction
For decades, a traditional engineering perspective was to use radio frequency (RF) signals exclusively for information transmission. However, this approach has been shown to be suboptimal [2]. Indeed, an RF signal carries both energy and information. From this standpoint, a variety of modern wireless systems question this conventional assumption and suggest that RF signals can be simultaneously used for information and energy transmission [3]. Typical examples of communications technologies already exploiting this principle are radio frequency identification (RFID) devices and power line communications. Beyond the existing applications, simultaneous transmission of both information and energy appears as a promising technology for a variety of emerging applications including low-power short-range communication systems, sensor networks, machine-to-machine networks and body-area networks, among others [4]. Nevertheless, information and energy transmission are often conflicting tasks and thus subject to a trade-off between the information transmission rate (bits per channel use) and the energy transmission rate (energy-units per channel use). This trade-off is evidenced in finite constellation schemes, as highlighted in Popovski et al.'s [5]. Consider the noiseless transmission of a 4-PAM signal over a point-to-point channel in the alphabet {−2, −1, 1, 2}. If there is no received energy rate constraint, one can clearly convey 2 bits/ch.use by choosing all available symbols with equal probability. However, if one requires the received energy rate to be for instance the maximum possible, the maximum transferable information rate is 1 bit/ch.use (since one is forced to communicate only with the largest energy symbols). From this simple example, it is easy to see how additional energy rate constraints may change the overall performance of the network.
Despite the vast existing literature on this subject, the fundamental limits of simultaneous energy and information transmission (SEIT) are still unknown in most multi-user channels. The pioneering works by Varshney in [2] and [6], as well as, Grover and Sahai in [7] provided the fundamental limits on SEIT in point-to-point channels. More specifically, in [6] the case of a the single point-to-point link was discussed and in [7] and [2] the case of parallel point-to-point links was studied.In the context of multi-user channels, most of the existing studies of SEIT follow a signal-processing or networking approach and focus mainly on the feasibility aspects. For instance, optimization of beamforming strategies over more involved network structures was considered in [8,9], and [10] for multi-antenna broadcast channels and in [11] for multi-antenna interference channels. SEIT was also studied in the general realm of cellular systems in [12] as well as in multi-hop relaying systems in [13,14,15,16,17], and [18]. Other studies in the two-way channel are reported in [5] and in [19] in graphical unicast and multicast networks.

SEIT in Multiple Access Channels (MACs)
In the particular case of the discrete memoryless multiple access channel (DM-MAC), the tradeoff between information rate and energy rate has been studied in [14]. Therein, Fouladgar et al. characterized the information-energy capacity region of the two-user discrete memoryless MAC when a minimum energy rate is required at the input of the receiver. Such a constraint changes the dynamic of the communication system in the sense that it requires additional transmitter coordination to achieve the targeted energy rate. An extension of the work in [14] to the Gaussian MAC (G-MAC) case is far from trivial due to the fact that the information-energy capacity region involves an auxiliary random-variable which cannot be eliminated as in the case without energy constraints, as independently suggested by Cover [20] and Wyner [21]. Other types of energy rate constraints for the G-MAC have been also investigated. For instance, Gastpar [22] considered the G-MAC under a maximum received energy rate constraint. Under this assumption, channel-output feedback has been shown not to increase the capacity region. In the case studied by Fouladgar et al. in [14], the effect of feedback is not yet well understood from an energy transmission perspective.
More generally, the use of feedback in the K-user G-MAC, even without energy rate constraints, has been shown to be of limited impact in terms of sum-rate improvement. This holds even in the case of perfect feedback. More specifically, the use of feedback in the G-MAC increases the sum-capacity by at most log 2 (K) 2 bits per channel use [23]. Hence, the use of feedback is difficult to justify from the point of view of exclusive information transmission.

Contributions
This paper studies the fundamental limits of SEIT in the two-user G-MAC with and without feedback. It shows that when the goal is to simultaneously transmit both information and energy, feedback can significantly improve the global performance of the system in terms of both information and energy transmission rates. One of the main contributions is the identification of all the achievable information and energy transmission rates in bits per channel use and energyunits per channel use, respectively. More specifically, the information-energy capacity region is fully characterized in both cases. In the case without feedback, an achievability scheme based on power-splitting and successive interference cancellation is shown to be optimal. Alternatively, in the case with feedback (G-MAC-F), a simple yet optimal achievability scheme based on powersplitting and Ozarow's capacity achieving scheme is presented. Three of the most important observations in this work are: (a) The information-energy capacity region of the G-MAC without feedback is a proper subset of the information-energy capacity region of the G-MAC-F, that is, the former is strictly contained in the latter and (b) Feedback can at most double the energy rate for a fixed information rate.

Organization of the Report
The remainder of the report is structured as follows. Sec. 2 formulates the problem of simultaneous energy and information transmission in the two-user G-MAC-F. Sec. 3 and Sec. 4 show the main results of this paper for the G-MAC without and with feedback, respectively. Namely, for both settings the following fundamental limits are derived: (a) the information-energy capacity region ; and (b) the maximum information individual rates and sum rates that can be achieved given a targeted energy rate. In Sec. 4, the maximum energy rate improvement that can be obtained by using feedback given a targeted information rate is also discussed. Sec. 6 presents the proof of achievability and converse for the information-energy capacity region of the G-MAC-F (Theorem 2). Sec. 7 presents the proof of the perfect feedback information sum-capacity for a given energy rate constraint (Proposition 4).

Gaussian Multiple Access Channel with Feedback
Consider the two-user memoryless G-MAC with perfect channel-output-feedback (G-MAC-F) in Fig. 1. At each channel use t ∈ N, X 1,t and X 2,t denote the real symbols sent by transmitters 1 and 2, respectively. Let n ∈ N denote the blocklength. The receiver observes the real channel output and the energy harvester (EH) observes where h 1i and h 2i are the corresponding constant non-negative channel coefficients from transmitter i to the receiver and EH, respectively. The channel coefficients must satisfy the following L 2 -norm condition: with h j (h j1 , h j2 ) T to ensure the principle of conservation of energy. The noise terms Z t and Q t are realizations of two identically distributed zero-mean unitvariance real Gaussian random variables. In the following, there is no particular assumption on the joint distribution of Q t and Z t .
A perfect feedback link from the receiver to transmitter i allows at the end of each channel use t, the observation of the channel output Y t−d at transmitter i, with d ∈ N the delay of the feedback channel. Without any loss of generality, the delay is assumed to be the same from the receiver to both transmitters and equivalent to one channel use, i.e., d = 1.
Within this context, two main tasks are to be simultaneously accomplished: information transmission and energy transmission.

Information Transmission
The goal of the communication is to convey the independent messages M 1 and M 2 from transmitters 1 and 2 to the common receiver. The messages M 1 and M 2 are independent of the noise terms Z 1 , . . . , Z n , Q 1 , . . . , Q n and uniformly distributed over the sets M 1 {1, . . . , 2 nR1 } and M 2 {1, . . . , 2 nR2 }, where R 1 and R 2 denote the transmission rates and n ∈ N the blocklength.
At each time t, the existence of feedback links allows the t-th symbol of transmitter i to be dependent on all previous channel outputs Y 1 , . . . , Y t−1 as well as its message index M i and a randomly generated index Ω ∈ {1, . . . , 2 nRr }, with R r 0, that is independent of both M 1 and M 2 and assumed to be known by all transmitters and the receiver. More specifically, for some encoding functions RR n°8804 The symbols X i,1 , . . . , X i,n satisfy an expected average input power constraint where P i denotes the average transmit power of transmitter i in energy-units per channel use for i ∈ {1, 2} and where the expectation is over the message indices and the noise realizations. The G-MAC-F above is fully described by the signal to noise ratios (SNRs): SNR ji , with ∀(i, j) ∈ {1, 2} 2 are defined as follows given the normalization over the noise powers. The receiver produces an estimate (M and the average probability of error is

Energy Transmission
The average energy transmission rate (in energy-units per channel use) at the EH is The goal of the energy transmission is to guarantee that the energy rate B (n) is not less than a given constant B that must satisfy for the problem to be feasible. Hence, the probability of energy outage is defined as follows: for some > 0 arbitrarily small.

Simultaneous Information and Energy Transmission
The G-MAC-F in Fig. 1 is said to operate at the information-energy rate triplet (R 1 , R 2 , B) ∈ R 3 + considered if both transmitters and the receiver use a transmit-receive configuration such that: (a) reliable communication at information rates R 1 and R 2 is ensured; and (b) the energy transmission rate during the whole block-length is not lower than B. Under these conditions, the information-energy rate triplet (R 1 , R 2 , B) is said to be achievable.
such that both the average error probability and the energy-outage probability tend to zero as the blocklength n tends to infinity. That is, lim sup  . Note that poins Q 1 , Q 2 and Q 3 are coplanar and satisfy that R 1 = R 2 . In particular, Q 1 = (0, 0, 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 ); and the points Q 2 and Q 3 are also collinear and R 1 = R 2 = 1 4 log 2 (1 + SNR 11 + SNR 12 ). The points Q 2 , Q 4 and Q 5 are coplanar and they satisfy that B = 1 + SNR 21 + SNR 22 . In particular, Q 4 = ( 1 2 log 2 (1 + SNR 11 ) , 0, 1 + SNR 21 + SNR 22 ) and From Def. 1, it is clear that for any achievable triplet (R 1 , R 2 , B), whenever the targeted energy rate B is smaller than the minimum energy rate required to guarantee reliable communications at the information rates R 1 and R 2 , the energy rate constraint is vacuous. This is mainly because the energy transmission rate is always satisfied and thus, the transmitter can exclusively use the available power budget for increasing the information transmission rate. Alternatively, when the energy rate B must be higher than what is strictly necessary to guarantee reliable communication, the transmitters face a trade-off between information and energy rates. Often, increasing the energy transmission rate implies decreasing the information transmission rates and vice-versa. This trade-off is accurately modeled by the notion of information-energy capacity region.
Definition 2 (Information-Energy Capacity Region). The information-energy capacity region of the G-MAC with perfect channel-output feedback E FB (SNR 11 , SNR 12 , SNR 21 , SNR 22 ) and without feedback E(SNR 11 , SNR 12 , SNR 21 , SNR 22 ) are the closure of all achievable information-energy rate triplets (R 1 , R 2 , B) in the corresponding cases.
The main results for the G-MAC with and without feedback presented in this paper are provided in terms of the information-energy capacity region (Def. 2) in the following two sections.

Information-Energy Capacity Region without Feedback
The information-energy capacity region of the G-MAC without feedback, denoted by E(SNR 11 , SNR 12 , SNR 21 , SNR 22 ), with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 is fully characterized by the following theorem.

Comments on the Proof
To prove the achievability of the region presented in Theorem 1, consider that each transmitter i, with i ∈ {1, 2}, uses a fraction β i ∈ [0, 1] of its available power to transmit information and uses the remaining fraction of power (1 − β i ) to transmit energy. Given a power-split (β 1 , β 2 ) ∈ [0, 1] 2 , the achievability of information rate pairs satisfying (16a)-(16c) follows the scheme described in [20] or [21]. Additionaly, in order to satisfy the received energy constraint (16d), transmitters send common randomness that is known to both transmitters and the receiver using all their remaining power. This common randomness does not carry any information and does not produce any interference to the information-carrying (IC) signals. More specifically, at each time t, transmitter i's channel input can be written as: for some independent zero-mean Gaussian IC symbols U 1,t and U 2,t with variances β 1 P 1 and β 2 P 2 , respectively, and independent thereof W t is a zero-mean unit-variance Gaussian energycarrying (EC) symbol known non-causally to all terminals. The receiver subtracts the common randomness and then performs successive decoding to recover the messages M 1 and M 2 . Note that this strategy achieves the corner points of the information rate-region at a given energy rate. Time-sharing between the corner points and the points on the axes is needed to achieve the remaining points.
The converse and the analysis of the average received energy rate follow the same lines as in the case with feedback described in Section 6 when the IC channel input components are assumed to be independent.
For any achievable triplet (R 1 , R 2 , B), whenever the required energy rate B is smaller than the minimum energy rate required to guarantee reliable communication at rates R 1 and R 2 , the energy constraint is vacuous. Hence, transmitting information is always enough to satisfy the energy constraint. See for instance the intersection the volume E (SNR 11 Fig. 3. This intersection corresponds to the set of triplets (R 1 , R 2 , B), in which the corresponding pairs (R 1 , R 2 ) form a set that is identical to the capacity region of the G-MAC without feedback, denoted by C(SNR 11 , SNR 12 ). That is, when the energy rate constraint is lower than the maximum energy rate achievable with independent symbols, all information rates of the information capacity region C(SNR 11 , SNR 12 ) are achievable. (See for instance points Q 2 , Q 3 , Q 4 , and Q 5 in Fig. 3.) On the other hand, when the energy constraint consists of guaranteeing an energy rate of B ∈ (1 + SNR 21 + SNR 22 , 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 ] energy-units per channel use, that is, when the energy rate B at the input of the energy harvester is required to be higher than what is strictly necessary to guarantee reliable communication at the information sum-rate, the transmitters deal with a trade-off between information and energy transmission. This can be interpreted in terms of power-splits, i.e., 0 β i < 1, for i ∈ {1, 2}. In this case, part of the transmitter power budget is exclusively dedicated to the transmission of energy. Thus, for all triplets (R 1 , R 2 , B), it follows that the corresponding information rate pairs (R 1 , R 2 ) form a proper set of the capacity region C(SNR 11 , SNR 12 ); see for instance the intersection of the volume Fig. 3. Finally, requiring an energy transmission rate B 22 , ∞) constrains the achievability of any positive rate (see point Q 1 in Fig. 3, which is achievable with (β 1 = β 2 = 0)). However, it is important to highlight that the transmitters cannot guarantee an energy rate that is higher than the energy rate achieved with full transmitter cooperation.

Information-Energy Transmission without Feedback and with Minimum Energy Rate Constraint b
Let 0 b 1 +SNR 21 +SNR 22 + 2 √ SNR 21 SNR 22 denote the minimum energy rate that must be guaranteed at the input of the EH in the G-MAC without feedback and with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 , and let ξ : R → R be defined as follows: In the following, for a fixed minimum energy rate constraint b, the maximum individual information rates as well as the information sum-capacity are identified.

Maximum Individual Information Rates without Feedback and with Minimum Energy Rate Constraint b
The maximum individual rate R NF i (b), with i ∈ {1, 2} given an energy rate constraint of b energyunits per channel use at the input of the EH is the solution to an optimization problem of the form The following proposition characterizes the solution to the optimization problem (19).

Proposition 1 (Maximum Individual Information Rates without Feedback with Minimum Energy Rate Constraint b).
For a fixed minimum energy rate b required at the input of the EH, the maximum individual rates R NF i (b) of the G-MAC without feedback, with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 , are given by with ξ(b) ∈ [0, 1] defined in (18).
Proof: From the assumptions of Proposition 1 it follows that an energy transmission rate of b energyunits per channel use must be guaranteed at the input of the energy harvester. Then, the set of power-splits (β i , β j ) that satisfy this constraint must satisfy with These power-splits are referred to as feasible power-splits.
Using a Fourier-Motzkin elimination in the constraints (16a)-(16c) to eliminate R j , it can be shown that transmitter i's individual rate maximization problem in (19) can be written as and g 0 (β 1 , β 2 ) is defined in (22). For any feasible power-split (β i , β j ), it holds that The target function f i (β i , β j ) is increasing in β i and is independent of β j . Since the constraint function is monotonically decreasing in (β i , β j ), in order to maximize transmitter i's individual rate, the optimal power-split should be a feasible power-split in which β i is maximized while β j can be forced to 0. Thus, the maximization problem in (19) can be written as follows: Transmitter i's achievable information rate is increasing in β i and the energy rate constraint is decreasing in β i . Hence, transmitter i is able to achieve the maximum individual rate if the energy transmission of transmitter i is made at the minimum rate to meet the energy rate constraint, i.e., if there is equality in (21). In this configuration, transmitter i can use a power-split in which the

Information Sum-Capacity with Minimum Received Energy Rate Constraint b
The information sum-capacity R NF sum (b) (i.e., the maximum information sum-rate) of the G-MAC subject to a minimum energy rate constraint b is the solution to an optimization problem of the form The solution to this problem is given by the following theorem.
Proposition 2 (Information Sum-Capacity with Minimum Energy Rate Constraint b). For a fixed minimum energy rate b required at the input of the EH, the information sum-capacity of the G-MAC without feedback and with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 is SNR 1k , and ξ(b) defined in (18),

RR n°8804
Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels 14 Proof: The sum-rate maximization problem in (27) can be written as follows: where the functions f 0 and g 0 are defined as and g 0 (β 1 , β 2 ) defined as in (22). For any nonnegative β 1 and β 2 it can be shown that and thus the function f 0 is monotonically increasing in (β 1 , β 2 ). The function g 0 is monotonically decreasing in (β 1 , β 2 ).
to be a solution to the optimization problem in (31) Assume that 1 + SNR 21 + SNR 22 Without loss of generality, consider transmitter 1. Since g 0 is monotonically decreasing in β 1 whereas f 0 is monotonically increasing in β 1 , there always exists a β 1 > β * 1 such , which contradicts the assumption of the lemma. Assume 0 b 1 + SNR 21 + SNR 22 and assume without loss of generality that transmitter 1 uses a power-split β * 1 < 1. From the initial assumption, the pair (1, which contradicts the assumption of the lemma and completes the proof. From Lemma 1, the optimization problem in (31) is equivalent to: Assume that 0 b 1 + SNR 21 + SNR 22 . Then, from Lemma 1, it follows that the solution to the optimization problem in (31) is β * 1 = β * 2 = 1. Assume now that: This can be rewritten in terms of ξ(b) as follows: ( with ξ(b) defined in (18). Note also that any solution to (37), must satisfy that Hence, to obtain the solution of the optimization problem in (31), it suffices to perform the maximization over all (β 1 , Then, there is a unique feasible choice of β * 1 to satisfy (37), given by The corresponding sum-rate is given by: which is a concave function of β * 2 . Hence, given a fixed β * 1 , the unique optimal β * 2 must be a solution to The equality in (40) and the correspondingβ * 1 is given by: In this case, the sum-rate is: Assume now that: This is equivalent to Under this condition, the only feasible pairs, i.e., solutions to g 0 (β 1 , it follows that the solution to (31) is given by β * i = 1 − ξ(b) 2 and β * j = 0 and this completes the proof.
One of the main observations from Prop. 2 is that there exist three particular regimes for the required energy rate b.
In the first regime, ∀b ∈ [0, 1 + SNR 21 + SNR 22 ], the information sum-rate corresponds to the sum-capacity. Hence, exclusively transmitting information at the sum-rate capacity is enough for satisfying the energy-rate constraint. This observation and Prop. 1 suggest that the set of (R 1 , R 2 ) that are achievable given the minimum energy rate constraint b is identical to the information capacity region of a Gaussian MAC without energy constraint (see Fig. 3). In , the information sum-rate is monotonically decreasing in b. Hence, increasing the minimum required energy-rate b beyond the threshold 1+SNR 21 + SNR 22 decreases the information sum-capacity (see Fig. 3).
In the third regime, ∀b ∈ 1 + SNR 21 , the sum rate is monotonically decreasing and it corresponds to the maximum individual rate (Prop. 1) of the transmitter with the highest SNR.
Remark 1. Optimal alternative transmission of energy and information does not always achieve information sum-capacity for a given minimum received energy constraint.
Consider the sum-rate optimization problem proposed in [14] in which both users alternate between information and energy transmission. Specifically, during a fraction of time λ ∈ [0, 1], transmitter i sends an information-carrying signal with power P i and during the remaining fraction of time it sends a non-information-carrying signal with power P i . Thus, the optimal sum-rate optimal time-sharing parameter λ and power control (P 1 , P 2 , P 1 , P 2 ) are solution to the optimization problem max (λ,P 1 ,P 1 ,P 2 ,P 2 )∈[0,1]×R 4 + λ 2 log 2 1 + h 2 11 P 1 + h 2 12 P 2 (46a) subject to : where P i is the total power budget of transmitter i. For any feasible choice of (λ, P 1 , P 1 , P 2 , P 2 ), by the concavity of the logarithm, it follows that Now, when λ = 1, then (47) holds with equality and the problem (46) can be written as which is infeasible for any b > 1 + SNR 21 + SNR 22 . When λ ∈ [0, 1), then (47) holds with strict inequality and the rate 1 2 log 2 1 + λ h 2 11 P 1 + h 2 12 P 2 is always achievable by a power-splitting scheme in which β i = λ P i Pi , with i ∈ {1, 2}, for any optimal tuple (λ, P 1 , P 1 , P 2 , P 2 ) in (46). This shows that the maximum information sum-rate achieved via alternating energy and information transmission is always bounded away from the information sum-capacity (Proposition 2), except when λ = 1, which implies that exclusively transmitting information transmission satisfies the energy rate constraint, i.e., b ∈ [0, 1 + SNR 21 + SNR 22 ].

Main Results: Information-Energy Capacity Region with Feedback
The information-energy capacity region of the G-MAC-F is fully characterized by the following theorem.
Remark 2. The information-energy capacity region without feedback described by Theorem 1 is identical to the information-energy capacity region described by Theorem 2 in the case in which channel inputs are chosen to be mutually independent, i.e., ρ = 0. This suggests that the information-energy capacity region without feedback is strictly included in the information-energy capacity region with feedback, and thus, for any non-zero SNR 11 , SNR 12 , SNR 21 , and SNR 22 , it holds that Note that the inclusion here is strict. For instance, any rate triplet (R 1 , R 2 , B) for which R 1 +R 2 equals the perfect feedback sum-capacity cannot be achieved without feedback.
The proof of Theorem 2 is presented in Section 6. The remainder of this subsection highlights some important observations about Theorem 2.

Comments on the Achievability
The achievability scheme in the proof of Theorem 2 is based on power-splitting and Ozarow's capacity achieving scheme [24]. From an achievability standpoint, the parameters β 1 and β 2 in Theorem 2 might be interpreted as the fractions of average power that transmitters 1 and 2 allocate for information transmission. More specifically, transmitter i generates two signals: an information-carrying (IC) signal with average power β i P i energy-units per channel use; and a noinformation-carrying (NIC) signal with power (1 − β i )P i energy-units per channel use. The role of the NIC signal is exclusively energy transmission from the transmitter to the energy harvester. Conversely, the role of the IC signal is twofold: information transmission from the transmitter to the receiver and energy transmission from the transmitter to the energy harvester.
The parameter ρ is the average Pearson correlation coefficient between the IC signals sent by both transmitters. This parameter plays a fundamental role in both information transmission and energy transmission. Note for instance that the upper-bound on the energy harvested per unit time (49d) monotonically increases with ρ, whereas the upper-bounds on the individual rates (49a) and (49b) monotonically decrease with ρ. Note also that the Pearson correlation factor between the NIC signals of both transmitters does not appear in Theorem 2. This is mainly because maximum energy transmission occurs using NIC signals that are fully correlated and thus, the corresponding Pearson correlation coefficient is one. Similarly, the Pearson correlation factor between the NIC signal of transmitter i and the IC signal of transmitter j, with j ∈ {1, 2} and j = i, does not appear in Theorem 2 either. This observation stems from the fact that, without loss of optimality, NIC signals can be chosen to be independent of the messages M 1 and M 2 as well as the noise sequences, and known by both the receiver and the transmitters. Hence, NIC signals can be independent of the IC signals and more importantly, the interference they create at the receiver can be easily eliminated. Under this assumption, a power-splitting (β 1 , β 2 ) ∈ [0, 1] 2 guarantees the achievability of non-negative rate pairs (R 1 , R 2 ) satisfying (49a)-(49c) by simply using Ozarow's capacity achieving scheme. At the EH, both the IC and NIC signals contribute to the total harvested energy (11). The IC signal is able to convey at most 22 energy-units per channel use. The sum of these two contributions as well as the contribution of the noise at the EH justifies the upper-bound on the energy transmission rate in (49d).

Information-Energy Transmission with Feedback and with Minimum Energy Rate Constraint b
Let 0 b 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 denote the minimum energy rate that must be guaranteed at the input of the EH in the G-MAC-F with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 .
In the following, for a fixed minimum energy rate constraint b, the maximum individual information rates as well as the information sum-capacity are identified. Hence, the set of all information-energy rate triplets that are achievable given an energy rate constraint of b energyunits per channel use at the input of the EH is fully characterized.

Individual Information Rates with Feedback and Minimum Energy Rate Constraint b
The maximum individual information rate R FB i (b), with i ∈ {1, 2}, of the G-MAC-F, with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 , given an energy rate constraint of b energy-units per channel use at the input of the EH is the solution to an optimization problem of the form The solution to the optimization problem (52) is given by the following proposition.

Proposition 3 (Maximum Individual Information Rates with Feedback and Minimum Energy
Rate Constraint b). Consider a G-MAC-F with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 . For a given required minimum energy rate b, the maximum individual information rates with feedback coincide with the maximum individual information rates without feedback in Proposition 1. That is, Proof: From the assumptions of Proposition 3 it follows that for a given energy transmission rate of b energy-units per channel use, a power-split (β 1 , β 2 ) is feasible if there exists at least one ρ ∈ [0, 1] that satisfies with Using a Fourier-Motzkin elimination in the constraints (49a)-(49c) to eliminate R j , it can be shown that transmitter i's individual rate maximization problem (52) is equivalent to with For a given triplet (β i , β j , ρ), there are two cases: either it satisfies

Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels 21
which implies that or it satisfies and in this case In the first case, Condition (58) cannot be true for any triplet (β i , β j , ρ) ∈ [0, 1] 3 and this case should be excluded.
In the second case, the function f FB i (β i , β j , ρ) is decreasing in ρ and does not depend on β j , thus, it holds that and the triplet (β i , 0, 0) is feasible if and only if g FB (β i , 0, 0) b. Under these assumptions, transmitter i is able to achieve its maximum individual rate if it uses a power-split in which the fraction β i is maximized and its energy transmission is made at the minimum rate to meet the energy rate constraint. In this case, the maximization problem (56) reduces to the maximization problem in (26) in the proof of Proposition 1. Thus, it can be shown that the individual rates with feedback are limited by R i is given by (18). The relevance of Proposition 3 stems from the insights it provides to the understanding of the shape of the volume E FB (SNR 11 , SNR 12 , SNR 21 , SNR 22 ) in comparison to the shape of the volume E (SNR 11 , SNR 12 , SNR 21 , SNR 22 ). Even if feedback does not increase the maximal individual rates that can be achieved for a given received energy rate b, it will be shown in the sequel that it increases the sum-rate that can be achieved (See Proposition 4).
Note that if b ∈ [0, 1 + SNR 21 + SNR 22 ], then ξ(b) = 0 and thus, the energy constraint does not add any additional bound on the individual rates other than (49a) and (49b). In general, any intersection of the volume E FB (SNR 11 , SNR 12 , SNR 21 , SNR 22 ), in the Cartesian coordinates (R 1 , R 2 , B), with a plane B = b ∈ [0, 1 + SNR 21 + SNR 22 ] corresponds to the set of triplets (R 1 , R 2 , b), in which the corresponding pairs (R 1 , R 2 ) form a set that is identical to the capacity region of the G-MAC with feedback and without EH, denoted by C FB (SNR 11 , SNR 12 ). Fig. 5 shows a general example of this intersection when SNR 11 = SNR 12 = SNR 21 = SNR 22 . In this case, transmitting information using all the available power budget is always enough to satisfy the energy constraint and thus, all information-transmission rate pairs of the capacity region C FB (SNR 11 , SNR 12 ) are achievable. In the particular case in which SNR 11 = SNR 12 = SNR 21 = SNR 22 = 10 (Fig. 4), the sum-capacity points Q 2 and Q 3 , as well as the corner points Q 4 and Q 5 are achievable by using Ozarow's scheme without any power-splitting, i.e., β 1 = β 2 = 1.
In the case in which b ∈ (1+SNR 21 +SNR 22 , 1+SNR 21 +SNR 22 +2ρ (1, 1) √ SNR 21 SNR 22 ], it follows that 1 − (ρ (1, 1)) 2 1 − ξ(b) 2 < 1 and thus, the energy constraint limits the individual rates. That is, the individual rate is bounded away from 1 2 log 2 (1 + SNR 1i ). The effect of these bounds can be seen in Fig. 4. Let B(b) ⊂ R 2 + be a box of the form  R 2 , B) for which the corresponding pairs (R 1 , R 2 ) satisfy which form a proper subset of C FB (SNR 11 , SNR 12 ). It is important to highlight that in this case, the sum-capacity of C FB (SNR 11 , SNR 12 ) can always be achievable. That is, the power-split β 1 = β 2 = 1 is always feasible. Consider for instance the triplet Q 6 in Fig. 4. The triplet Q 6 is achievable by using Ozarow's perfect feedback capacity-achieving scheme without any powersplitting, since only information transmission satisfies the energy constraint. Fig. 5 In this case, the set B(b) is a proper subset of C FB (SNR 11 , SNR 12 ) and it does not contain the sum-rate pair (R 1 , R 2 ) ∈ C FB (SNR 11 , SNR 12 ). This is clearly shown by Fig. 5. Indeed, for any b > 1 + SNR 21 + SNR 22 + 2ρ (1, 1) √ SNR 21 SNR 22 , the set B(b) monotonically shrinks with b.

Information Sum-Capacity with Feedback and with Minimum Energy Constraint b
The perfect feedback information sum-capacity R FB sum (b) of the G-MAC-F, with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 , given an energy rate constraint of b energy-units per channel use at the input of the EH is the solution to The solution to this problem is given by the following theorem.
Proposition 4 (Perfect Feedback Information Sum-Capacity with Minimum Energy Rate Constraint b). Let b be the minimum energy rate that must be guaranteed at the input of the EH. Then, the perfect feedback information sum-capacity of the G-MAC-F, with parameters SNR 11 , SNR 12 , SNR 21 , and SNR 22 is

RR n°8804
Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels 23 with the function ξ(b) defined in (18).
The proof of Proposition 4 is provided in Section 7 ahead. One of the key observations from Proposition 4 is that if the minimum energy rate b required at the input of the EH is less than what is needed for transmitting information using all the available power budget at the maximum sum-rate, i.e., b 1 + SNR 21 + SNR 22 + 2ρ (1, 1) √ SNR 21 SNR 22 , the minimum energy constraint does not have any impact on the sum-rate (see Fig. 6). That is, in this case the requirement of a minimum energy transmission rate is automatically met by exclusively transmitting information at the sum-capacity.
Nonetheless, when the energy rate required at the input of the receiver is b 1 + SNR 21 + SNR 22 + 2ρ (1, 1) √ SNR 21 SNR 22 , then there exists a loss of sum-rate induced by the fact that at least one of the fractions β 1 and β 2 is smaller than one. More specifically, for these values of b , R i 1 2 log 2 1 + (1 − (ρ(1, 1) ) 2 )SNR 1i for at least one i ∈ {1, 2} and thus, the sum-rate is strictly smaller than the sum capacity.
Clearly, the maximum energy rate is achieved when β 1 = β 2 = 0, which implies that no information is conveyed from the transmitters to the receiver (see Fig. 6).

Main Results: Energy Transmission Enhancement with Feedback
In this section, the enhancement on the energy transmission rate due to the use of feedback is quantized when the information sum-rate is the information sum-capacity without feedback (see the blue triangles and orange squares in Fig. 6). Denote by B NF = 1 + SNR 21 + SNR 22 the maximum energy rate that can be guaranteed at the EH in the G-MAC without feedback when the information sum-rate is the corresponding information sum-capacity without feedback. Denote also by B F the maximum energy rate that can be guaranteed at the EH in the G-MAC with feedback when the information sum-rate is the information sum-capacity without feedback. The exact value of B F is given by the following lemma.
Lemma 2. The maximum energy rate B F that can be guaranteed at the EH in the G-MAC with feedback when the information sum-rate is the information sum-capacity without feedback is with γ ∈ (0, 1) defined as follows: Proof: The maximum energy transmission rate B F when the information sum-rate is the information sum-capacity of the G-MAC without feedback satisfies subject to : 1 + SNR 11 + SNR 12 = min 1 + β 1 SNR 11 + β 2 SNR 12 + 2ρ β 1 SNR 11 β 2 SNR 12 , is the information sum-capacity with feedback when only information transmission is performed and B 1 1 + 2(1 + ρ (1, 1))SNR represents the corresponding maximum energy rate that can be guaranteed at the EH. Blue triangles represent the pairs (B NF , R NF sum (B NF )) in which R NF sum (B NF ) is the information sum-capacity without feedback and B NF 1 + 2SNR is the corresponding maximum energy rate that can be guaranteed at the EH without feedback. Orange squares represent the pairs (B F , R NF sum (B F )) in which B F is the corresponding maximum energy rate that can be guaranteed at the EH with feedback. Black (small) circles represent the pairs (B max , 0) in which B max 1 + 4SNR is the maximum energy rate that can be guaranteed at the EH.
The solution B F to the optimization problem in (72) satisfies that B F ∈ (1 + SNR 21 . Thus, from Theorem 3, it follows that the information sum-rate is exclusively upper bounded by with the function ξ : R + → [0, 1] defined in (18). Note that ξ(b) is monotonically increasing with its argument. Thus, the optimization problem in (72) can be rewritten as follows: where Following the definition of ξ in (18) and solving for B F in (73) yields (70). This completes the proof of Lemma 2.
Consider the general non-co-located asymmetric setup parametrized by: for some deterministic coefficients (a, a 1 , a 2 ) ∈ R 3 + . In this case, γ in (71) reduces to and the ratio BF BNF is given by The following theorem evaluates the very low SNR asymptotics of the energy enhancement with feedback.
and thus feedback does not enhance energy transmission.
Proof: The proof follows immediately from (78). The following theorem provides an upper bound on the ratio BNF BF . Theorem 4 (Maximum Energy Rate Improvement with Feedback). The maximum energy rate improvement with feedback is given by where the upper-bound holds with equality when a 2 = 1, i.e., when SNR 21 = SNR 22 .
Corollary 1. Feedback can at most double the energy transmission rate:   7 compares the exact value of the ratio BF BNF in (78) to the high-SNR limit in (80) as a function of the SNRs in the special case in which the receiver and the EH are co-located. In this case, (78) simplifies to: This implies that the channel coefficients between the transmitters and the receiver can be considered identical to those between the transmitter and the EH., i.e., SNR 11 = SNR 21 = SNR 1 and SNR 12 = SNR 22 = SNR 2 . Note that in the symmetric case, i.e., SNR 1 = SNR 2 = SNR, the upper-bound in (80) is tight as the ratio BF BNF becomes arbitrarily close to two as SNR tends to infinity. In the non-symmetric cases SNR 1 = SNR 2 , this bound is loose.

Proof of Theorem 2
The proof is divided into two parts: achievability and converse parts.

Proof of Achievability
The proof of achievability uses a very simple power-splitting technique in which a fraction β i ∈ [0, 1] of the power is used for information transmission and the remaining fraction (1 − β i ) for energy transmission. The information transmission is made following Ozarow's perfect feedback capacity-achieving scheme in [24]. The energy transmission is accomplished by random symbols that are known at both transmitters and the receiver. Despite its simplicity and a great deal of similarity with the scheme in [24], the complete proof is fully described hereunder for the sake of completeness.
Codebook generation: At the beginning of transmission, each message M i is mapped into the real-valued message point where Encoding: The first three channel uses are part of an initialization procedure during which there is no energy transmission and the channel inputs are Through the feedback links, transmitter 1 observes (Z −1 , Z 0 ) and transmitter 2 observes (Z −2 , Z 0 ). After the initialization phase, each transmitter i ∈ {1, 2} can thus compute where ρ (β 1 , β 2 ) is the unique solution in (0, 1) to (51). During the remaining channel uses 1, . . . , n, for i ∈ {1, 2}, instead of repeating the messagepoint Θ i (M i ), transmitter i simultaneously describes Ξ i to the receiver and transmits energy to the energy harvester. Let β i , with i ∈ {1, 2} be the power-splitting coefficient of transmitter i. More specifically, at each time t ∈ {1, . . . , n}, transmitter i sends Here W t is a Gaussian zero-mean unit-variance random variable that is known non-causally to the transmitters and to the receiver and is independent of the messages and the noise sequences. The symbol U i,t is a zero-mean Gaussian random variable with variance β i P i and is chosen as follows: where the parameter γ i,t is chosen to satisfy E U 2 i,t = β i P i andΞ (t−1) i is explained below. For each t ∈ {1, . . . , n}, upon receiving the channel output Y 1,t , the receiver subtracts the signal induced by the commom randomness to form the observation Y 1,t as follows: The receiver then calculates the minimum mean square error (MMSE) estimatê Ξ (t−1) i = E Ξ i |Y 1,1 , . . . , Y 1,t−1 of Ξ i given the prior observations Y 1,1 , . . . , Y 1,t−1 . By the orthogonality principle of MMSE estimation, (U 1,t , U 2,t , Z t ) are independent of the observations Y 1,1 , . . . , Y 1,t−1 and thus of Y 1,1 , . . . , Y 1,t−1 . Let ρ t denote the correlation coefficient between U 1,t and U 2,t , i.e., ρ t . It can be shown [25] that for all t ∈ {1, . . . , n}, ρ t = ρ (β 1 , β 2 ).

RR n°8804
After reception of the output symbols Y 1,−2 , . . . , Y 1,n , the receiver formŝ Ξ (n) i E Ξ i |Y 1,1 , . . . , Y 1,n , for i ∈ {1, 2}. Then, it forms an estimate of the message point Finally, the message index estimate M i is obtained using nearest-neighbor decoding based on the valueΘ i , as follows: Analysis of the probability of error: An error occurs whenever the receiver is not able to recover one of the messages, i.e., (M 1 , M 2 ) = (M 1 ,M 2 ) or if the received energy rate is below the desired minimum rate B (n) < B.
First, consider the probability of a decoding error. Note that for i ∈ {1, 2}, is a centered Gaussian random variable, by the definition of ∆ i in (84), the error probability P e,i while decoding message index M i can be bounded as where (σ By the joint Gaussianity of Ξ i and Y 1 , the MMSE estimateΞ (n) i is a linear function of Y 1 (see, e.g., [26]). Moreover, by the orthogonality principle, the MMSE Ξ i −Ξ (n) i is independent of the observations Y 1 . Hence, we have where (a) holds becauseΞ Equation (95) can equivalently be written as RR n°8804

Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels 29
Combining (93) with (96) yields that the probability of error of message M i tends to 0 as n → ∞, if the rate R i satisfies On the other hand, as proved in [25,Section 17.2.4], and irrespective of n and t ∈ {1, . . . , n}, it holds that Hence, for i ∈ {1, 2} it holds that and the limit inferior is a proper limit. Combining, (97) and (100) yields that when n → ∞, this scheme can achieve all non-negative rate-pairs (R 1 , R 2 ) that satisfy and by (51) it automatically yields Furthermore, the total consumed power at transmitter i for i ∈ {1, 2} over the n + 3 channel uses is upper bounded by (n + 1)P i , hence, this scheme satisfies the input-power constraints.
Average received energy rate: The average received energy rate is given by B (n) 1 n n t=1 Y 2 2,t . By the choice of the random variables, the sequence Y 2,1 , . . . , Y 2,n is independently and identically distributed (i.i.d.) and each Y 2,t follows a zero-mean Gaussian distribution with variancē B given bȳ By the weak law of large numbers, it holds that ∀ > 0 Consequently, lim n→∞ Pr B (n) >B + = 0, and (104a) From (104b), it holds that for any energy rate B which satisfies 0 < B B , it holds that To sum up, any information-energy rate triplet (R 1 , R 2 , B) that satisfies is achievable. To achieve other points in the information-energy capacity region, transmitter 1 can split its message M 1 into two independent submessages (M 1,0 , M 1,1 ) ∈ {1, . . . , 2 nR1,0 } × {1, . . . , 2 nR1,1 } such that R 1,0 , R 1,1 ≥ 0 and R 1,0 + R 1,1 = R 1 . It uses a power fraction α 1 ∈ [0, 1] of its available information-dedicated power β 1 P 1 to transmit M 1,0 using a non-feedback Gaussian random code and uses the remaining power (1 − α 1 )β 1 P 1 to send M 1,1 using the sum-capacityachieving feedback scheme while treating M 1,0 as noise. Transmitter 2 sends its message M 2 using the sum-capacity-achieving feedback scheme.

RR n°8804
Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels 31 Then, using successive cancellation, the receiver recovers M 1,0 successfully if By substituting R 1 = R 1,0 + R 1,1 , it can be seen that successful decoding of (M 1 , M 2 ) is possible with arbitrarily small probability of error if the rates (R 1 , R 2 ) satisfy Now, the average received energy rate of this scheme is analyzed. The sequence Y 2,1 , . . . , Y 2,n is i.i.d. and each Y 2,t for t ∈ {1, . . . , n} follows a zero-mean Gaussian distribution with variance B given by Here also weak law of large numbers implies that (110) and (111), then any non-negative information-energy rate triplet (R 1 , R 2 , B) satisfying where ρ ∈ [0, ρ (β 1 , β 2 )] and ρ (β 1 , β 2 ) uniquely satisfies equation (51), is achievable. If the roles of transmitters 1 and 2 are reversed, it can be shown that any non-negative information-energy rate triplet (R 1 , R 2 , B) such that for any ρ ∈ [0, ρ (β 1 , β 2 )], is achievable.
Time-sharing between all information-energy rate triplets in the union of the two regions described by the constraints (113) and (114) concludes the proof of achievability of the region for any ρ ∈ [0, ρ (β 1 , β 2 )].

Proof of Converse
Fix an information-energy rate triplet (R 1 , R 2 , B) ∈ E FB (SNR 11 , SNR 12 , SNR 21 , SNR 22 ). For this information-energy rate triplet and for each blocklength n encoding and decoding functions are chosen such that and such that the input power constraint (8) is satisfied.
Using assumption (118a), applying Fano's inequality and following similar steps as in [24], it can be shown that the rates (R 1 , R 2 ) must satisfy nR 1 n t=1 I(X 1,t ; Y 1,t |X 2,t ) + n(R 1 + R 2 ) n t=1 I(X 1,t X 2,t ; Y 1,t ) + n tend to zero as n tends to infinity. Using assumption (118b), for a given n > 0, for any η > 0 there exists n 0 (η) such that for any n ≥ n 0 (η) it holds that Pr(B (n) < B − n ) < η. Equivalently, Using Markov's inequality [27], the probability in (121) can be upper-bounded as follows: Combining (121) and (122) yields which can be written as for some δ n > n (for sufficiently large n). Hence, (119) and (124) are an upper-bound for any (R 1 , R 2 , B) satisfying (118a) and (118b). In the following, the bounds in (119) and (124) are evaluated for the G-MAC-F. For this purpose, assume that X 1,t and X 2,t are arbitrary correlated random variables with Note that from (1), for each t ∈ {1, . . . , n}, it holds that: h(Y 1,t |X 1,t , X 2,t ) = h(Z t ) = 1 2 log 2 (2πe) , from the assumption that Z t follows a zero-mean unit-variance Gaussian distribution. Note also that for any random variable X with variance σ 2 X [28], it holds that h(X) 1 2 log 2 2πeσ 2 X , with equality when X follows a Gaussian distribution. Finally, it is useful to hightlight that for any a ∈ R, it holds that h(X + a) = h(X). Using these elements, the right-hand side terms in


extfieldsofstudy:
Physics
Computer Science

text:
Secure and Efficient Signature Scheme Based on NTRU for Mobile Payment

Mobile payment becomes more and more popular, however the traditional public-key encryption algorithm has higher requirements for hardware which is not suitable for mobile terminals of limited computing resources. In addition, these public-key encryption algorithms do not have the ability of anti-quantum computing. This paper researches public-key encryption algorithm NTRU for quantum computation through analyzing the influence of parameter q and k on the probability of generating reasonable signature value. Two methods are proposed to improve the probability of generating reasonable signature value. Firstly, increase the value of parameter q. Secondly, add the authentication condition that meet the reasonable signature requirements during the signature phase. Experimental results show that the proposed signature scheme can realize the zero leakage of the private key information of the signature value, and increase the probability of generating the reasonable signature value. It also improve rate of the signature, and avoid the invalid signature propagation in the network, but the scheme for parameter selection has certain restrictions.

Introduction
With the widespread use of third-party mobile payment, mobile payment has become a serious area of cyber-crime [1]. During the process of mobile payment, the user needs to send the relevant information about the payment, including the order information, payment information, user or merchant information and so on. These data are related to the security of users' funds, which will have serious consequences if they are exploited by lawbreakers. On the other hand, with the advent of the shor quantum algorithm [2] and the rapid development of quantum computers, the threat of RSA and ECC is increasing. With the improvement of computing performance, the low-security public-key encryption algorithm applied to mobile terminals is no longer safe. The security of third-party mobile payment becomes an important obstacle to mobile payment development and popularization [3].
In the face of the threat of quantum computing to the traditional encryption system, this paper researches public-key encryption algorithm NTRU for quantum computation, which is applicable to the terminal of finite computing resources. In order to satisfy the non-repudiation of information, the main method is digital signature. The classic digital signature schemes are RSA [4] and ECC [5]. These two algorithms have the properties of the public key that can be decrypted correctly using the private key, thus can be used directly as the signature algorithm. However, the efficiency of RSA signature algorithm is very low, and the efficiency of ECC signature algorithm is much slower than that of NTRU. The encryption system NTRU [6] is based on the polynomial ring, and it avoids the modular arithmetic of the big integer power, which only involves the addition and subtraction of polynomials and multiplication. The efficiency of encryption algorithm NTRU is better than RSA and ECC, and encryption algorithm NTRU is considered to be the most future public-key encryption algorithm. However, the encryption algorithm NTRU encrypt using private key and this will leak the information of private key. Therefore, this paper redesigns the signature algorithm based on NTRU.
The rest of paper is organized as follows: Section 2 introduces some related work to our research. In section 3, we propose an improved signature algorithm based on NTRU for the defects, and analyze the security and operation performance. Conclude our paper in the section 4.

Realted Works
Ajtai provided a ground-breaking conclusion [7]: the security of any cryptographic system based on some of the lattice problems is equivalent to the most difficult password system, and presented the AD encryption system based on the most difficult case of u-SVP (unique Shortest Vector Problem) [8]. The scheme can be proved to be safe, but the system is inefficient and cannot meet the practical requirements. Park in [9] proposed a NFC mobile payment system based on zero-knowledge digital signature of NTRU, instead of using users' private information directly, thus ensuring the security of users' privacy. One innovation of the scheme was the use of NTRU encryption technology, achieving user authentication. However, the shortcomings of proposed method were obvious: the digital signature technology of NTRU was still immature. The NTRU encryption algorithm was applied to PKI in [10], which was found to have a large advantage in speed and the CA certificate was generated faster compared with PKI using RSA.
Hoffstein, Pipher, and Silverman in [11] presented NSS signature scheme based on the difficulty of finding CVP of recent vector problems in the grid. The scheme adopted the structure of NTRU algorithm, so the speed of encryption and decryption was relatively fast. Later, Silverman and Mironov in [12] presented the attack on the signature restoring private key. Subsequently, Hoffstein, Pipher and Silverman in [13] proposed the strengthening version of NSS for the attack of Silverman. However, Gentry and Szydlo researched the characteristics of R-NSS as a single secret key, and in [14] presented a large number of attacks on the signature restoring private key by combining the maximal common factor method. And then, Hoffstein in [15] proposed the NTRUSign algorithm, which has a large structural change compared with NSS and R-NSS algorithm, and its secret key is not the characteristic of a single secret key, using a linear combination of secret keys. However, Nguyen in [16] recovered the private key by a large number of valid signature values according to the characteristics of the uniform distribution of NTRUSign secret-key coefficient. Hu in [17] proposed an improved signature scheme based on R-NSS according to the problem of leaking private key of R-NSS and NTRUSign. Li in [18] proposed a novel identity based undeniable signature scheme, and the paper analyzed the proposed scheme was unfalsified and anonymous under stochastic prediction mode.
Melchor in [19] proposed a method to hide the leaking NTRUSign signature value through gaussian noise. At the same time, a strong parameter setting scheme was proposed according to the latest attack on NTRUSign to realize zero knowledge of signature value and anti-counterfeiting attack. Zhang in [20] presented a new type of NTRU signature algorithm based on CVP problem, and the efficiency was about 1/7 faster than the signature algorithm designed by Hu [17]. However, the proposed method did not disturb the private key directly by signing the private key, so the algorithm still has the problem of leaking private key. Hoffstein J, Pipher J, Schanck J in [21] proposed a new signature scheme based on NTRU, called NTRUMLS. The results showed that the security and efficiency of the scheme were relatively high, but the probability of generating reasonable signature was lower and cannot meet the requirement of mobile payment signature. At the same time Xie in [22] put forward a kind of identity signature scheme based on NTRU lattice, and the security of the scheme was based on SVP - difficult problems. An obvious advantage of the proposed method was the efficiency is higher than the same digital signature scheme based on grid.
As a result, the researches on the signature scheme of NTRU were mainly the improvement of NSS, R-NSS and NTRUSign. On one hand, proposed solutions for the classic attack schemes, and on the other, proposed new signature schemes based on NTRU. However, few of the above were suitable for Besides, the probability of reasonable signature value of signature scheme based on NTRU is less than 1, and even some valid probability of signature scheme cannot meet the practical demand. Therefore, it was not suitable for application in a large number of users in mobile payment.

Secure and Efficient Signature Scheme For Mobile Payment
Through the research of the proposed signature scheme NTRUMLS [21] by Hoffstein, the analysis showed that the proposed method can realize zero knowledge of signature value. But the proposed scheme had the problem that the effective of signature value was low. For a lot of users of mobile payments, a large number of invalid signature value would greatly aggravate network congestion and the burden of service systems. This paper proposes two ways to improve the signature probability of NTRUMLS by analyzing the influence factors of the probability of reasonable signature value of NTRUMLS. Firstly, select reasonable parameter to narrow down the space to find a valid signature, and ensure that the signature value has a larger probability in the L∩R range. Secondly, during the process of signature, filtrate the conditions that satisfy a valid signature value, and we can ensure that the generated signature values are reasonable.

Increasing the probability of reasonable signature
According to the related parameters recommended by NTRUMLS [21], the probability of reasonable signature value generated by NTRUMLS is shown in table 3.1.  In regard to the probability of reasonable signature value generated by NTRUMLS, this paper can be inspired by another parameters.
Compared with table 3.1 and table 3.2, we can find that the change of parameters has a great influence on the probability of reasonable signature value generated by NTRUMLS. Therefore, this paper can be inspired by setting relevant parameters to improve the probability of reasonable signature value generated by NTRUMLS.
Firstly, this paper studies the correlation factors of the probability of reasonable signature value generated by NTRUMLS. For the convenience of research, this paper set   setting parameters, q must be much larger than B, or the probability of generating a reasonable signature will be small. Consider the general form of signature value: In the formula (1) above, In the formula (2) above, the coefficients of s and t are less than Then make: We can obtain: In the formula (5) above k is a small constant. From the above analysis, it can be seen that the probability of generating a reasonable signature is about k e 9  . And it is associated with constant k.
Therefore, the improved method can be realized by raising constants k to improve the accuracy of generating a reasonable signature. The influence of constant k on the probability of generating a reasonable signature is shown in figure 3.1.
According to figure 3.1, constant 12  k when the probability of generating a reasonable signature is about 50%. If we raise the constant k to 25, the probability of generating a reasonable signature will be greater than 70%. So it will be a feasible scheme by increasing the constant k. In the formula NB q k  , parameter N responds to the security of NTRUMLS, and therefore N cannot be changed. Parameters can improve performance. However, it brings difficult to find suitable signature value. Therefore, according to the above analysis, it is possible to appropriately improve the value of parameter q. We    Comparing table 3.1 with table 3.3, it can be seen that the probability of generating a reasonable signature value is obviously improved through double the value of parameter q. However, if you want to make the reasonable signature value close to 100%, the value of parameter q will become very large, and the following will discuss the effect of parameter q on the performance of NTRUMLS. Because key structure of NTRUMLS is similar to the NTRU, so parameter q has little impact on the rate of NTRUMLS through the analysis above. Key sizes of NTRUMLS and cipher text size is related to parameters N, q has no effect on it. Therefore, in order to improve the probability of generating a reasonable signature value, the solution given in this paper is to improve the parameter q appropriately. Table 3.3 is the revised parameter q given in this paper.

Adding Authentication Conditions for Signature
The template is used to format your paper and style the text. All margins, column widths, line spaces, and text fonts are prescribed; please do not alter them. You may note peculiarities. For example, the head margin in this template measures proportionately more than is customary. This measurement and others are deliberate, using specifications that anticipate your paper as one part of the entire proceedings, and not as an independent document. Please do not revise any of the current designations. According to literature [20], if   In this paper the proposed signature scheme is an improvement of NTRUMLS, and there is no significant change in the algorithm structure, so its security depends on NTRUMLS. According to analysis of the literature [20], this signature can guarantee the security of private key information. Therefore, the security of signature algorithm is fully guaranteed. Efficiency performance: In this paper, the proposed signature scheme is compared with that of NTRUMLS: firstly, the probability of parameter q is improved greatly, so that the probability of reasonable signature is improved. Second, the authentication conditions are added to avoid the illegal signature value spreading through the network. Table 3.4 reflects experiment contrast of the proposed signature scheme is given in this paper and NTRUMLS. Test environment is: the system is android 5.0, CPU is Intel Z3560 of dominant frequency of 1.8 GHz, memory is 4g. The result is the average of the data of 100. According to table 3.4, the key generation time and authentication time of the proposed signature scheme are slightly higher than NTRUMLS in the key generation phase. This is because the parameter q is twice larger, which slightly increases the calculation of the key generation, but this is small. The worst time complexity of key generation of the proposed signature scheme in this paper is As can be seen from the above data, the parameter N has great influence on proposed signature scheme, and q has little influence on its speed. The result also verifies the discussion of the key generation and decryption speed of the parameter q for NTRU.
In theory, the parameter q becomes larger and the signature time will become longer in the signature phase. But there will be a significant reduction in the time of generating signature. This is because the signature phase is a process of finding a reasonable signature, and if the selected signature value does not meet the criteria, the signature process will be repeated until it is found to satisfy the given condition. In this paper, the parameter q of the proposed signature is larger than that of to be sent to the validation party, in the proposed signature scheme the authentication conditions are supplemented during the signature phase, in order to ensure that all signature values are valid. The verification condition is the mode of the signature value, so the calculation is very small, and the influence of the signature time is very small, so the signature time can be shortened greatly.
At the same time, under the condition of parameter q of the proposed signature scheme in this paper change for 2 times, the key size and signature size have no change. So the proposed scheme is secure and efficient which can raise the speed and probability of generating reasonable signature value.

Conclusion
This paper researches the non-repudiation of data in mobile payment process, considering traditional RSA, ECC and other signature schemes are less efficient and do not have the ability of anti-quantum attack, and we introduce the signature scheme based on NTRU in this paper. However, several classical NTRU signature algorithms, include NSS, R-NSS, NTRUSign, exist the problem of leaking private key information and the classical NTRU signature algorithms NTRUMLS, which has unsatisfactory probability of generating a reasonable signature value. On the basis of these classical signature scheme, this paper proposed an efficient and secure signature scheme which is suitable for mobile payment by increasing the value of parameter q and adding the authentication condition that meet the reasonable signature requirements during the signature phase. Experimental results show that the proposed signature scheme can realize the zero leakage of the private key information of the signature value, and increase the probability of generating the reasonable signature value. It also improve rate of the signature, and avoid the invalid signature propagation in the network, but the scheme for parameter selection has certain restrictions.

Acknowledgment
This research is supported by the National Natural Science Foundation of China (NO.61672299, NO61373135). The authors thank the sponsors for their support and the reviewers for helpful comments.