2
$\begingroup$

I'm reading about the broadcast encryption described in Fiat and Naor's paper, I screen grabbed the relevant part below. My question is essentially:

If there's a secret:

$g^{abc}$ $mod$ $A$ (where $A=PQ$ (both sufficiently large primes))

why is it that one user who knows:

$g^d$ $mod$ $A$, $a$, $b$, $c$, $d$, and $A$

could not calculate $g^{abc}$ $mod$ $A$ but when you add a second user who know $g^e$ $mod$ $A$, and $e$, they can then collude to calculate $g^{abc}$ $mod$ $A$ ?

Context is provided below.

the 1-resilient scheme

The full paper can be found here

The paper states that one user not in the privileged set could not calculate the secret, but two colluding users could (and so they rate the scheme 1-resilient).

$\endgroup$
2
  • $\begingroup$ Isn't this question about roots, not logarithms? $\endgroup$ May 8, 2015 at 8:18
  • $\begingroup$ That is true, it's about solving for the base not the exponent. Could you change the title to something you think makes more sense? $\endgroup$
    – cciollaro
    May 9, 2015 at 16:34

1 Answer 1

3
$\begingroup$

The idea is that someone who just knows $g^d \bmod N$ and $d$, they cannot compute $g$ (because they don't know the factorization of $N$; hence this is the RSA problem); however, if they know $g^d \bmod N$ and $d$ and $g^e \bmod N$ and $e$, then (assuming $gcd(d, e) = 1$), they can (and once they have $g$, they can compute $g^{abc} \bmod N$).

That's because, since they know $d$ and $e$, they can compute two integers $s$ and $t$ such that $sd + te = 1$ (that's where the assumption that $gcd(d, e) = 1$ comes in; if that's not true, then no such $s$, $t$ will exist). Once that have those two integers, they can compute $(g^d)^s \times (g^e)^t = g^{sd + te} = g^1 = g$, recovering $g$. One of $s$ and $t$ will be negative; that's not an issue, as we can compute inverses modulo a number of unknown factorization.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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