Skip to content

Latest commit

 

History

History
43 lines (28 loc) · 2.77 KB

README.md

File metadata and controls

43 lines (28 loc) · 2.77 KB
Raw

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 xi ∈ X on E. (Derive)
  3. for each of the derived points xi, the sender computes point multiplication: axi, 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 axi ∈ aX with private key b: b(axi) 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 yi ∈ Y on E. (Derive)
  7. for each of the derived points yi, the receiver computes point multiplication: byi, 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 byi ∈ bY with his private key a: a(byi) 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