SXDH

SXDH, short for Symmetric External Diffie-Hellman, is a cryptographic hardness assumption used in pairing-based cryptography. It relates to bilinear pairings e: G1 x G2 -> GT, where G1 and G2 are cyclic groups of prime order and GT is the target group. The SXDH assumption posits that the decisional Diffie-Hellman (DDH) problem is hard in both source groups G1 and G2. Concretely, for random exponents a and b in Z_p, given generators g1 in G1 and g2 in G2, and the elements g1^a in G1 and g2^b in G2, it is computationally infeasible to determine whether a provided element T in GT equals e(g1, g2)^{ab} or is random. In other words, even with access to both groups and the pairing, distinguishing the real pairing result from a random element remains hard.

The assumption is used to analyze and prove security for various pairing-based constructions, including certain group signatures, identity-based encryption schemes, and other protocols that operate across both source groups. SXDH is related to, and in some settings stronger than, the XDH family of assumptions; it is especially relevant for Type-3 pairings where there is no efficient isomorphism between G1 and G2.

Limitations and notes: like other cryptographic assumptions, SXDH is unproven and relies on believed hardness properties of specific pairing-friendly curves. Its applicability depends on choosing curves where DDH remains hard in both G1 and G2, and it is often invoked in security proofs for schemes that require cross-group secrecy guarantees.