Describe ROM-based DRE about otrv4

[tcz001]

ROM-based DRE

Random Oracle Model based Dual Receiver Encryption (hereinafter referred to DRE) is a hybrid public key encryption scheme which enables a ciphertext to be decrypted by two independent
receivers. Anyone who has the public keys can verify the plaintext equivalence without any of the secret keys.

The DRE scheme consists of three functions:

1. pk, sk = DRGen(), a key generation function
2. γ = DREnc(pk1, pk2, m), an encryption function
3. m = DRDec(pk1, pk2, sk_i, γ), a decryption function

DRE in OTRv4 consists of the Cramer-Shoup cryptosystem and a NIZKPK.

[tcz001]

Setup

In the Cramer-Shoup scheme, we have a group G with prime order q. In OTRv4, we choose Ed25519 as our group G.

We select the following two element (in bytes encode of ed25519) as generators from G:
g1 = 662e951dcd1ed163d4b75e8206a34f5fbdfe0c5f394d35b63f7855bdeb938a46
g2 = e11ef81fc08128bf0965b3b9ea00d17f751d1dca18170432144661f4aca4f0fd

Regarding Ed25519 group operations, we use * to represent PointAddition, and ^ to represent ScalarMultiplication in the following definitions.

[tcz001]

Dual Receiver Key Generation: DRGen()

As in Creamer Shoup scheme.

1. Randomly choose x1, x2, y1, y2, z in Zq.
2. Compute group elements c = g1^x1 * g2^x2, d = g1^y1 * g2^y2, h = g1^z.
3. The public key is pk = {c, d, h} and the secret key is sk = {x1, x2, y1, y2, z}.

[tcz001]

Dual Receiver Encryption: DREnc(pk_1, pk_2, m)

pk_1 and pk_2 are the Cramer-Shoup public key of two receivers.
m is the message to be encrypted using a random AES-OCB key K.
K is itself encrypted twice using Cramer-Shoup (once for each public key).
NIZKPK of plaintext equality ensures that both Cramer-Shoup ciphertexts are encryptions of the same K.

To do the DREnc, we need to:

1. Choose K, k_1, k_2 randomly from Zq
2. For i ∈ {1,2} encrypt K with k_i and pk_i, use CramerShoup:
   1. pk_i is interpreted as {c_i,d_i,h_i}
   2. Compute u_1i = g1^k_i, u_2i = g2^k_i, e_i = (h_i^k_i) * K
   3. Compute α_i = decodeIntEd25519_big-endian(SHA-3_256(u_1i, u_2i, e_i))
   4. Compute v_i = (c_i^k_i) * (d_i^(k_i * α_i))
3. The message m is encrypted using φ = AEncK(m), where AEncK denotes an encryption under key K using an implementation-defined cryptosystem with IND-CCA2 security (ciphertext indistinguishability-adaptive chosen cipher text security), such as crypto secretbox from the NaCl library, or AES-256 in OCB or an equivalent unpatented mode. // TODO: find out which one is the best.
4. The NIZKPK is produced by:
   1. For i ∈ {1,2}, generate random value t_i in Zq. Compute T_1i = g1^t_i, T_2i = g2^t_i, T_3i = (c_i * (d_i^α_i))^t_i and T_4 = (h_1^t_1) / (h_2^t_2) // TODO: how to do division
   2. Compute L = SHA-3_256(g1 ∥ g2 ∥ q ∥ pk_1 ∥ pk_2 ∥ u_11 ∥ u_21 ∥ e_1 ∥ v_1 ∥ α_1 ∥ u_12 ∥ u_22 ∥ e_2 ∥ v_2 ∥ α_2 ∥ T_11 ∥ T_21 ∥ T_31 ∥ T_12 ∥ T_22 ∥ T_32 ∥ T_4 ∥ Φ). Φ is any session-specific protocol state available to both parties in the higher-level protocol, and H2 is a cryptographic hash function modeled by a random oracle. // TODO: find out the session-specific protocol state.
   3. For i ∈ {1,2} compute n_i = t_i - L * k_i (mod q) // TODO: how to do subtraction

Result: γ = (u_11, u_21, e_1, v_1, u_12, u_22, e_2, v_2, L, n_1, n_2, φ).

[claucece]

Dual Receiver Decryption: DRDec(pk_1, pk_2, sk_i, γ):

1. Parse γ to retrieve components γ = (u_11, u_21, e_1, v_1, u_12, u_22, e_2, v_2, L, n_1, n_2, φ).
2. Verify NIZKPK,
   1. for j ∈ {1,2}:
      1. α'_j = SHA256(u1_j ∥ u_2j ∥ e_j)
      2. T'_1j = (g1^n_j) * (u_1j^L)
      3. T'_2j = (g2^n_j) * (u_2j^L)
      4. T'_3j = (c_j * (d_j^a'_j))^n_j * (v_j^L)
      5. T'_4 = ((h1^n1) /( h2^n2)) * ((e1 / e2)^L)
   2. Compute L' = SHA-3_256(g1 ∥ g2 ∥ q ∥ pk_1 ∥ pk_2 ∥ u_11 ∥ u_21 ∥ e_1 ∥ v_1 ∥ α'_1 ∥ u_12 ∥ u_22 ∥ e_2 ∥ v_2 ∥ α'_2 ∥ T'_11 ∥ T'_21 ∥ T'_31 ∥ T'_12 ∥ T'_22 ∥ T'_32 ∥ T'_4 ∥ Φ).
   3. Verify L ≟ L'
3. Verify Cramer-Shoup ((u_1i^x_1i) * (u_2i^x_2i)) * (((u_1i^y_1i) * (u_2i^y_2i))^α'_i) ≟ v_i
4. Recover secret key by K = (e_i )/ (u1_i^z_i).

Receiver can now recover m by ADecK(φ), where ADecK refers to the decryption routine under key K corresponding to AEncK.

[claucece]

TO DO:

• Make this human readable but keep somewhere else this explanation: clarified on the draft.
• Be consistent in notation.
• Find out how to do subtraction and division: We can use inverse of a point to do this.
• Do we really need an appropriate implementation-defined cryptosystem with IND-CCA2 security? We need to encrypt "I"||"R"||g1^i||g1^r. // @tcz001 OK
• Find an appropriate implementation-defined cryptosystem with IND-CCA2 security: secretbox from NaCl is pretty straightforward. Secretbox uses XSalsa20 and Poly1305 to encrypt and authenticate messages with secret-key cryptography. AES-256 in OCB can be used freely in software not developed and not sold inside the US or licensed under the GNU General Public License: XSalsa20 and Poly1305.
• Find a one-way hash function: As stated by Bruce Schneier in Applied Criptography (pag. 455), the SHA family seems like a good choice. Choosing here SHA-3_256. It will be target collision resistant. At least 'kill SHA1 with fire and use SHA3', as stated here.
• Find out what a hash function is modeled by a random oracle. It will be: collision-resistance, preimage resistance and have the pseudorandom function property, as defined here by Koblitz and Menezes. Chosing SHA-3_256, following definitions on Introduction to Modern Cryptography (pag. 178) by Katz and Lindell.
• Explain SHA-3 properties.
• Find out how to slice the output of SHA-3_256.
• Find out the session-specific protocol state: not using, is that ok?

The ≟ denotes 'questioned equal to', following Minkowski's question mark function. Means 'not yet demonstrated to be equal to'.

[juniorz]

Another TODO:

Quoting "Improved Techniques for Implementing Strongly Deniable Authenticated Key Exchanges", in ROM DRE section:

All hash functions used in this paper output values in Zq.

We need to define how to decode an array of bytes (the output of the hash) into a (big) number and reduce it modulo q. Ed448 reference implementation uses a barret-reduction for this, and assumes the array of bytes is a number in a specific endianness (I can't remember which).

[tcz001]

About the hash function output:

for ed25519, we can use the decodeint function to deserialize a 256 bit length data, which will convert the SHA3-256 output into a scalar in Zq.