Fair decision-making in Machine Learning (ML) remains a critical challenge, particularly when access to sensitive information is restricted due to legal, ethical, or organizational constraints. These limitations affect both accuracy and fairness, creating tradeoffs central to the deployment of ML systems in the real world. While prior work has studied fairness-accuracy tradeoffs, most approaches focus on model outputs rather than directly examining how restricted data access impacts fairness. This leaves an important gap: understanding how fairness constraints affect model performance under real-world data restrictions . To address this gap, we propose a framework that explicitly models fairness-accuracy tradeoffs in data-restricted environments. Unlike prior work, our approach analyzes the behavior of the optimal Bayesian classifier using a discrete approximation of the data distribution, allowing us to systematically isolate the effects of fairness constraints. We evaluate our framework on three benchmark datasets—Adult, Law, and Dutch Census—revealing key insights: (1) enforcing equal accuracy on imbalanced datasets can substantially degrade performance under additional fairness constraints, (2) individual and group fairness often impose conflicting constraints, and (3) decorrelating sensitive attributes from features does not usually reduce accuracy. These findings demonstrate that our framework provides an effective, structured approach for practitioners to assess fairness constraints in decision-making pipelines.

The growing use of machine learning (ML) has raised concerns that an ML model may reveal private information about an individual who has contributed to the training dataset. To prevent leakage of sensitive data, we consider using differentially- private (DP), synthetic training data instead of real training data to train an ML model. A key desirable property of synthetic data is its ability to preserve the low-order marginals of the original distribution. Our main contribution comprises novel upper and lower bounds on the excess empirical risk of linear models trained on such synthetic data, for continuous and Lipschitz loss functions. We perform extensive experimentation alongside our theoretical results.

Increases in the deployment of machine learning algorithms for applications that deal with sensitive data have brought attention to the issue of fairness in machine learning. Many works have been devoted to applications that require different demographic groups to be treated fairly. However, algorithms that aim to satisfy inter-group fairness (also called group fairness) may inadvertently treat individuals within the same demographic group unfairly. To address this issue, this article introduces a formal definition of within-group fairness that maintains fairness among individuals from within the same group. A pre-processing framework is proposed to meet both inter- and within-group fairness criteria with little compromise in performance. The framework maps the feature vectors of members from different groups to an inter-group fair canonical domain before feeding them into a scoring function. The mapping is constructed to preserve the relative relationship between the scores obtained from the unprocessed feature vectors of individuals from the same demographic group, guaranteeing within-group fairness. This framework has been applied to the Adult, COMPAS risk assessment, and Law School datasets, and its performance is demonstrated and compared with two regularization-based methods in achieving inter-group and within-group fairness.

Randomness extractors provide a generic way of converting sources of randomness that are merely unpredictable into almost uniformly random bits. While in general, deterministic randomness extraction is impossible, it is possible if the source has some structural constraints.While much of the literature on deterministic extraction has focused on sources with strong independence properties, a natural class where deterministic extraction is possible is sources that can sampled by a polynomial size circuit, Levin [SIAM J Comp’86]. Trevisan and Vadhan [FOCS’00] explicitly constructed deterministic randomness extractors for this class of sources, assuming very strong circuit lower bounds.We suggest that there is perhaps an even more reasonable model of natural sources of randomness than Levin’s: sources sampled by polynomial size quantum circuits. Under a suitable circuit lower bound, we show that Trevisan and Vadhan’s extractor indeed works for this class.Along the way, we substantially improve their analysis in the classical case, showing that a circuit lower bound against NP-circuits suffice in the classical case (as opposed to a lower bounds on $\Sigma_{5}$-circuits, as shown by Trevisan and Vadhan). Moreover, we show that under this assumption, it is possible to handle sources sampled by postselecting circuits (a variant of nondeterministic circuits). We show that this model is sufficient to capture randomness extraction in the presence of efficiently computable leakage.

In this work, we recover the private key material of the FrodoKEM key exchange mechanism as submitted to the NIST Post Quantum Cryptography (PQC) standardization process.

Fully homomorphic encryption (FHE) enables a simple, attractive framework for secure search. Compared to other secure search systems, no costly setup procedure is necessary; it is sufficient for the client merely to upload the encrypted database to the server. Confidentiality is provided because the server works only on the encrypted query and records. While the search functionality is enabled by the full homomorphism of the encryption scheme. For this reason, researchers have been paying increasing attention to this problem. Since Akavia et al. (CCS 2018) presented a framework for secure search on FHE encrypted data and gave a working implementation called SPiRiT, several more efficient realizations have been proposed. In this paper, we identify the main bottlenecks of this framework and show how to significantly improve the performance of FHE-base secure search. In particular, To retrieve l matching items, the existing framework needs to repeat the protocol l times sequentially. In our new framework, all matching items are retrieved in parallel in a single protocol execution. The most recent work by Wren et al. (CCS 2020) requires O(n) multiplications to compute the first matching index. Our solution requires no homomorphic multiplication, instead using only additions and scalar multiplications to encode all matching indices. Our implementation and experiments show that to fetch 16 matching records, our system gives an 1800X speed-up over the state of the art in fetching the query results resulting in a 26X speed-up for the full search functionality.

There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class ℱ? First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: - Functions that change d/2 symbols, where d is the distance of the code; - Functions where each input symbol affects only a single output symbol; - Functions where each of the n output bits is a function of n-log n input bits. Furthermore, we rule out constructions of non-malleable codes for certain classes ℱ via reductions to the assumption that a distributional problem is hard for ℱ, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P ⊈ NC.

Abstract We consider a scenario where multiple organizations holding large amounts of sensitive data from their users wish to compute aggregate statistics on this data while protecting the privacy of individual users. To support large-scale analytics we investigate how this privacy can be provided for the case of sketching algorithms running in time sub-linear of the input size. We begin with the well-known LogLog sketch for computing the number of unique elements in a data stream. We show that this algorithm already achieves differential privacy (even without adding any noise) when computed using a private hash function by a trusted curator. Next, we show how to eliminate this requirement of a private hash function by injecting a small amount of noise, allowing us to instantiate an efficient LogLog protocol for the multi-party setting. To demonstrate the practicality of this approach, we run extensive experimentation on multiple data sets, including the publicly available IP address data set from University of Michigan’s scans of internet IPv4 space, to determine the trade-offs among efficiency, privacy and accuracy of our implementation for varying numbers of parties and input sizes. Finally, we generalize our approach for the LogLog sketch and obtain a general framework for constructing multi-party differentially private protocols for several other sketching algorithms.

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. AC0tampering functions), our codes have codeword length n = k1+0(1)for a k-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length 2O(√k). Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n ≤ k1+ε), and extending our result beyond this would require separating P from NC1. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.

A function f is d-resilient if all its Fourier coefficients of degree at most d are zero, i.e. f is uncorrelated with all low-degree parities. We study the notion of approximate resilience of Boolean functions, where we say that f is α-approximately d-resilient if f is α-close to a [-1, 1]-valued d-resilient function in ℓ1 distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class C over the uniform distribution. Roughly speaking, if all functions in a class C are far from being d-resilient then C can be learned agnostically in time nO(d) and conversely, if C contains a function close to being d-resilient then agnostic learning of C in the statistical query (SQ) framework of Kearns has complexity of at least nΩ(d). Focusing on monotone Boolean functions, we exhibit the existence of near-optimal α-approximately -resilient monotone functions for all α > 0. Prior to our work, it was conceivable even that every monotone function is Ω(1)-far from any 1-resilient function. Furthermore, we construct simple, explicit monotone functions based on Tribes and CycleRun that are close to highly resilient functions. Our constructions are based on general resilience analysis and amplification techniques we introduce. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas, a natural variant of the well-studied junta learning problem. In particular we show that no SQ algorithm can efficiently agnostically learn monotone k-juntas for any k = ω(1) and any constant error less than 1/2.