I know how to do Cramer-Shoup with cyclic groups. But how do I do it in elliptic curve cryptogrpahy (ECC)?

Cramer-Shoup with cyclic groups

Following was taken from Wikipedia: https://en.wikipedia.org/wiki/Cramer%E2%80%93Shoup_cryptosystem

Key Generation

  • Alice generates an efficient description of a cyclic group $G$ of order $q$ with two distinct, random generators $g_1, g_2$.
  • Alice chooses five random values $({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z)$ from $\{0, \ldots, q-1\}$.
  • Alice computes $c = {g}_{1}^{x_1} g_{2}^{x_2}, d = {g}_{1}^{y_1} g_{2}^{y_2}, h = {g}_{1}^{z}$.
  • Alice publishes $(c, d, h)$, along with the description of $G, q, g_1, g_2$, as her public key. Alice retains $(x_1, x_2, y_1, y_2, z)$ as her secret key. The group can be shared between users of the system.


To encrypt a message $m$ to Alice under her public key $(G,q,g_1,g_2,c,d,h)$,

  • Bob converts $m$ into an element of $G$.
  • Bob chooses a random $k$ from $\{0, \ldots, q-1\}$, then calculates:
    • $u_1 = {g}_{1}^{k}, u_2 = {g}_{2}^{k}$
    • $e = h^k m$
    • $\alpha = H(u_1, u_2, e)$, where ''H''() is a universal one-way hash function (or a collision-resistant cryptographic hash function, which is a stronger requirement).
    • $v = c^k d^{k\alpha}$
  • Bob sends the ciphertext $(u_1, u_2, e, v)$ to Alice.


To decrypt a ciphertext $(u_1, u_2, e, v)$ with Alice's secret key $(x_1, x_2, y_1, y_2, z)$,

  • Alice computes $\alpha = H(u_1, u_2, e) \,$ and verifies that ${u}_{1}^{x_1} u_{2}^{x_2} ({u}_{1}^{y_1} u_{2}^{y_2})^{\alpha} = v \,$. If this test fails, further decryption is aborted and the output is rejected.
  • Otherwise, Alice computes the plaintext as $m = e / ({u}_{1}^{z}) \,$.

The decryption stage correctly decrypts any properly-formed ciphertext, since

$ {u}_{1}^{z} = {g}_{1}^{k z} = h^k \,$, and $m = e / h^k. \,$

If the space of possible messages is larger than the size of $G$, then Cramer–Shoup may be used in a hybrid cryptosystem to improve efficiency on long messages.


  • How to convert Cramer-Shoup into ECC?
  • How do I proof the security of ECC Cramer-Shoup?


Cramer, Ronald and Victor Shoup (1998). “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack.” Advances in Cryptology—CRYPTO'98, Lecture Notes in Computer Science, vol. 1462, ed. Hugo Krawczyk. Springer-Verlag, Berlin, 13–25.


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.