# Looking for a group where multiplicative inverse is hard but calculating multiple pairwise inverses is easy

I have an equation that comes up in trying to do an Attribute Based Encryption scheme, where users have certificates that sign off on attributes that are also watermarked. I perform a division to ensure that all attributes came from the same certificate. Each user will have a different $$w_x^{-1}$$ (unwatermark), but only the CA knows $$w_x$$ (the watermark)

$$(f0_a * (a * z * w_x) + f0_b * (b * z * w_x)) \times w_x^{-1} = (f0_a * a + f0_b * b) * z$$

Nothing necessarily commutes. Only the CA can calculate a $$w$$. But for every user, they have a different $$x$$. I think this rules out RSA because $$w_x$$ and $$w_y$$ would have a different RSA modulus. But I want every user to calculate the same value $$(f0_a * a + f0_b * b) * z$$ in the end. That would basically be an AES key for a case of two "signed" expressions (a and b are signed by CA via multiplication by z).

The question is... if not RSA, then what system? My understanding is that the value would not come out the same for $$w_x$$ vs $$w_y$$ even though algebraically, it cancels out.

Or maybe something more subtle... like use RSA to generate $$w_x$$ and $$w_x^{-1}$$, and just use the modulus on that multiplication; and a different fixed modulus for the other times operators.

Is there insight on what group would be appropriate for this?

If its commutative multiplication, I think that's ok here (but not required). But if the user were able to calculate $$w_x$$ from $$w_x^{-1}$$, then this scheme falls down. Same for being able to extract $$z$$, which is the CA's signing secret.

• Actually, it appears that you're looking for a field (or at least, a ring); you have both the addition and multiplication operations, and appear to assume that the distribution property holds... – poncho Jan 23 at 20:15
• @poncho yes. associativity, (maybe) distribution, and the inability of users to invert elements. i know that most existing Identity Based Encryption schemes are based on EC Pairings, but I honestly don't really understand them. So I started with a hash-based system that works, but doesn't stop collusion between users. And this would stop collusion. I'm not sure if normal EC can do this, or if I need to figure out pairings to pull it off. $f0_a * a * w_x + f0_b * b * w_x$ would work as well. The CA can sign, watermark, and then sum the attributes individually. – Rob Jan 24 at 1:30
• it might be with pairings that you can cancel out the watermarks in the final step, so that every user gets the same result. – Rob Jan 24 at 1:41
• A pairing based approach might work, but it's not clear if the system will satisfy the other required security requirements. If we reinterpret the system as $$e( f0_a \cdot a \cdot z \cdot w_x + f0_b \cdot b \cdot z \cdot w_x, w_x^{-1}G ) = e( f0_a \cdot a + f0_b \cdot b, zG)$$, that would satisfy the immediate requirement; however only one of $f0_a, a, z, w_x$ can be an EC point, and it's not clear if just making one of them will work. For example, if $a, b$ are both just a scalar, then it'll be easy to compute $b \cdot z \cdot w_x$ from $a, b, a \cdot z \cdot w_x$ - is this a problem? – poncho Jan 24 at 19:13
• @poncho What I was trying with pairing was basically to atomically swap out the watermark to the user into a watermark to the file, so that you can make this transition... $a * z * w_z + b * z * w_z \to a * z * f0_a + b * z * f0_b$ Without allowing you to recover $z$, $w_z$ or especially $a * z$ in the process. This is because the user has every certificate (to represent collusion) and the expression hiding attribute $a$ approved by $z$ for the purpose of $f0_a$. ( $a * z * f0_a$). I came up with something similar to what you describe. I paired $a * z * w_x$ with $f0_a * w_x^{-1}$. – Rob Jan 26 at 19:15