Efficient and Strongly Secure Dynamic Domain-Specific Pseudonymous Signatures for ID Documents

Abstract

The notion of domain-specific pseudonymous signatures (DSPS) has recently been introduced for private authentication of ID documents, like passports, that embed a chip with computational abilities. Thanks to this privacy-friendly primitive, the document authenticates to a service provider through a reader and the resulting signatures are anonymous, linkable inside the service and unlinkable across services. A subsequent work proposes to enhance security and privacy of DSPS through group signatures techniques. In this paper, we improve on these proposals in three ways. First, we spot several imprecisions in previous formalizations. We consequently provide a clean security model for dynamic domain-specific pseudonymous signatures, where we correctly address the dynamic and adaptive case. Second, we note that using group signatures is somehow an overkill for constructing DSPS, and we provide an optimized construction that achieves the same strong level of security while being more efficient. Finally, we study the implementation of our protocol in a chip and show that our solution is well-suited for these limited environments. In particular, we propose a secure protocol for delegating the most demanding operations from the chip to the reader.

A Appendix

1.1 A.1 A Proof of Knowledge of a Valid Certificate

Let $\mathtt {P}$ be the protocol Fig. 3 for proving knowledge of $(f,(A,x))$ such that $A=\big (g_1\cdot h^f\big )^{\frac{1}{\gamma +x}}$ and $\mathsf {nym}=h^f\cdot \mathsf {dpk}^x$. In [3], we show that (i) for an honest verifier, the transcripts $T$, $(R_1,R_2,R_3)$, $c$, $(s_f,s_x,s_a,s_b,s_d)$ can be simulated in an indistinguishable way, without knowing any valid certificate, and that (ii) there exists an extractor for the protocol $\mathtt {P}$.

Fig. 3.

The $\mathtt {P}$ protocol

1.2 A.2 Simulation of Signatures with Delegated Computation

We now adapt the proofs of our main scheme to the extended model of Sect. 4. We first simulate the $\mathtt {GetPreComp}$ step. In the seclusiveness proof, all signatures are honestly computed. In the unforgeability proof, if $i\ne \mathsf {i}$, then all signatures are honestly computed. If $i=\mathsf {i}$, then, given $\mathsf {H}$ (from the $\mathsf {DL}$ challenge), $A_\mathsf {i}$, $x_\mathsf {i}$ and $f_\mathsf {i}''$, $B$ picks $a,c,s_f,s_x,s_a,s_b\mathop {\leftarrow }\limits ^{\tiny {\$}}\mathbb {Z}_p$ and computes $B_1:=({A_\mathsf {i}}^{-x_\mathsf {i}}\cdot \mathsf {H}\cdot h^{f_\mathsf {i}''})^c\cdot A^{s_x}\cdot h^{a\cdot s_x-s_f-s_b}$ and $B_2:=h^{a\cdot c-s_a}$. In the cross-domain anonymity proof, the challenger honestly computes signatures for all users, but $\mathsf {i}$, for which signatures are simulated. Given $\mathsf {A}$ (from the $\mathsf {DDH}$ challenge) and $f_\mathsf {i}$, $B$ picks $\alpha \mathop {\leftarrow }\limits ^{\tiny {\$}}\mathbb {Z}_p$. The same $\alpha$ is used in each signature, for consistency. Then, for each signature query, $B$ picks fresh values $a,c,s_f,s_x,s_a,s_b$ and computes $B_1:=(\mathsf {A}^{-\alpha }\cdot h^{f_\mathsf {i}})^c\cdot T^{s_x}\cdot h^{-s_f-s_b}$ and $B_2:=h^{a\cdot c-s_a}$. (The simulation is done as if $A_\mathsf {i}:={g_1}^\alpha$.)

We now simulate the $\mathtt {Sign}'$ oracle (identically in the three proofs). $B$ retrieves $m,B_1,B_2,c,s_a,s_x,s_a,s_b$ from the $\mathtt {GetPreComp}$ step. Whatever $D$ is ($D$ may not equal $e(B_1,g_2)\cdot e(B_2,w)$), $B$ picks $s_d\mathop {\leftarrow }\limits ^{\tiny {\$}}\mathbb {Z}_p$, computes $T$, $R_1$ and $R_2$ as usual and sets $c$ as the random oracle’s value for the input $\mathsf {dpk}\Vert \mathsf {nym}\Vert T\Vert R_1\Vert R_2\Vert D\Vert m$. If $D$ is correct w.r.t. $B_1$ and $B_2$, then $B$ returns a valid signature. If not, then the signature is no longer valid but the response remains consistent w.r.t. $B_1$ and $B_2$.   $\square$