Why does the "strong LRSW" assumption by Ateniese et al. [Untraceable RFID Tags via Insubvertible Encryption, CCS'05] hold ONLY for type 3 pairings and NOT for symmetric pairings? Whereas, the LRSW assumption by Lysyanskaya et al. [Pseudonym Systems, SAC'99] does hold for all types of pairings.


In a type-3 group, after an oracle query you get to see $(g_1^a, g_1^{at}, g_1^{as+axst}, g_1^{ax}, g_1^{axt})$ but not $g_1^s$ or $g_1^t$ (those are in $G_2$). Suppose you had a homomorphism $G_2 \to G_1, g_2 \mapsto g_1$ so you could recover $g_1^s$ and $g_1^t$.

Call your tuple from the oracle $(A, B, C, D, E)$ and compute $(Ag_1^r, B(g_1^t)^r, C(g_1^s)^r, D, E)$ for an $r$ of your choice. There is a unique value of $u \in \mathbb Z_p$ (where $p$ is the group order) such that $a+r = ua$ and if my math is correct, the modified tuple is now a correct tuple for $a' = ua$ and $x' = u^{-1}x$, which the oracle never signed.

Indeed, for the $D, E$ components the change of variables $a \mapsto ua, x \mapsto u^{-1}x$ does not affect the product $a'x' = ax$ so we can leave them alone. For $C$, the exponent was $as + axst$, the second summand is ok but the first one has $as = a'u^{-1}s$ so we want to change that $a$ to $a'$. We can't do that directly, but since $au = a + r$ we can make up the difference by adding $g_1^{rs}$. This change from a multiplicative relationship (that leaves the product $ax$ alone) to an additive one (that we can use to adjust the remaining terms) is what makes this attack work. For $A, B$ we then do the appropriate adjustment as well.

Note that you never actually get to know the value of $u$, or $x'$. That's why this doesn't work against plain LRSW, where you need to output $x'$ as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.