1 Introduction
2 Completeness and unforgeability
-
\({\mathcal {G}}\) takes security parameter \(1^\lambda \) as input, and returns a secret key \(\text {sk}\) (to be given to the signer only) and a corresponding public key \(\text {PK}\) (known to all parties in the system).
-
\({\mathcal {S}}\) and \({\mathcal {U}}\) are in fact interactive algorithms where signer \({\mathcal {S}}\) has private input \(\text {sk}\) and public input the public message \({\overline{m}}\) (with length polynomial in the security parameter \(\lambda \)), while user \({\mathcal {U}}\) has private input message \(m\) (also with length polynomial in the security parameter \(\lambda \)) and public input \(\text {PK}\) and \({\overline{m}}\). \({\mathcal {S}}\) and \({\mathcal {U}}\) interact with each other over a public communication channel. After the interaction, \({\mathcal {S}}\) outputs either \(\textsf {success}\) or \(\textsf {fail}\), and \({\mathcal {U}}\) outputs either a signature \(\sigma \) or \(\bot \). \({\mathcal {U}}\)’s output is private. \({\mathcal {S}}\)’s output is public.
-
\({\mathcal {V}}\) takes as input a public key \(\text {PK}\), public message \({\overline{m}}\), a message \(m\) and a signature \(\sigma \), and outputs either \(\textsf {accept}\) or \(\textsf {reject}\). This verification can be performed by any party.
3 The two faces of blindness
3.1 Blindness
3.2 Message indistinguishability
-
Let \(E_{{k_{ }}}()\) be a pseudo-random function (it could be a block cipher or a hash function keyed by \({k_{ }}\)).
-
Let m be a message whose length is a multiple of the block length of this underlying block cipher, and write \(m = m_1 \,\Vert \,\ldots \,\Vert \,m_z\).
-
Compute the tag t for message m by using \(E_{{k_{ }}}()\) in CBC mode: define \(t_1 = E_{{k_{ }}}(m_1)\), let \(t_{i+1} = E_{{k_{ }}}(m_{i+1} \oplus t_i)\) and let \(t = t_z\). We write \(t = T_{{k_{ }}}(m)\) Again (for simplicity) tags are assumed to be exactly as long as a single block.
-
Compute the key stream blocks \(A_i\) by encrypting a counter with \({k_{ }}\), i.e., \(A_i =E_{{k_{ }}}(i)\).
-
The full CCM ciphertext is obtained by XOR-ing \(m \,\Vert \,t\) with \(A_0 \,\Vert \,\ldots \,\Vert \,A_z\).
3.3 Message hiding
3.4 Signature unlinkability
-
\(m_0' = h_2(m_0) r_0^e \bmod n\) (and that it is computed by \({\mathcal {U}}_0\)),
-
\(m_1' = h_2(m_1) r_1^e \bmod n\) (and that it is computed by \({\mathcal {U}}_1\)),
-
\(\sigma _0 = h_2(m_0)^d \bmod n\) and \(\sigma _1 = h_2(m_1)^d \bmod n\) given in the order defined by a random bit b.
3.5 Message indistinguishability and signature unlinkability
4 Conclusions
-
\(A \rightarrow B\) and \(B \rightarrow C\) implies \(A \rightarrow C\).
-
\(A \mid \!\!\!-\;B\) and \(B \rightarrow C\) implies \(A \mid \!\!\!-\;C\).
-
\(A \rightarrow B\) and \(B \mid \!\!\!-\;C\) implies \(A \mid \!\!\!-\;C\).