ECDH-PSI 协议#

算法流程#

算法分为2阶段，第一阶段为握手过程，第二阶段为算法主体，其流程如下：

握手过程#

握手所用的 HandshakeRequest 定义如下：

interconnection/algos/psi.proto#

message HandshakeRequest {

  // The version of psi handshake message. Start from 1.
  //
  // 握手请求版本号
  int32 version = 1;

  // Supported algorithms （支持的 PSI 算法）: ecdh, pcg*, bark-oprf*
  repeated string supported_algos = 2;

  // Corresponding psi algo parameters proposals.
  //
  // 相应的 PSI 算法详细握手参数，与 supported_algos 一一对应
  repeated google.protobuf.Any algo_params = 3;

  // How many items do I've.
  //
  // 待求交的 PSI 数据总量
  int64 item_num = 4;

  // Usually we need to make partitions for large-scale PSI. This field defines
  // the number of bucket we've proposed. Note the larger one will be chosen as
  // the final bucket number.
  //
  // 大规模数据（比如十亿）求交需要决定的分桶数，任何一方都可以给出分桶数，最后以大的一方为主。
  // 未使用
  int64 bucket_num = 5;

  // Which rank can receive the psi results.
  //
  // 确定 PSI 结果获取方。
  //
  // NOTES:
  //   `-1`: all parties (所有机构都可以拿到交集结果)
  //   `>= 0`: corresponding rank can get the results (指定机构拿到交集结果)
  int32 result_to_rank = 7;
}

HandshakeRequest 主要包括以下信息：

协议版本号
想使用的具体 PSI 算法，比如使用 ECDH-PSI
每类 PSI 算法的详细参数，比如 ECDH-PSI 需要说明具体的椭圆曲线类型，HASH 算法相关参数等
结果可见性说明：结果是A，B都可见，还是只对某一方可见

如果算法是 Ecdh-psi，则 HandshakeRequest 中的 algo_params 字段格式如下：

interconnection/algos/psi.proto#

// ECDH PSI algorithm parameters proposal.
//
// ECDH PSI 算法参数握手请求
message EcdhPsiParamsProposal {
  // supported versions，支持的算法版本列表
  // 当前必须为 1
  repeated int32 supported_versions = 1;

  // Supported curve types（ EC 曲线 ）:
  //
  //   - curve25519;
  //   - sm2;
  repeated string curves = 2;

  // Supported hash methods( 支持的哈希算法 ):
  // 与 curves 字段长度相同，元素一一对应
  //
  //   - sha256;
  //   - sm3;
  repeated string hash_methods = 3;

  // Nonce for hashing.
  //
  // 哈希的额外随机数
  string nonce = 4;
}

握手请求的结果 HandshakeResponse 定义如下：

interconnection/algos/psi.proto#

// The handshake response from peer.
//
// 对手的握手决策响应
message HandshakeResponse {
  // response header
  ResponseHeader header = 1;

  // The final algo determined.
  //
  // 决策下来的 PSI 算法
  string algo = 2;

  // The number of items for each party.
  //
  // 每一方的待求交总数
  int64 item_count = 3;

  // The number of bucket.
  //
  // 实际使用的分桶数
  // 未使用
  int64 bucket_num = 4;

  // The final algorithm parameters.
  //
  // 决策出来的算法参数
  google.protobuf.Any algo_params = 6;
}

其中 ResponseHeader 定义如下：

interconnection/common/header.proto#

syntax = "proto3";

package org.interconnection;

// 31100xxx is the white box interconnection code segment
// 31100xxx 为引擎白盒互联互通号段
enum ErrorCode {
  OK = 0;

  GENERIC_ERROR = 31100000;
  UNEXPECTED_ERROR = 31100001;
  NETWORK_ERROR = 31100002;

  INVALID_REQUEST = 31100100;
  INVALID_RESOURCE = 31100101;

  HANDSHAKE_REFUSED = 31100200;
  UNSUPPORTED_VERSION = 31100201;
  UNSUPPORTED_ALGO = 31100202;
  UNSUPPORTED_PARAMS = 31100203;
}

message ResponseHeader {
  int32 error_code = 1;
  string error_msg = 2;
}

algo_params 定义如下：

interconnection/algos/psi.proto#

// ECDH PSI parameters that parties has agreed.
//
// ECDH PSI 算法结果参数
message EcdhPsiParamsResult {
  // The psi version actual used.
  string version = 1;

  // The curve type actual used.
  string curve = 2;

  // The chosen hash method.
  string hash_method = 3;

  // The chosen salt used in hash method, i.e. hash(content || nonce).
  string nonce = 4;
}

Protobuf 传输方式#

Protobuf 传输使用《传输层白盒互联互通协议》中的 P2P 传输协议进行传输。其中传输的 key 按照《传输层白盒互联互通协议》中定义的方法生成，value 即为 protobuf 序列化之后的二进制字符串。

算法主体#

算法第二步、第四步使用 EcdhPsiCipherBatch 格式进行传输，EcdhPsiCipherBatch 定义如下：

interconnection/algos/psi.proto#

// The universal ciphertext for each batch.
//
// ECDH PSI 密文传输
message EcdhPsiCipherBatch {

  // The type hint for each message. (密文类型)
  //
  // "enc": the first stage ciphertext
  //
  // "dual.enc": the second stage ciphertext
  //
  // ECDH PSI 密文阶段类型，主要用来区分一阶段和二阶段的密文.
  string type = 1;

  // The bucket index. Start from 0.
  //
  // Bucket 索引
  // 未使用
  int32 bucket_index = 2;

  // The batch index. Start from 0.
  //
  // Batch 索引，从 0 开始
  int32 batch_index = 3;

  // Is last batch flag
  bool is_last_batch = 4;

  // Count of items in this batch.
  // count == 0 is allowed for last batch
  int32 count = 6;

  // The packed all in one ciphertext for this batch.
  //
  // The first stage ciphertext takes 256 bits for each ciphertext element.
  // However, the second stage ciphertext takes 96 bits each. According to PSI
  // papers, we do not need to send all 256 bit for the final ciphertext. The
  // number of bits needed to compare is `Log(MN) + 40` given a 40 bits
  // statistical security parameter. TODO (add paper link here).
  //
  // We define each bucket has less than 2^28 items, i.e. about 270 million
  // (单桶最多 2.7亿) items, which is general enough for various psi algorithms.
  //
  // NOTE: we do not use `repeated`` here to save overhead of metadata.
  bytes ciphertext = 7;
}

其中 ciphertext 字段用于存放 ECC 上的点，存放方式为所有点依次连续存放，curve25519 每个点长度为 32 Bytes，SM2/secp256k1 使用点压缩编码存放，每个点长度33byte，参见 SEC1。