In recent years, Federated Unlearning (FU) has gained attention for addressing the removal of a client’s influence from the global model in Federated Learning (FL) systems, thereby ensuring the “right to be forgotten” (RTBF). State-of-the-art methods for unlearning use historical data from FL clients, such as gradients or locally trained models. However, studies have revealed significant information leakage in this setting, with the possibility of reconstructing a user’s local data from their uploaded information. Addressing this, we propose Starfish, a privacy-preserving federated unlearning scheme using Two-Party Computation (2PC) techniques and shared historical client data between two non-colluding servers. Starfish builds upon existing FU methods to ensure privacy in unlearning processes. To enhance the efficiency of privacy-preserving FU evaluations, we suggest 2PC-friendly alternatives for certain FU algorithm operations. We also implement strategies to reduce costs associated with 2PC operations and lessen cumulative approximation errors. Moreover, we establish a theoretical bound for the difference between the unlearned global model via Starfish and a global model retrained from scratch for certified client removal. Our theoretical and experimental analyses demonstrate that Starfish achieves effective unlearning with reasonable efficiency, maintaining privacy and security in FL systems.

We consider the problem of efficient construction ofq-ary 2-deletion correcting codes with low redundancy. We show that our construction requires less redundancy than any existing efficiently encodableq-ary 2-deletion correcting codes. Precisely speaking, we present an explicit construction of aq-ary 2-deletion correcting code with redundancy 5 logn+10 log logn+ 3 logq+O(1) whereqis assumed to be a constant with respect ton. Using a minor modification to the original construction, we obtain an efficiently encodableq-ary 2-deletion code that is efficiently list-decodable. Similarly, we show that our construction of list-decodable code requires a smaller redundancy compared to any existing list-decodable codes. To obtain our sketches, we transform aq-ary code-word to a binary string which can then be used as an input to the underlying base binary sketch. This is then complemented with additionalq-ary sketches that the originalq-ary codeword is required to satisfy. In other words, we build our codes via a binary 2-deletion code as a black-box. Finally we utilize the binary 2-deletion code proposed by Guruswami and Håstad to our construction to obtain the main result of this paper.

In order to remain competitive, Internet companies collect and analyse user data for the purpose of the improvement of user experiences. Frequency estimation is a widely used statistical tool, which could potentially conflict with the relevant privacy regulations. Privacy preserving analytic methods based on differential privacy have been proposed, which require either a large user base or a trusted server. Although the requirements for such solutions may not be a problem for larger companies, they may be unattainable for smaller organizations. To address this issue, we propose a distributed privacy-preserving sampling-based frequency estimation method which has high accuracy even in the scenario with a small number of users while not requiring any trusted server. This is achieved by combining multi-party computation and sampling techniques. We also provide a relation between its privacy guarantee, output accuracy, and the number of participants. Distinct from most existing methods, our methods achievecentralizeddifferential privacy guarantee without the need of any trusted server. We established that, even for a small number of participants, our mechanisms can produce estimates with high accuracy and hence they provide smaller companies with more opportunity for growth through privacy-preserving statistical analysis. We further propose an architectural model to support weighted aggregation in order to achieve a higher accuracy estimate to cater for users with varying privacy requirements. Compared to the unweighted aggregation, our method provides a more accurate estimate. Extensive experiments are conducted to show the effectiveness of the proposed methods.

For codes equipped with metrics such as Hamming metric, symbol pair metric or cover metric, the Johnson bound guarantees list-decodability of such codes. That is, the Johnson bound provides a lower bound on the list-decoding radius of a code in terms of its relative minimum distance$\delta $, list size$L$and the alphabet size$q$. For study of list-decodability of codes with insertion and deletion errors (we call such codes insdel codes), it is natural to ask the open problem whether there is also a Johnson-type bound. The problem was first investigated by Wachter-Zeh and the result was amended by Hayashi and Yasunaga where a lower bound on the list-decodability for insdel codes was derived. The main purpose of this paper is to move a step further towards solving the above open problem. In this work, we provide a new lower bound for the list-decodability of an insdel code. As a consequence, we show that unlike the Johnson bound for codes under other metrics that is tight, the bound on list-decodability of insdel codes given by Hayashi and Yasunaga is not tight. Our main idea is to show that if an insdel code with a given Levenshtein distance$d$is not list-decodable with list size$L$, then the list decoding radius is lower bounded by a bound involving$L$and$d$. In other words, if the list decoding radius is less than this lower bound, the code must be list-decodable with list size$L$. At the end of the paper we use such bound to provide an insdel-list-decodability bound for various well-known codes, which has not been extensively studied before.

Privacy-preserving data analysis is an emerging area that addresses the dilemma of performing data analysis on user data while protecting users’ privacy. In this paper, we consider the problem of constructing privacy-preservingK-means clustering protocol for data analysis that provides local privacy to users’ data. To enable a desirable degree of local privacy guarantee while maintaining high accuracy of the clustering, we adopt a generalized differential privacy definition,dχ-privacy, which quantifies the distinguishability level based on the distance between data records defined by the distance functiondχ. In our work, we consider the space of data points as a metric space imbued with Euclidean distance and propose a bounded perturbation mechanism (BPM) with bounded sampling space of the perturbed data points, which is formally shown to achievedχ-privacy. BPM perturbs the data as a whole instead of treating each dimension independently, which is desirable since the privacy budget is no longer required to be split among different dimensions. Bounded output space also means that we will not get into the case where the report or the statistical result is so far out of the data domain that it is hard to interpret. Furthermore, it can also help in limiting the amount of bandwidth needed to send such report to the server. The design of BPM is based on a probability density function which decreases exponentially as the Euclidean distance with respect to the true value grows. It is also designed with the aim of ensuring that BPM produces perturbed data that provides the claimed privacy guarantee while ensuring high utility response. To guarantee the efficiency of the perturbation method, we propose an efficient algorithm to sample from the proposed distribution and apply BPM to the design ofdχ-privateK-means clustering algorithms. Lastly, we analyse the privacy and utility guarantee provided by the proposed method and provide its experimental results.

In this work, we consider the leakage-resilience of algebraic-geometric (AG for short) codes based ramp secret sharing schemes extending the analysis on the leakage-resilience of linear threshold secret sharing schemes over prime fields that is done by Benhamouda et al. in the effort to construct linear leakage-resilient secret sharing schemes with constant share size. Since there does not exist any explicit efficient construction of AG codes over prime fields with constant field size, we consider constructions over prime fields with the help of concatenation method and constructions of codes over field extensions. Extending the Fourier analysis done by Benhamouda et al., one can show that concatenated algebraic geometric codes over prime fields do produce some nice leakage-resilient secret sharing schemes. One natural and curious question is whether AG codes over extension fields produce better leakage-resilient secret sharing schemes than the construction based on concatenated AG codes. Such construction provides several advantage compared to the construction over prime fields using concatenation method. It is clear that AG codes over extension fields give secret sharing schemes with a smaller reconstruction threshold for a fixed privacy parameter$t$. In this work, it is also confirmed that indeed AG codes over extension fields have stronger leakage-resilience under some reasonable assumptions. Furthermore, we also show that AG codes over extension fields may provide strong multiplicative property which may be used in its application to the study of multiparty computation. In contrast, the same cannot be said for constructions based on concatenated AG codes, even when we are considering multiplication friendly embeddings. These advantages strongly motivate the study of secret sharing schemes from AG codes over extension fields. The current paper has two main contributions: (i) we obtain leakage-resilient secret sharing schemes with constant share sizes and unbounded numbers of players. Some of the schemes constructed without the use of concatenation also possesses strong multiplicative property (ii) via Fourier Analysis, we analyze the leakage-resilience of secret sharing schemes from codes over extension fields. This is of its own theoretical interest independent of its application to secret sharing schemes from algebraic geometric codes over extension fields.

Crowdsourcing plays an essential role in the Internet of Things (IoT) for data collection, where a group of workers is equipped with Internet-connected geolocated devices to collect sensor data for marketing or research purpose. In this article, we consider crowdsourcing these worker's hot travel path. Each worker is required to report his real-time location information, which is sensitive and has to be protected. Encryption-based methods are the most direct way to protect the location, but not suitable for resource-limited devices. Besides, local differential privacy is a strong privacy concept and has been deployed in many software systems. However, the local differential privacy technology needs a large number of participants to ensure the accuracy of the estimation, which is not always the case for crowdsourcing. To solve this problem, we proposed a trie-based iterative statistic method, which combines additive secret sharing and local differential privacy technologies. The proposed method has excellent performance even with a limited number of participants without the need of complex computation. Specifically, the proposed method contains three main components: iterative statistics, adaptive sampling, and secure reporting. We theoretically analyze the effectiveness of the proposed method and perform extensive experiments to show that the proposed method not only provides a strict privacy guarantee, but also significantly improves the performance from the previous existing solutions.

Insertion and deletion (insdel for short) errors are synchronization errors in communication systems caused by the loss of positional information in the message. Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability in the classical setting. This interest also translates to the insdel metric setting, as the Guruswami-Sudan decoding algorithm can be utilized to provide a deletion correcting algorithm in the insdel metric. Nevertheless, there have been few studies on the insdel error-correcting capability of Reed-Solomon codes. Our main contributions in this article are explicit constructions of two families of 2-dimensional Reed-Solomon codes with insdel error-correcting capabilities asymptotically reaching those provided by the Singleton bound. The first construction gives a family of Reed-Solomon codes with insdel error-correcting capability asymptotic to its length. The second construction provides a family of Reed-Solomon codes with an exact insdel error-correcting capability up to its length. Both our constructions improve the previously known construction of 2-dimensional Reed-Solomon codes whose insdel error-correcting capability is only logarithmic on the code length.

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes.

Tandon et al. (2017) introduced a coding theoretic framework to alleviate the problem of stragglers in distributed learning. Following Tandon et al., many authors provided explicit schemes that were able to compute a certain function using n - s replies from n workers in the worst case. In this work, we focus on reducing the expected delay. To reduce the expected delay, we modify existing schemes so that less than (n - s) replies are sufficient in most cases. In particular, we provide a simple modification to existing optimal schemes and demonstrate that with this modification, the expected delay time converges to the fundamental delay. Additionally, for specific parameters, we reduce the number of replies further so that the expected delay time converges faster to the fundamental delay.