ECDH PSI implementation

protocol

The Diffie-Hellman private set intersection (DHPSI) [1] is one of the first PSI protocols and is communication efficient, but requires expensive computations from both parties: a sender and a receiver. We implement DHPSI using elliptic curve (specifically ristretto255 [2]) instead of finite field exponentiation for performance reasons. The point operation of kP is the multiplication of a ristretto point P with a scalar k over an ellipic curve (Curve25519).

1. the receiver and the sender agree on a preset elliptic curve E (Curve25519).
2. the sender generates his private key (scalar) a, and hashes each identifier from his input audience list to obtains points x_i ∈ X on E. (Derive)
3. for each of the derived points x_i, the sender computes point multiplication: ax_i, and obtains the set of multiplied points aX. (Multiply)
4. the sender permutes aX and sends them to the receiver. (ShuffleWrite)
5. the receiver receives aX from the sender. The receiver generates his private key (scalar) b and multiplies each element ax_i ∈ aX with private key b: b(ax_i) to obtain the set of multiplied points baX and index it. (ReadMultiply)
6. the receiver hashes each identifier from his input audience list to obtain points y_i ∈ Y on E. (Derive)
7. for each of the derived points y_i, the receiver computes point multiplication: by_i, and obtains the set of multiplied points bY. (Multiply)
8. the receiver permutes bY and sends them to the sender. (ShuffleWrite)
9. The sender receives bY, and multiplies each element by_i ∈ bY with his private key a: a(by_i) to obtain the set of multiplied points abY, and sends them back to the receiver. (ReadMultiply)
10. the receiver receives abY, and finds the intersecting identifiers from the set baX and abY. (Intersect)

data flow

          Sender                                        Receiver
          X, a                                          Y, b


Stage 1   DM/Shuffle    --------------aX------------->  M -> baX              Stage 1

Stage 2   M -> abY      +-------------bY--------------  DM/Shuffle            Stage 2.1
                        |
                        +-------------abY------------>  intersect(baX, abY)   Stage 2.2


     DM:  ristretto255  derive/multiply
      M:  ristretto255  multiply
Shuffle:  cryptographic quality shuffle

References

[1] C. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In IEEE S&P’86, pages 134–137. IEEE, 1986.

[2] https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448