PSI based on ECDH

1.1. Requirements Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

1.2. Data Structures and Notations

In this document, data structures are defined and encoded according to the conventions laid out in Section 3 of [RFC8446].¶

2.1. Elliptic Curves

An elliptic curve E is defined by a two-variable equation over a finite field F with prime characteristic p larger than three. Except for a special point called point at infinity, a point on E is a (x,y)-coordinate pair that satisfies the curve equation, where x and y are elements of F. All distinct points of curve E consists an algebraic group of order n, where the point at infinity is the identity element. Applications and standards generally use a prime order (sub)group <G> generated by a point G on E. The order of <G> is denoted by r.¶

This document uses term "addition" to refer to the group operation of a elliptic curve group, meaning two points P and Q can be added together to get a third point R. Scalar multiplication refers to the operation of adding a point P with itself repeatedly. This document uses scalar_mul to denote the scalar multiplication process. It takes a integer x<r and a point P as inputs and outputs the multiplication result Q, which is written by Q=scalar_mul(P,x).¶

Many cryptographic applications require the participants to generate elliptic curve key pairs. Usually, a key pair on refers to a (PK,sk) tuple, where sk is a integer generated uniformly between 1 and r-1, and PK=scalar_mul(G,sk). In the context of ECDH-PSI, only sk, namely the private key, is used. Thus, this document uses the notation sk=keygen() to refer to the process of generating a private key on the elliptic curve and omits PK.¶

2.2. Hashing to Elliptic Curves

A hash_to_curve function encodes data of arbitrary length to a point on a elliptic curve. The encoding process first hashes the byte string to one or more elements of fixed length, and then calculates a point on the curve with the elements using so-called map_to_curve and clear_cofactor functions.¶

[RFC9380] describes a series of hash_to_curve methods (which are also called "suites") for standard curves such as NIST P-256 and curve25519. It specifies two encoding types denoted by "encode_to_curve" and "hash_to_curve". Both encodings can be proven indifferentiable from random oracles (ROs)[MRH04], but have different output distributions. This document only uses "hash_to_curve" encodings which output uniformly random points. It also uses the notation P=hash_to_curve(data) to refer to the process of encoding data of arbitrary length to a point P on the curve given in the context.¶

[RFC9380] requires all uses of the hash_to_curve suites must enforce domain separation with domain separation tags (DSTs). In particular, DSTs are distinct strings that enable different applications to simulate distinct RO instances with the same hash function. That is, each application concatenates the DST with its message as the input to hash function. This document allocates each suit with a unique DST. For simplicity, DST strings are omitted when writing the process of calculating the hash value of a string. The notation tag=hash(str) means that the hash function actually takes "dst||str" as its input rather than str alone, where dst is the DST string defined for the corresponding hash_to_curve suite. Similarly, this document also omits DST strings when describing hash_to_curve functions, assuming that the corresponding DST has been taken as a part of the input.¶

A suite defined by [RFC9380] includes a series of parameters such as the curve, hash function, and encoding type. In applications, these suites are very efficient to be referred to, as the included parameters can also be used beyond the scenario of mapping data to curves. For example, the participants can negotiate a hash_to_curve suite, and then use the curve deduced from the suite for other cryptographic functions such as encryption and key establishment.¶

To extend the usage of hash_to_curve suites, [RFC9380] also describes methods and naming conventions for defining new suites, which enables developers to define suites with new curves and hash functions.¶

3.1. Overview

The specification of ECDH-PSI consists of two phases as shown in Figure 2, including a handshake phase which negotiates the protocol parameters and a data exchange phase that performs the operations described by Figure 1.¶

• In the handshake phase, a participant, which is denoted by requester, sends a HandshakeRequest message to initiate the ECDH-PSI protocol flow. This message carries lists of parameters supported by the requester and information about the requester's data. Then, the other participant, denoted by responder, selects parameters from the requester's lists, and sends the parameters with its data information in a HandshakeResponse message.¶
• Next, in the data exchange phase, both parties perform ECDH-PSI operations with parameters selected in the handshake phase, where EcdhPsiBatch messages are exchanged. The receiver of an EcdhPsiBatch replies with a EcdhPsiBatchResponse message, which tells sender the handling status of last EcdhPsiBatch message.¶

This specification enables masked data to be transferred by many batches, as the entire data set may be extremely large and requires numerous resources to be handled with properly. For example, the size of a data set may exceed the limit of a single package of the underlying network protocol. The participants can divide the data set to multiple batches and use multiple EcdhPsiBatch messages to send them so as to meet the limits of network, storage or computation resources.¶

Besides hash_to_curve suites and data formats, the handshake phase also determines the interaction pattern for data exchange phase. The pattern is decided by the following options:¶

• The participant that outputs the result. If only one participant (for example, A) has the privilege of obtaining the result, then, in the second round, EcdhPsiBatch messages will be only sent from B to A.¶
• The maximum size of a single EcdhPsiBatch message. Upon the determination of maximum batch size, the participants can deduce the number of batch messages sent or received in each round by dividing the size of entire data set with the maximum size.¶
• The order of sending EcdhPsiBatch messages. When both participants need to send batch messages in the same round, the requester will always send the first one. Then, they can send EcdhPsiBatch messages in turn, or let the requester send all batches in sequence before the responder sending its data.¶

                  A                                     B
-----------------------------------------------------------------------
                  |                                     |
Handshake Phase:  |                                     |
                  |----------HandshakeRequest---------->|
                  |<---------HandshakeResponse----------|
                  |                                     |
Data Exchange     |
Phase:            |                                     |
                  |                                     |
                  |-------------EcdhPsiBatch----------->|
                  |<--------EcdhPsiBatchResponse--------|
                  |                   .                 |
                  |                   .                 |
                  |                   .                 |
                  |-------------EcdhPsiBatch----------->|
                  |<--------EcdhPsiBatchResponse--------|
                  |                   .                 |
                  |                   .                 |
                  |                   .                 |

3.2. Handshake

The handshake phase includes a HandshakeRequest and a HandshakeResponse message. The structures of these messages are documented as follows.¶

  struct {
    uint8 version = 1;
    ProtocolProposal protocol_param;
    DataProposal data_param;
  } HandshakeRequest;

enum {
  null (0),
  P256_XMD:SHA-256_SSWU_NU_ (1),
  P384_XMD:SHA-384_SSWU_NU_ (2),
  P521_XMD:SHA-512_SSWU_NU_ (3),
  curve25519_XMD:SHA-512_ELL2_NU_ (4),
  (255)
} HashToCurveSuite

enum { compressed (0), uncompressed  (1), (255) } PointOctetFormat

enum {
  no_truncation (0),
  128_bit_truncation (1),
  (255)
  } TruncationOption

struct {
  HashToCurveSuite    suites<1..255>;
  PointOctetFormat    point_octet_formats<1..255>;
  TruncationOption    truncation_options<1..255>;
} ProtocolProposal

truncated_mask_data = kdf(mask_data, nil, "ECDH-PSI", 128)

enum { continuous (0), interactive (1), (255) } BatchMode

enum { both (0), requester (1), responder (2), (255) } OutputMode

struct{
  BatchMode  supported_batch_modes<1..255>;
  OutputMode supported_output_modes<1..255>;
  uint64     max_batch_size;
  uint64     item_num;
} DataProposal

enum {
  success(0),
  generic_error         (0x01),
  unsupported_version   (0x02)
  invalid_request       (0x03),
  out_of_resource       (0x04),
  unsupported_parameter (0x05),
  (0xFF)
} HandshakeStatus

struct {
  HandshakeStatus status;
  ProtocolResult protocol_param;
  DataResult data_param;
} HandshakeResponse;

struct {
  HashToCurveSuite    suite;
  PointOctetFormat    point_octet_format;
  TruncationOption    truncation_option;
} ProtocolResult;

struct  {
  BatchMode   batch_mode;
  OutputMode  output_mode;
  uint64      max_batch_size;
  uint64      item_num;
} DataInfoResult;

3.3. Data Exchange

The data exchange phase consists of two rounds. In each round, a participant may send or receive multiple EcdhPsiBatch messages. Upon receiving a EcdhPsiBatch and handling the data properly, the participant SHOULD respond with a EcdhPsiBatchResponse message, indicating its partner that it is ready to receive the next EcdhPsiBatch message.¶

enum { transmit(0), retransmit(1), fatal_error(2), (255)} BatchStatus

struct {
  uint64 index;
  opaque octet;
} ECPointOctet;

struct {
  BatchStatus   status;
  uint32        batch_type;
  uint64        batch_index;
  uint64        batch_count;
  uint32        is_last_batch;
  ECPointOctet  data<1..2^64-1>;
} EcdhPsiBatch;

enum {
  success (0),
  retransmit (1),
  fatal_error (2),
  (255)
} BatchResponseStatus;

struct {
  BatchResponseStatus status;
  uint64 batch_index;
} EcdhPsiBatchResponse;

4.1. The Representation of EC Point

When deciding the point encoding format for the elliptic curves expect curve25519, the participants should consider the aspects of bandwidth, storage and computation comprehensively. Compressed point format could decrease the costs of transmission and storage, but it also needs more computation resources to "decompress" the point. The "decompress" process may be as costly as scalar multiplication [CZZDL24]. Uncompressed format requires more storage spaces and needs more time to transmit, but the participant can perform scalar multiplications without extra effort to recover the points.¶

For example, when both parties are deployed in the same data center and linked with a high-bandwidth local area network (LAN), they can choose to use the uncompressed format to achieve better performance.¶

As another example, the parties may be deployed in geographically separated data centers connected with low bandwidth wide area network (WAN), and equipped with high-end computation acceleration devices such as Graphics Processing Units (GPUs). In this case, the computation resource may not be the bottleneck, and the participants can choose the compress format to minimize the costs of data transmission.¶

4.2. The Management of Index

A RECOMMENDED method of maintaining indexes is storing the records with a database table and use the row numbers or prime keys as indexes. The intersection result can be matched with original data items by a simple join operation. The participant could also design a different indexing mechanism on its own, as long as guaranteeing its uniqueness.¶

This document uses explicit indexes to identify data items rather than treats the order of records as "implicit" indexes. Compare with the implicit counterpart, explicit indexes can be efficiently created and maintained by modern databases, and do not require the participants to implement extra logic to preserve the order of records.¶

When masking the EC points from its partner, a participant MUST send the doubly-masked data with correct indexes. To achieve this, it keeps the indexes of each data items received in the first round, masks the records with its private key, and associates the masked records with the same indexes. These operations can also be implemented easily with database operations by viewing the received records and masked records as columns in the same table, which enables them to be linked naturally via the primary key.¶

4.3. Support More hash_to_curve Suites

Participants can negotiate hash_to_curve suites besides the ones listed by Section 3.2.1.1. They can use other suites defined by [RFC9380], or use a self-defined suite following the syntax and convention given by Section 8.9 and 8.10 of [RFC9380].¶

As an example, this document next defines a hash_to_curve suite for the ShangMi(SM) curve and cryptography algorithms. The SM algorithms are becoming mandatory in China, and have been accepted by international standards such as [ISO-SM2], [ISO-SM3] and [RFC8998].¶

The new suite, denoted by curveSM2_XMD:SM3_SSWU_RO, encodes data to points on the so-called curveSM2[GBT.32918.5-2017] with SM3 hash algorithm[GBT.32905-2016], and reuses the expand_message_xmd and Simplified Shallue-van de Woestijne-Ulas (SSWU) methods for message expansion and mapping.¶

In particular, curveSM2_XMD:SM3_SSWU_RO_ is defined as follows:¶

• encoding type: hash_to_curve¶

• E: y^2 = x^3 + A * x + B, where¶

  • A = -3¶
  • B = 0x28e9fa9e9d9f5e344d5a9e4bcf6509a7f39789f515ab8f92ddbcbd414d940e93¶
• p: 2^256-2^224-2^96+2^64-1¶
• m: 1¶
• k: 128¶
• expand_message: expand_message_xmd (Section 5.3.1 of [RFC9380])¶
• H: SM3¶
• L: 48¶
• f: SSWU method (Section 6.6.2 of of [RFC9380])¶
• Z: -9¶
• h_eff: 1¶

The value Z is calculated by the sage script given by Appendix H.2 of [RFC9380] with the p, A and B parameters of curveSM2.¶

The participants SHOULD agree on the meaning of HashToCurveSuite values. In this document, suite curveSM2_XMD:SM3_SSWU_RO_ is identified as follows:¶

enum {
  null                              (0),
  ... // (1) to (4) follow section 3.2.1.1
  curveSM2_XMD:SM3_SSWU_RO_         (5),
  ... // other hash_to_curve suites
  (255)
} HashToCurveSuite;

5.1. Data Truncation

This section provides a detailed discussion on the truncation mechanism presented in this document.¶

The truncation, undoubtedly, will raise the probability of message collision. That is, two different data item may be mapped to the same string after the procedures of masking and truncation by coincidence. The collision may happen across the datasets owned by different participants, which causes a false-positive case that two different records are matched by PSI, or happen in the same dataset. The later situation may also lead to a false-positive case. To be more specific, consider a participant A has two different data items data_X and data_Y which are mapped to the same record mask_data_XY. Its partner, say B, also has record data_X which is mapped to mask_data_XY. Finally, A outputs both data_X and data_Y as the result of PSI, as it cannot distinguish which one matches the record of mask_data_XY.¶

To avoid such false-positive case, we have to consider the collision probability with respect to the sum number of data items owned by A and B. Such probability can be computed with the well-known birthday paradox bound. Let n be the number of sampling and d be the output space, the probability of collision can be approximately computed with:¶

p(n,d)=1-e^(-n(n-1)/2d)

This document uses a truncated length of 128 bit, which means d=2^128. For different n, which is the sum size of records, the probability are calculated as follows:¶

• If n=2^50, p(2^50, 2^128) = 2^-29¶

• If n=2^45, p(2^45, 2^128) = 2^-33¶

• If n=2^41, p(2^41, 2^128) = 2^-47¶

• If n=2^40, p(2^40, 2^128) = 2^-49¶

• If n=2^39, p(2^39, 2^128) = 2^-51¶

That is, if the number of records is less than 2^40, the probability of false-positive will be smaller than 2^-48. The participant can also decide the truncation option by calculating the collision probability, and only use truncation when they both agree that the probability is acceptable.¶