Abstract
Abstract
The widespread adoption of password-based authentication across diverse digital platforms, has significantly heightened exposure to security threats. Due to memorability constraints, users often reuse passwords across multiple platforms, thereby increasing vulnerability to credential-stuffing attacks. Although password managers mitigate this issue, they face practical adoption challenges. Existing password reuse detection mechanisms typically require access to sensitive credentials, raising serious privacy concerns. Password database breach detection represents another critical and challenging problem. Among existing approaches, honeyword-based techniques have gained considerable attention in the research community; however, generating realistic and secure honeywords remains a non-trivial task. To address the above mentioned challenges, we propose two privacy-preserving protocols built on Private Set Intersection (PSI). We first introduce a Password Reuse Detection (PRD) protocol with two instantiations: a Diffie–Hellman (DH)-based PSI construction and an Oblivious Transfer (OT)-based PSI construction. We further present a Breach Detection (BD) protocol that leverages DH-based PSI to identify credential-stuffing attacks in real time. Compared to existing approaches, including Wang et al., our PRD protocol achieves approximately 2.8
$$\times $$
improvement in computational efficiency and reduced storage overhead for 5000 honeywords, while the BD protocol enables real-time detection. Both protocols prevent disclosure of password values during cross-site comparison and preserve user privacy. We formally prove their semantic security in the Real-or-Random (RoR) model under the Decisional Diffie–Hellman (DDH) assumption.