# Can a Cramer-Shoup public key have two different private keys?

Since I am new to the Cramer-Shoup algorithm, I would like to know: Is it possible to have two different private keys for a public key due the key pair generation algorithm that Cramer-Shoup uses? I know that in public key algorithms, this is not possible in all cases, but I want to make sure what the answer is for Cramer-Shoup.

• Yes, I think the spec allows that, as you'd "simply" had to find two pairs $(x_1,x_2),(x_3,x_4)$ for which $g_1^{x_1}\cdot g_2^{x_2} \equiv g_1^{x_3} \cdot g_2^{x_4} \pmod{q}$ or something likewise for the $y$s. However I'm not sure if constructing such a second key is feasible... (I'm referring to Wikipedia)
– SEJPM
Aug 1 '15 at 21:03
• @SEJPM It is feasible if $\log_{g_1}g_2$ is known. Aug 1 '15 at 21:04
• @yyyyyyy, calculating $\log_{g_1}(g_2)$ however looks infeasible as $g_1,g_2$ need to be chosen randomly distinct which means you'd have to solve the DLP...
– SEJPM
Aug 1 '15 at 21:06
• @yyyyyyy would you give me more explanation.. I mean what is DLP? and how hard to solve it? does RSA suffer from the same thing? and does DH if used as public key? and since $g_1 and$g_2 are part of the public key why would $log_g1 not known? sorry for such silly question but I want to understand :) Aug 1 '15 at 21:41 • @БасселЖаббор, sorry for this one :) DLP is the discrete logarithm problem which is widely assumed to be hard. RSA is based on the RSA-Problem which is widely believed to be close to the factoring problem. If you can break generic DLP however you can also break RSA. DH can be broken if DLP isn't hard. You wouldn't know the logarithm because you'd only be give the$g_1$and$g_2$and as you need to calculate a discrete logarithm you can't do this (if you assume DLP to be hard) – SEJPM Aug 1 '15 at 21:47 ## 1 Answer Yes, this is possible. One possible argument is of algebraic nature, using the fact that there is some$a\in\{0,\dots,q-1\}$with$g_2=g_1^a$and rewriting the public key's defining equations using this relation. However, there's a much simpler justification: A Cramer-Shoup public key consists of five elements$g_1,g_2,c,d,h$of a group of order$q$, hence there are at most$q^5$possible public keys. However, a private key consists of two freely chosen elements$g_1,g_2$and five freely chosen integers$x_1,x_2,y_1,y_2,z$between$0$and$q-1$, yielding$q^7$possible private keys. Therefore, there exist (on average) at least$q^2$private keys mapping to a single public key. (In fact, the algebraic argument mentioned above shows that there are exactly$q^5$public keys, each of which corresponds to exactly$q^2$private keys.) • @yyyyyyy what about RSA in your opinion ? can one RSA public key have 2 different private keys Aug 1 '15 at 22:27 • then for carmen shoup suppose the attacker knew the public key can hey make private key for it and decrypt the message since every public key have$q^2$private.. my point is: is not easy for attacker assuming he have access to strong servers to create any private key for the same public key then decrypt the message that is encrypt with it? sorry for my may be silly question but I am a web developer not crypto expert Aug 2 '15 at 15:19 • @БасселЖаббор The RSA private key$d$corresponding to a public key$(n,e)$is unique modulo the exponent of the group$(\mathbb Z/n)^\ast$, that is$\lambda(n)=\operatorname{lcm}(p−1,q−1)$. Hence, if you ensure that$d$is in$\{0,\dots,\lambda(n)-1\}=\{0,\dots,\operatorname{lcm}(p-1,q-1)-1\}\$, then it it is unique. Aug 2 '15 at 18:22
• @БасселЖаббор That there are many private keys corresponding to a given public key does not imply that it is easy to find them — they still comprise only a negligible fraction of all possible private keys, so a brute-force search is still infeasible. For all reasonable public-key cryptosystems, it is assumed hard to compute the private key given only a public key: after all, that's the whole point. Aug 2 '15 at 18:26
• thank you for this simple yet sufficient answer, but, please let me tell you what I understood from the answers and please correct me if I am wrong: carmer shoup does have multiple private keys for the same public key but in order for the attacker to find a private key or one of them either he will have to solve the DLP which is hard and require a lot of time if there solution (assuming we implemented cramer shoup correctly) or he will have to Brut-force searching for a key which can not be done in reasonable time. Aug 2 '15 at 20:37