Differential Privacy (DP) is a widely adopted standard for privacy-preserving data analysis, but it assumes a uniform privacy budget across all records, limiting its applicability when privacy requirements vary with data values. Per-record Differential Privacy (PrDP) addresses this by defining the privacy budget as a function of each record, offering better alignment with real-world needs. However, the dependency between the privacy budget and the data value introduces challenges in protecting the budget's privacy itself. Existing solutions either handle specific privacy functions or adopt relaxed PrDP definitions. A simple workaround is to use the global minimum of the privacy function, but this severely degrades utility, as the minimum is often set extremely low to account for rare records with high privacy needs. In this work, we propose a general and practical framework that enables any standard DP mechanism to support PrDP, with error depending only on the minimal privacy requirement among records actually present in the dataset. Since directly revealing this minimum may leak information, we introduce a core technique called privacy-specified domain partitioning, which ensures accurate estimation without compromising privacy. We also extend our framework to the local DP setting via a novel technique, privacy-specified query augmentation. Using our framework, we present the first PrDP solutions for fundamental tasks such as count, sum, and maximum estimation. Experimental results show that our mechanisms achieve high utility and significantly outperform existing Personalized DP (PDP) methods, which can be viewed as a special case of PrDP with relaxed privacy protection.

翻译：差分隐私（DP）是一种广泛采用的隐私保护数据分析标准，但其假设所有记录具有统一的隐私预算，当隐私需求随数据值变化时，其适用性受到限制。逐记录差分隐私（PrDP）通过将隐私预算定义为每条记录的函数来解决这一问题，从而更好地与现实需求相匹配。然而，隐私预算与数据值之间的依赖关系给保护预算本身的隐私带来了挑战。现有解决方案要么处理特定的隐私函数，要么采用宽松的PrDP定义。一种简单的变通方法是使用隐私函数的全局最小值，但这会严重降低数据效用，因为最小值通常设置得极低，以应对具有高隐私需求的罕见记录。在本研究中，我们提出了一个通用且实用的框架，使任何标准DP机制都能支持PrDP，其误差仅取决于数据集中实际存在记录的最小隐私需求。由于直接揭示该最小值可能泄露信息，我们引入了一项核心技术，称为隐私指定域划分，可在不损害隐私的前提下确保准确估计。我们还通过一种新技术——隐私指定查询增强，将我们的框架扩展到本地DP设置。利用该框架，我们首次为计数、求和及最大值估计等基本任务提供了PrDP解决方案。实验结果表明，我们的机制实现了高数据效用，并显著优于现有的个性化差分隐私（PDP）方法，后者可视为隐私保护较宽松的PrDP特例。