Fuzzy Identity-Based Matchmaking Encryption and Its Application

Ateniese et al. introduced the primitive of matchmaking encryption (ME) at CRYPTO 2019 and left open several important questions, which include extending ME to fuzzy cases or giving an efficient ME in the identity-based setting without relying on random oracles. The main challenge is to achieve fuzzy bilateral access control while providing identity privacy of the sender and receiver, message confidentiality and authenticity without random oracles. In this work, we resolve the question by formalizing the first fuzzy identity-based ME (IB-ME) and presenting a concrete construction. Specifically, we propose the formal syntax definition of fuzzy IB-ME. In fuzzy IB-ME, the identities of senders and receivers are characterized by attribute sets. A ciphertext can be correctly decrypted if the overlaps between the attribute set of the sender or receiver and the attribute set specified by the other party are simultaneously greater than a threshold, which can be applied to many attractive applications such as fuzzy bilateral access control in online social dating. Then, we present concrete details of fuzzy IB-ME based on fuzzy identity-based encryption, which does not rely on other cryptographic tools such as two-input functional encryption and non-interactive zero-knowledge proof systems. In this process, fuzzy bilateral access control and identity privacy are achieved through the formalism of arranged ME and the splitting technique while message authenticity is provided through the authentication and binding of the encryption key. The identity privacy of the sender and receiver, confidentiality, and authenticity of messages are reduced to the decisional bilinear Diffie-Hellman, decision linear, and computational bilinear Diffie-Hellman assumptions in the selective model without random oracles. Finally, we implement the scheme and evaluate its performance through theoretical analyses and experiments to demonstrate its efficiency.