Describe ROM-based Auth about otrv4

[tcz001]

ROM-based Authentication

Random Oracle Model based Authentication (hereinafter referred as Auth) is a NIZKP scheme with a signature proof of knowledge of the following statement:

Given a message m signed, the prover P knows one of the secret key a of three Diffie-Hellman public keys {A_1,A_2,A_3}, which means P knows: g^a == A_1 OR g^a == A_2 OR g^a == A_3

The Auth scheme consists of two functions:

1. σ = Auth(A_i,a_i,{A_1,A_2,A_3},m), an authentication function
2. Verif({A_1,A_2,A_3},σ,m), a verification function

[tcz001]

Setup

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

In NIZKPK of Auth, We reuse one previous defined generator in Cramer-Shoup of DRE (in bytes encode of ed25519):
g = 662e951dcd1ed163d4b75e8206a34f5fbdfe0c5f394d35b63f7855bdeb938a46

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

[tcz001]

Authentication: Auth(a_i,{A_1,A_2,A_3},m):

a_i is one of the secret key of the three public keys {A_1,A_2,A_3}.
m is the message to be signed.

1. Choose t_1, c_2, c_3, r_2, r_3 randomly from Zq.
2. Compute T_1 = g^t_1
3. Compute T_2 = (g^r_2) * (A_2^c_2), and T_3 = (g^r_3) * (A_3^c_3)
4. Compute c = SHA3-256(g ∥ q ∥ A_1 ∥ A_2 ∥ A_3 ∥ T_1 ∥ T_2 ∥ T_3 ∥ m ∥ Φ)
5. Compute c_1 = c - c_2 - c_3 (mod q)
6. Compute r_1 = t_1 - c_1 * a_1

Result: σ = (c_1, r_1, c_2, r_2, c_3, r_3)

[tcz001]

Verification: Verif({A_1,A_2,A_3},σ,m)

1. Parse σ to retrive components (c_1, r_1, c_2, r_2, c_3, r_3).
2. Compute c' = SHA3-256(g ∥ q ∥ A_1 ∥ A_2 ∥ A_3 ∥ (g^r_1) * (A_1^c_1) ∥ (g^r_2) * (A_2^c_2) ∥ (g^r_3) * (A_3^c_3) ∥ m ∥ Φ).
3. Check if c' ≟ c_1 + c_2 + c_3 (mod q).