Secure processors with hardware-enforced isolation are crucial for secure cloud computation. However, commercial secure processors have underestimated the capabilities of attackers and failed to provide secure execution environments capable of protecting sensitive information against side-channel attacks. Remote Attestation protocols based on traditional signature schemes are not secure under side-channel attacks anymore since their secret keys can be leaked. Previously, Key-Insulated Schemes (KIS) have been introduced to mitigate the damage caused by secret key exposure in cryptosystems by breaking the lifetime of secret keys into independent sessions. KIS protect the security of all other sessions if any session keys are compromised, however, provide no security guarantees for a compromised session. We introduce a new cryptographic primitive called One-Time Signature with Secret Key Exposure (OTS-SKE), which ensures no one can forge a valid signature of a new message or nonce even if all secret session keys are leaked. OTS-SKE enables us to sign attestation reports securely under a powerful adversary who can observe all digital states in secure enclaves through side-channel attacks. We also minimize the trusted computing base by introducing a secure co-processor that is only responsible for key generation into the system. Our experiments show that the signing of OTS-SKE is faster than KIS as well as Elliptic Curve Digital Signature Algorithm (ECDSA) used in Intel SGX.

The XOR Arbiter PUF was introduced as a strong PUF in 2007 and was broken in 2015 by a Machine Learning (ML) attack, which allows the underlying Arbiter PUFs to be modeled individually by exploiting reliability information of the measured responses. To mitigate the reliability-based attacks, state-of-the-art understanding shows that the reliability of individual Arbiter PUFs and the overall XOR Arbiter PUF can be boosted to an arbitrarily high level, thus rendering all known reliability-based ML attacks infeasible; alternatively, an access control interface around the XOR Arbiter PUF can prevent the same challenge-response pairs from being accessed repeatedly, thus eliminating the leakage of reliability information. We show that, for the first time, a perfectly reliable XOR Arbiter PUF can be successfully attacked in a divide-and-conquer manner, meaning each underlying Arbiter PUF in an XOR Arbiter PUF can be attacked individually. This allows us to attack large XOR Arbiter PUFs efficiently, even without reliability information or any side-channel information. Our key insight is that, instead of reliability information, the responses of highly correlated challenges also reveal how close the responses are to the response decision boundary. This leads to achosen challenge attackon XOR Arbiter PUFs by carefully choosing correlated challenges to measure and aggregate the collected information. We validate our attack by using PUF simulation, as well as an XOR Arbiter PUF implemented on FPGA. We also demonstrate that our chosen challenge methodology is compatible with the state-of-the-art combined gradient-based multi-objective optimization attack. Finally, we discuss an effective countermeasure that can prevent our attack but with a relatively large area overhead compared to the PUF itself.

We introduce a multiple target optimization framework for DP-SGD referred to as pro-active DP. In contrast to traditional DP accountants, which are used to track the expenditure of privacy budgets, the pro-active DP scheme allows one to *a-priori* select parameters of DP-SGD based on a fixed privacy budget (in terms of $\epsilon$ and $\delta$) in such a way to optimize the anticipated utility (test accuracy) the most. To achieve this objective, we first propose significant improvements to the moment account method, presenting a closed-form $(\epsilon,\delta)$-DP guarantee that connects all parameters in the DP-SGD setup. Generally, DP-SGD is $(\epsilon\leq 1/2,\delta=1/N)$-DP if $\sigma=\sqrt{2(\epsilon +\ln(1/\delta))/\epsilon}$ with $T$ at least $\approx 2k^2/\epsilon$ and $(2/e)^2k^2-1/2\geq \ln(N)$, where $T$ is the total number of rounds, and $K=kN$ is the total number of gradient computations where $k$ measures $K$ in number of epochs of size $N$ of the local data set. We prove that our expression is close to tight in that if $T$ is more than a constant factor $\approx 4$ smaller than the lower bound $\approx 2k^2/\epsilon$, then the $(\epsilon,\delta)$-DP guarantee is violated. Our enhanced DP theory allows us to create a utility graph and DP calculator. These tools link privacy and utility objectives and search for optimal experiment setups, efficiently taking into account both accuracy and privacy objectives, as well as implementation goals. We furnish a comprehensive implementation flow of our proactive DP, with rigorous experiments to showcase the proof-of-concept.

Hogwild! implements asynchronous Stochastic Gradient Descent (SGD) where multiple threads in parallel access a common repository containing training data, perform SGD iterations and update shared state that represents a jointly learned (global) model. We consider big data analysis where training data is distributed among local data sets in a heterogeneous way – and we wish to move SGD computations to local compute nodes where local data resides. The results of these local SGD computations are aggregated by a central “aggregator” which mimics Hogwild!. We show how local compute nodes can start choosing small mini-batch sizes which increase to larger ones in order to reduce communication cost (round interaction with the aggregator). We improve state-of-the-art literature and show O(K^{0.5}) communication rounds for heterogeneous data for strongly convex problems, where K is the total number of gradient computations across all local compute nodes. For our scheme, we prove a tight and novel non-trivial convergence analysis for strongly convex problems for heterogeneous data which does not use the bounded gradient assumption as seen in many existing publications. The tightness is a consequence of our proofs for lower and upper bounds of the convergence rate, which show a constant factor difference. We show experimental results for plain convex and non-convex problems for biased (i.e., heterogeneous) and unbiased local data sets.

In this paper, we propose a unified convergence analysis for a class of generic shuffling-type gradient methods for solving finite-sum optimization problems. Our analysis works with any sampling without replacement strategy and covers many known variants such as randomized reshuffling, deterministic or randomized single permutation, and cyclic and incremental gradient schemes. We focus on two different settings: strongly convex and nonconvex problems, but also discuss the non-strongly convex case. Our main contribution consists of new non-asymptotic and asymptotic convergence rates for a wide class of shuffling-type gradient methods in both nonconvex and convex settings. We also study uniformly randomized shuffling variants with different learning rates and model assumptions. While our rate in the nonconvex case is new and significantly improved over existing works under standard assumptions, the rate on the strongly convex one matches the existing best-known rates prior to this paper up to a constant factor without imposing a bounded gradient condition. Finally, we empirically illustrate our theoretical results via two numerical examples: nonconvex logistic regression and neural network training examples. As byproducts, our results suggest some appropriate choices for diminishing learning rates in certain shuffling variants.

We propose a novel hybrid stochastic policy gradient estimator by combining an unbiased policy gradient estimator, the REINFORCE estimator, with another biased one, an adapted SARAH estimator for policy optimization. The hybrid policy gradient estimator is shown to be biased, but has variance reduced property. Using this estimator, we develop a new Proximal Hybrid Stochastic Policy Gradient Algorithm (ProxHSPGA) to solve a composite policy optimization problem that allows us to handle constraints or regularizers on the policy parameters. We first propose a single-looped algorithm then introduce a more practical restarting variant. We prove that both algorithms can achieve the best-known trajectory complexity to attain a first-order stationary point for the composite problem which is better than existing REINFORCE/GPOMDP and SVRPG in the non-composite setting. We evaluate the performance of our algorithm on several well-known examples in reinforcement learning. Numerical results show that our algorithm outperforms two existing methods on these examples. Moreover, the composite settings indeed have some advantages compared to the non-composite ones on certain problems.

We study Stochastic Gradient Descent (SGD) with diminishing step sizes for convex objective functions. We introduce a definitional framework and theory that defines and characterizes a core property, called curvature, of convex objective functions. In terms of curvature we can derive a new inequality that can be used to compute an optimal sequence of diminishing step sizes by solving a differential equation. Our exact solutions confirm known results in literature and allows us to fully characterize a new regularizer with its corresponding expected convergence rates.

We study the convergence of Stochastic Gradient Descent (SGD) for strongly convex objective functions. We prove for all $t$ a lower bound on the expected convergence rate after the $t$-th SGD iteration; the lower bound is over all possible sequences of diminishing step sizes. It implies that recently proposed sequences of step sizes at ICML 2018 and ICML 2019 are {\em universally} close to optimal in that the expected convergence rate after {\em each} iteration is within a factor $32$ of our lower bound. This factor is independent of dimension $d$. We offer a framework for comparing with lower bounds in state-of-the-art literature and when applied to SGD for strongly convex objective functions our lower bound is a significant factor $775\cdot d$ larger compared to existing work.

The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is violated for cases where the objective function is strongly convex. In Bottou et al. (2018), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. We show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime. We then move on to the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime in the case of diminished learning rate. It is well-known that SGD converges if a sequence of learning rates $\{\eta_t\}$ satisfies $\sum_{t=0}^\infty \eta_t \rightarrow \infty$ and $\sum_{t=0}^\infty \eta^2_t < \infty$. We show the convergence of SGD for strongly convex objective function without using bounded gradient assumption when $\{\eta_t\}$ is a diminishing sequence and $\sum_{t=0}^\infty \eta_t \rightarrow \infty$. In other words, we extend the current state-of-the-art class of learning rates satisfying the convergence of SGD.

Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime, which results in more relaxed conditions than those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate.

Arbiter Physically Unclonable Functions (APUFs), while being relatively lightweight, are extremely vulnerable to modeling attacks. Hence, various compositions of APUFs such as XOR APUF and Lightweight Secure PUF have been proposed to be secure alternatives. Previous research has demonstrated that PUF compositions have two major challenges to overcome: vulnerability against modeling and statistical attacks, and lack of reliability. In this paper, we introduce a multiplexer-based composition of APUFs, denoted as MPUF, to simultaneously overcome these challenges. In addition to the basic MPUF design, we propose two MPUF variants namely cMPUF and rMPUF to improve the robustness against cryptanalysis and reliability-based modeling attack, respectively. An rMPUF demonstrates enhanced robustness against the reliability-based modeling attack, while even the well-known XOR APUF, otherwise robust to machine learning based modeling attacks, has been modeled using the same technique with linear data and time complexities. The rMPUF can provide a good trade-off between security and hardware overhead while maintaining a significantly higher reliability level than any practical XOR APUF instance. Moreover, MPUF variants are the first APUF compositions, to the best of our knowledge, that can achieve Strict Avalanche Criterion without using any additional input network (or hardware) for challenge transformation. Finally, we validate our theoretical findings using Matlab-based simulations of MPUFs.

PUF-PRFs are Pseudorandom Functions (PRFs) constructed using Physically Unclonable Functions (PUFs) as a hardware building block to provide the random input-output mapping. Since PUF-PRFs inherit all the principal properties of PUFs such as memory-leakage resilience, unclonablity, tampering-resistance, pseudo-randomness, and provable security, PUF-PRFs hold great promise as an extremely useful cryptographic hardware primitive. In this paper, we evaluate the security of PUF-PRFs against Side Channel Attacks. Two different attacks based on analysis of power side channel are developed, and demonstrated through the experiments on Xilinx FPGAs. In addition, we reduce the complexity of Correlation Power Analysis (CPA) to recover n-bit secret, from O(2 2n) to O(3n 2n). Based on our experimental results, we conclude that the security of PUF-PRFs, when subjected to side channel attacks, depends on not only the security of the used PUFs, but also the PUF-PRF architecture.

Unpredictability is an important security property of Physically Unclonable Function (PUF) in the context of statistical attacks, where the correlation between challenge-response pairs is explicitly exploited. In the existing literature on PUFs, the Hamming Distance Test, denoted by HDT( t ), was proposed to evaluate the unpredictability of PUFs, which is a simplified case of the Propagation Criterion test PC( t ). The objective of these test schemes is to estimate the output transition probability when there are t or fewer than t bits flips, and ideally this probability value should be 0.5. In this work, we show that aforementioned two test schemes are not enough to ensure the unpredictability of a PUF design. We propose a new test, which is denoted as HDT( e , t ). This test scheme is a fine-tuned version of the previous schemes, as it considers the flipping bit pattern vector e along with parameter t . As a contribution, we provide a comprehensive discussion and analytic interpretation of HDT( t ), PC( t ), and HDT( e , t ) test schemes for Arbiter PUF (APUF), Exclusive-OR (XOR) PUF, and Lightweight Secure PUF (LSPUF). Our analysis establishes that HDT( e , t ) test is more general in comparison with HDT( t ) and PC( t ) tests. In addition, we demonstrate a few scenarios where the adversary can exploit the information obtained from the analysis of HDT( e , t ) properties of APUF, XOR PUF, and LSPUF to develop statistical attacks on them, if the ideal value of HDT( e , t ) = 0.5 is not achieved for a given PUF. We validate our theoretical observations using the simulated and Field Programmable Gate Array (FPGA) implemented APUF, XOR PUF, and LSPUF designs.

Due to their unique physical properties, physically unclonable functions (PUF) have been proposed widely as versatile cryptographic primitives. It is desirable that silicon PUF circuits should be lightweight, i.e., have low-hardware resource requirements. However, it is also of primary importance that such demands of low hardware overhead should not compromise the security aspects of PUF circuits. In this paper, we develop two different mathematical attacks on previously proposed lightweight PUF circuits, namely composite PUF and the multibit output lightweight secure PUF (LSPUF). We show that independence of various components of composite PUF can be used to develop divide and conquer attacks which can be used to determine the responses to unknown challenges. We reduce the complexity of the attack using a machine learning-based modeling analysis. In addition, we elucidate a special property of the output network of LSPUF to show how such feature can be leveraged by an adversary to perform an intelligent model building attack. The theoretical inferences are validated through experimental results. More specifically, proposed attacks on composite PUF are validated using the challenge-response pairs (CRPs) from its field programmable gate array (FPGA) implementation, and attack on LSPUF is validated using the CRPs of both simulated and FPGA implemented LSPUF.

The success of a side-channel attack depends mainly on three factors, namely, the cipher algorithm, the attack platform, and the measurement noise. In this paper, we consider a class of side-channel attacks known as differential cache attacks on Feistel ciphers, and develop a theoretical framework to understand the relationship between the attack's success, the target platform, and the cipher algorithm. The framework allows a comparison of various differential cache attack forms, and is supported by case studies on the block ciphers CLEFIA and CAMELLIA. To understand the effect of noise in the attack's success, the paper uses empirical methods on standard Intel platforms in a time driven side-channel analysis scenario.