In some papers, server generates keys for users as follows: $$sk_i=msk+H(ID_i)v_i\ (mod \ p)$$ where $msk=$ the secret key of server

$v_i$ is randomly selected from $Z_p$ for i-th user , $p$ is a prime number

$ID_i=$ the identity of i-th user

$sk_i=$ the secret key for i-thuser

$H$ is the hash function

If there is a user who knows more than one secret key, does that key generation scheme prevent to reveal the value of $msk$ from users.

How to prove the security?

I have forgotten paper references. Sorry for that.

  • 1
    $\begingroup$ Can we assume that $v$ and $p$ are generated once for the server? Please explain how they are used in the protocol. You've specified the algorithm, which is great, but I'm missing the context and time factor. $\endgroup$
    – Maarten Bodewes
    Commented Jan 24, 2017 at 8:27
  • $\begingroup$ @MaartenBodewes. $v$ is uniformly randomly selected for each users. Therefore, we can assume $v_i$ for i-th user. $p$ is generated once for the server. $\endgroup$ Commented Jan 24, 2017 at 10:12
  • $\begingroup$ Do the users learn their $v_i$ directly at any point or are they just being given their $sk_i$? $\endgroup$
    – SEJPM
    Commented Jan 24, 2017 at 12:10
  • $\begingroup$ @SEJPM. No, server gives $v_iP$ and $sk_i$ to user. Users do not learn $v_i$ directly. $\endgroup$ Commented Jan 25, 2017 at 1:48

1 Answer 1


Not really worked with these kinds of schemes, but here's my viewpoint.

Write $w_i=H(ID_i)v_i$. The value $H(ID_i)$ is some fixed public value, so we can kind of forget about it. That is, if $v_i$ is uniformly random, then so is $w_i$.

Now the key is generated as $sk_i=msk+w_i\pmod{p}$. Since $w_i$ is uniformly random, this is simply a generalisation of the one-time pad. In other words, $sk_i$ reveals no information whatsoever about $msk$. Therefore however many times you repeat this, the user will still learn nothing about $msk$.

  • $\begingroup$ This is a good answer considering the information about the problem that is given and assuming that when the user gets $v_iP$ the $v_i$ is protected by DLOG. $\endgroup$
    – Elias
    Commented Jan 25, 2017 at 17:43

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.