单次连接交叉标签算法

多查询无额外泄漏

与JXT不同，该算法在多次查询中不泄漏额外结果，支持等值连接并消除线性搜索复杂度。

Qiaoer, Xu · 王剑锋 · Sun, Shifeng · Zhipeng, Liu · 陈晓峰

IEEE Transactions on Knowledge and Data Engineering 2025

参数信息

搜索延迟加速比

98.5 ×

搜索延迟加速比

1000000 ×

存储成本降低

62.5 %

存储成本降低

78.5 %

查询延迟

21 ms

技术优势

不泄漏额外结果

通过非线性变换的编码方法，每次查询只揭示结果的并集，避免了 JXT 随着查询增多而逐渐累积泄漏。

支持等值连接

扩展了 JXT 仅支持自然连接的限制，使方案适用于一般等值连接查询。

消除线性搜索

通过新的标签设计，避免了 Shafieinejad 等人方案中的线性搜索复杂度，查询更高效。

应用场景

• 加密数据库：让云上加密数据库支持安全高效的等值连接查询，减少结果泄漏。
• 安全多方计算：可作为 SMPC 中的连接算子，在多方联合查询时减少中间结果泄漏。
• 隐私保护查询：实现加密数据上的隐私保护连接查询，替代会累积泄漏的传统标签方案。
• 数据安全：通过一次性交叉标签设计，从机制上杜绝多次查询导致的额外数据泄漏。