Differentially Private Stochastic Gradient Descent (DP-SGD) is a prime method for training machine learning models with rigorous privacy guarantees. Since its birth, DP-SGD has gained popularity and has been widely adopted in both academic and industrial research. One well-known challenge when using DP-SGD is how to improve utility while maintaining privacy. To this end, recently we have seen several proposals that clip the gradients with adaptive thresholds rather than a fixed one. Although each proposal comes with some theoretical justification, the theories often rely on strong assumptions and are not compatible with each other. It is hard to know whether they are good in practice and how good they are. In this paper, we investigate adaptive clipping in DP-SGD from an empirical perspective. With extensive experiments, we were able to gain some fresh insights and proposed two new adaptive clipping strategies based on them. We cross-compared the existing methods and our new strategies experimentally. Results showed that our strategies did provide a substantial improvement in model accuracy, and outperformed the state-of-the-art adaptive clipping methods consistently.

Homomorphic encryption (HE) schemes, such as fully homomorphic encryption (FHE), support a number of useful computations on ciphertext in a broad range of applications, such as e-voting, private information retrieval, cloud security, and privacy protection. While FHE schemes do not require any interaction during computation, the key limitations are large ciphertext expansion and inefficiency. Thus, to overcome these limitations, we develop a novel cryptographic tool, MAS-Encryption (MASE), to support real-value input and secure computation on the multiply-add structure. The multiply-add structures exist in many important protocols, such as classifiers and outsourced protocols, and we will explain how MASE can be used to protect the privacy of these protocols, using two case study examples. Specifically, the first case study example is the privacy-preserving Naive Bayes classifier that can achieve minimal Bayes risk, and the other example is the privacy-preserving support vector machine. We prove that the constructed classifiers are secure and evaluate their performance using real-world datasets. Experiments show that our proposed MASE scheme and MASE based classifiers are efficient, in the sense that we achieve an optimal tradeoff between computation efficiency and communication interactions. Thus, we avoid the inefficiency of FHE based paradigm.

Strings are used to model genomic, natural language, and web activity data, and are thus often shared broadly. However, string data sharing has raised privacy concerns stemming from the fact that knowledge of length-k substrings of a string and their frequencies (multiplicities) may be sufficient to uniquely reconstruct the string; and from that the inference of such substrings may leak confidential information. We thus introduce the problem of protecting length-k substrings of a single string S by applying Differential Privacy (DP) while maximizing data utility for frequency-based mining tasks. Our theoretical and empirical evidence suggests that classic DP mechanisms are not suitable to address the problem. In response, we employ the order-k de Bruijn graph G of S and propose a sampling-based mechanism for enforcing DP on G. We consider the task of enforcing DP on G using our mechanism while preserving the normalized edge multiplicities in G. We define an optimization problem on integer edge weights that is central to this task and develop an algorithm based on dynamic programming to solve it exactly. We also consider two variants of this problem with real edge weights. By relaxing the constraint of integer edge weights, we are able to develop linear-time exact algorithms for these variants, which we use as stepping stones towards effective heuristics. An extensive experimental evaluation using real-world large-scale strings (in the order of billions of letters) shows that our heuristics are efficient and produce near-optimal solutions which preserve data utility for frequency-based mining tasks.