Editing Cramer–Shoup cryptosystem (section)

== The cryptosystem ==
Cramer–Shoup consists of three algorithms: the key generator, the encryption algorithm, and the decryption algorithm.

=== Key generation ===
* [[Alice and Bob|Alice]] generates an efficient description of a [[cyclic group]] <math>G</math> of order <math> q </math> with two distinct, random [[generating set of a group|generator]]s <math>g_1, g_2</math>.
* Alice chooses five random values <math>({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z)</math> from <math>\{0, \ldots, q-1\}</math>.
* Alice computes <math>c = {g}_{1}^{x_1} g_{2}^{x_2}, d = {g}_{1}^{y_1} g_{2}^{y_2}, h = {g}_{1}^{z}</math>.
* Alice publishes <math>(c, d, h)</math>, along with the description of <math>G, q, g_1, g_2</math>, as her [[public key]].  Alice retains <math>(x_1, x_2, y_1, y_2, z)</math> as her [[secret key]]. The group can be shared between users of the system.

=== Encryption ===
To encrypt a message <math>m</math> to Alice under her public key <math>(G,q,g_1,g_2,c,d,h)</math>,

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

=== Decryption ===
To decrypt a ciphertext <math>(u_1, u_2, e, v)</math> with Alice's secret key <math>(x_1, x_2, y_1, y_2, z)</math>,

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

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

: <math> {u}_{1}^{z} = {g}_{1}^{k z} = h^k \,</math>, and <math>m = e / h^k. \,</math>

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