在 SPU 中调研并实现 FK-PK Join

[Candicepan]

此 ISSUE 为 隐语开源共建计划（SecretFlow Open Source Contribution Plan，简称 SF OSCP）Phase 5 任务 ISSUE，欢迎社区开发者参与共建～

• 认领前，辛苦确认是否完成报名～
• 更多任务，可查看 「OSCP Phase5 Season of Dev」Project

This ISSUE is one of the tasks of the SecretFlow Open Source Contribution Plan (referred to as SF OSCP) Phase 5. Welcome to join us in building it together!

• Before claiming a task, please make sure you have signed up.
• For more tasks, you can check the "OSCP Phase4 Season of Dev" Project.

任务介绍

基于SPU，实现FK-PK join功能：即类比数据库系统中，key join后会把两张数据表拼接到一起（key一致的两个行拼到一起）；在这个情况下，假设其中一个join key is unique。

• 任务名称：在 SPU 中调研并实现 FK-PK Join
• 技术方向：SPU
• 任务难度：挑战🌟🌟🌟
• 任务预估完成时间：7周+
• 任务 Reviewer：deadlywing

详细要求

• 安全性：原则上需要确保无信息泄漏，若有特殊方案需要着重分析与说明安全性
• 功能性：
  • 必须支持secret key join secret key的general case；
  • 必须支持inner join
  • 必须支持SEMI2K协议（其他协议可选择性支持）
  • 通信轮数的复杂度不超过$ \log(n) $（或其多项式）；
  • 若实现以下功能任一，可有Extra Bonus**：**
    • 实现其他所有的连接方式：左连接，右连接，全连接，半连接🌟**；**
    • 支持key，payloads的任意Visibility组合，且优化至理论性能最佳🌟🌟**；**
• 正确性：需完整的单测和benchmark性能分析
• 代码规范：C++代码需进行格式化（流水线包含代码规范检查卡点），参考https://github.com/secretflow/spu/blob/main/CONTRIBUTING.md
• 提交说明：关联该 issue 并提交代码至
  • https://github.com/secretflow/spu/tree/main/experimental/joins（若路径不存在则自行创建）
• 特殊说明：
  • 本任务难度较高，需要开发者自行调研方案，在开发之前请务必与maintainer确认方案的可行性；得到认可后再开始代码开发
  • 为了高效沟通，请自备文档，必须包括的内容有：
    1. 参考文献（若有特殊building block，请一并附上）
    2. 方案详细说明
    3. 必要的分析：
       1. 是否需要引入新的MPC原语（衡量短期内方案可行性）
       2. 安全性分析（必须非常明确，理论上SPU只接受不泄漏任何信息的方案，如有特殊的算子安全性不明确，必须有顶会paper背书）
       3. 正确性分析（是否概率性成功）
       4. 理论性能分析（非常重要！！不可缺少！！请结合SEMI2K协议，同时给出通信量和轮数的精确计算，注意不能只是模糊的复杂度量级）

能力要求

• 熟悉C++，bazel等编程语言与工具
• 熟悉SPU的代码架构
• 熟悉SEMI2K协议，非常清楚MPC层算子的开销
• 具有有一定科研能力，能自主调研和设计方案

操作说明

• 贡献指引文档：https://github.com/secretflow/spu/blob/main/CONTRIBUTING.md