I am using ABE scheme that has already proven under BDHE assumption. Here is the scheme https://eprint.iacr.org/2008/290.pdf

In the key generation algorithm, I want to tie the user secret key components with a message $m∈GT$. $m$ is different from the one used in the encryption algorithm.
I did like this

$S=M.e(g^t, g^d) = M.e(g,g)^{td}$ where $t,d∈Z$ are randomly chosen. $t$ is used to tie all other secret key components together.

$S$ will be given to the user along with the secret key which have these components $(K=g^bg^{at}, L=g^t, h1^t, h2^t, …)$

$d $ and $g^d$ will be kept secure with the authority.

My question, do I need to re-prove the security of the scheme considering $S$

  • $\begingroup$ What do you want that tieing to achieve? ​ ​ $\endgroup$
    – user991
    Jul 23, 2016 at 20:48
  • $\begingroup$ @RickyDemer thank you, I want to ensure that (1) it hard to distinguish the term $e(g,g)^{td}$? given the secret key including $S$, and (2) the user cannot exchange (collude) $S$ with other user's $S'$ $\endgroup$
    – Alex
    Jul 23, 2016 at 21:04
  • $\begingroup$ "hard to distinguish the term $e(g,g)^{td}$" from what? ​ What does your property (2) mean? ​ ​ ​ ​ $\endgroup$
    – user991
    Jul 23, 2016 at 23:01
  • $\begingroup$ @RickyDemer (1) distinguish from a random value; the second property is about whether or not the scheme will be resisted against collusion between users $\endgroup$
    – Alex
    Jul 23, 2016 at 23:24
  • $\begingroup$ How is $t$ generated for (1)? ​ ​ $\endgroup$
    – user991
    Jul 24, 2016 at 0:25

1 Answer 1


I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or you may be able to reuse a lot of the intermediate claims of the proof of the original scheme. However, you must prove!


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.