extfieldsofstudy:
Computer Science
Mathematics

text:
Achieving Large Sum Rate and Good Fairness in MISO Broadcast Communication

A tradeoff between sum rate and fairness for MISO broadcast communication employing dirty paper coding or zero-forcing dirty paper coding at physical layer is investigated in this paper. The tradeoff is based on a new design objective termed"tri-stage"approach as well as a new L1-based fairness measure that is much more robust than the well-known Jain's index for comparing fairness levels achieved by various design objectives at a much finer resolution in high SNR regime. The newly proposed tri-stage design also introduces a new concept of statistical power allocation that randomly allocates powers to users based on an optimal probability distribution derived from the tradeoff between sum rate and fairness. Simulation results show that the proposed approach can simultaneously achieve a larger sum rate and better fairness than the reputable proportional fairness criterion. A performance upper bound is also given in the paper to show that the excellent performance of the proposed approach at moderate and high SNR regimes as well as some potential for further improvement in low SNR regime.

I. INTRODUCTION
In the downlink of wireless communication, a multi-antenna transmitter could send information simultaneously to multiple single-antenna users. Such communication channel is commonly referred to as the multiple-input single-output (MISO) broadcast channel (BC) in the literatures [1]. It is the dual of SIMO (single-input multiple-output) multiple-access channel (MAC) [2], where multiple single-antenna users send information simultaneously to a common multi-antenna receiver. The MISO BC has appeared widely not only in traditional mobile communications, but also in the latest Internet of Things (IoT) and device-to-device (D2D) communication systems [3].
When broadcasting information to all users, the transmitter could apply the well-known dirty-paper-coding (DPC) scheme [4], [5] for encoding messages, provided that 1) a certain ordering of users has been established a priori, 2) each user has a perfect knowledge of the channel state information (CSI) of his/her incoming channels, and 3) the transmitter has a complete knowledge of the CSI of all users. The second requirement is commonly referred to as the CSIR -CSI at receiver -and can be achieved through channel estimation; the last requirement is coined as the CSIT -CSI at transmitter -in the literature and can be realized by using a feedback channel from the users to the transmitter. These requirements can be easily achieved, as the mechanisms for channel estimation and feedback already exist in modern communication systems [6]. Armed with the ordering and complete knowledge of CSI, the DPC strategy successively encodes each user's message taking into account the noncausal knowledge of interference signals caused by preceding users. The scheme then converts the broadcast channel into a special kind of the Gelfand-Pinsker channel [7] with states non-causally known at the transmitter. The DPC strategy not only achieves the capacity of the Gelfand-Pinsker channel [4], [8], but also turns out to be optimal for MIMO BC. To elaborate, Caire and Shamai [1] investigated the capacity region of the two-user BC when the base station has arbitrary number of transmit antennas and each user has only single receive antenna. They showed through direct calculation that the DPC is optimal in terms of achieving the sum capacity of the two-user MISO BC. Weingarten et al. [9], [10] studied the capacity region of Gaussian MIMO BC based on the notion of an enhanced broadcast channel under a wide range of input constraints, including the total power and per-antenna constraints. They showed that the capacity region coincides with the DPC rate region. An alternative proof for the capacity region of degraded Gaussian MIMO BC without using the notion of enhanced channel can be found in [11].
Many iterative algorithms [12], [13] have been proposed to find the optimal coding (beamforming) vector associated to each user in the DPC strategy, aiming to maximize the overall sum rate. These algorithms are based on the duality between the MAC and BC [14] and suffer from a relatively high computational complexity. In [1] Caire and Shamai proposed a suboptimal transmission strategy, termed zero-forcing DPC (ZFDPC), that combines both the advantages of zero-forcing beamformer and DPC for MISO BC, when the number of transmit antennas at base station exceeds or equals the number of single-antenna users. The ZFDPC eventually decomposes the MISO BC into a group of parallel interference-free channels and simplifies the problem of finding optimal coding vectors, but is at a cost of certain capacity loss. Since then, the idea of combining zero forcing and DPC has been applied to many other communication problems. For instance, Dabbagh and Love [15] extended the work in [1] and proposed a successive ZFDPC encoder for the MIMO broadcast channel, i.e. when the users are equipped with multiple receive antennas. Mohammed and Larsson [16] proposed a usergroup based ZFDPC precoder by splitting users into disjoint groups. Hu and Rusek [17] considered a generalized zeroforcing beamforming that is not only orthogonal to the channel vectors of the succeeding users but also to part of those of the preceding users, thereby yielding a generalized ZFDPC strategy, where the DPC encoder only has to take into account the multiuser interference caused by a small constant number of immediately preceding users.
All the above works share a common objective, namely, maximizing the sum of transmission rates of users [8], and care less whether the scheme is equally beneficial to the individuals. In other words, there can be two (contradicting) objectives for designing communication schemes for BC, one from the transmitter's viewpoint, i.e. sum rate maximization (as all the above schemes do), and the other from the viewpoint of each user, i.e. fairness maximization. Generally speaking, the former objective can be mathematically and quantitively expressed using the formula of achievable rates of the communication scheme used, say DPC, ZFDPC, ZF beamforming, etc., but the notion of fairness is unfortunately much harder to be quantified. Several conceptual, philosophical and qualitative definitions of fairness, such as proportional fairness [18], harmonic mean fairness [19], max-min fairness [20], etc. have been proposed in the literature, each holding a different opinion regarding how it means to be fair. There are also some quantitive measures for fairness in the literatures. Plausible fairness measures are generally required to satisfy axioms such as continuity, homogeneity, asymptotic saturation, and monotonicity [21]. Examples of such fairness measures are the entropy-based index [22], Jains fairness index [23], αfairness from networking research community [18], [20], and a much more complicated construction [21] that includes many existing measures as special cases. In particular, α-fairness measure can be used to justify some of the aforementioned qualitative approaches for fairness by varying the parameter α. For instance, setting α = 0 yields the aim of sum rate maximization [21]. Setting α = 1 gives the proportional fairness criterion, and the case of α = ∞ corresponds to the max-min fairness. Studies of tradeoffs between sum rate and fairness also appear in literatures. In [24], Sediq et al. investigated such tradeoff at network level based on Jain's index and α-fair utility [20]. In particular, the transmission rates in [24] were replaced by the numbers of resource blocks allocated to each user in the downlink of wireless networks using OFDM, thereby yielding an orthogonal communication. Such communication scheme is extremely suboptimal in terms of maximal achievable rates from the viewpoint of multiterminal information theory [1], [8], [10], [11], [25], since orthogonal schemes have sum degrees of freedom always equal to one, regardless of the increase of transmit antennas and users. It then leaves a significant room for improving the tradeoff between rates and fairness.
In this paper, we will investigate the tradeoff between the sum rate and fairness for MISO BC at physical layer by employing communication schemes such as DPC or ZFDPC to guarantee the close-to-capacity performance. In addition, we will aim to provide a systematic design that can offer not only a good sum rate but also a reasonable fairness to all users at the same time. To this end, we will first review in Section II the system model of MISO BC as well as the DPC and ZFDPC strategies. In Section II-B we will discuss several commonly used design objectives derived from the qualitative notions of fairness. Quantitive fairness measures will be discussed in Section II-C. In particular, it will be seen that the Jain's index, though widely accepted as a fairness measure, behaves less sensitive to the fluctuations of transmission rates in high SNR regime. An alternative measure based on 1 -norm will be proposed in Section II-C for replacement. The new measure is easily computable and satisfies almost all axioms listed in [21]. In Section III we will present the new design objective, termed tri-stage, which takes into account both the qualitative and quantitive aspects of fairness. As the name suggests, the proposed approach consists of three stages, where the first two stages aim to obtain a tradeoff between sum rate and fairness as well as a byproduct which will be discussed next. Note that the tradeoff is just a function relating sum rate to fairness and says nothing about which pair of sum rate and fairness should be chosen for operation. Choosing the operating pair can be philosophically hard. For instance, it is arguable to allege that scheme A having a sum rate of 10 bits per channel use and 90 per cent fairness is better than scheme B having a sum rate of 11 bits per channel use and 80 per cent fairness, and vice versa. One might assert that schemes A and B are equally good as they are both Pareto optimal points on the sum rate-fairness tradeoff curve from the viewpoint of operational research. Yet, it would be universally agreed that another Pareto optimal, equally good scheme C having a sum rate of 12 bits per channel use and 10 per cent fairness should be totally unacceptable. Thus, we will turn to the qualitative notion of fairness to decide the operating pair in the third stage of the proposed design. Achieving the sum rate and fairness of the chosen operating point makes use of the byproduct obtained in the first two stages: a new concept of statistical power allocation, which is in sharp contrast to the fixed, deterministic method used in all existing wireless/wired communication systems. The new scheme randomly -based on an optimal probability distribution derived from the tradeoff -allocates powers to users, thereby offering not only a larger sum rate but also a better fairness than the existing designs. Several simulation results will be provided in Section IV-B to justify the excellent performance of the proposed approach. Concluding remarks are given in Section V.
The following notations have been used in this paper. Underlined lowercase letter x represents a vector, and uppercase letter A denotes a matrix of certain size. A † (resp. A ) denotes the Hermitian transpose (resp. transpose) of matrix A, and A p denotes its p norm for some p ≥ 1. I n is the (n × n) identity matrix. a, b is the usual Euclidean inner product for a, b ∈ R n . Matrix inequalities such as , , and ≺, are the partial orderings of positive semi-definite matrices [26,Section 7.7]. We say x ∼ CN (m, K) when x is a circularly symmetric complex Gaussian random vector with mean m and covariance matrix K.

II. THE MISO BROADCAST CHANNEL
Consider a K-user MISO broadcast channel, where each user has only one antenna and the base-station has N antennas. Assume that with a codebook X ⊂ C N the base-station transmits x ∈ X simultaneously to all users, subject to an average power constraint E x 2 2 ≤ P . With an implicit ordering of users, the signal received by the k-th user is given by where h k ∈ C N is the channel vector from the base-station to the k-th user, and w k ∈ CN (0, 1) is the additive complex Gaussian noise associated with the channel. Assume further that the transmitted signal can be decomposed into where x k is the signal intended for the k-user and satisfies E x k 2 2 ≤ p k . The signals x k are statistically uncorrelated, so we have p 1 + · · · + p K ≤ P , i.e. the total power constraint. We will assume throughout the paper that the channel vectors {h k } are known perfectly to the base-station, but each user, say user k, knows only the channel vector h k of his/her own incoming channel. Substituting (2) into (1) gives an alternative expression of the received signal of user k where s k is the interference caused by preceding users and z k is the overall noise consisting of the signals of succeeding users and the Gaussian noise w k . Specifically, we have

A. Coding Strategies
When the channel vectors {h k } are all known completely to the transmitter, i.e. the full CSIT scenario, it is known that the capacity region of the MISO BC -with respect to the specific ordering of users -can be achieved by coding strategies such as DPC [9], [10], which encodes the message of user k taking into account the noncausal knowledge of interference signal s k caused by preceding users. Specifically, assume the signal vectors as the x k 's are uncorrelated by hypothesis. Focusing on the k-th user, the standard approach of DPC uses the following auxiliary random vector to construct a random codebook for user k, where is chosen such that v k − y k β k and y k are statistically uncorrelated. Regarding s k as the side-information known to the transmitter (i.e. the base-station encoder), but not to the receiver (i.e. the decoder of the k-th user), the maximal achievable rate of the k-th user equals that of the Gelfand-Pinsker channel and is given by in bits per channel use. Thus, the maximal sum rate achieved by DPC in MISO BC with respect to the specific ordering of users equals which could be further increased by optimizing over all possible K! orderings of users. Several iterative algorithms [12], [13] have been proposed to tackle the complicated optimization problem (10), but the required computational complexity is generally high. Caire and Shamai [1] proposed a much simpler but suboptimal transmission strategy, termed zero-forcing DPC (ZFDPC), that combines both advantages of zero-forcing beamformer and DPC for MISO BC when K ≤ N (the situation when the base station has more transmit antennas than the number of single-antenna users). Given a pre-determined ordering of users, the ZFDPC encoder uses zero-forcing beamformer to ensure that the coding (beamforming) vector of each user is orthogonal to the channel vectors of all preceding users, thereby avoiding the interference caused by succeeding users. At the same time, the ZFDPC applies the DPC scheme to eliminate the multiuser-interference caused by preceding users. Mathematically, the ZFDPC can be formulated as a special case of DPC when restricting to one-dimensional signaling for all users, i.e. the case when the covariance matrices K k are of rank 1 and are decomposed as K k = p k q k q † k , for some unit-modular beamforming vector q k . Consequently, the signal vector of the k-th user takes the following form for some x k ∈ C satisfying the average power constraint E |x k | 2 ≤ 1. The beamforming vector q k is required to be orthogonal to the channel vectors of all preceding users, i.e. it satisfies Substituting (11) and (12) into the channel input-output equation (3) shows that the received signal of the k-th user is The first term i<k √ p i k,i x i of (13) can be seen as the interference caused by preceding users and can be eliminated by employing DPC at transmitter in a form similar to (7). Thus, the ZFDPC literally decomposes the MISO BC into a group of parallel interference-free channels, at a cost of certain capacity loss. The values of {q k } and { k,i } can be easily (and optimally) determined as follows. Let be the overall (K × N ) channel matrix that is completely known to the base-station. Then the optimal choices of {q k } and { k,i } are given by the QR-decomposition of matrix H † ; is an (N × K) matrix with orthonormal columns, and L = [ k,i ] is a lower triangular matrix of size (K ×K). The desired signaling vectors q k are exactly the column vectors of Q and are proved to be optimal for arbitrary performance measure, whenever the total power constraint is enforced [27]- [30].
To summarize, the ZFDPC strategy first converts the problem of MISO broadcast communication into that of SISO broadcast communication, by restricting to one-dimensional signaling and rank(K k ) = 1, at the cost of a certain loss in the maximal achievable rates. The SISO broadcast channel is then further ramified -with help from beamforming and DPC -into a set of parallel interference-free SISO pointto-point channels, undertaking another loss in capacity, due to the constraints (12) imposed to eliminate the interference signals from succeeding users. Compared to the DPC (cf. (9)), the maximal achievable rate of the k-th user using ZFDPC is given by provided that the x k 's (cf. (11)) are encoded by a SISO DPC. Despite a certain capacity loss, it has been shown in [1] that the ZFDPC remains asymptotically optimal in high and low SNR regimes, provided that the {h k } are linearly independent.

B. Qualitative Approaches of Fairness
It can be seen from (9) and (15) that the achievable rates of either DPC or ZFDPC are functions of individual powers p 1 , . . . , p K . Thus, how to distribute the total power P to each user calls for a specific design-objective. Many objectives have been formulated and proposed in the literature, each involving a certain qualitative consideration of fairness. Below we will briefly review four objectives commonly used in the field of wireless network communications. For simplicity, these objectives will be presented in the form of ZFDPC, and we will write the achievable rate of the k-user (cf. (15)) as R ZFDPC,k (p), where p = [p 1 , . . . , p K ] ∈ (R + ) K , to emphasize the dependence upon power distribution. These objectives can also be easily rephrased for DPC -simply replacing R ZFDPC,k (p) with R DPC,k (p) (in (cf. (9)) subject to additional constraints tr(K k ) ≤ p k for k = 1, . . . , K.
The first design-objective seeks to maximize the overall sum rate and is formulated as This objective has no concern of fairness among the users; it only aims to maximize the sum of transmission rates of all users, which is an ordinary goal in conventional multi-terminal information theory [8].
The second design-objective, termed proportional fairness [18], [31], seeks an optimal generalized Nash solution to the K-player problem [32], where a power distribution p pf is said to be optimal if replacing p pf with any other p results in a negative aggregate proportional value of each user's rate, i.e.
Such design-objective follows directly from the Nash standard for fairness: a transfer of resources (i.e. power in our scenario) among users is favorable and fair if the sum of the percentage increases of each user's rate is positive. The optimal distribution p pf can be found by solving the following optimization problem [31] p pf = arg maximize p k log R ZFDPC,k (p) subject to 1 p ≤ P, p 0 (18) and yields the following sum rate for ZFDPC The third frequently used design-objective is to maximize the "average" of the rates of users. Such "average" should not be the usual arithmetic mean, for otherwise the objective would be equivalent to the maximal sum rate given in the first design-objective. Instead, researchers resort to the harmonic mean [19], and the design-objective is to seek a power distribution that maximizes the harmonic mean of the rates, i.e. 20) and the resulting sum rate is The last commonly used design-objective is termed maxmin criterion introduced by Kalai and Smorodinsky [33]. It aims to maximize the lowest rate among all users, thereby improving the worst-case performance. The criterion can be easily formulated as subject to 1 p ≤ P, p 0 (22) and the resulting sum rate is We remark that all the four optimization problems, (16), (18), (20) and (22), can be easily solved by standard convexoptimization techniques. Solution to the last design-objective, i.e. max-min criterion, is particularly simple and has an analytical form. The optimum is achieved when all rates are equal, i.e.
hence the power p mm,k allocated to the kth user is given directly by

C. Quantitive Approaches of Fairness
Each of the design objectives discussed in the previous section has its own take of fairness. Without a common and quantitive measure, it is unlikely to tell which design-objective is better, subject to a constraint on the overall sum rate. The sum rate constraint is particularly important; without it the max-min criterion would surely be the fairest, as all rates are equal (cf. (24)), but at the same time it has the lowest sum rate among the four. This is of course generally not preferred in wireless communications.
Generally accepted quantitive measures for fairness include entropy-based index [22], Jain's index [23] and α-fairness. For simplicity, here we will focus only on Jain's index, while all upcoming discussions can be easily reformulated in terms of other fairness measures. The Jain's index satisfies all the conditions in [21] for being a plausible fairness measure and has been widely used in many areas, including wireless communication. The formal definition of Jain's index is reproduced below.
Definition 1: Given a set of achievable rates {R k : k = 1, . . . , K}, the corresponding Jain's index for fairness is where is the normalized rate vector.
It should be noted that in (26) we have reformulated the Jain's index in terms of the normalized rate vector γ, rather than the actual rates R k 's that generally appear in literatures [23], [24], [34]. The new formulation in γ actually gives a better insight into how the function J(γ) measures fairness in general -much more than simply being the ratio of the squared first moment to the second moment. To this end, note that we have 1 K ≤ J(γ) ≤ 1 for any set of rates, where the upper bound represents the case of 100 per cent fairness, and the equality holds if and only if all rates are equal, i.e. when the normalized rate vector equals e = 1 K 1. The lower bound 1 K of J(γ) comes from the fact that γ 2 ≤ γ 1 = 1 and (26). The proposition below then shows that the Jain's index J(γ) can be related to the geometric angle between vectors γ and e: the smaller the angle is, the more similar γ is to e; hence the fairer the rates are to the users, and the closer to value 1 the Jain's index should be. Proposition 1: Given the normalized rate vector γ, let θ be the angle between γ and e = 1 K 1 in the Euclidean inner product vector space R K . Then the Jain's index can be alternatively defined as Proof: It follows directly from the definition of cosine in R K , namely, where the last equality is due to γ, e = 1 K and e 2 2 = 1 K .
Unfortunately, Proposition 1 also reveals a disadvantage of Jain's index when used as the fairness measure, despite satisfying all the axioms listed in [21]. To see this, note that from Taylor's expansion of cos(θ) in (28) we have 1 for small values of θ, i.e. |θ| 1. When γ is close to e (with respect to any normed distance in R K ), we have cos(θ) close to 1 and θ close to 0; then the Jain's index J(γ) becomes insensitive to the variation of θ because of the quadratics. Such phenomenon is particularly pronounced in the high SNR regime, where the total power P is large and all users have similar rates for transmission. In other words, when P is large, all the approaches for qualitative fairness discussed in the previous section, either max sum rate, proportional fairness, harmonic-mean or max-min, have the same form of asymptotic rate log 2 (P ) + O(1) for each user. Then, the rates of various approaches differ only in the O(1) term, which quickly vanishes when computing the ratios in γ. It is therefore difficult to tell which approach yields a better fairness if the Jain's index were used as the quantitive fairness measure. An alternative measure for fairness is thus proposed below to avoid such disadvantage.
Definition 2: Given the normalized rate vector γ defined in (27), the proposed measure for fairness is where γ − e 1 is the 1 distance from γ to the equal-rate vector e.
Same as the Jain's index, we have F (γ) = 1 if and only if γ = e for the 100 per cent fairness. The factor K 2(K−1) appearing in the second term of F (γ) comes from a consideration occurred in the most unfair case. Note that the normalized rate vector γ is nonnegative and has a unit 1 norm, i.e. 1 γ = 1. It is easy to show that the largest 1 distance for γ to deviate from e is sup γ − e 1 : γ 0, γ 1 = 1 = 2(K − 1) K .
Thus, with the additional factor K 2(K−1) in (29) we have normalized the range of fairness function F (γ) to [0, 1], where the minimum value 0 now indicates the most unfair distribution of rates among the users.
The function F (γ) also satisfies the axioms of continuity, homogeneity, asymptotic saturation, and monotonicity, that are required for being a plausible fairness measure [21], and is much easier to compute than the Jain's index. The resolution range of F (γ) -from 0 to 100 per cent -is independent of the number of users and is broader than the Jain's index, which has value 1 K for the most unfair case. It is also much more sensitive to the small changes of θ as shown by the following theorem.
Theorem 2: Given the normalized rate vector γ, we have for small θ defined in Proposition 1.
Proof: It follows from the proof of Proposition 1 that The proof is complete after invoking the following standard inequality between 1 and 2 norms and hence It follows that the newly proposed fairness measure F (γ) varies linearly with θ when γ is in the neighborhood of e -a region of far more interest in practice. Hence, it can provide a better resolution for comparing the fairness achieved by various qualitative approaches.

III. TRI-STAGE APPROACH
In the previous section we had discussed four commonly used design-objectives for distributing powers among users, namely, the max sum rate, proportional fairness, harmonic mean and max-min criteria, each offering a different sum rate and a different degree of fairness. The max sum rate problem (cf. (15) and (16)), in particular, can be easily solved by waterfilling method and results in the largest possible sum rate. However, when the total power P is small, users with small values of | k,k | 2 (cf. (15)) will not be given any powerbecause of the water-filling strategy -and therefore have zero transmission rate. Hence, the max sum rate criterion has unfortunately the worst fairness-performance among the four. The max-min criterion, on the other hand, offers an undisputed fairness as all users have the same transmission rate, but it has the smallest sum rate. The other two objectives, the proportional fairness and harmonic mean criteria, provide moderate sum rates and reasonable fairnesses. The aim of this section is to come up with a new design-objective that can offer a larger sum rate and at the same time better fairness, compared to those obtained by the proportional fairness criterion. The proposed method consists of three stages: cake-cutting, mixing and selection stages. For simplicity, it will be presented in the form of ZFDPC, while it can be easily reformulated for other strategies such as DPC to achieve better performance, but at a cost of much higher computational complexity.

A. The First Stage: Cake-cutting
In the first stage, we divide the overall power P -namely, the cake -into two portions, cP and (1 − c)P for some c ∈ [0, 1]. The portion cP is first distributed among all users following the max-min objective. This would ensure that all users are included in the broadcast and no one is left behind, thereby establishing a basic guarantee of fairness. Once the "basic" need of each user is satisfied, we move on to the second wave of power allocation and distribute the remaining power (1−c)P to all users; only this time we aim to maximize the overall sum rate.
Specifically, given any c ∈ [0, 1], we first distribute the power cP among all users employing the max-min objective for optimization maximize min k R ZFDPC,k (p) subject to 1 p ≤ cP and p 0 By (25) the optimal solution to the above problem is The next step is to distribute the remaining power (1 − c)P among all users, aiming to maximize the overall sum rate. Hence, we seek solutions to the following optimization problem p 2 (c) = arg maximize p k R ZFDPC,k (p + p 1 (c)) subject to 1 p ≤ (1 − c)P and p 0 (33) Finally, the overall power-allocation vector (parameterized by the splitting factor c) is the sum of the power-allocation vectors from both steps, and this completes the first stage of the proposed design. The power-allocation vector p(c) in turn gives transmission rate R ZFDPC,k (p(c)) of user k and an overall sum rate R sum (c) := k R ZFDPC,k (p(c)).
The corresponding fairness value, measured by the newly proposed 1 -based function in (29), equals where e = 1 K 1 is the equal rate vector and Thus, by the end of this stage we have obtained a wide spectrum of achievable sum rates and fairnesses {(R sum (c), F(c)) : c ∈ [0, 1]}. Note that both max sum rate and max-min criteria are covered by setting c equal to 0 and 1, respectively.

B. The Second Stage: Mixing
The key to the second stage is the observation that wireless channels are often quasi-static, meaning that the channel vectors h k can hold constant and unchanged for many channel uses. Within the constant-valued channel block, a fixed choice of c is not necessarily the best for all transmissions, and a mixed strategy of using various c's could actually offer better sum rate and fairness. Finding the best mixed strategy calls for an optimal tradeoff between achievable sum rate and fairness. Given the desired sum rate R, the best fairness that our design can offer is characterized by the following function plays the role of time-sharing among all possible ways to cut a cake: the probability of c being used for the cake-cutting is exactly w(c). In other words, for a quasi-static block of T channel uses, the vector p(c) will be used for power allocation in approximately T · w(c) times. Equation (37) then seeks the best possible strategy for combining the c's to yield the largest possible degree of fairness, provided that the average sum rate R is to be achieved.

C. The Third Stage: Selection
The optimal sum rate-fairness tradeoff F max (R) given in (37) provides a set of sum rate-fairness pairs {(R, F max (R)) : R ∈ R} that can be achieved by our "mixed" power-allocation strategy. It does not say which pair should be chosen for operation. In fact, it is impossible to make any rational choice of the operation point, without having an explicit rule dictating quantitatively how much more important the sum rate to the fairness is. The Nash standard [31], [32] argues -in the qualitative sense of fairness -that the best sum ratefairness pair should satisfy that any deviation from the power distribution p pf (cf. (18)) would incur a negative aggregate proportional change of the rates (cf. (17)). The standard does not invoke explicitly (or implicitly) any quantitive measure of fairness; therefore it is not necessarily the best selection rule from the viewpoint of tradeoff F max (R). Specifically, the proportional fairness criterion yields the following sum rate where It is easy to show that for K = 2 meaning that the proportional fairness criterion cannot be any fairer than the tri-stage design, with respect to the newly proposed fairness measure (29). In other words, as far as the two-player problem [32] is concerned, the proposed tristage scheme could potentially offer performance better than proportional fairness, which is derived from the Nash standard [31]. There are at least three implications from the inequality (40): 1) we could use the proposed tri-stage method to send information to all users at rate R sum,pf -same as that of proportional fairness -and obtain a better fairness F max (R sum,pf ), or 2) we could send at a rate slighter higher than R sum,pf and get a fairness value between F pf and F max (R sum,pf ), or 3) we could sacrifice a little bit on the rate in exchange for a better fairness. As already said, all is not clear unless we are given a specific rule weighing the importances between sum rate and fairness. On the other hand, when such rule is not available, the proportional fairness criterion remains to be a good starting point to search for operation points on F max (R) as the Nash standard has performed very well in many areas of engineering and economics since its first appearance. Thus, given the pair (R sum,pf , F pf ) from the proportional fairness criterion, we propose to seek a point on curve F max (R) that offers slightly better performance than (R sum,pf , F pf ) -a small wish that can be easily granted. The exact proposed operating pair is the following (R sum,tri , F tri ) := Algorithm 1 The Proposed Statistical Power Allocation Strategy to Achieve (R sum,tri , F tri ) Input: The desired average sum rate R sum,tri and desired average fairness F tri with F max (R sum,tri ) = F tri ) 1: Find an optimal solution w * (c) to the optimization problem (37), i.e. the nonnegative-valued function w * (c) satisfies where R sum (c) and F(c) are defined in (35) and (36), respectively. 2: Generate a random value C ∈ [0, 1] based on the probability density function w * (c). Use the power allocation vector p(C) (cf. (34)) obtained from the first stage to distribute the total power P among users and perform broadcast communication using ZFDPC. 3: Repeat Step 2 for various C's within the quasi-static channel block.
where the second case is just an insurance policy in case our wish is denied, and where the first case echos the third implication discussed in the above paragraph. A simple illustration of the proposed selection method is given Figure  1, where the pairs (R sum (c), F(c)) are from the cake-cutting stage for some c ∈ [0, 1]. It should be noted that the solid line formed by {(R sum (c), F(c)) : c ∈ [0, 1]} is in general not convex; we only make it so for the illustration purpose. The dashed line represents the optimal sum rate-fairness tradeoff F max (R) resulting from the mixing stage. The point marked by an X is (R sum,pf , F pf ) obtained by the proportional fairness criterion; the point marked by an O is the proposed operating point (R sum,tri , F tri ) given by the selection rule (41) and can be achieved by using a statistical power allocation method outlined in Algorithm 1.
To summarize, the proposed tri-stage design first finds a tradeoff F max (R) between the sum rate and fairness based on a statistical two-step cake-cutting method -the parameter c from the first stage is seen as a random variable in the second stage. We then use the proportional fairness as a starting point to choose the operating point (R sum,tri , F tri ) on F max (R). For quasi-static channels, the proposed design also offers a statistical power-allocation method for MISO BC using ZFDPC (or any other communication schemes). This is in sharp contrast to all current communication schemes in which only a single, deterministic power-allocation is used. It will be seen from simulation results in Section IV-B that the proposed statistical power-allocation could offer not only larger sum rate but also better fairness than the commonly used design objectives.

A. Upper Bound on Rate-Fairness Tradeoff: Rate-Split
Given the channel vectors {h k } of all users (or equivalently the channel matrix H in (14)) we have shown that the basestation can employ either DPC, ZFDPC, or other coding schemes to simultaneously send information to all K users under a total power constraint. The proposed tri-stage designobjective, as outlined in Section III, provides an efficient strategy to distribute power among all users, taking both sum rate and fairness into consideration. When the channel is quasi-static, we further showed a mixed strategy can provide performance, in terms of both sum rate and fairness, much better than the commonly used design objectives. The mixed strategy also gives an optimal tradeoff -in terms of the tristage design -between the sum rate and fairness. The tradeoff is explicitly characterized by the function F max (R), and has an implicit dependence upon the channel matrix H. In this section we will focus on such dependence and will write the tradeoff as F max (H, R) for emphasis.
Given the channel matrix H, the tradeoff F max (H, R) is optimal when the tri-stage design-objective is employed and when the coding is restricted to take place within the channel block where H is fixed. In other words, for a series of channel blocks H 1 , H 2 , . . . , H L , the proposed tri-stage approach gives the sum rate-fairness pair (R sum,tri (H ), F tri (H )) at theth channel block H , and achieves the following asymptotic average sum rate and fairness for an ergodic channel R sum,tri := lim On the other hand, if coding is allowed to take place across multiple channel blocks, then we can have different sum rate for each block, as long as their asymptotic average still equalsR sum,tri . This could potentially lead to a larger value of fairness. Specifically, given a series of L channel realizations,  (H , R sum, ). Therefore, for any desired average sum rateR sum we could optimize over all possible rate-split functions R (L) sp to obtain a better fairness. In other words, if the mixing stage of tri-stage design is allowed to take place in multiple channel blocks of an ergodic quasistatic channel, then the optimal sum rate-fairness tradeoff is given by sp (H 1 , . . . , H L ) = (R sum,1 , . . . , R sum,L ), where the supremum is taken over all possible rate-split functions R (L) sp having average sum rateR sum . We remark that the functionF max (R sum ) can be easily evaluated using Monte-Carlo methods.
This ultimate tradeoffF max (R sum ), though has performance superior to the single-block achievable pair (R sum,tri ,F tri ), is in fact unachievable in practice. AchievingF max (R sum ) requires the non-causal knowledge of H 1 , H 2 , . . . , at the base-station, hence we shall regardF max (R sum ) as the upper bound for the rate-fairness tradeoff.
The ultimate tradeoffF max (R sum ) is also an excellent performance benchmark for the selections of operating sum ratefairness pairs from the single-block tradeoff F max (R). Recall that in the last stage of the proposed tri-stage approach we were asked to decide which operating point from the singleblock tradeoff F max (R) should be chosen for transmission, and we made our choice based on the reputable proportional fairness -choosing the point on F max (R) that is the closest to the point of proportional fairness. Our intuitive choice achieves an average sum rateR sum,tri (cf. (42)) and an average fairness F tri (cf. (43)) in the long run. The ultimate tradeoff (45) then helps us to see how far off the performance of our choice to that of the best possible selection (if there is one) is. The tradeoffF max (R sum ) also serves as the ultimate benchmark for all possible selection schemes that can be considered and/or be eventually employed in the last stage of the proposed design objective.

B. Performance Results
Two simulation results are presented to demonstrate the performance proposed tri-stage design. While the design is general and can be integrated into any coding scheme used for wireless network communication, here the simulations are performed for MISO BC using ZFDPC, due to its simplicity for implementation. In particular, we first consider the case of K = 2 single-antenna users and N = 2 transmit antennas at the base-station. The results are given in Figure 2 for (a) P = 0 dB and (b)P = 15 dB, representing the performance in low and moderate SNR regimes. In both cases, the sum ratefairness pairs obtained from the max sum rate criterion always achieve the largest sum rate but at the cost of low fairness value. The level of unfairness is much more pronounced when the total power P is small, as one of the two users could be given zero power and be excluded from communication. When P is large, the encoder has more resources for power distribution, so both users are included in the transmission, and an acceptable -but not satisfactory -level of fairness is achieved. The max-min criterion, on the other hand, aims to provide an equal transmission rate to both users, hence the fairness value is always at 100 percent, but at a cost of certain loss in sum rate. The sum rate-fairness pair derived from the  proportional fairness has sum rate smaller than that of max sum rate but much fairer to the users, especially in the low SNR regime. In both cases, it is seen that the proposed tristage criterion has better performance than the proportional fairness, not only a larger sum rate but also better fairness. The performance gains, however, come at a price of higher computational complexity, since the proposed tri-stage design involves an optimization in the mixing stage to find the best time-sharing among all possible cake cuttings. All the achievable sum rate-fairness pairs are upper bounded by the ultimate tradeoffF max (R sum ), as achieving the latter calls for the noncausal knowledge of all future channel realizations. It is also seen from Figure 2.(b) that in moderate SNR regime both proportional fairness and tri-stage designs are fairly close to the ultimate boundF max (R sum ), leaving little room for further improvement. But for low SNR regime as in  Figure 2.(a), it appears possible to improve the rate-selection method in the last stage to yield a better sum rate-fairness pair. A similar simulation for a much more complex case of K = 8 single-antenna users and N = 8 transmit antennas transmitting at P = 0 dB at base-station is given in Figure 3. It can be seen that the proposed tri-stage method not only is much fairer than the proportional fairness but also provides a slightly higher sum rate.

V. CONCLUSION
In this paper we first investigated the tradeoff between sum rate and fairness for MISO BC. The achievable sum rates were based on DPC or ZFDPC, subject to an individual power constraint. Several qualitative approaches for fairness, such as max sum rate, proportional fairness, harmonic mean and max-min, were also discussed. For the quantitive approaches, we showed that the widely used Jain's index could become insensitive at high SNR regime and hence proposed an 1norm based fairness measure that can compare the fairness levels achieved by various design objectives at a much finer resolution. We also introduced a new tri-stage design objective that is based on a new concept of statistical power allocation, in sharp contrast to the fixed, deterministic method used in all existing wireless/wired communication systems. The new scheme randomly allocates powers to users based on an optimal probability distribution derived from the tradeoff between sum rate and fairness. We also remark that the proposed tristage design objective can be easily extended to MIMO BC with successive zero forcing DPC [15] as well as zero-forcing beamforming methods. Simulation results showed that the proposed approach can simultaneously achieve a larger sum rate and better fairness than the reputable proportional fairness. A performance upper bound was also given in the paper to show that there might still be rooms for further improvement, especially in the low SNR regime. Finally, it is worth to note that the ordering of users also has some impact on fairness and sum rate. For traditional DPC, all user-orderings have the same sum rate but possibly different fairness values. For ZFDPC, both sum rate and fairness value could change as the ordering of users varies. How to use the ordering of users to improve sum rate and fairness still calls for further research.


Using Global Terrorism Database (GTD) and Machine Learning Algorithms to Predict Terrorism and Threat

It is evident that there has been enormous growth in terrorist attacks in recent years. The idea of online terrorism has also been growing its roots in the internet world. These types of activities have been growing along with the growth in internet technology. These types of events include social media threats such as hate speeches and comments provoking terror on social media platforms such as twitter, Facebook, etc. These activities must be prevented before it makes an impact. In this paper, we will make various classifiers that will group and predict various terrorism activities using k-NN algorithm and random forest algorithm. The purpose of this project is to use Global Terrorism Database as a dataset to detect terrorism. We will be using GTD which stands for Global Terrorism Database which is a publicly available database which contains information on terrorist event far and wide from 1970 through 2017 to train a machine learning-based intelligent system to predict any future events that could bring threat to the society.

I. INTRODUCTION
There has been a huge growth in Internet users in the past decade. Technological advancement has not only benefited the society but also has given rise to various problems in the society. One of such threats is the growth in cyber terrorism. Due to exponential increase in Internet users it is evident that people have started using this technological advancement for carrying out unlawful activities. Purposeful use of computers, web and various other systems for hurting others or carrying out un-lawful activities or personal motive can be called as cyber terrorism. Like every coin has two sides, technological advancement has also its advantage and disadvantage. Nowadays we are exposed to much more vulnerability and risk on the web on the hands of predator or cyber-terrorists. Estonia, a Baltic nation which is continually developing as far as innovation, turned into a battleground for cyber terror in April, 2007 after debates with respect to the expulsion of a WWII soviet statue situated in Estonia's capital Tallinn.
It is very necessary to identify the fact that cyberterrorism has had very disastrous effect in our society. We intend to use various Machine Learning algorithms to analyze, predict and categorize various terrorist activities using various algorithms like Natural Language Processing (NLP), sentiment analysis, k-NN algorithm and random forest algorithm to train a system by feeding it with data from Global Terrorism Database and various threats related text on Social Media.

II. RELATED WORK
This paper intends to deal with the following details:a. To Study and investigate various techniques and work done used to identify and channel vicious and hurtful solitary substance online on the web. b. To play out a comprehensive investigation and contemplating of these systems and discover basic patterns. The underlying advance is to begin by thinking of a few meanings of withdrawn conduct, and after that quest up for some ideas on terrorist conduct. Studying asocial practice: Antisocial conduct, incorporates exercises, for example, "trolling, cyberbullying, grieving and criminal activities", they have generally been utilized and discussed. Research on Online people group to recognize introverted conduct has significantly led with subjective measures instead of quantitative.
These examinations for the most part included the various kinds of social defaming which happens and persuasive explanation for performing these types of exercises and various systems that are used by many people in light of these kinds of activities. Techniques to distinguish antisocial conduct: There are a few similar kinds of studies done on asocial practice. In any case many had been completed in this domain. Endeavors had been additionally done in the field of recognition along with avoidance of substantial indications identified with reserved messages in networks.

A. Antisocial Content Identification
The Fundamental goal is to discover untruthful, exploitative, bigot and fake substance on the online networks. Influencing the attitude of an individual or to coast misleading information to the network is the primary undertaking. Examining this information will result in the wellspring of abhor advertiser or reserved information.

B. Obtaining Criminal Information
Searching as well as investigating for criminal information and evidence can give concealed examples along with obscure patterns utilized by every lawbreaker. In spite of the fact that it is documented as well as investigated by concerned authorities that manages the wrongdoings and offenders to keep away from its abuse.

C. Cyber Infrastructure Shielding
It has the procedure to ensure digital foundation if there should be an occurrence of digital dangers and digital assaults. These assaults could be a foundational withdrawn action. It can also be an endeavor for risking the safety measures.
There can be numerous strategies as well as procedures for examining an individual"s brain however techniques haven"t been created for natural identification of asocial practices on the internet. Information as well as content available on interpersonal organization is either not structured or not classified information which turns into significant obstacle for locating reasonable technique for natural identification of anti-social practice.

III. DESIGN AND METHODOLOGY
Following approach were used for accomplishing the required target:

A. Data Set
The Global Terrorism Database, is an organization which is financed by (START) which stands for National Consortium for the Study of Terrorism and Responses to Terrorism, is a dataset of terrorist events ranging from a period length since 1970. The GTD holds more than 170 thousand assaults by terrorists having more than 40 factors for every occurrence, that made this dataset as "right now finest exhaustive unsorted information dependent upon psychological militant occasions on the planet. In perspective on its effectiveness and exhaustiveness, GTD information has highlighted in various scholastic papers as exact investigation for the examination on different parts of fear-based oppression, from current patterns to sorts of psychological oppression.

B. Data Preprocessing
The GTD incorporates in excess of 170,000 instances of terrorist events far and wide from 1970 to 2017. For every occurrence, data is accessible on the area and date of the comparing episode, summing up to 132 characteristics. Be that as it may, the information was gathered from various information assets, which would bring about information inconsistence. Regarding the present problem, we are setting the limit of offer proportion to twenty percent, that indicates those traits which have been documented inside over twenty percent of the all-out occurrences are investigated. Ensuing measurable investigation, more than 50 properties were chosen but left out information yet resides inside portion"s record. For taking care of the issue, the Mean Imputation (MI) technique is utilized, trading left out information using every single recognized estimation of the trait of the set in which the left-out quality has a place.

C. Classification
Appointing items to one of a few preset classes is the fundamental concept of classification. Two broadly utilized classifiers have been considered, k-Nearest Neighbor (k-NN) and Random Forest Algorithm. i.

K-Nearest Neighbour Classification Approach
k-NN falls under automatic learning algorithm category. K-NN algorithm is considered to be an instance-based algorithm. This algorithm is one of the notable methodologies in the field of example acknowledgment. The k-NN algorithm is normally and broadly utilized in categorizing text, and classifying text. k-NN algorithm is one of the widely used algorithm for mining purpose and is popularly used in classification of text and is effectively adaptable to enormous applications. Since k-NN algorithm can have multiple classifiers and class labels, it is preferred in multi-model classes.
The input data that is used as training data-sets of k-NN algorithm is plotted against multi-dimensional element, which is portioned into different areas which are then characterized based on the order of training data-sets. Fig.5 demonstrates a diagram of locale region of a k-NN classifier which includes three unique classifications, in particular w1, w2 and w3. These classifications are related with the preparation information and circles, triangles as well as square-blocks are marks of information point's w1, w2 and w3, separately. In the following figures, 'X' means the information preparing information for grouping.

Random Forest
Random Selection as well as bagging are the two machine learning methods that RF merges together to combine their benefits. In bagging forecast is made by selecting the maximum number of votes. This is done by training each and every tree, using bootstrap test. While Random-Feature selection looks for the best part in every node over irregular portion of the highlights. It is a renowned coordinated learning algorithm by taking decision tree as the fundamental classifier. It has demonstrated its accomplishment in applications like email spam filtering, voice classification, and picture classification and text classifier. To order another document from the information vector, it passes the information vector through every one of the trees of the forests with each tree giving a result, i.e. a classification, which is named as "votes" for that specific class. Like the election results, the last result would be the class that has the most votes. The most important features of Random Forest algorithms are enlisted below: a. Random Forest is un-affected by noise as well as outliers. b. Random Forest gives better result and is faster than boosting as well as bagging c. Incase of huge data sets RF is considered to be quite efficient. d. In comparison to other readily available classification algorithms, RF is considered more precise and hence superior. e. In case of missing data, Random Forest Algorithm is considered to be more productive for evaluating purpose.

IV. RESULTS
In this paper we have explored various classifiers on the basis of their accuracy and speed. We finally went with k-NN algorithm for Weapon Classifier and Random Forest algorithm for Perpetrator Classifier. k-NN algorithm was best suitable for Weapon Classifier and similarly Random Forest Algorithm stood out to be best for Perpetrator classifier on our multiple attempts using various algorithms. The data-sets generated using GTD was divided into the ratio of 8:2 for training and testing our model respectively.

A. Visualization
We have visualized various contents from the Global Terrorism Database, to better understand the Datasets we are provided with. We have visualized various attributes from the year 1996 to 2017 that were enlisted in the Global Terrorism Database. Following are the diagrams generated from the GTD after visualization of the contents based on attacks by year, fatalities by year, countries by total attack, and attacks by type. The diagrams below have been plotted using "catplot()".

Fig.6. Attacks by Year
The above bar diagram shows us the number of attacks carried out every year from the year 1996 to 2017. We can conclude that the attacks were increasing from the year 2011 to 2014 and then it started to gradually drop.

Fig.7. Fatalities by Year
The above bar diagram shows the number of fatalities that happened every year from 1996 to 2017.It is evident that the most fatalities happened between the years 2011 to 2017.

Fig.8. Top 20 Countries by Total Attack
The above diagram lists the countries based on the most number of terrorist acts acted upon. It is evident that Iran, Pakistan, Afghanistan and India are the top 4 countries where most number of attacks have happened from the year 1996-2017.

Fig.9. Total Attacks Type
The above bar diagram depicts the total attacks by type. It is evident that bombing and explosion followed by Armed Assault are the most preferred attack types with a total count of more than 90,000 attacks from the year 1996-2017. The World map in Fig.10 shows the hottest Terrorist locations, showing active terrorist encounters in South and East Asia.

B. Weapon Classifier
The weapon classifier was built using k-NN algorithm that classifies the attacks based on types of weapons. We have chosen "K" by trial and error strategy for which we obtained the ideal outcome. We have calculated the neighbors from the GTD where k=12.

Fig.11. k-NN Varying Number of Neighbors
The above graph was generated using k-NN algorithm by trial and error. The graph shows the accuracy for 12 different clustering and we finally got the most effective clustered dataset when k was equal to 12. Thus, from the majority of the 12 attributes we predicted the weapons that could be used. The accuracy that we got using the k-NN algorithm was 88.74%.

Fig.12. Total Attacks by Weapon Type
The above graph classifies the attacks by weapon types from the year 1996-2017. It is evident that explosion and firearms are the most preferred weapon types.

C.
Perpetrator Classifier The perpetrator classifier classifies various groups or organization that carries out illegal and influences terrorism. We used Random Forest Algorithm for creating the Perpetrator Classifier. We grouped and listed various groups responsible for various attacks from 1996 to 2017 using random forest algorithm. A list of major perpetrator groups was displayed, along with the accuracy, precision, recall and f1after the training of the model.

V. DISCUSSION AND CONCLUSION
Terrorism has become a huge threat over the world. Various Machine learning system, artificial intelligence and Data-Analytics have provided us with a system to help the investigator and anti-terrorist or counter-terrorist squad to rapidly decide the most probable perpetrator responsible of a particular terrorist attack. We have demonstrated how the methods like k-Nearest algorithm and Random Forest can help us predict the responsible perpetrator precisely eight out of ten times. This helps the anti-terrorist organizations to reduce the list of possible suspects and help them act rapidly to find and catch the real suspect. In future we further mean to attempt different algorithms and methods like deep learning models and package classifiers to further improvise the accuracy of result and hence successfully predict the perpetrator with more precision and accuracy. Besides this in future we also intend to use web-scrapping methods and sentimental analysis to study various posts and comments on social media sites for hatred speech and text and further filter them and create a classifier to merge the current project with the social media texts. Devyash Bordia is currently pursuing his Bachelors in Science and Technology degree in SRM Institute of Science and Technology. He is also a member of various technical clubs of SRM IST. He is currently working on a ML project on creating a classifier that studies Cancer.

AUTHORS PROFILE
Sanskar is currently pursuing his Bachelors in Science and Technology degree in SRM Institute of Science and Technology. He is also member of various technical clubs of SRMIST. He has participated in many national level technical events and fests. He is currently working on various web design and development projects.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Brief Note: Asynchronous Verifiable Secret Sharing with Optimal Resilience and Linear Amortized Overhead

In this work we present hbAVSS, the Honey Badger of Asynchronous Verifiable Secret Sharing (AVSS) protocols - an AVSS protocol that guarantees linear amortized communication overhead even in the worst case. The best prior work can achieve linear overhead only at a suboptimal resilience level (t<n/4) or by relying on optimism (falling back to quadratic overhead in case of network asynchrony or Byzantine faults). Our protocol therefore closes this gap, showing that linear communication overhead is possible without these compromises. The main idea behind our protocol is what we call the encrypt-and-disperse paradigm: by first applying ordinary public key encryption to the secret shares, we can make use of highly efficient (but not confidentiality preserving) information dispersal primitives. We prove our protocol is secure under a static computationally bounded Byzantine adversary model.

I. INTRODUCTION
In a verifiable secret sharing (VSS) protocol, a dealer shares a secret among a set of n parties, such that t + 1 honest parties can reconstruct the secret. VSS forms the basis for fault tolerant file storage [5], [9], shared databases [2], and many other applications. It is also an essential component of secure multiparty computation (MPC) protocols, used both for generating random preprocessing elements and for accepting secret-shared inputs from untrusted clients.
The verifiability property means that if any party gets their shares, then every correct party also receives a valid share. This is essential when VSS is used as input to MPC, since parties need to assume the shares will be available in order to make irrevocable actions (such as revealing intermediate outputs of a computation). The challenge is that a faulty dealer may provide invalid data to some but not all of the parties. The main idea behind nearly all VSS protocols, starting from Feldman et al., [8], is to broadcast a polynomial commitment, enabling parties to individually validate their shares.
In the case of synchronous VSS, we can simply wait to hear a confirmation from all n parties, or else abort. The asynchronous VSS case is more difficult since we must proceed after hearing from only n − f of the parties, where f is the number of parties that undergo a Byzantine fault. Since crashed nodes are indistinguishable from slow nodes, it could be that f of the ones we waited for are corrupted, hence only n − 2 f correct parties received valid shares.
In order to cope with asynchrony, AVSS protocols typically distribute shares with additional redundancy, such that parties  [2] t < n/3 O(N) O(N 2 ) eAVSS [1] t < n/3 O(N 2 ) AVSS [4] t < n/3 O(N 3 ) Sh [6] t < n /4 O(N) who received invalid shares can recover their shares through interaction with the others. This recovery process either results in extra communication overhead [4], or else relies on loosened resilience guarantees [6].
Improvements to AVSS have made use of concise polynomial commitments based on pairing cryptography [1]. Most notably, in recent work, Basu et al. [2] present an optimistic AVSS protocol that achieves linear communication overhead in the typical case, but in the presence of Byzantine faults or network asynchrony may fall back to quadratic overhead. The goal of this paper is to present a protocol that provides linear guarantees even in the worst case.
Overview of our solution. The main idea behind our approach is a technique we call encrypt-then-disperse, inspired by a related application in HoneyBadgerBFT [12]. The secret share encoding and polynomial commitments are as usual. However, before transmitting, the secret shares are first encrypted using public key encryption. Next the encrypted payload is dispersed using an information dispersal routine, which can guarantee robustness and efficiency since it does not have to provide secrecy.
The use of information dispersal guarantees that every honest node receives some data, even in the asynchronous setting. If it turns out to be invalid, then it can be used as evidence to implicate the leader. Once the dealer is determined to be faulty, we enter a share recovery phase, which ensures every correct party receives their share. The share recovery phase can be very efficient too, since it does not need to ensure confidentiality at all, since it can only be initiated once the dealer is determined to be faulty. A summary comparison of our results to related work is given in Table I.

II. PRELIMINARIES A. Asynchronous Network Model
Throughout this paper we assume the standard asynchronous network model. We assume a fixed set of n communicating parties P 1 , ..., P n , as well as a dealer D. We consider a static Byzantine corruption model. The dealer and up to f < n/3 of the parties may be corrupted, in which case they are controlled entirely by the adversary. The parties are connected by pairwise authenticated channels. Messages between uncorrupted parties are guaranteed eventually to be delivered, although the order and timing of delivery of messages is determined by the adversary. We assume a computationally bounded adversary that is unable to break cryptographic primitives.

B. Asynchronous Verifiable Secret Sharing
Here we give the security definition for our construction: In an AVSS protocol, the dealer D receives input s ∈ F p , and each party P i receives an output share φ (i) for some degree-t polynomial φ : The protocol must satisfy the following properties: • Correctness: If the dealer D is correct, then all correct parties eventually output a share φ (i) where φ is a random polynomial with φ (0) = s. • Secrecy: If the dealer D is correct, then the adversary learns no information about φ except for the shares of corrupted parties. • Agreement: If any correct party receives output, then there exists a unique degree-t polynomial φ such that each correct party P i eventually outputs φ (i).
For simplicity, this definition is written to be specific to Shamir sharing, though a more generic definition would be possible [1]. Our agreement property is written to incorporate the strong commitment property from Backes et al. [1], in which the secret-shared value must be determined by the time that the first correct party outputs a share (and cannot be influenced thereafter by the adversary).

C. Polynomial Commitments
Polynomial commitments are an interface by which a committer can create a commitment to a polynomial as well as witnesses to its evaluation at different points, so to prove that evaluations are correct without revealing the full polynomial. Polynomial commitments have been implicit in all cryptographic VSS protocols since Feldman [8], but were first formalized by Kate et al. [11] We use the scheme from Kate et al. because it gives commitments that are additively homomorphic and constant-sized. Definition 2. (PolyCommit (c.f. [11]) Let (F p ) κ be a family of finite fields indexed by a security parameter κ (we'll typically omit κ and just write F p ). A PolyCommit scheme for F p consists of the following algorithms: Setup(1 κ ,t) generates system parameters SP to commit to a polynomial over F p of degree bound t. Setup is run by a trusted or distributed authority. SP can also be standardized for repeated use. PolyCommit(SP, φ (·)) outputs a commitment C to a polynomial φ (·) for the system parameters SP, and some associated decommitment information aux.
If so, the algorithm outputs accept, otherwise it outputs reject.
A PolyCommit scheme must satisfy the following properties: , then except with negligible probability, an adversary can not create then except with negligible probability, an adversary can not create an evaluation φ ( j), witness w j , and decommitment information aux j such that VerifyEval(SP,C, i, φ ( j), w j , aux j ) = 1 if i = j. • Hiding: Given C and w i for any i, an adversary either -Can only determine φ (·) or φ (i) with negligible probability given bounded computation (Computational Hiding) -Can not determine any information about φ (·) or φ (i), even given unbounded computation (Unconditional Hiding) We additionally require that the commitments and witnesses be additively homomorphic. This allows us to create new commitments and witnesses through interpolation, a property we rely on in our AVSS construction.
• Additive Homomorphism: Given commitments C a and C b to polynomials φ a (·) and φ b (·) respectively, there should be an efficient operation to compute C a+b , the commitment to φ a (·) + φ b (·). Additionally, given w i,a and w i,b , the witnesses for the evaluations of φ a (·) and φ b (·) at i respectively, it should be similarly efficient to compute w i,a+b . Lastly, it should also be efficient to compute w i+ j,a from w i,a and w j,a .
In this work we use PolyCommitPed from Kate et al. [11], which provides a constant-sized commitment that achieves unconditional hiding as well as our desired homomorphic properties. We also note that PolyCommitPed achieves unconditional hiding through the use of a hiding polynomial, which we notate as aux in this work. As aux is instantiated as a polynomial over a finite field, it too realizes our desired property of additive homomorphism.

D. Asynchronous Verifiable Information Dispersal
Our protocol relies on an information dispersal protocol as defined below. Our definition is for a batch, such that M messages v 1 , ..., v M are dispersed at once and can be individually retrieved. Hendricks et al. [10] present AVID − FP, an AVID protocol whose total communication complexity is only O(|v|) in disperse phase for a sufficiently large batch v >> n, i.e. it achieves only constant communication overhead.

E. Reliable Broadcast
Reliable broadcast [3] is a primitive that enables a dealer D to broadcast a message v to every party. Regardless of if the dealer is correct, if any party receives some output v then every party eventually receives v . Reliable broadcast is a special case of information dispersal, where each party simply begins Retrieve immediately after Disperse completes. In fact, all efficient protocols we know of, such as Cachin and Tessaro [5] or Duan et al., [7], are built from an AVID protocol. We therefore skip the definition but use the ReliableBroadcast syntax in our protocol description as short hand for Disperse followed by all parties immediately beginning Retrieve.

F. Public Key Encryption
We make use of a semantically secure public key encryption scheme, (Enc, Dec), such that Enc PK (m) produces a ciphertext encrypted under public key PK, while Dec SK (c) decrypts the message using secret key SK. We assume a PKI, such that each party P i already knows SK i . We also assume that each public key is a function of the secret key, written PK = g SK , which we make use of by revealing secret key during the dealer implication phase.
We note that while in our presentation we only consider a single session with a single dealer, for a practical deployment, we would want to derive per-session keys from a single longterm keypair and allow a recipient to present the session key along with a proof of its correctness, rather than reveal her secret key (and consequently need to update her key in the PKI).  Fig. 1. Illustration of hbAVSS. A batch of secrets s 1 , ..., s N are encoded as a degree-(t,t) bivariate polynomial φ (·, ·). Each party P i 's shares φ (i, ·) are encrypted, then dispersed. Polynomial commitments to the sharings are broadcast, enabling parties to validate their shares. If a party P i detects an invalid share, they publish their decryption key, enabling the other parties to confirm the dealer is faulty. Invalid shares are then recovered in two steps: (R1) each party P j receives valid shares to interpolate one column φ (·, j), then (R2) each party P i reconstructs their shares φ (i, ·).

III. THE hbAVSS PROTOCOL A. Protocol description
At a high level, the hbAVSS protocol consists of the following steps: 1) Dealer's phase: the dealer creates Shamir sharings for t + 1 secrets and broadcasts t +1 commitments to the polynomials that encode them. The dealer then encrypts each party's shares using their public encryption keys, and disperses the encrypted payloads. 2) Share validation: each party retrieves their encrypted payload, and then attempts to decrypt and validate their shares against the polynomial commitments. If sufficiently many parties successfully receive valid shares, then the shares are output. 3) Implicating a faulty dealer: if any party finds that the shares they receive are invalid or fail to decrypt, they reveal their secret key, enabling the other parties to confirm that the dealer was faulty. 4) Share recovery: once the dealer is implicated as faulty, the parties who did receive valid shares distribute them to enable the remaining parties also to reconstruct their shares. We now explain these steps in more detail. The protocol pseudocode is given in Algorithm 1, and the narration below refers to the schematic illustration in Figure III-A. 1) Sharing and committing: : The protocol shares a batch of t + 1 inputs at a time, {s 1 , ..., s t+1 }. The dealer creates a degree-t Shamir sharing φ (·, k) for each input such that φ (0, k) = s k , and each party P i 's share of s k is φ (i, k). We visualize this as a matrix, with each party's shares forming a row as illustrated in Figure III-A. Later, if share recovery is needed, we make use of φ (·, ·) as a degree-(t,t) bivariate polynomial.

512:
output shares {φ (i, k)} k∈[t+1] * Note: To avoid clutter, the protocol is written to share a batch of exactly t + 1 secret values. To achieve linear communication overhead, the ReliableBroadcast and Disperse instances should be shared among a batch of several simultaneously executing instances, as explained in Section III-C.
The dealer then uses PolyCommit to create a commitment C k to each sharing φ (·, k). The commitments are then broadcast, ensuring all the parties can validate their shares consistently.
Next, for each share k and party P i , the dealer creates an encrypted payload z i,k , consisting of the shares φ (i, k) and the polynomial evaluation witness w i,k , encrypted under P i 's public key PK i . The dealer then Disperses these encrypted payloads. With the broadcast and dispersal complete, the dealer's role in the protocol is concluded -in fact since information dispersal itself requires only one message from the dealer, the dealer's entire role is just to send messages in the first round.
2) Share Verification: : Each party P i waits for ReliableBroadcast and Disperse to complete, and then retrieves just their payload {z i,k } k∈[t+1] . The party then attempts to decrypt and validate its shares. If decryption is successful and all the shares are valid, then P i signals this by sending an OK message to the other recipients. The goal of the OK and READY messages (lines 302-307) is to ensure that if any party outputs a share, then enough correct parties have shares for share recovery to succeed if necessary.
3) Implicating a faulty dealer: : If any honest party P i receives a share that either fails to decrypt or fails verification, they reveal their secret key by sending (IMPLICATE, SK i , k), which other parties can use to repeat the decryption and confirm that the dealer dispersed invalid data. 4) Share Recovery: After a dealer is implicated as faulty, the protocol enters a two-step share recovery process, following the approach of Choudhury et al. [6]. In the first step, parties wait for t + 1 R1 messages from parties that received valid shares originally. The R1 can be checked individually by making use of the homomorphic property of polynomial commitments and witnesses (Section II-C). Every correct party P j participates in the second phase of share recovery, by reconstructing one column of the bivariate polynomial φ (·, j).
The second step is the transpose, where each party reconstructs the row polynomial corresponding to its shares. Since all correct parties send an R2 message, even if they did not originally receive valid shares, we can interpolate through ordinary robust decoding rather than using the polynomial commits.
Batching: For simplicity, we have described the protocol as sharing a batch of exactly t +1 values. However, to reach our desired amortized complexity goals, we need to run multiple instances in parallel in order to offset the overhead of Disperse and ReliableBroadcast. The idea is to run several instances of hbAVSS such that the Disperse and ReliableBroadcast protocols are in lockstep, sharing their control messages (i.e., the payloads are concatenated across the several instances).
B. Security Analysis of hbAVSS Theorem 1. The hbAVSS protocol (Algorithm 1) satifies the requirements of an AVSS protocol (with high probability) when instantiated with an additively homomorphic polynomial commitment scheme (Setup, Commit), an AVID protocol (Disperse, Retrieve), a reliable broadcast protocol ReliableBroadcast, and a semantically secure public key encryption scheme (Enc, Dec) with a pre-established PKI such that each party P i knows their secret key SK i and the public keys {PK i = g SK i } i∈ [N] are well known.
Proof. Correctness. The correctness property follows easily: If the dealer D is correct, then ReliableBroadcast and Disperse complete, so each honest party receives their valid shares and outputs them through the ordinary case (line 307). Secrecy. Secrecy also follows easily. The hiding property of the broadcasted polynomial commitments ensures that they reveal nothing about the shares. Each party's shares are encrypted prior to dispersal, so the computationally-bounded adversary only obtains the shares that can be decrypted using corrupt parties' secret keys. Share recovery reveals more information, but if the dealer is correct, then any attempts by the adversary to initiate share recovery will be rejected (line 405). Agreement. It is easy to check that parties only output shares that are consistent with the broadcasted polynomial commitments. The challenge is in showing that if any correct party outputs a share, then all of them do. In the following, assume a correct party has output a share, either through the typical path (line 307) or through share recovery (line 512). In either case, the broadcast and dispersal must have completed and the party must have received 2t + 1 READY messages (line 305).
First, notice the READY-amplification in line 304 plays the same role as in Bracha broadcast: Claim 1. If any correct party outputs a share, then all correct parties eventually receive 2t + 1 READY messages (line 305).
If any correct party receives 2t + 1 READY messages, then at least t + 1 correct parties must have sent READY messages, which causes all correct parties to send READY messages.
Next, the following claim ensures that share recovery can proceed if necessary: Claim 2. If any correct party outputs a share, then at least t + 1 correct parties receive valid shares.
For READY-amplification to begin, some correct party must have initially sent READY after receiving 2t + 1 OK messages (line 302), thus t + 1 correct parties must have successfully received valid shares (line 208).
Because of the availability and agreement properties of dispersal, every correct party either receives valid shares (and by then Claim 1 outputs ordinarily) or else receives an invalid share and initiates share recovery, which by Claim 2 is able to proceed.

C. Performance Analysis of hbAVSS
We now analyze the performance of hbAVSS, focusing primarily on communication complexity. Recall that our goal is to achieve linear amortized communication overhead. Since one run of this protocol results in t + 1 secret shared values, we have a budget of O(n 2 ) communication complexity to keep in mind.
We encounter a challenge: the up-front overhead (independent of payload size) of the Broadcast and Disperse primitives is either O(n 2 log n) if Merkle tree checksums are used (as in Cachin and Tessaro [5]) or O(n 3 ) if full cross checksums are used (as in Hendricks et al. [10]). Hence to obtain linear overhead, we consider amortizing these costs across at least n multiple runs executing in parallel, sharing the upkeep.
The broadcast payload consists of t + 1 commitments, but each one is constant size. Since the overhead of broadcast is O(n), the total communication cost is O(n 2 ). The total size of the Disperse payload is n(t + 1) elements, but the overhead of dispersal is constant, so the total cost is O(n 2 ). Each party Retrieves only a block of t + 1 elements, thus all n of them. The Bracha-like OK and READY messages clearly contribute O(n 2 ).
The share recovery process clearly involves O(n 2 ) total communication, but only occurs at most once, since it enables all correct parties to reconstructing their shares at once.
The final challenge is dealing with spurious implications. In the worst case, each honest party may need to validate up to t false implications, each of which requires retrieving a block from the dispersal protocol, thus O(n 3 ) worst case cost in total. Fortunately, we amortize this in the same way, by running at least n concurrent instances of the protocol. We only need to process at most one implication per party across all the instances. If spurious, further implications are ignored; if confirmed, initiate share recovery in all instances.