Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
本文研究差分隐私（DP）约束下的基础图优化问题，并给出基于“重构攻击”思路的新型下界证明。作者考虑图 G=(V,E,w⃗)，其中顶点集 V 与边集 E 是公开的，只有边权函数 w:E→ℝ 需要满足 ℓ1 邻接关系下的差分隐私。研究对象包括两
#cs.DS
共收录 54 条相关情报。
← 返回所有主题Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
该论文研究量子算法中「查询次数与内存（量子比特）之间的权衡」这一核心问题。经典背景下，对于均匀随机函数 f:[N]→[N]，BHT 算法用 O(N^{1/3}) 次查询加上一张 O(N^{1/3}) 规模的量子可访问经典表即可找到碰撞，而仅
Scalable Composition of Byzantine Agreements under Reorder Attacks
拜占庭协议（BA）是分布式系统的核心基础组件，多实例执行下的安全性分析近年受到越来越多关注。然而现有敌手模型大多只考虑节点被腐化，忽视了通信信道被对抗性操纵带来的重要威胁。攻击者可通过信道攻击在多个协议执行实例之间对消息进行重排序，从而破坏
Machine Unlearning as Private Retroactive Algorithms
本文是理论计算机科学与数据隐私方向的研究论文，研究机器学习中的“机器遗忘”问题。传统机器遗忘旨在模拟“从头重新训练”的效果：当收到删除请求时，遗忘算法应产生一个结果，该结果与从未包含被删除数据点时从头训练得到的结果一致。近期研究表明，对于一
Online Differentially Private Consistent Clustering
本文研究在线流式设置下的差分隐私（DP）k-means 与 k-median 聚类问题。在在线场景中，数据点按顺序持续到达，算法需在每个时间步基于已见数据输出一组 k 个中心，以最小化聚类代价（如 k-means 的平方距离和或 k-med
Decisive Margins in Differentially Private Voting
差分隐私通过向输出注入随机噪声来保护个人数据隐私，但在选举等场景中，噪声可能导致错误结果，尤其是当胜负差距很小时。本文系统研究了在中央差分隐私和本地差分隐私模型下，多种常见投票规则（包括 Plurality、Condorcet、Maximi
Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
本文提出一种求解最短向量问题（SVP）的随机化算法。SVP 是格密码学中的核心困难问题，其求解复杂度直接关系到基于格的密码方案（如 NTRU、LWE）的安全性评估。此前由 Aggarwal、Dadush、Regev 和 Stephens-D
Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
本文研究纯ε差分隐私（DP）下连续计数问题中任意实数矩阵分解的成本。设T_n为下三角前缀和矩阵，Laplace矩阵机制的因子化成本c_frob和c_two分别控制每坐标平方误差的均值和最大值。作者证明了对于任意符号、稀疏性和平方性限制，以及
Bitcoin Mempool Linearization
论文研究比特币矿工交易内存池（mempool）中的线性化问题。在比特币系统中，交易持续到达矿工的内存池，等待被包含在后续区块中。每笔非coinbase交易必须花费由先前交易创建的未花费输出，这导致了内存池中交易之间的依赖约束。同时，矿工在经
Edit-Neighboring Data Streams and Privacy under Continual Observation
本文研究持续观察（Continual Observation, CO）模型下的差分隐私（Differential Privacy, DP）问题。在CO模型中，敏感数据流随时间不断产生，算法实时发布输出，隐私损失随输出序列累积。传统CO隐私定
Pure-DP Statistical Query Release at the Conjectured Square-Root Rate
本文研究了纯差分隐私下统计查询释放的问题。Nikolov 和 Ullman 曾提出一个猜想：对于大小为 T 的域上的 k 个统计查询，是否存在一种纯差分隐私机制，其最坏坐标误差能够达到已知下界所暗示的平方根速率。本文证明了该猜想的上界成立。
Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
本文研究在边级别差分隐私保护下发布合成图的问题，要求该合成图能近似原始输入图中所有切割的大小。作者提出一种多项式时间的 (ε,δ)-差分隐私算法，对于任意 n 顶点无权重图 G，输出一个非负权重合成图 Ĝ，使得对于任意切割 S，其权重误差以
Fast and Private Max-Sum Diversification
该论文首次在差分隐私框架下研究结果多样化问题，聚焦于最大和多样化（MSD）模型。MSD旨在选择一组项目，最大化一个线性组合：子模函数（衡量相关性）与所选项目间成对距离之和（衡量多样性）。现有非私有方法在处理敏感数据时存在隐私泄露风险。作者提
Publicly-Verifiable Certificates for Statistical Algorithms
该论文旨在解决机器学习模型输出结果的可公开验证性问题。作者在Goldwasser等人提出的交互式学习证明框架基础上，首次研究了非交互式学习证明，并定义了一种新概念：公开可验证的统计有效性证书（Publicly-Verifiable Cert
Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
该论文提出了一种空间高效的量子算法，用于解决素数域上的椭圆曲线离散对数问题（ECDLP），这是密码学中的基础难题。Shor算法在理论上能高效求解ECDLP，但实际量子实现需要大量量子资源，尤其是逻辑量子比特数。当前最先进的实现需要超过100
Is Randomness Necessary for Adaptive Data Analysis?
该论文研究了自适应数据分析（Adaptive Data Analysis, ADA）中的基本问题：随机性是否必要？ADA 问题形式化了在数据集被重复使用时防止虚假发现和过拟合的挑战。输入是一个包含 n 个独立同分布样本的数据集，来自未知分布
Lower Bounds for PIR with Preprocessing from Blackbox Cryptography
本文针对单服务器私有信息检索（PIR）在预处理场景下的计算下界进行了研究。已有工作表明，单服务器PIR若实现亚线性通信，则每个查询需要线性数量的（公钥）服务器操作。近期的突破性工作通过利用预处理成功构造了查询计算亚线性的单服务器PIR，从而
Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection
论文《Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection》解决了分布式地理数据中范围计数查询的隐私
Calculating the floor of y**(1/m)
该论文针对自然整数 y>2 和 m>1，提出了两种基于牛顿-拉夫森方法的算法，用于计算 y^(1/m) 的向下取整（即整数部分）。该问题在数论中常用于判断一个整数是否为另一个整数的整数次幂。尽管传统上二分查找方法被认为更易实现，但作者提出的
The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
本文研究了差分隐私（Differential Privacy, DP）下的持续计数问题（Continual Counting）。问题设定是：给定一个长度为 n 的二进制流，每个 1 代表一个个体的贡献，目标是在保护每个个体隐私的前提下，发布