Federated learning enables training a global model from data located at the client nodes, without data sharing and moving client data to a centralized server. Performance of federated learning in a multi-access edge computing (MEC) network suffers from slow convergence due to heterogeneity and stochastic fluctuations in compute power and communication link qualities across clients. We propose a novel coded computing framework, CodedFedL, that injects structured coding redundancy into federated learning for mitigating stragglers and speeding up the training procedure. CodedFedL enables coded computing for non-linear federated learning by efficiently exploiting distributed kernel embedding via random Fourier features that transforms the training task into computationally favourable distributed linear regression. Furthermore, clients generate local parity datasets by coding over their local datasets, while the server combines them to obtain the global parity dataset. Gradient from the global parity dataset compensates for straggling gradients during training, and thereby speeds up convergence. For minimizing the epoch deadline time at the MEC server, we provide a tractable approach for finding the amount of coding redundancy and the number of local data points that a client processes during training, by exploiting the statistical properties of compute as well as communication delays. We also characterize the leakage in data privacy when clients share their local parity datasets with the server. Additionally, we analyze the convergence rate and iteration complexity of CodedFedL under simplifying assumptions, by treating CodedFedL as a stochastic gradient descent algorithm. Finally, for demonstrating gains that CodedFedL can achieve in practice, we conduct numerical experiments using practical network parameters and benchmark datasets, in which CodedFedL speeds up the overall training time by up to 15× in comparison to the benchmark schemes.

Lightweight cryptography has become more and more important in recent years because of the rise of the Internet of Things (IoT) and usage of smart mobile devices. In this paper, we propose a novel secure lightweight entity authentication hardware primitive called SLATE, where its area is about 50% to more than 3X smaller than existing lightweight ciphers and strong physical unclonable functions (PUFs), respectively. Even though the authentication of SLATE is done through challenge response pair (CRP) verification similar to strong PUFs, the source of the key for SLATE must be coming from any existing secret key storage used for any ciphers. A main advantage of SLATE over most existing strong PUFs being an entity authentication primitive is that SLATE is resistant to known attacks to strong PUFs or logic obfuscations, such as model building attacks and Boolean satisfiability (SAT) attacks. Furthermore, we show that the implementation cost of SLATE with a 176-bit key and 244 CRPs is only 663 gate equivalents (GEs). Compared with lightweight ciphers and existing secure strong PUFs, we show that SLATE is a practical security primitive for resource constrained systems for its extremely small footprint and security. Finally, we show that SLATE is information theoretically secure when valid CRPs are communicated through insecure channels.

In wireless mobile edge computing platforms, such as those supported by vehicular networks, location specific machine learning models can be trained by distributing computations using resources available at the edge. The computational and communication resources at the wireless edge are heterogeneous and unreliable, which can lead to straggler effects that significantly slow down recursive learning tasks, such as gradient descent. In this paper we propose a coded computation framework, which utilizes statistical knowledge of resource heterogeneity to determine optimal encoding and load balancing of training data using Random Linear codes, while avoiding an explicit step for decoding gradients. Results show that the proposed coding framework speeds up the training time for linear regression models, by up to ten times, when compared with repetition coding schemes.

The lack of stability is one of the limitations that constrain physical unclonable function (PUF) from being put in widespread practical use. In this paper, we propose a weak PUF and a strong PUF that are both completely stable. These PUFs are called locally enhanced defectivity physical unclonable function (LEDPUF). An LEDPUF is a pure functional PUF that does not require any kinds of correction schemes as conventional parametric PUFs do. The source of randomness of an LEDPUF is extracted from locally enhance defectivity without affecting other parts of the chip. In this paper, we construct a weak LEDPUF by forming arrays of directed self-assembly random connections, and the strong LEDPUF is implemented by using the weak LEDPUF as the key of a keyed-hash message authentication code. Our simulation and statistical results show that the entropy of the weak LEDPUF bits is close to ideal, and the inter-chip Hamming distances of both weak and strong LEDPUFs are about 50%, which means that these LEDPUFs are not only stable but also unique. We develop a new unified framework for evaluating the security of PUFs, based on password security, by using information theoretic tools of guesswork. The guesswork model allows us to quantitatively compare, with a single unified metric, PUFs with varying levels of stability, bias, and available side information. In addition, it generalizes other measures to evaluate the security level, such as min-entropy and mutual information. We evaluate the guesswork-based security of some measured static random access memory and ring oscillator PUFs as an example and compare them with an LEDPUF to show that the stability has a more severe impact on the PUF security than biased responses. Furthermore, we find the guesswork of two new problems: guesswork under the probability of attack failure and the guesswork of strong PUFs that are used for authentication.

In this work we analyze the average guesswork for the problem of hashed password cracking (i.e., finding a password that has the same hash value as the actual password), when averaging over all hash functions whose effective distribution is i.i.d. Bernoulli(p) for any strategy of guessing passwords one by one (i.e., the fractions of passwords that are hashed to any bin, correspond to a probability mass function, which is i.i.d. Bernoulli(p)). We analyze the average guesswork under both online and offline attacks by deriving upper and lower bounds on the average guesswork as a function of the bins to which passwords are hashed, along with the most likely average guesswork, that is, the average guesswork of the most likely set of bins. Furthermore, we provide a concentration result that shows for this problem, that the probability mass function of guesswork is concentrated around its mean value. These results give quantifiable bounds for the effect of bias as well as the number of users on the average guesswork of a hash function, and show that increasing the number of users has a far worse effect than bias in terms of the average guesswork. However, when there exists a backdoor mechanism that enables “beamforming” certain passwords to the least likely bins, bias can in fact increase the average guesswork.

Embedded sensing systems are pervasively used in life- and security-critical systems such as those found in airplanes, automobiles, and healthcare. Traditional security mechanisms for these sensors focus on data encryption and other post-processing techniques, but the sensors themselves often remain vulnerable to attacks in the physical/analog domain. If an adversary manipulates a physical/analog signal prior to digitization, no amount of digital security mechanisms after the fact can help. Fortunately, nature imposes fundamental constraints on how these analog signals can behave. This work presents PyCRA, a physical challenge-response authentication scheme designed to protect active sensing systems against physical attacks occurring in the analog domain. PyCRA provides secure active sensing by continually challenging the surrounding environment via random but deliberate physical probes. By analyzing the responses to these probes, the system is able to ensure that the underlying physics involved are not violated, providing an authentication mechanism that not only detects malicious attacks but provides resilience against them. We demonstrate the effectiveness of PyCRA in detecting and mitigating attacks through several case studies using two sensing systems: (1) magnetic sensors like those found on gear and wheel speed sensors in robotics and automotive, and (2) commercial Radio Frequency Identification (RFID) tags used in many security-critical applications. In doing so, we evaluate both the robustness and the limitations of the PyCRA security scheme, concluding by outlining practical considerations as well as further applications for the proposed authentication mechanism.

A long-standing question in coding theory is whether code ensembles having a low-density parity check (LDPC) matrix can attain capacity under belief propagation (BP) decoding. An affirmative answer to this problem was recently given by the special class of spatially-coupled LDPC code ensemble. In this work, we provide a simple derivation of a different LDPC code ensemble that approaches capacity under BP decoding, following the classical approach of serial concatenation. This LDPC code ensemble is constructed by concatenating a high-rate outer LDPC code with an inner random convolutional one. The analysis of the concatenated-coding framework takes a particularly simple - “black box” - form. Specifically, the joint effect of the particular inner code and the binary-input memoryless output-symmetric (BMS) channel is encapsulated in a single parameter - the Bhattacharyya parameter, which is maximal for the binary symmetric channel (BSC). This implies that an inner convolutional code designed for the BSC achieves good performance over all BMS channels with a given capacity. Moreover, the performance guarantee of the outer LDPC code under BP decoding is dictated solely by this parameter. This, in turn, implies that the overall concatenated code approaches capacity under BP decoding for all BMS channels with a given capacity, simultaneously.

In this paper, the optimal diversity-multiplexing tradeoff (DMT) is investigated for the multiple-input multiple-output fading multiple-access channel with no power constraints (infinite constellations). For K users (K > 1), M transmit antennas for each user, and N receive antennas, infinite constellations in general and lattices in particular are shown to attain the optimal DMT of finite constellations for N ≥ (K + 1)M - 1, i.e., user limited regime. On the other hand, for Nmax [1, (N - M + 1)/M], considering the shaping region in the decoding process plays a crucial role in pursuing the optimal DMT. By investigating the cases in which the infinite constellations are optimal and suboptimal, this paper also gives a geometrical interpretation to the DMT of infinite constellations in multiple-access channels.

A max-product algorithm for approximating maximum-likelihood lattice decoding of low density lattice codes is derived, operating directly in the Euclidean space. First we derive the max-product algorithm for continuous channels by taking a factor graph based approach. Then, for the additive white Gaussian noise channel we show the relation between the sum-product and max-product algorithms for low density lattice codes. In both algorithms the messages consist of the same Gaussians. While in the sum-product algorithm we sum the Gaussians in each message, for the max-product we take the maximal envelope of these Gaussians. Finally, we extend the parametric approach to efficiently implement the max-product algorithm, and show decrease in the word error rate (WER).

The fundamental and natural connection between the infinite constellation (IC) dimension and the best diversity order it can achieve is investigated in this paper. In the first part of this work we develop an upper bound on the diversity order of IC for any dimension and any number of transmit and receive antennas. In the second part of this work we prove that by choosing the correct dimensions, IC in general and lattices in particular can achieve the optimal diversity-multiplexing tradeoff of finite constellations. This work gives a framework for designing lattices for multiple-antenna channels using lattice decoding.

An extension of the class of low density lattice codes (LDLC's) to the complex case (i.e. complex lattices) is presented. We propose an extended belief-propagation decoding algorithm and present a complex parametric decoder. The complex decoder attains better performance for small dimensions, and for LDLC's with small degrees. This extension is also required in order to use LDLC's as a lattice space time codes.

A new efficient parametric algorithm for implementing the low density lattice codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains essentially the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its smaller storage requirements and its relatively low computational complexity.