Cryptanalysis of LC-MUME : A Lightweight Certificateless Multi-User Matchmaking Encryption for Mobile Devices
Ramprasad Sarkar · 2025
Read Cryptanalysis of LC-MUME : A Lightweight Certificateless Multi-User Matchmaking Encryption for Mobile Devices by Ramprasad Sarkar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22674.txt.
Introduction
Ramprasad Sarkar breaks a published encryption scheme designed for matching users on mobile phones. The scheme, LC-MUME, promised light, certificate-free security for one-to-many messaging. Its authors claimed a strong grade of unforgeability under attack. Sarkar shows the claim fails.
His study builds an attacker who needs no full private key from the sender. That attacker can still forge a valid ciphertext that passes every check. The math shows the hole, and a working build confirms it runs at minimal cost. Such a break voids the scheme's core promise for phone users. Sarkar closes with a repair strategy for this family of schemes. The paper is a reminder that published proofs deserve hostile re-reading.
Catalog record
| CREATOR | Ramprasad Sarkar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22674
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cryptanalysis of LC-MUME : A Lightweight Certificateless Multi-User Matchmaking Encryption for Mobile Devices Ramprasad Sarkar Abstract Yang et al. proposed a lightweight certificateless multi-user matchmaking encryption ( LC-MUME ) scheme for mobile devices, published in IEEE Transactions on Information Forensics and Security (TIFS) (DOI: 10.1109/TIFS.2023.3321961). Their construction aims to reduce computational and communication overhead within a one-to-many certificateless cryptographic framework. The authors claim that their scheme satisfies existential unforgeability under chosen-message attacks ( EUF-CMA ) in the random oracle model. However, our cryptanalytic study demonstrates that the scheme fails to meet this critical security requirement. In particular, we show that a Type-I adversary can successfully forge a valid ciphertext without possessing the complete private key of the sender. Both theoretical analysis and practical implementation confirm that this attack can be mounted with minimal computational cost. To address these weaknesses, we propose a modification strategy to strengthen the security of matchmaking encryption schemes in mobile computing environments. I Introduction Matchmaking Encryption ( ME ) is an advanced cryptographic primitive that enables bilateral access control between the sender and the receiver. Unlike traditional encryption schemes that enforce access policies unilaterally, ME empowers the sender to define an access policy specifying which receivers may decrypt the message, while simultaneously allowing the receiver to verify whether the ciphertext originates from a legitimate sender. This dual control mechanism improves communication privacy, particularly by protecting the sender’s identity. To address the shortcomings of conventional attribute-based encryption and signature-based mechanisms, Chen et al. [ 1 ] introduced a certificateless matchmaking encryption ( CL-ME ) scheme tailored for IoT environments, presenting two efficient constructions based on bilinear pairings and lightweight cryptographic techniques. Building on this line of work, Yang et al. [ 2 ] proposed a lightweight certificateless multi-user matchmaking encryption ( LC-MUME ) scheme for mobile platforms. Their construction aims to improve efficiency by avoiding pairings and relying on standard hardness assumptions. They claim that their scheme achieves existential unforgeability under chosen-message attacks ( EUF-CMA ). II Review of Yang et al. ’s LC-MUME The original LC-MUME scheme includes five algorithms due to space limitations; here, we omit the detailed description, which can be referred to [ 2 ] . III Our Proposed Attacks In this section, we identify the security vulnerabilities present in Yang et al.’s scheme [ 2 ] . A secure Certificateless Multi-User Matchmaking Encryption scheme should ensure that a sender cannot repudiate sending a valid encrypted message to a receiver. Additionally, it must prevent any adversary from impersonating the sender to create valid encrypted messages without knowing the full private key of the sender. Yang et al. [ 2 ] claim that their scheme is existentially unforgeable under a chosen message attack. However, we will demonstrate that a Type-I Adversary \mathcal{ADV}_{I} can successfully forge a valid encrypted message to the receiver by substituting the sender’s public key. The attack comprises the following three stages: Step-1. In this stage, \mathcal{ADV}_{I} replaces public key of the sender. For that, \mathcal{ADV}_{I} randomly selects a^{*},b^{*}\in\mathbb{Z}^{*}_{q} and replaces the corresponding public key \textsf{PK}^{*1}_{\textsf{Id}_{\textsf{S}}}=a^{*}\textsf{P}, \textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}}=b^{*}\textsf{P} , while \mathcal{ADV}_{I} uses the secret key for the sender as \textsf{SK}^{*}_{\textsf{Id}_{\textsf{S}}}= (\textsf{SK}^{*1}_{\textsf{Id}_{\textsf{S}}},\textsf{SK}^{*2}_{\textsf{Id}_{\textsf{S}}})= (a^{*},b^{*}) . Step-2. In this stage, \mathcal{ADV}_{I} generates a ciphertext under the replaced public key \textsf{PK}^{*}_{\textsf{Id}_{\textsf{S}}} . \mathcal{ADV}_{I} does the following. (i) \mathcal{ADV}_{I} chooses r,s,d^{*}_{1},d^{*}_{2}\in\mathbb{Z}^{*}_{q} and computes \textsf{CT}^{*}_{1}=r\textsf{P} and \textsf{CT}^{*}_{2}=s\textsf{P}-\mathcal{H}_{1}(\textsf{Id}_{\textsf{S}},\textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}})\mathcal{P}^{{}^{\prime}} . (ii) For \textsf{Id}_{\textsf{i}}\in\textsf{Rcvr} , it computes \displaystyle\tau^{*}_{i} \displaystyle=\textsf{SK}^{*1}_{\textsf{Id}_{\textsf{S}}}\cdot\textsf{PK}^{1}_{\textsf{Id}_{\textsf{i}}} \displaystyle\mathcal{V}^{*}_{\textsf{Id}_{\textsf{i}}} \displaystyle=\mathcal{H}\left(r\cdot\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})\left(\textsf{PK}^{2}_{\textsf{Id}_{\textsf{i}}}+\mathcal{H}_{1}(\textsf{Id}_{\textsf{i}},\textsf{PK}^{2}_{\textsf{Id}_{\textsf{i}}})\mathcal{P}^{{}^{\prime}}\right)\right) \displaystyle\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{i}}} \displaystyle=\left(s+\textsf{SK}^{*2}_{\textsf{Id}_{\textsf{S}}}+\textsf{SK}^{*1}_{\textsf{Id}_{\textsf{S}}}\cdot\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})\right)\textsf{PK}^{1}_{\textsf{Id}_{\textsf{i}}}. (iii) Then the adversary sets two n -degree polynomials as follows. \displaystyle f^{*}(x) \displaystyle=\prod\limits_{\textsf{Id}_{\textsf{k}}\in\textsf{Rcvr}}(x-\mathcal{V}^{*}_{\textsf{Id}_{\textsf{k}}})+d^{*}_{1}=\sum\limits_{\textsf{k}=0}^{n-1}a^{*}_{\textsf{k}}x^{\textsf{k}}+x^{n}(\bmod~q) \displaystyle g^{*}(y) \displaystyle=\prod\limits_{\textsf{Id}_{\textsf{k}}\in\textsf{Rcvr}}(y-\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{k}}})+d^{*}_{2}=\sum\limits_{\textsf{k}=0}^{n-1}b^{*}_{\textsf{k}}y^{\textsf{k}}+y^{n}(\bmod~q) (iv) Then, it computes the following ciphertext components as follows. \displaystyle\textsf{CT}^{*}_{3} \displaystyle=\left[\mathcal{H}_{2}(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},d^{*}_{1},d^{*}_{2})\right]_{l-l_{1}}\parallel\left(\left[\mathcal{H}_{2}(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\right.\right. \displaystyle\left.\left.d^{*}_{1},d^{*}_{2})\right]^{l_{1}}\bigoplus m\right) \displaystyle\textsf{CT}^{*}_{4} \displaystyle=\mathcal{H}_{3}(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\textsf{CT}^{*}_{3},a^{*}_{0},a^{*}_{1},\ldots,a^{*}_{n-1},b^{*}_{0},b^{*}_{1},\ldots,b^{*}_{n-1}). (v) Finally, it returns a corresponding ciphertext \textsf{CT}^{*} = \left(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\textsf{CT}^{*}_{3},\textsf{CT}^{*}_{4},a^{*}_{0},a^{*}_{1},\ldots,a^{*}_{n-1},b^{*}_{0},b^{*}_{1},\right. \left.\ldots,b^{*}_{n-1}\right) . Step-3. We notice that, since there’s no binding between a user’s identity and his public key, the receiver cannot detect that the sender’s public key is replaced by the adversary. In this stage, upon receiving the ciphertext, the receiver \textsf{Id}_{\textsf{i}} invokes the decryption algorithm as follows. 1. It parses the ciphertext \textsf{CT}^{*}=\left(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\textsf{CT}^{*}_{3},\right. \left.\textsf{CT}^{*}_{4},a^{*}_{0},a^{*}_{1},\ldots,a^{*}_{n-1},b^{*}_{0},b^{*}_{1},\ldots,b^{*}_{n-1}\right) and check whether the equation \textsf{CT}^{*}_{4}=\mathcal{H}_{3}\left(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\textsf{CT}^{*}_{3},\right. \left.a^{*}_{0},a^{*}_{1},\ldots,a^{*}_{n-1},b^{*}_{0},b^{*}_{1},\ldots,b^{*}_{n-1}\right) . 2. If not, returns \bot . Otherwise, it calculates \displaystyle\tau^{*}_{\textsf{i}}=\textsf{SK}^{1}_{\textsf{Id}_{\textsf{i}}}\cdot\textsf{PK}^{*1}_{\textsf{Id}_{\textsf{S}}},~\mathcal{V}^{*}_{\textsf{Id}_{\textsf{i}}}=\mathcal{H}(\textsf{SK}^{2}_{\textsf{Id}_{\textsf{i}}}\cdot\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{\textsf{i}})\cdot\textsf{CT}^{*}_{1}) \displaystyle\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{i}}}=\textsf{SK}^{1}_{\textsf{Id}_{\textsf{i}}}\left(\textsf{CT}^{*}_{2}+\textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}}+\mathcal{H}_{1}(\textsf{Id}_{\textsf{S}},\textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}})\mathcal{P}^{{}^{\prime}}+\mathcal{H}_{4}\left(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\right.\right. \displaystyle\left.\left.\tau^{*}_{i}\right)\textsf{PK}^{1}_{\textsf{Id}_{\textsf{i}}}\right). 3. It then recovers d^{*}_{1} and d^{*}_{2} by computing d^{*}_{1}=f(\mathcal{V}^{*}_{\textsf{Id}_{\textsf{i}}}),d^{*}_{2}=g(\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{i}}}) . Then it finally returns the message as follows m=\left[\mathcal{H}_{2}(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},d^{*}_{1},d^{*}_{2})\right]^{l_{1}}\bigoplus\left[\textsf{CT}^{*}_{3}\right]^{l_{1}} if \left[\mathcal{H}_{2}(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},d_{1},d_{2})\right]_{l-l_{1}}=\left[\textsf{CT}^{*}_{3}\right]_{l-l_{1}}, otherwise it return \bot . The adversary generated a forged ciphertext that is well-defined and correct due to the following calculations. \displaystyle\tau^{*}_{i} \displaystyle=\textsf{SK}^{*1}_{\textsf{Id}_{\textsf{S}}}\cdot\textsf{PK}^{1}_{\textsf{Id}_{\textsf{i}}}=a^{*}x_{\textsf{i}}\textsf{P} \displaystyle\mathcal{V}^{*}_{\textsf{Id}_{\textsf{i}}} \displaystyle=\mathcal{H}(\textsf{SK}^{2}_{\textsf{Id}_{\textsf{i}}}\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{\textsf{i}})\textsf{CT}^{*}_{1}) \displaystyle=\mathcal{H}(r\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{\textsf{i}})d_{\textsf{i}}\textsf{P}) \displaystyle=\mathcal{H}(r\cdot\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{\textsf{i}})(\textsf{PK}^{2}_{\textsf{Id}_{\textsf{i}}}+\mathcal{H}_{1}(\textsf{Id}_{\textsf{i}},\textsf{PK}^{2}_{\textsf{Id}_{\textsf{i}}})\mathcal{P}^{{}^{\prime}})) \displaystyle\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{i}}} \displaystyle=\textsf{SK}^{1}_{\textsf{Id}_{\textsf{i}}}\left(\textsf{CT}^{*}_{2}+\textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}}+\mathcal{H}_{1}(\textsf{Id}_{\textsf{S}},\textsf{PK}^{*2}_{\textsf{Id}_{\textsf{S}}})\mathcal{P}^{{}^{\prime}}\right. \displaystyle\left.+\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})\textsf{PK}^{*1}_{\textsf{Id}_{\textsf{S}}}\right) \displaystyle=x_{\textsf{i}}\left(s\textsf{P}+b^{*}\textsf{P}+\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})a^{*}\textsf{P}\right) \displaystyle=x_{\textsf{i}}\textsf{P}\left(s+b^{*}+\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})a^{*}\right) \displaystyle=\left(s+\textsf{SK}^{*2}_{\textsf{Id}_{\textsf{S}}}+\textsf{SK}^{*1}_{\textsf{Id}_{\textsf{S}}}\cdot\mathcal{H}_{4}(\textsf{Id}_{\textsf{S}},\textsf{Id}_{\textsf{i}},\tau^{*}_{i})\right)\textsf{PK}^{1}_{\textsf{Id}_{\textsf{i}}} Since the receiver \textsf{Id}_{\textsf{i}} is from the set Rcvr , therefore, it can recover the d_{1} and d_{2} by computing d^{*}_{1}=f(\mathcal{V}^{*}_{\textsf{Id}_{\textsf{i}}}),d^{*}_{2}=g(\mathcal{Z}^{*}_{\textsf{Id}_{\textsf{i}}}) . This follows that the forged ciphertext \textsf{CT}^{*}=\left(\textsf{CT}^{*}_{1},\textsf{CT}^{*}_{2},\textsf{CT}^{*}_{3},\right. \left.\textsf{CT}^{*}_{4},a^{*}_{0},a^{*}_{1},\ldots,a^{*}_{n-1},b^{*}_{0},b^{*}_{1},\ldots,b^{*}_{n-1}\right) is valid. Therefore, the scheme is subject to universal forgery with respect to a Type-I adversary \mathcal{ADV}_{I} who replaces the sender’s public key. IV Performance Analysis and Implementation This section presents a performance evaluation and practical implementation of the proposed forgery attacks against the certificateless matchmaking encryption scheme of Yang et al. [ 2 ] , under the EUF-CMA security model. In this setting, a Type-I adversary \mathcal{ADV}_{I} attacks in two main stages: Step 1 and Step 2, ultimately generating a valid forged ciphertext. In Step 3, the forged ciphertext can be verified and correctly decrypted by an authorized user or the challenger, thus violating the EUF-CMA security notion. The total cost incurred by \mathcal{ADV}_{I} is the sum of all operations performed during Steps 1 through 3. Table I summarizes the computational complexity per operation step, as well as the total execution time (in milliseconds) required to complete the forgery for various values of the target user set size n . Our attack technique was implemented on a Dell laptop equipped with an AMD A9-9400 Radeon processor, 12 GB RAM, running Ubuntu 22.04.4 LTS (64-bit) with GNOME 42.9. We used the Pairing-Based Cryptography ( PBC ) library, version 0.5.14 [ 3 ] , utilizing a Type A bilinear pairing over the supersingular curve defined by y=x^{3}+x . The attack strategy was executed for different sizes of the user groups: n\in\{8,16,32,64,128,256,512,1024\} . The timing results (in milliseconds) are reported in Table I , along with the detailed breakdown of the cryptographic operations involved. The findings indicate that the proposed attack is highly efficient and scales linearly with the number of target user sets. TABLE I: Computation Cost and Execution Time of EUF-CMA Attack Step #Z #SM #SS #Hash Attack Time (ms) for Varying User Sizes ( n ) 8 32 128 256 512 1024 Step-1 2 2 – – 11.20 39.04 150.40 298.88 595.84 1189.76 Step-2 2n+4 3n+1 7n+3 n+4 Step-3 – – 7 6 #Z : element generation in \mathbb{Z}_{p}^{*} , #SM : scalar multiplication in the source or target group, #SS : group addition/multiplication, #Hash : hash function evaluation. n : number of users. V Countermeasures Against the Proposed Attacks As shown in Section III , Yang et al. ’s scheme [ 2 ] is vulnerable to forgery attacks launched by a Type-I adversary. The root cause of this vulnerability lies in unaccounted algebraic dependencies within the underlying group structure, which the security proof fails to capture. In particular, these attacks do not imply that the adversary solves the underlying hard problems in a general or random instance. Attacks on certificateless encryption systems can