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].¶

The following notations are used throughout this document:¶

• sqrt(x): The square root of x.¶
• log(x,y): The logarithm of y to the base x.¶
• x^-1: The inverse of x (over a finite field).¶
• x||y: Concatenate string x and y.¶
• intersection(set_1,set_2): The intersection of set_1 and set_2¶
• |set|: The cardinality of set.¶

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 constitute 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 an 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 an integer x<r and a point P as inputs and outputs the multiplication result Q, which is written by Q=scalar_mul(P,x) or simply Q=P^x. When set_p is a set of EC points, set_m=set_p^x denotes that all elements of set_p are multiplied by x to obtain set_m.¶

Many cryptographic applications require the participants to generate elliptic curve key pairs. Usually, a key pair refers to a (PK,sk) tuple, where sk is an 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 [RFC9380] encodes data of arbitrary length to a point on an elliptic curve. The encoding process first hashes the byte string to 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 set_p=hash_to_curve(set_d) to refer to the process of encoding every elements in set_d to points on a curve and obtains set_p.¶

[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. To meet the requirement of DSTs, this document allocates each suite with a unique DST, and uses the notation of set_p=hash_to_curve(set_d) assuming that the corresponding DST strings have been taken as internal inputs.¶

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.¶

2.3. Transport Layer Security

The TLS protocol [RFC8446] has been widely used for secure communication over the Internet. It operates over any underlying communication channel that provides reliable, in-order data stream, ensuring important security properties of authentication, confidentiality and integrity. In particular, TLS provides mutual authentication methods so that the peers can authenticate each other. It also uses DH key exchange to establish session keys and employs authenticated encryption to guarantee that the transferred messages are encrypted and not manipulated.¶

The notion of "channel binding" is originally proposed by [RFC5056], which enables applications to bind authentication to secure sessions at lower layers in the network stack so as to prevent the so-called Man-In-The-Middle (MITM) attack. To extend the notion to TLS, [RFC9266] presents a method of binding applications to the underlying TLS 1.3 sessions, which is denoted by 'tls-exporter'. It outputs exported keying material (EKM) established by the TLS session, which can be seen as the output of a pseudorandom function (PRF) based on TLS. The application can bind to the TLS session by taking EKM as an input to the application-layer cryptographic session.¶

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. 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 carrying masked EC points are exchanged.¶

In the second round, the EcdhPsiBatch message sent from the requester is optional since the requester may not allow the responder to output the intersection, which is determined in the handshake phase.¶

             A(requester)                          B(responder)
-----------------------------------------------------------------------
                  |                                     |
Handshake Phase:  |                                     |
                  |----------HandshakeRequest---------->|
                  |<---------HandshakeResponse----------|
                  |                                     |
Data Exchange     |
Phase:            |                                     |
                  |                                     |
                  |-------------EcdhPsiBatch----------->|
                  |<------------EcdhPsiBatch------------|
                  |                                     |
                  |--------EcdhPsiBatch(optional)------>|
                  |<------------EcdhPsiBatch------------|
                  |                                     |

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;
    uint8 output_mode;
    uint64 record_num;
    ProtocolProposal protocol_param;
  } HandshakeRequest;

enum {
  null (0),
  P256_XMD_SHA256_SSWU_NU_ (1),
  P384_XMD_SHA384_SSWU_NU_ (2),
  P521_XMD_SHA512_SSWU_NU_ (3),
  curve25519_XMD_SHA512_ELL2_NU_ (4),
  (255)
} HashToCurveSuite;

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

enum {
  no_truncation (0),
  128_bit_truncation (1),
  192_bit_truncation (2),
  (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", truncation_len)

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

struct {
  HandshakeStatus status;
  uint64 record_num;
  ProtocolResult protocol_param;
} HandshakeResponse;

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

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;

3.3. Data Exchange

In the data exchange phase, masked EC points are exchanged as EcdhPsiBatch messages. The participants MUST generate fresh ECDH-PSI keys after the handshake phase, and use the newly generated keys to mask the EC points. The ECDH-PSI keys SHOULD be removed immediately after the data exchange phase in order to prevent leakage or being reused by other applications by coincidence.¶

This phase consists of two rounds. In the first round, both participants send EcdhPsiBatch messages carrying locally masked EC points, where the requester sends the first one. In the second round, EcdhPsiBatch messages carrying jointly masked EC points are sent. If the requester sets output_mode field by 1, then only the responder sends an EcdhPsiBatch message, otherwise both participant sends EcdhPsiBatch messages as in the first round.¶

If the participants have negotiated a truncation_option of 128 or 192 bit in the handshake phase, such option MUST NOT be used in the first round, since truncated strings cannot be recovered to EC points, which makes the second mask operation completely infeasible.¶

struct {
  uint64 index;
  opaque encoded_point[encoded_point_length];
} ECPointOctet;

struct {
  uint32        batch_type;
  uint64        batch_count;
  ECPointOctet  encoded_points<1..2^64-1>;
} EcdhPsiBatch;

4.1. The Representation of EC Point

When deciding the point encoding format for the elliptic curves except for 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 computation resources to "decompress" the point. 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 compressed format to minimize the cost of data transmission.¶

4.2. The Management of Index

A RECOMMENDED method of maintaining indexes is storing the records with a database table and using 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 the index can be used to identify a record uniquely.¶

This document uses explicit indexes to identify data items rather than treating the order of records as "implicit" indexes. Compared 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.¶

After masking the EC points from its partner, a participant MUST send the jointly 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 prime keys.¶

4.3. Large Record Size

The EcdhPsiBatch message can be very large. For example, if the dataset contains 2^30 records, the size of encoded EC points included in a single EcdhPsiBatch message can be over 60 GB. Participants of ECDH-PSI SHOULD take great care when implementing the underlying communication channel, and guarantee that there are enough buffer or storage space for sending or receiving such messages.¶

The methods of sending and handling large messages are beyond the scope of this document.¶

5.1. Threat Model

Traditionally, ECDH-PSI protocols are considered secure under the so-called semi-honest setting, where both participants will follow the protocol specification, but try to guess each others' private inputs by observing the received messages.¶

This document considers an extended setting of malicious attackers. In such setting, ECDH-PSI cannot guarantee that the participants always output correct results, as a malicious participant can send arbitrary messages that produce wrong results. However, it is excepted that ECDH-PSI can somehow preserve the main security goal of data privacy even under such a setting.¶

In particular, the threat model considers external attackers who have the privilege to access the communication channel between the participants, and internal attackers who act a participant of the protocol.¶

In this document, most external attackers are excluded by TLS protocol [RFC8446] with mutual authentication, where the participants are authentcated mutually, and the messages are encrypted and authenticated. With the protection of TLS, the external attacker will not be able to inject, replay, truncate or manipulate messages transferred by the channel. Any malicious behavior will be detected immediately by TLS, and the relevant data will be discarded without passing to the application layer. However, TLS alone cannot prevent the Man-In-The-Middle (MITM) attack performed by a malicious node who concurrently runs two sessions and forwards messages from one session to another, which is discussed by Section 5.4.¶

Malicious internal attackers may send arbitrary messages during the protocol execution. That is to say, it may sends:¶

• Malformed handshake messages.¶
• Malformed masked points.¶
• Malformed jointly masked points.¶

In fact, malformed handshake message or jointly masked points may eliminate the protocol execution due to incorrect message syntaxes or mislead the victim to output wrong result, which will not harm the major security goal of data privacy. However, the attacker can use malformed masked points to construct a static ECDH oracle, as the victim will always mask those points with its own private key and send the results back. That is to say, if P1 is a malformed masked EC point sent by the attacker and sk is the victim's secret key used in ECDH-PSI, the attacker will get P1^sk. Once the attacker obtains some advantages with the querying process and calculates sk, it can immediately calculate sk^-1 and use it to "de-mask" any data masked by the victim.¶

5.2. Static ECDH Oracle

In this section, we analysis the risk of static ECDH oracle as described by Section 5.1, where each ECDH-PSI session can be utilized as an oracle for the ECDH-PSI key used in the current session. The attacker can declare that the size of its dataset is very large, and query the oracle as many times as it could. However, once the session ends, the victim will delete the ECDH-PSI key and use a freshly generated key for new sessions, which means that the attacker will query different oracle instances in different sessions.¶

In general, let v be the maximum time of querying an oracle instance, the static ECDH oracle may decrease the security level of elliptic curve by about log(2,v)/2 bits. The problem of static ECDH oracle has been studied extensively in a series of literatures including [BG04][Gra10][MU10][JV13].¶

For the curves employed by this document, the most efficient attack strategy is still the one described by [BG04]. In particular, let u and v be a pair of integers satisfying u*v=r-1, the [BG04] attack requires the attacker to query the oracle v times and uses¶

2(sqrt(u)+sqrt(v))=2(sqrt((r-1)/v)+sqrt(v))

scalar multiplications to calculate the secret key. Take the relationship that the security level of an elliptic curve group can be approximately seen as n=log(2,sqrt(r)), the number of scalar multiplications can be seen as 2(2^n/sqrt(v)+sqrt(v)). However, in ECDH-PSI, v is limited by the maximum number of elements holding by one of the participants, which is 2^64 since the parameter of batch_count is carried by an uint64. That is to say, for all the group parameters employed by this document, 2^n/sqrt(v) will be much larger than sqrt(v), and the attacker needs to perform 2^n/(sqrt(v)/2) multiplications, which approximately means the security level will be decreased by log(2,sqrt(v)/2)=log(2,v)/2-1 bits. For the maximum value of v, which is 2^64, the conclusion indicates that the security level will be decreased by 31 bits.¶

For the curves employed by this document, the decrease of 31 bits is acceptable, as the minimum security level is 128 bit, which will be decreased to 128 - 31 = 97 bits. Currently, there dose not exist any evidence that an elliptic curve with security level of 97 bits is vulnerable to practical attacks. Furthermore, this document does not use elliptic curves defined over extension fields which may be vulnerable to the more efficient attacks proposed by [Gra10] and [JV13].¶

[MU10] describes another attack by combing static ECDH oracles with the notorious small-group attack. To prevent such attacks, the receiver of a set of EC points MUST checks that every point is on the curve, as specified by Section 3.3.¶

5.3. Key Reuse

This section discusses the risks of reusing ECDH-PSI key across different sessions. In particular, reusing an ECDH-PSI key may decrease the security level of the elliptic curve based on the discussion presented by Section 5.2, or be utilized by a semi-honest attacker to reveal information related with different protocol runs.¶

As shown by Section 5.2, the key point of [BG04] attack strategy is the maximum query number for a single oracle instance. Reusing ECDH-PSI key will decrease the security level by much more than 31 bits as the allowed number of queries changes to the sum of queries allowed by all instances using the same key. In the worst case where the sum of queries is 2^(n/2), the security level will be decreased by almost a half.¶

If an ECDH-PSI key is reused across sessions, an attacker can participate these sessions as partners and obtain some extra information. For instance, the victim V may provide two different sets (denoted by set_0 and set_1) in two different sessions, where the elements are masked by the same secret key sk as set_0^sk and set_1^sk. Then, the attacker who joins both the sessions can calculate intersect(set_0^sk,set_1^sk) and learn the size of intersect(set_0,set_1). Despite that the attacker still cannot recover the original set set_0 or set_1, it indeed learns extra information beyond the original output of PSI even in the semi-honest setting.¶

5.4. Man-In-The-Middle Attack

MITM attack in ECDH-PSI refers to the case that the adversary acts as an agent who transmits messages between two honest participants. If the attacker transmits messages faithfully, it finally learns the cardinality of the intersection as it obtains the jointly masked datasets of both participants. However, as stated above, the attacker cannot break the privacy of original data items as it cannot obtain the ECDH-PSI keys with such attacks.¶

In this document, such attacks are avoided by the TLS binding mechanism [RFC9266]. In particular, the particpants use the "tls_exporter" channel binding type to export EKM strings from the TLS sessions, and concatenate the EKM string with the original data item as input to the hash_to_curve function as specified by Section 3.3.¶

If the malicious adversary M performs MITM attacks against participants A and B, it will establish two different TLS sessions denoted by s_a and s_b. Then, A will export EKM ekm_a from TLS session s_a, and B will export a different ekm_b from s_b, which means that the same data element data will be mapped to different points on the curve with P_A=hash_to_curve(ekm_a||data) and P_B=hash_to_curve(=ekm_b||data). The PSI protocol will finally fail since the same data item cannot be mapped to the same point on the curve, but the attacker also cannot learn the size of the intersection, which provides more privacy guarantee beyond the secrecy of original data items.¶

5.5. Replay Attack

In [CY20], Cui and Yu design a new attack for concurrent runs of ECDH-PSI sessions in the malicious setting. In this attack, the attacker establishes two sessions with the same victim who uses two different data sets set_1 and set_2 in different sessions, and finally learns the size of intersect(set_1,set_2).¶

Let sk_1 and sk_2 denote the ECDH-PSI keys that the victim uses in different sessions, the attacker M performs the attack to V as follows (also refer to Figure 3):¶

• Step 1: M initiates the first session with V, where V maps all elements of set_1 to points as set pset_1, masks them with sk_1, and sends mset_1=pset_1^sk_1.¶
• Step 2: M initiates another session with V, and obtains mset_2=pset_2^sk_2 as in Step 1.¶
• Step 3: The attacker chooses r_1 and r_2, and masks the sets received in Step 1 and 2 with rset_1=mset_1^r_1 and rset_2=mset_2^r2.¶
• Step 4: M "reflects" the set received in session 1 to V in session 2 by sending rset_1 to V in the second session. Then the victim masks rset_1 with its ECDH-PSI key for session 2 and sends dset_2=rset_1^sk_2 to the attacker.¶
• Step 5: As in Step 4, the attacker sends rset_2 to the victim in session 1, and receives dset_1=rset_2^sk_1.¶
• Step 6: Upon receiving dset_1 and dset_2, the attacker de-randomizes the sets with r_2^-1 and r_1^-1 respectively, and obtains:¶
• Step 7: M calculates the intersection of vset_1 and vset_2, which has the same cardinality with the intersection of set_1 and set_2.¶

vset_1=dset_1^(r_2^-1)=pset_1^sk_1^sk_2
vset_2=dset_2^(r_1^-1)=pset_2^sk_2^sk_1

                   V                                     M
      -----------------------------------------------------------------
                   |                                     |
s1:       pset_1=hash_to_curve(set_1)                    |
          mset_1=pset_1^sk_1                             |
                   |               mset_1                |
                   | ----------------------------------> |
                   |                                     |
s2:       pset_2=hash_to_curve(set_2)                    |
          mset_2=pset_2^sk_2                             |
                   |               mset_2                |
                   | ----------------------------------> |
                   |                                     |
                   |                             choose r_1 and r_2
                   |                             rset_1=mset_1^r_1
                   |                             rset_2=mset_2^r_2
                   |                                     |
s2:                |               rset_1                |
                   | <---------------------------------- |
          dset_2=rset_1^sk_2                             |
                   |               dset_2                |
                   | ----------------------------------> |
                   |                                     |
s1:                |               rset_2                |
                   | <---------------------------------- |
          dset_1=rset_2^sk_1                             |
                   |               dset_1                |
                   | ----------------------------------> |
                   |                                     |
                   |                           vset_1=dset_2^(r_1^-1)
                   |                           vset_2=dset_1^(r_2^-1)
                   |                                     |
                   |                    calculate |intersect(vset_1,vset_2)|
                   |                                     |

The replay attack can also be mitgated with TLS channel binding mechanism. In particular, if the participants adopt TLS channel binding as specified by Section 3.3, then, in steps 1 and 2 of the replay attack, the victim will extract different EKMs and use them to calculate pset_1 and pset_2 respectively. That is to say, even set_1 and set_2 contain some common elements, they will be mapped to different points in pset_1 and pset_2 as the EKMs are different, which finally fails the attacker in step 7 as overlapped elements are mapped to different points in vset_1 and vset_2.¶

5.6. Side Channel

In some circumstances, the order of elements and data indexes can be utilized by a semi-honest attacker as a side-channel which leaks information about the original dataset. When two participants A and B execute ECDH-PSI and output the intersection result, one party (say, B) also knows where these common elements appear in A's list and their indexes, such orders and indexes can be used to infer the orders of inserting those elements to a database table.¶

A generic method to avoid such side-channels is shuffling the order of elements, as well as the indexes, before they are sent to the partner. However, the shuffling operation may be costly or even practically infeasible when the size of dataset is very large. The participant SHOULD evaluate the risk of side-channels and use suitable mitigation mechanisms when the risk is unacceptable.¶

5.7. 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 two truncation sizes of 128 bit and 192 bit. For 128-bit truncation, the probabilities of different n and d=2^128 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¶

For 192-bit truncation, the probabilities are listed as follows:¶

• If n=2^50, p(2^50, 2^192) = 2^-93¶

• If n=2^45, p(2^45, 2^192) = 2^-103¶

• If n=2^41, p(2^41, 2^192) = 2^-111¶

• If n=2^40, p(2^40, 2^192) = 2^-113¶

• If n=2^39, p(2^39, 2^192) = 2^-115¶

That is, if the number of records is less than 2^40, the probability of false-positive will be smaller than 2^-48 for truncation length of 128 bit, and smaller than 2^-112 for 192 bit. 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.¶