本文首次研究了差分隐私下的范围子图计数问题（DPRSC）。子图计数是图分析中的基本问题，传统方法通常计算整个图中特定模式的出现次数。然而，实际应用常需对由多维属性范围选中的顶点诱导子图进行查询，同时保护隐私。差分隐私子图计数面临重大挑战：子图计数是非线性函数且敏感度高，单个边的修改可能影响大量子图出现次数。为此，本文提出了一种高效算法，通过引入子图投影，将DPRSC转化为加权正交范围计数问题。利用范围树和局部敏感度估计，实现了低加性误差的私有查询响应。此外，还通过将重构攻击归约为DPRSC并利用离散理论，证明了任何差分隐私算法都必须承受随维度指数增长的加性误差。实验表明，所提算法在准确性和运行时间上显著优于基线方法，同时保持强隐私保证。该研究为图数据分析中的隐私保护提供了新工具，尤其适用于社交网络、生物信息学等需敏感数据查询的场景。

本文研究了一种针对加密数据库的数据库重建攻击，攻击者仅需获取少量多维范围查询的访问模式（即查询结果的行数或是否存在），即可重建整个数据库的内容。现有工作大多假设攻击者能观察到大量查询或细粒度的泄露，而本文证明即使在极有限的泄露下（如仅知道查询返回的行数），也能实现精确重建。核心方法包括：（1）形式化地定义查询泄露与数据库结构之间的关系；（2）提出一种基于整数线性规划的重建算法，利用少量查询的约束条件来推断每条记录是否属于某个查询结果；（3）通过理论分析证明，对于任意数据库，只需约 O(d * log n) 个随机范围查询（d为维度，n为记录数），就能以高概率唯一确定数据库。实验在合成数据和真实数据集上验证了方法的有效性，仅需数百个查询即可重建具有数千条记录的多维数据库。该工作揭示了一种新型的侧信道威胁，对加密数据库系统的安全性提出了新的挑战。