An introduction to local differential privacy protocols using block designs

• URL: http://arxiv.org/abs/2602.02744v1
• Date: Mon, 02 Feb 2026 19:58:58 GMT
• Title: An introduction to local differential privacy protocols using block designs
• Authors: Maura B. Paterson, Douglas R. Stinson,
• Abstract summary: Local differential privacy (or LDP) protocols utilise the randomised encoding of outcomes of an experiment using a transition probability matrix (TPM)<n>Several authors have observed that balanced incomplete block designs (BIBDs) provide nice examples of TPMs for LDP protocols.<n>We show that the optimal estimators for BIBD-based TPMs are precisely those obtained from the Moore-Penrose inverse of the corresponding TPM.
• Score: 1.360738859820932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The design of protocols for local differential privacy (or LDP) has been a topic of considerable research interest in recent years. LDP protocols utilise the randomised encoding of outcomes of an experiment using a transition probability matrix (TPM). Several authors have observed that balanced incomplete block designs (BIBDs) provide nice examples of TPMs for LDP protocols. Indeed, it has been shown that such BIBD-based LDP protocols provide optimal estimators. In this primarily expository paper, we give a detailed introduction to LDP protocols and their connections with block designs. We prove that a subclass of LDP protocols known as pure LDP protocols are equivalent to $(r,λ)$-designs (which contain balanced incomplete block designs as a special case). An unbiased estimator for an LDP scheme is a left inverse of the transition probability matrix. We show that the optimal estimators for BIBD-based TPMs are precisely those obtained from the Moore-Penrose inverse of the corresponding TPM. We also review some existing work on optimal LDP protocols in the context of pure protocols.

Related papers

• LDP$^3$: An Extensible and Multi-Threaded Toolkit for Local Differential Privacy Protocols and Post-Processing Methods [1.0486921990935787]
  Local differential privacy (LDP) has become a prominent notion for privacy-preserving data collection.<n>This paper presents LDP$3$, an open-source, benchmarking, and multi-threaded toolkit for LDP researchers and practitioners.
  arXiv  Detail & Related papers  (2025-07-08T10:51:42Z)
• Automated Selfish Mining Analysis for DAG-Based PoW Consensus Protocols [0.0]
  Selfish mining is strategic rule-breaking to maximize rewards in proof-of-work protocols.<n>We propose a generic attack model that covers a wide range of protocols, including Proof-of-Work, GhostDAG, and Parallel Proof-of-Work.
  arXiv  Detail & Related papers  (2025-01-18T21:57:02Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  We propose the Observation-Aware Spectral (OAS) estimation technique, which enables the POMDP parameters to be learned from samples collected using a belief-based policy. We show the consistency of the OAS procedure, and we prove a regret guarantee of order $mathcalO(sqrtT log(T)$ for the proposed OAS-UCRL algorithm.
  arXiv  Detail & Related papers  (2024-10-02T08:46:34Z)
• Benchmarking Secure Sampling Protocols for Differential Privacy [3.0325535716232404]
  Two well-known models of Differential Privacy (DP) are the central model and the local model. Recently, many studies have proposed to achieve DP with Secure Multi-party Computation (MPC) in distributed settings.
  arXiv  Detail & Related papers  (2024-09-16T19:04:47Z)
• On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks [17.351593328097977]
  Local differential privacy (LDP) protocols are vulnerable to data poisoning attacks.<n>This vulnerability raises concerns regarding the robustness and reliability of LDP in hostile environments.
  arXiv  Detail & Related papers  (2024-03-28T15:43:38Z)
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective [4.5282933786221395]
  We introduce the LDP-Auditor framework for empirically estimating the privacy loss of locally differentially private mechanisms. We extensively explore the factors influencing the privacy audit, such as the impact of different encoding and perturbation functions. We present a notable achievement of our LDP-Auditor framework, which is the discovery of a bug in a state-of-the-art LDP Python package.
  arXiv  Detail & Related papers  (2023-09-04T13:29:19Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid. We propose a theory characterizing the approximation error of the particle filtering techniques that these algorithms use.
  arXiv  Detail & Related papers  (2022-10-10T21:11:55Z)
• Towards Semantic Communication Protocols: A Probabilistic Logic Perspective [69.68769942563812]
  We propose a semantic protocol model (SPM) constructed by transforming an NPM into an interpretable symbolic graph written in the probabilistic logic programming language (ProbLog) By leveraging its interpretability and memory-efficiency, we demonstrate several applications such as SPM reconfiguration for collision-avoidance.
  arXiv  Detail & Related papers  (2022-07-08T14:19:36Z)
• Semi-Markov Offline Reinforcement Learning for Healthcare [57.15307499843254]
  We introduce three offline RL algorithms, namely, SDQN, SDDQN, and SBCQ. We experimentally demonstrate that only these algorithms learn the optimal policy in variable-time environments. We apply our new algorithms to a real-world offline dataset pertaining to warfarin dosing for stroke prevention.
  arXiv  Detail & Related papers  (2022-03-17T14:51:21Z)
• Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
  Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server. This has led to significant efforts on reducing the communication cost of LDP algorithms.
  arXiv  Detail & Related papers  (2021-02-24T07:04:30Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  We consider the regret problem for reinforcement learning in latent Markov Decision Processes (LMDP) In an LMDP, an MDP is randomly drawn from a set of $M$ possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We show that the key link is a notion of separation between the MDP system dynamics.
  arXiv  Detail & Related papers  (2021-02-09T16:49:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.