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.

  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Jan 23 '20 at 20:15
  • $\begingroup$ @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. $\endgroup$ – Rob Jan 24 '20 at 1:30
  • $\begingroup$ it might be with pairings that you can cancel out the watermarks in the final step, so that every user gets the same result. $\endgroup$ – Rob Jan 24 '20 at 1:41
  • 1
    $\begingroup$ 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? $\endgroup$ – poncho Jan 24 '20 at 19:13
  • $\begingroup$ @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}$. $\endgroup$ – Rob Jan 26 '20 at 19:15

Your Answer

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

Browse other questions tagged or ask your own question.