\section{Introduction}
\label{sec:intro}

The relevance of a precise measurement of single top production at hadron colliders
was already stressed  in several papers in the recent years
~\cite{Tait:1999cf}.
A well known peculiarity of the process is actually the fact that it offers
the unique possibility of a direct measurement of the $Wtb$ coupling $V_{tb}$,
thus allowing severe tests of the conventionally assumed properties
of the CKM matrix in the Minimal Standard Model; for a very accurate
review of the topics we defer to~\cite{Alwall:2006bx}.

For the specific purpose of a "precise" determination of $V_{tb}$,
two independent requests must be met. The first one is that of a
correspondingly "precise" experimental  measurement of the process. For
the $t$-channel case on which we shall concentrate in this paper the CMS
study~\cite{Pumplin:2002vw}  concludes that, with $10$ fb$^{-1}$ of
integrated luminosity, one could be able to reduce the (mostly systematic)
experimental uncertainty of the cross section below the ten percent
level (worse uncertainties are expected for the two other processes, the
$s$-channel and the associated $Wt$ production, whose cross section is
definitely smaller than that of the $t$-channel).\\
The second request is that of a similarly
accurate theoretical prediction of the observables of the process.
In this respect, one must make the precise statement that, in order to cope with the
goal of measuring $V_{tb}$ at the few (five) percent level, a complete NLO
calculation is requested. In the SM this has been done for the QCD component
of the $t$-channel, resulting in a relatively small (few percent)
effect~\cite{Stelzer:1997ns}.
The electroweak effects have been computed very recently at the
complete one loop level within the MSSM for the dominant $ub\to dt$ component of the process
(to be defined in Section~\ref{sec:section2})~\cite{Beccaria:2006ir}.\\
One conclusion was that the genuine SUSY effect, for a set on mSUGRA benchmark
points, was systematically modest, roughly at the one-two percent level.
The SM contribution was computed in a preliminary way, i.e. only including
the soft photon radiation to achieve cancellation of infrared singularities,
ignoring the potentially relevant hard photon contribution.
Actually, the main purpose of~\cite{Beccaria:2006ir} was that of investigating the possible
existence and size of genuine supersymmetric effects, that would be
essentially unaffected  by the SM QED contribution.
In this approximate approach, the one-loop SM contribution turned out to be
sizable, of roughly ten percent on the total rate. This contribution should be
considered as a perfectly known term, to be included in the theoretical
expression of the rate and compared with the corresponding experimental
measurement to extract the precise value of the $Wtb$ coupling $V_{tb}$.\\
In fact, from the negative (for what concerns supersymmetric searches) result
that the $t$-channel rate is not sensitive to genuine mSUGRA MSSM effects,
adding the extra known feature that NLO QCD effects are small , of the order
of five percent, and well under
control~\cite{QCDNLO}~\cite{QCDNLODecay}~\cite{Frixione:2005vw},
one concludes that an extremely precise theoretical determination of
the process would be possible, provided that a rigorous electroweak
one-loop description were given. This requires two different steps:
first, an extension of the calculation of ~\cite{Beccaria:2006ir}
to the seven remaining $t$-channel processes since the final $dt$ state is only the numerically dominant one.
Second, the additional calculation of the complete QED effect,
including properly hard photon radiation.
This is precisely the aim of this paper, whose goal will be that of offering
a clean theoretical expression to be used for a significant measurement of
$V_{tb}$.\\
Technically speaking, this paper is organized as follows. In Section
\ref{sec:section2} the definition of the eight considered
processes will be given, and the main tasks that were fulfilled
to perform a complete one loop electroweak calculation will be indicated.
Since the problems to be solved were practically identical with
those already met in~\cite{Beccaria:2006ir}, our description will
be whenever possible quick and essential.
In Section \ref{sec:QED}, we shall expose the new
calculation of the complete QED
effects.
In Section \ref{sec:SUSYQCD} we briefly discuss the one loop SUSY QCD effects that we have recomputed
from scratch in the same scheme adopted for the electroweak corrections.
In Section \ref{sec:observable} we shall define the considered observables
and show the results
of our calculation, particular emphasis being given to the value of the
total $t$-channel rate.
A few conclusions will be drawn in the final Section \ref{sec:concl}.

\section{The $t$-channel processes at one electroweak loop}
\label{sec:section2}
The complete description of the $t$-channel  involves at
partonic level four  sub-processes for single $t$ production:  $ub\to td$,
$\bar{d}b\to t\bar{u}$,  $cb\to ts$,  $\bar{s}b\to t \bar{c}$,
and the related four for the single $\bar{t}$ production.\\
The starting point is the cross section for the $ub\to td$ process
with the complete set of one loop electroweak corrections (in the MSSM and SM).
The $\mathcal{O}(\alpha)$ corrections to the (unpolarized) differential cross section of this process read:
\begin{equation}
d \sigma^{\mbox{\tiny ew}}_{ub\to td} =  \frac{dt}{64 \pi s^2} \sum_{\mbox{\tiny spin}}
2  \mathfrak{Re} \{ \mathcal{M}^{0 ~*} \mathcal{M}^1  \}
\end{equation}
where $\mathcal{M}^0$ is the tree level contribution to the amplitude of the partonic process $ub \to dt$ while
$\mathcal{M}^1$ describes the EW one loop contribution to the same amplitude. The Mandelstam variables are defined as:
\begin{eqnarray}
s&=&(p_b+p_u)^2\nonumber\\
t &=& (p_b-p_t)^2 \\
u &=& (p_b-p_d)^2\nonumber
\end{eqnarray}
The analytical  expression for $\mathcal{M}^{0}$ is available in
literature (see for instance~\cite{Beccaria:2006ir}).
 $\mathcal{M}^{1}$  has been generated with the help of \verb|FeynArts|~\cite{FeynArts}, the algebraic reduction of the
one loop integrals is performed with the help of \verb|FormCalc|~\cite{FormCalc} and
the scalar one loop integrals are  numerically evaluated using \verb|LoopTools|~\cite{LoopTools}.
We treat UV divergences using dimensional reduction while IR
singularities are parametrized giving a small mass $m_\gamma$ to the photon. The masses of the light quarks
are used as regulators of the collinear singularities and are set to zero elsewhere.  \\
UV divergences are cured renormalizing the parameters and the wavefunctions appearing in $\mathcal{M}^{0}$. In our case we have to renormalize the wavefunction of the
external quarks, the mass of the W boson, the electroweak mixing  angle and the electric charge. We use the on shell scheme decribed in Ref.~\cite{DennerHab}.
This scheme uses the fine structure constant evaluated in the Thomson limit as input parameter. In order to avoid large logarithms arising from the runnning
of $\alpha$ to the electroweak scale $M_W$, we slightly modify this scheme using as input parameter the Fermi constant $G_F$. We consistently change the definition
of the renormalization constant of the fine structure constant following the guidelines of Ref.~\cite{WjetProd}. \\

\noindent
The unpolarized differential cross section for the process  $\bar d b \to \bar u t$ can be obtained from that of the process $ub\to td$ by crossing:
\begin{equation}
d \sigma^{\mbox{\tiny ew}}_{\bar d b \to \bar u t} = \frac{dt}{64 \pi s^2} \sum_{\mbox{\tiny spin}}
2  \mathfrak{Re} \{ \mathcal{M}^{0 ~*}(s\to u,~u\to s)  \mathcal{M}^1(s\to u,~u\to s)  \}   .
\end{equation}
For the $\bar{t}$ production the cross sections can be calculated using the
identities
\bqa
d \sigma^{\mbox{\tiny ew}}_{u b \to t d} &=& d \sigma^{\mbox{\tiny ew}}_{\bar{u}  \bar{b} \to \bar{d} \bar{t}}\nonumber\\
d \sigma^{\mbox{\tiny ew}}_{\bar{d} b \to t \bar{u}} &=& d \sigma^{\mbox{\tiny ew}}_{d  \bar{b} \to u \bar{t}}
\eqa
while the  processes involving the second generation $c,s$ and $\bar{s}, \bar{c}$
quarks can be computed from the previous, simply replacing the masses of the external particles
(and some masses in the loop corrections).

\section{QED effects}
\label{sec:QED}
In order to obtain physically meanigful observables one has to include the differential cross section for
the process of $t$-channel single top production associated with the
emission of a  photon integrated over the whole photonic phase space.
So we have to consider the partonic processes
$ub\to td \gamma$, $\bar{d}b\to t\bar{u} \gamma$,  $cb\to ts \gamma$,  $\bar{s}b\to t \bar{c} \gamma$,
and the related four for the single $\bar{t}$ production.  \\
The unpolarized differential cross section of these processes has been obtained using two different procedures. In the first
approach the amplitude has been generated and squared using \verb|FeynArts| and  \verb|FormCalc| while in the second one
the complete matrix element has been calculated with the help of FORM. The two methods are in mutual agreement. \\
The phase space integration of the aforementioned differential cross section is singular in the region in which the photon is soft
and in the region in which it is collinear to a massless quark.
According to KLN theorem~\cite{KLN} IR singularities and the
collinear singularities
related to the final state radiation cancel in sufficiently inclusive
observables while the collinear singularities related to initial state
radiation
have to be absorbed in the redefinition of the Parton Distribution
Functions (PDF). In order to
regularize these divergences
we use two different procedures: the Dipole Subtraction method and
the Phase Space Slicing method. \\
In the Subtraction approach one has to  add and subtract
to the squared amplitude
an auxiliary function with the  same asymptotic behaviour and
such that it can be analytically integrated
over the photon phase space. Among the different choices we
use the function quoted in Ref.~\cite{Dipole}.
In this Reference
explicit expression for the subtraction function and for its
analytical integration is obtained using
the so called Dipole Formalism~\cite{DipoleQCD}. \\
The idea behind the Phase Space Slicing approach is
to isolate the singular region of the phase
space introducing a cut off on the energy of the
photon ($\Delta E = \delta_s \sqrt{s} /2$) and on the
angle between the photon and
the massless quarks ($\delta_c$). In the regular region the phase space integration can be done numerically while in the singular region
it can be performed analytically provided that the cutoffs are small enough. The form of the differential cross section in the
singular region is universal and its explicit expression in the soft (collinear) region  can be
found in Ref.~\cite{DennerHab}~(\cite{WjetProd}). \\
As can be inferred from Fig.~\ref{fig:2} the two methods are in good  numerical agreement.

\section{One loop SUSY QCD corrections}
\label{sec:SUSYQCD}

The one loop SUSY QCD corrections to $t$-channel single top production have been computed at LHC in Ref.~\cite{Zhang:2006cx}.
We include these corrections re-computing them from scratch following the guidelines described in Sec.~\ref{sec:section2}.
The only difference is that, following a standard procedure in SUSY QCD, we treat UV divergences using dimensional regularization.
Moreover in  this case we have to renormalize
only the wavefunctions of the squarks since the other renormalization constant do not
have $\mathcal{O}(\alpha_s)$ corrections. These corrections are IR safe.

\section{Observable quantities}
\label{sec:observable}

The differential hadronic cross section reads
\begin{eqnarray}
d \sigma (S) = \sum_{\mbox{\tiny{(q, q')}}}  \int_{\tau_0}^1 d \tau
&& \frac{dL_{qb}}{d \tau}           \left(
                                 d \sigma^{\mbox{\tiny ew}}_{q b \to q' t}(s)          +
                                 d \sigma^{\mbox{\tiny ew}}_{q b \to q' t \gamma}(s)    +
                                 d \sigma^{\mbox{\tiny SQCD}}_{ q b \to q' t }(s) \right)  \nonumber \\
&&  \frac{dL_{\bar q \bar b}}{d \tau} \left(
                                 d \sigma^{\mbox{\tiny ew}}_{\bar q \bar b \to \bar q' \bar t}(s)          +
                                 d \sigma^{\mbox{\tiny ew}}_{\bar q \bar b \to \bar q' \bar t \gamma}(s)    +
                                 d \sigma^{\mbox{\tiny SQCD}}_{\bar q \bar b \to \bar q' \bar t }(s)     \right)
\end{eqnarray}
Where $(q,q')=(u,d),(c,s),(\bar d, \bar u), (\bar s, \bar d)$. The differential luminosity has been defined according to Ref.~\cite{PinkBook}
while $\tau_0 = m^2_t / S$ and $s = \tau S$. $ d \sigma^{\mbox{\tiny ew}}_{X}$ ($d \sigma^{\mbox{\tiny SQCD}}_{X}$)
are the $\mathcal{O}(\alpha^3)$ (SUSY QCD) corrections to  the differential cross section  of the process $X$.

As pointed out in Sec.~\ref{sec:QED}, initial state Collinear Singularities  are not cancelled in the sum of virtual and real corrections and they are absorbed in the
definition of the PDF. We use the $\overline{\mbox{MS}}$ factorization scheme at the scale $\mu_F = m_t$.  Concerning the choice of the parton distributions set,
we follow ~\cite{WjetProd}. The calculation of the full $\mathcal{O}(\alpha)$ corrections to any hadronic observable must include
QED effects in the DGLAP evolution equations. Such effects are taken into account in the MRST2004QED PDF~\cite{Martin:2004dh} which are NLO QCD.
Since our computation is leading order QCD, we use the LO set CTEQ6L since the QED effects are known to be small~\cite{Roth:2004ti}.

\subsection{Numerical Results}
\label{subsec:num}

In this subsection we present our numerical results.
We define $M_{inv}$ as the invariant mass of the (anti)top quark and of the light
quark in  the final  state. Also, we denote by $p_T$ the transverse momentum of the  (anti)top quark.
We consider as physical observables the transverse momentum distribution
$\frac{d \sigma}{dp_{T}}$, the invariant mass distribution $\frac{d
 \sigma}{dM_{\mbox{\tiny inv}}}$  and two integrated observables derived from
the previous: the integrated transverse momentum distribution, defined as the
integral of
$\frac{d \sigma}{dp_{T}}$ from a minimum $p_T^{\rm min}$ up to infinity:
\begin{equation}
\sigma(p_T^{\rm min}) = \int_{p_T^{\rm min}}^{\infty} ~\frac{d \sigma}{d p'_T} d p'_T
\end{equation}
and the cumulative invariant mass distribution
$\sigma(M^{\rm max}_{\mbox{\tiny inv}})$, defined as the integral of the invariant mass distribution from
the production threshold up to $M^{\rm max}_{\mbox{\tiny inv}}$:

\begin{equation}
\sigma(M^{\rm max}_{\mbox{\tiny inv}}) =
\int_{\tau_0}^{M^{\rm max}_{\mbox{\tiny inv}}} ~\frac{d \sigma}{d M'_{\mbox{\tiny inv}}} d M'_{\mbox{\tiny inv}}
\end{equation}

For each observable we present the plots for the LO and NLO curves and for the
percentage effect of the NLO corrections to the observable $ (\delta = \frac{NLO
  - LO}{NLO} \times 100)$. Apart from the Standard Model results, we
analyzed several supersymmetric mSUGRA benchmark points: in the figures we
present the numerical results for the two representative
ATLAS DC2 mSUGRA benchmark points SU1 and SU6~\cite{DC2};
in the other cases the results are similar.
The SU1 and SU6 input parameters generate a moderately light supersymmetric
scenarios, where the masses of the supersymmetric particles are below the $1~TeV$:
the two physical spectra are quite similar, characterized by relatively
heavy squark sector ($562-631~GeV$ for the lightest squark in SU1 and SU6
respectively), a light neutralino and a light chargino state. The typical
masses for the supersymmetic Higgs are of order of $400-500~GeV$.
The main difference between the two points is the value of $\tan \beta$
input parameter: $10$ for SU1 and $50$ for SU6.
\subsubsection{SM Results}

In the Standard Model framework the behaviour of the four observables is shown
in Figures \ref{Fig:pT_SM}, \ref{Fig:M_distr_SM}, \ref{Fig:pT_int_SM} and
\ref{Fig:M_int_SM}: the left panels report the LO and NLO curves, and the right
panels show the relative percentage effect of the one loop electroweak
corrections: as one can see the curves for the NLO and LO are
almost overlapping, and the global $\mathcal{O}(\alpha^3)$ NLO effect is rather
small. This is particularly evident considering the plot for the cumulative
invariant mass distribution, where the percentage effect saturate to the
$\simeq 1.5 \% $ for $M_{\mbox{\tiny inv}} > 1500~GeV$.

\subsubsection{MSSM Results}

The following figures show the analogous
results for the transverse momentum distribution
$\frac{d \sigma}{dp_{T}}$, the invariant mass distribution $\frac{d
  \sigma}{dM_{\mbox{\tiny inv}}}$,  the integrated $p_T$ ditribution $\sigma(p_T^{\rm min})$
and the cumulative invariant mass distribution
$\sigma(M^{\rm max}_{ \mbox{\tiny inv} })$ for the SU1
(Fig.~\ref{Fig:pT_SU1},~\ref{Fig:M_distr_SU1},~\ref{Fig:pT_int_SU1},~\ref{Fig:M_int_SU1}) and for
the SU6  (Fig.~\ref{Fig:pT_SU6},~\ref{Fig:M_distr_SU6},~\ref{Fig:pT_int_SU6},~\ref{Fig:M_int_SU6}) benchmark points.
In the MSSM cases the NLO is defined as the sum of the electroweak part
$\mathcal{O}(\alpha^3)$ and of the SUSY QCD part; in each figure we show in the panel
{\bf (a)}  the behaviour of the observable at LO and NLO;
in {\bf (b)}  the global NLO  effect (where "global" means $\mathcal{O}(\alpha^3)$ plus SUSY QCD);
in {\bf(c)} and {\bf{(d)}} the separate percentage contributions of
the $\mathcal{O}(\alpha^3)$ and SUSY QCD parts respectively.\\
A first comment that can be drawn from the inspection of the plots is that the
$t$-channel process is very weakly sensitive to the presence of the
supersymmetric particle in the loops. The difference with the Standard Model case, below
the percent level, is negligible for both the mSUGRA benchmark points, without
appreciable differences between the two sets.\\
The plots for percentage effect of the SUSY QCD corrections only
(the {\bf (d)} panel in
Fig. ~\ref{Fig:pT_SU1},~\ref{Fig:M_distr_SU1},~\ref{Fig:pT_int_SU1},~\ref{Fig:M_int_SU1} for SU1 and ~
\ref{Fig:pT_SU6},~\ref{Fig:M_distr_SU6},~\ref{Fig:pT_int_SU6},~\ref{Fig:M_int_SU6} for SU6)
show that the contribution of diagrams with virtual squark and gluinos
is systematically small, below the $1 \%$ level, in agreement  with Ref.~\cite{Zhang:2006cx}.
The same conclusion holds for the pure electroweak supersymmetric contribution,
being the $\mathcal{O}(\alpha^3)$ effect due almost completely to the Standard Model part.

\subsubsection{PDF uncertainties}
An important source of theoretical uncertainty is given by the contribution
of the parametric errors associated with the parton densities. This
could become particularly relevant for single top channels, due to the
presence of an initial state $b$ quark,
whose distribution function is strictly related to the gluon distribution.
We have studied the impact of such uncertainties on the
transverse momentum distribution $\frac{d \sigma}{dp_{T}}$ and
on the invariant mass distribution $\frac{d \sigma}{dM_{\mbox{\tiny inv}}}$
by using the PDF sets MRST2001E and CTEQ61E as in the LHAPDF
package~\cite{lhapdf}. For each bin in the histograms the maximum
and minimum values are calculated starting
from the central value according to the formula
$\sigma({\rm central}) \pm 1/2 \sqrt{\sum_{i=20(15)}
(\sigma(2i - 1) - \sigma(2i))^2}$,
according to the prescription of Ref.~\cite{pdfpage}.
The results are shown in Figure~\ref{fig:pdfunc}.
The spread of the predictions obtained with the MRST set displays a
relative deviation of about 2\% or less, increasing on the large scale tails
of the distributions (where the cross section is however very small),
while the CTEQ set gives a larger
uncertainty, of the order of 3-4\%.
This is due to different values of the tolerance parameter~\cite{Tpdf}, the
latter being defined as the allowed maximum of the $\Delta\chi^2$ variation
w.r.t. the parameters of the best PDFs fit.
Conservatively, we can associate to our predictions an uncertainty due
to the present knowledge of parton densities of about 3\%. It is also worth
noting that the uncertainties obtained according to such a procedure
are of purely experimental origin only ({\it i.e.} as due to the systematic
and statistical errors of the data used in the global fit), leaving aside
other sources of uncertainty of theoretical origin.

\section{Conclusions}
\label{sec:concl}

We have computed in this paper the complete one-loop electroweak effect on
various observables in the MSSM. The calculation has fully included QED
effects. The overall result is that the one-loop effect is small,
of a  positive few percent in the total rate that we have considered
as the first realistically measurable quantity.
Technically speaking, this small number arises from a
competition of negative weak contributions and positive QED terms.
In the considered mSUGRA symmetry breaking scheme, the genuine SUSY
effect in the considered benchmark points is systematically modest,
at most of a one percent size. The values that we have obtained e.g. for
the total rate should still be modified by the additional NLO QCD
contribution. The latter is known, small and theoretically safe and could
be easily added to our calculation.
It will appear in a forthcoming paper that will provide an expression
for the overall single top production at LHC, including the already
existing calculations for the associated $tW$ production (our paper and the QCD
ones).
We have also given an estimate of the parametric errors associated with
the present knowledge of the parton densities. The distributions studied
in this paper are affected by a few percent PDF uncertainty. It is
worth saying that this uncertainty is expected to be lowered once
the LHC data will become available.
In conclusion, a precise measurement of the $t$-channel rate appears as a
perfect way to determine the value of the $V_{tb}$ coupling,
both within the SM
and within the MSSM with mSUGRA symmetry breaking. We cannot exclude, though,
that for different symmetry breaking mechanisms the genuine SUSY effect is
more sizable. This question, that is beyond the purposes of this preliminary
paper, remains open and, in our opinion,
would deserve a special dedicated rigorous analysis.

\vspace{1cm}
\noindent
{\bf Acknowledgements} \\
We are gratefull to T.~Hahn an S.~Pozzorini for helpful discussions. E.M. is indebted with S.~Dittmaier for
valuable suggestions on the Dipole Subtraction Formalism.


\section*{References}

\bibitem{WW30}  V. Weisskopf und E. Wigner,  Z. Phys. \textbf{63}, 54 (1930).

\bibitem{D27} P.A.M. Dirac, Proc. Roy. Soc. (London), ser. A \textbf{114}, 243
(1927).

\bibitem{MCA89}  P.W. Milonni, R.J. Cook, and  J.R. Ackerhalt, Phys. Rev. A \textbf{40}, 3764 (1989).

\bibitem{MS77} B. Misra and E.C.G. Sudarshan,  J. Math. Phys \textbf{18}, 756 (1977).

\bibitem{CSM77} C.B. Chiu,  E.C.G. Sudarshan, and B. Misra,  Phys. Rev. D \textbf{16}, 520 (1977).

\bibitem{Sch97}  L.S. Schulman, J. Phys. A: Math. Gen. \textbf{30}, L293 (1997).

\bibitem{H81}  M. Hillery,  Phys. Rev. A, \textbf{24}, 933 (1981).

\bibitem{FP98}  P. Facchi and S. Pascazio, Phys. Lett. A  \textbf{241}, 139 (1998).

\bibitem{SG91} K.M. Sluis and E.A. Gislason, Phys. Rev. A \textbf{43}, 4581
(1991).

\bibitem{Kh90} L.A. Khalfin, Usp. Fiz. Nauk \textbf{160}, 185 (1990)
[Sov. Phys. Usp. \textbf{33}, 868 (1990)].

\bibitem{L52} F. Low,  Phys. Rev. \textbf{88}, 53 (1952).

\bibitem{AE75} L. Allen and J.H. Eberly.
\textit{Optical Resonance and Two-Level Atoms} (NY, John Wiley and
Sons, 1975).

\bibitem{M69} B. R. Mollow, Phys. Rev. \textbf{188}, 1969 (1969).

\bibitem{IH+90}  W.M. Itano, D.J. Heinzen, J.J. Bollinger, and D.J. Wineland,
Phys. Rev. A \textbf{41}, 2295 (1990).

\end{thebibliography}

\end{document}


\section{Introduction}
In 1998, Blaze, Bleumer  and Strauss \cite{BBS98} proposed a
cryptographic
  primitive  where a semi-trusted proxy is given some information
  that
  allows   turning \mbox{Alice}'s signature on a   message into Bob's
  signature on the same message. These \emph{proxy re-signatures}
   (PRS) -- not to be confused with proxy signatures \cite{MUO96} --  require that the proxy
   be unable to
  sign on behalf of
    Alice or Bob on its own. The last few years saw a renewed
    interest   in proxy re-cryptography
    \cite{AFGH05,AFGH05bis,AH05,GA,Hoh06,HRSV07,CH07}. \\
 \indent
This paper presents the first constructions of \emph{multi-use}
\emph{unidirectional} proxy re-signature wherein the proxy can only
translate signatures in one direction and messages can be re-signed
a polynomial number of times.  Our constructions are efficient  and
demand new (but falsifiable) Diffie-Hellman-related intractability
assumptions in bilinear map groups. One of our contributions is a
secure scheme in the standard   model (\emph{i.e.} without resorting
to the random oracle model).

\medskip
\noindent\textsc{Related work.}  Alice -- the delegator -- can
easily designate a proxy translating   signatures computed using
Bob's secret key  -- the delegatee -- into one that are valid w.r.t.
her public key by storing her secret key at the proxy. Upon
receiving Bob's signatures, the proxy can check them and re-sign the
message using Alice's private key. The problem with this approach is
that the proxy can sign arbitrary messages on behalf of Alice. Proxy
re-signatures aim at securely enabling the delegation of signatures
without fully trusting the proxy. They are related to proxy
signatures, introduced in  \cite{MUO96} and revisted in
\cite{DI,BPW03,MOY04}, in that any PRS can be used to implement a
proxy signature mechanism but
the converse is not necessarily true. \\
\indent In 1998, Blaze \emph{et al.}  \cite{BBS98} gave the first
example of PRS  where signing keys remain hidden from the proxy. The
primitive was formalized in 2005 by Ateniese and Hohenberger
\cite{AH05}  who pinned down useful properties that can be expected
from proxy re-signature schemes. \\
\begin{figure}[!h]
\begin{enumerate}
\item \textsf{Unidirectional:} re-signature keys can only be used for
  delegation in one direction;
\item \textsf{Multi-use:} a message can be re-signed a polynomial number of
  times;
\item \textsf{Private Proxy:} re-signature keys can be kept secret by
  an honest proxy;
\item \textsf{Transparent:} a user may not even know that a proxy exists;
\item \textsf{Unlinkable:} a re-signature cannot be linked to the one
  from which it was generated;
\item \textsf{Key optimal:} a user is only required to store a
  constant amount of secret data;
\item \textsf{Non-interactive:} the delegatee does not act in the
  delegation process;
\item \textsf{Non-transitive:} the proxy cannot re-delegate signing rights;
\end{enumerate}
\label{fig:properties}\vspace{-0.8 cm}
\end{figure}
\indent Blaze \emph{et al.}'s construction is \emph{bidirectional}
(\emph{i.e.} the
  proxy information allows  ``translating'' signatures in either direction) and \emph{multi-use} (\emph{i.e.} the
  translation of signatures can be performed in sequence and multiple
  times by distinct proxies without requiring the intervention of
  signing entities). Unfortunately, Ateniese and Hohenberger \cite{AH05}
  pinpointed a flaw in the latter scheme: given a
  signature/re-signature pair, anyone can deduce the re-signature key that has
  been used in the delegation  (\emph{i.e.}
  the \emph{private proxy} property is not satisfied). Another issue in \cite{BBS98} is that
  the proxy and the delegatee can collude to expose the delegator's
  secret. \\
  \indent
To overcome these limitations, Ateniese and Hohenberger proposed two
constructions based on bilinear maps. The first one
is
a quite simple multi-use, bidirectional protocol built on
Boneh-Lynn-Shacham (BLS) signatures \cite{BLS}. Their second scheme
is unidirectional (the design of such a scheme was an
open problem raised in \cite{BBS98}) but single-use.
It involves two different signature algorithms: \emph{first-level}
signatures   can  be translated by the proxy whilst
\emph{second-level} signatures   cannot. A slightly less efficient
variant
was also suggested to ensure the privacy of re-signature keys kept
at the proxy. The security of all schemes was analyzed in the random
oracle model \cite{BR}. \\ \vspace{-0.3 cm}

\noindent\textsc{Our contributions.} Ateniese and Hohenberger left
as  open challenges the design of  multi-use  unidirectional
 systems and that of secure schemes in the
standard security model. The present paper solves both problems:
\begin{itemize}
\item we present a simple and efficient system (built  on the short signature put forth by Boneh \emph{et
al.} \cite{BLS}) which is secure in the random oracle
  model under a reasonable extension of the Diffie-Hellman  assumption;
\item using an elegant technique due to Waters \cite{Wat05},
    the scheme is easily modified so as to achieve security in the standard
  model. To the best of our knowledge, this actually provides the
  first unidirectional PRS that dispenses with random oracles
    and thereby improves a recent  bidirectional construction
  \cite{SCWL}.
\end{itemize}
 Both
proposals additionally preserve the privacy of proxy keys (with an
improved efficiency w.r.t. \cite{AH05} in the case of the first
one). They  combine almost all of the above properties. As  in
prior unidirectional schemes, proxies are not completely transparent
since signatures have different shapes and lengths  across successive levels.
 The size of our signatures actually grows linearly
with the number of past translations: signatures at level $\ell$
(i.e. that have been translated $\ell-i$ times if the original
version was signed at level $i$) consist of about $2\ell$ group
elements. In spite of this blow-up, we retain  important benefits:
\begin{itemize}
\item signers may want to tolerate a limited number (say $t$) of signature translations for specific messages.
Then, if at most $L$  translations are permitted in the global system,
users can directly generate a signature at level $L-t$.
\item the conversion of a $\ell^{\textrm{th}}$ level signature
is indistinguishable from one generated  at level $\ell+1$ by the
second signer. The original signer's identity is moreover
perfectly hidden and the verifier only needs the new signer's
public key.
\end{itemize}
\indent  The simplicity of our schemes makes them attractive for
applications that motivated the search for multi-use unidirectional
systems in \cite{AH05}. One of them was to provide a proof that a
certain path was taken in a directed graph: for instance, U.S.
customs only need one public key (the one of the immigration agent
who previously validated a signature on an e-passport) to make sure
that a foreign visitor legally entered the country and went through
the required checkpoints. Another application was the conversion of
certificates where valid signatures for untrusted public keys can be
turned into signatures that verify under trusted keys. As
exemplified in \cite{AH05}, unidirectional schemes are quite
appealing for converting certificates between {\it ad-hoc} networks:
using the public key of network B's certification authority (CA),
the CA of network A can non-interactively compute a translation key
and set up a proxy converting certificates from network B within its
own domain without having to rely on untrusted nodes of B. \\
\vspace{-0.3 cm}

\noindent\textsc{Roadmap.} In the forthcoming sections, we recall
the syntax of  unidirectional PRS schemes and the security model
in section \ref{sec:model}.  Section
 \ref{sec:bilinear} explains which algorithmic assumptions we need. Section \ref{BLS-Version}    describes our
random-oracle-using scheme.
 Section \ref{Waters-version} details how to get rid of the random
oracle idealization.

\vspace{-0.2 cm}

\section{Model and Security Notions}\label{sec:model}

We first recall the syntactic definition of unidirectional PRS
schemes from \cite{AH05}.
\begin{definition}[Proxy Re-Signatures]
A (unidirectional) proxy re-signature (PRS) scheme for $N$ signers
and $L$ levels (where $N$ and $L$ are both polynomial in the
security parameter $\lambda$) consists of a tuple of (possibly
randomized)
  algorithms
$(\mathsf{Global\textrm{-}Setup},\mathsf{Keygen},\mathsf{ReKeygen},\mathsf{Sign},\mathsf{Re\textrm{-}Sign},\mathsf{Verify})$
where:
\begin{description}
 \item[$\mathsf{Global\textrm{-}Setup}(\lambda)$:] is a randomized algorithm (possibly run by a trusted party) that takes as   input a
 security parameter $\lambda$ and produces  a set of system-wide public
 parameters $\mathsf{cp}$.
 \item[$\mathsf{Keygen}(\mathsf{cp})$:] is a probabilistic algorithm that, on
 input of public parameters $\mathsf{cp}$, outputs  a signer's
 private/public key pair $(sk,pk)$.
 \item[$\mathsf{ReKeygen}(\mathsf{cp},pk_i,sk_j)$:] on input of
 public parameters $ \mathsf{cp}$, signer $i$'s public key $pk_i$
 and signer $j$'s private key $sk_j$, this (ideally non-interactive) algorithm outputs a
 re-signature key $R_{ij}$ that allows translating $i$'s
 signatures into  signatures in the name of $j$.
 \item[$\mathsf{Sign}(\mathsf{cp},\ell,sk_i,m)$:] on input of
 public parameters $\mathsf{cp}$, a message $m$, a private key
 $sk_i$ and an integer
 $\ell \in \{1,\ldots,L\}$, this (possibly probabilistic)
 algorithm outputs a signature $\sigma$ on behalf of signer $i$ at
 level $\ell$.
  \item[$\mathsf{Re\textrm{-}Sign}(\mathsf{cp},\ell,m,\sigma,R_{ij},pk_i,pk_j)$:]
  given common   parameters $\mathsf{cp}$,  a  level $\ell< L$ signature $\sigma$ from signer
  $i\in \{1,\ldots,N\}$ and a re-signature key $R_{ij}$, this
  (possibly randomized) algorithm first checks that  $\sigma$ is valid w.r.t $pk_i$. If yes, it outputs a
  signature $\sigma'$ which verifies at level  $\ell+1$   under public key $pk_j$.
 \item[$\mathsf{Verify}(\mathsf{cp},\ell,m,\sigma,pk_i )$:]  given public parameters
 $\mathsf{cp}$, an integer $\ell \in \{1,\ldots,L\}$, a message
 $m$, an alleged signature $\sigma$ and a public key $pk_i$, this deterministic
 algorithm outputs $0$ or $1$.
\end{description} For all security parameters $\lambda \in \mathbb{N}$ and
 system-wide   parameters $\mathsf{cp}$ output by
 $\mathsf{Global\textrm{-}Setup}(\lambda)$, for all couples of
  private/public key pairs $(sk_i,pk_i)$, $(sk_j,pk_j)$ produced by
 $\mathsf{Keygen}(\mathsf{cp})$, for any $\ell \in \{1,\ldots,L\}$ and
  message $m$, we should have
\begin{eqnarray*}
&
\mathsf{Verify}(\mathsf{cp},\ell,m,\mathsf{Sign}(\mathsf{cp},\ell,sk_i,m),pk_i
)= 1; & \\
&\mathsf{Verify}(\mathsf{cp},\ell,m,\mathsf{ReSign}(\mathsf{cp},\ell,m,\mathsf{Sign}(\mathsf{cp},\ell,sk_i,m),\mathsf{ReKeygen}(\mathsf{cp},pk_i,sk_j)),pk_j
) = 1.&\\
\end{eqnarray*}
\end{definition}
To lighten notations, we  sometimes omit to explicitly include
public parameters $\mathsf{cp}$ that are part of the input of all
but one algorithms. \\
\indent The security model of \cite{AH05} considers the following
two orthogonal notions termed \emph{external} and \emph{insider
security}.

\begin{description}
\item[External security:] is the security against adversaries
outside the system (that differ from the proxy and delegation
partners). This notion demands that the next
probability be a negligible   function of the security parameter
$\lambda$:
\begin{eqnarray*}
\textrm{Pr}[ \{pk_i,sk_i) & \leftarrow &  \mathsf{Keygen}(\lambda)
\}_{i\in [1,N]},\\ && (i^\star,L,m^\star,\sigma^\star) \leftarrow
\mathcal{A}^{\mathcal{O}_{Sign}(.),\mathcal{O}_{Resign}(.)}(\{pk_i\}_{i\in
[1,N]}): \\ & & \mathsf{Verify}(L,pk_{i^\star},m^\star,\sigma^\star)
\wedge (i^\star,m^\star) \not\in Q ]
\end{eqnarray*}
where $\mathcal{O}_{Sign}(.)$ is an oracle taking as input a
message and an index  $i \in \{1,\ldots,N\}$  to return a first
level signature $\sigma \leftarrow \mathsf{Sign}(1,sk_i,m)$; the
oracle $\mathcal{O}_{Resign}(.)$ takes as input indices $i,j \in
\{1,\ldots,N\}$ and a level $\ell$ signature $\sigma$ and returns
the output of $\sigma' \leftarrow
\mathsf{Re\textrm{-}Sign}(\ell,m,\sigma,\mathsf{ReKeygen}(pk_i,sk_j))$;
and $Q$ denotes the set of (signer,message) pairs $(i,m)$ queried
to $\mathcal{O}_{Sign}(.)$ or such that a tuple $(?,j,i,m)$, with
$j \in \{1,\ldots,N\}$, was queried to $\mathcal{O}_{Resign}(.)$.
 This notion only
makes sense if re-signing keys are kept private by the proxy. \\
\vspace{-0.3 cm}
\item[Internal security:] The second security notion considered in
\cite{AH05} strives to protect users, as much as possible, against
dishonest proxies and colluding delegation partners. Three security
guarantees should be ensured. \\ \vspace{-0.3 cm}
\begin{itemize}
\item[1.] {\bf Limited Proxy security:} this notion captures the
proxy's inability to sign messages on behalf of the delegatee or to
create
 signatures for the delegator unless messages were   first signed by
one of the latter's delegatees.  Formally, we consider a game where
adversaries have all re-signing keys but are denied access to
signers' private keys. The following probability should be
negligible:
\begin{eqnarray*}
\textrm{Pr}\big[ \{pk_i,sk_i)  \leftarrow  \mathsf{Keygen}(\lambda)
\}_{i\in [1,N]},~ \{R_{ij}   \leftarrow  \mathsf{ReKeygen}(pk_i,sk_j)
\}_{i,j \in [1,N]},  & &     \\  (i^\star,L,m^\star,\sigma^\star) \leftarrow
\mathcal{A}^{\mathcal{O}_{Sign}(.,.)}
\big(\{pk_i\}_{i\in [1,N]},  \{R_{ij}
\}_{i,j \in [1,N]}  \big): & & \\
\mathsf{Verify}(L,pk_{i^\star},m^\star,\sigma^\star) \wedge m^\star
\not\in Q \big]
\end{eqnarray*}
where $\mathcal{O}_{Sign}(.,.)$ is an oracle taking as input a
message and an index $i \in \{1,\ldots,N\}$ to return a first level
signature $\sigma \leftarrow \mathsf{Sign}(1,sk_i,m)$   and $Q$ stands for the set of
messages $m$ queried to the signing oracle. \\ \vspace{-0.3 cm}
\item[2.] {\bf Delegatee Security:} informally, this notion
protects the delegatee from a colluding delegator and proxy. Namely,
the delegatee is assigned the index $0$. The adversary is provided
with an oracle returning first level signatures on behalf of $0$ and
 is also granted access to re-signature keys\footnote{In non-interactive schemes, the adversary can compute those keys herself from $pk_0$ and $sk_i$,
 with $i\neq 0$,  and the definition
can be   simplified. In the general case, they remain part of the adversary's input.} $R_{0i}$ for all $i\neq 0$
(but not $R_{i0}$ for any $i$). Her probability of success
\begin{eqnarray*}
\textrm{Pr}\big[&&\{pk_i,sk_i)  \leftarrow  \mathsf{Keygen}(\lambda)
\}_{i\in [0,N]},   \\ & & \{R_{ij}   \leftarrow  \mathsf{ReKeygen}(pk_i,sk_j)
\}_{i \in  \{0,\ldots,N\},j \in \{1,\ldots,N\}}  \\ & &  (L,m^\star,\sigma^\star) \leftarrow
\mathcal{A}^{\mathcal{O}_{Sign}(0,.)}
\big(pk_0,\{pk_i,sk_i\}_{i\in [1,N]},\{R_{ij}
\}_{i \in  \{0,\ldots,N\},j \in \{1,\ldots,N\}} \big):  \\
& &  \mathsf{Verify}(L,pk_{0},m^\star,\sigma^\star) \wedge m^\star
\not\in Q ~\big],
\end{eqnarray*}
where  $Q$ is the set of messages queried to $\mathcal{O}_{Sign}(0,.)$, should be negligible. \\ \vspace{-0.3 cm}
\item[3.] {\bf Delegator Security:} this notion captures that a
collusion between the delegatee and the proxy should be harmless for
the honest delegator.  Namely, we consider a target delegator with
index $0$. The adversary is given private keys of all other signers
$i \in \{1,\ldots,N\}$ as well as {\it all} re-signature keys
including $R_{i0}$ and $R_{0i}$ for $i \in \{1,\ldots,N\}$. A
signing oracle $\mathcal{O}_{Sign}(0,.)$ also provides her with
first level signatures for $0$. Yet, the following  probability
should be negligible,
\begin{eqnarray*}
\textrm{Pr}\big[ \{pk_i,sk_i)  \leftarrow  \mathsf{Keygen}(\lambda)
\}_{i\in [0,N]},  \{R_{ij} \leftarrow  \mathsf{ReKeygen}(pk_i,sk_j)
\}_{i,j \in [0,N]}, & & \\  (1,m^\star,\sigma^\star) \leftarrow
\mathcal{A}^{\mathcal{O}_{Sign}(0,.)}
\big(pk_0,\{pk_i,sk_i\}_{i\in [1,N]},  \{R_{ij}\}_{i,j \in [0,N]},   \big): & & \\
\mathsf{Verify}(1,pk_{0},m^\star,\sigma^\star) \wedge m^\star
\not\in Q \big],
\end{eqnarray*}
  meaning   she has little chance of framing user $0$ at the first level.
\end{itemize}
\end{description}
 An important difference between   external   and   limited proxy
 security should be underlined. In the former, the attacker is
 allowed to obtain signatures on the target message $m^\star$ for
  signers other than $i^\star$. In the latter, the target message
 cannot be queried for signature at all (knowing   all proxy keys, the attacker would trivially win
 the game otherwise).

\section{Bilinear Maps and Complexity Assumptions}\label{sec:bilinear}

\noindent\textsc{Bilinear  groups.} Groups $(\mathbb{G},\mathbb{G}_T)$ of prime
order $p$ are called \emph{bilinear map groups} if there is a
mapping $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ with the following
properties:
\begin{enumerate}
\item[1.] bilinearity: $e(g^a,h^b)=e(g,h)^{ab}$ for any $(g,h)\in \mathbb{G}\times \mathbb{G}$ and $a,b\in \mathbb{Z}$;
\item[2.] efficient computability for any  input pair;
\item[3.] non-degeneracy: $e(g,h)\neq 1_{\mathbb{G}_T}$ whenever $g,h\neq 1_{\mathbb{G}}$.
\end{enumerate}
\indent In these groups, we  assume the hardness of the well-known
Computational Diffie-Hellman (CDH) problem which is to compute
$g^{xy}$ given $g^x$ and $g^y$.

\medskip
\noindent\textsc{Flexible Diffie-Hellman problems.} Our signatures
rely on new   generalizations of the
  Diffie-Hellman problem. To motivate  them, let us
first recall the definition of the \emph{2-out-of-3 Diffie-Hellman}
problem \cite{KJP06}.

\begin{definition}
In a prime order group $\mathbb{G}$, the {\bf
$\mathbf{2}$-out-of-$\mathbf{3}$ Diffie-Hellman } problem
($2$-$3$-CDH) is, given $(g,g^a,g^b)$, to find a pair $(C,C^{ab})
\in \mathbb{G} \times \mathbb{G}$ with $C \neq 1_{\mathbb{G}}$.
\end{definition}
We introduce a potentially harder version of this problem that we
call $1$-Flexible Diffie-Hellman problem:

\begin{definition}
The {\bf $\mathbf{1}$-Flexible Diffie-Hellman} problem ($1$-FlexDH)
is, given $(g,A=g^a,B=g^b) \in \mathbb{G}^3$, to find a triple
$(C,C^a,C^{ab}) \in (\mathbb{G}\backslash\{1_{\mathbb{G}}\})^3$.
\end{definition}
The unforgeability of our multi-use unidirectional proxy
re-signatures is proved assuming the intractability of a relaxed
variant of this problem where   more flexibility is permitted in the
choice of the base $C$ for the Diffie-Hellman computation.
\begin{definition}
The {\bf $\mathbf{\ell}$-Flexible Diffie-Hellman} problem
($\ell$-FlexDH) is, given $(g,A=g^a,B=g^b) \in \mathbb{G}^3$, to find a
$(2\ell+1)$-uple
$$(C_1,\ldots,C_\ell,D_1^a,\ldots,D_\ell^a,D_{\ell}^{ab}) \in \mathbb{G}^{2\ell+1}   $$
where $\log_g(D_j) = \prod_{i=1}^j \log_g(C_i) \neq 0$   for $j \in
\{1,\ldots\ell\}$.
\end{definition}
A given  instance  has many publicly verifiable solutions: a
candidate $2\ell+1$-tuple
$(C_1,\ldots,C_\ell,D_1',\ldots,D_\ell',T)$ is  acceptable if
$e(C_1,A)=e(D_1',g)$, $e(D_j',g)=e(D_{j-1}',C_j)$ for
$j=2,\ldots,\ell$ and $e(D_{\ell}',B)=e(T,g)$. The $\ell$-FlexDH
assumption is thus  falsifiable according to  Naor's classification
 \cite{Naor}.

 In generic groups, the general intractability result given by
   theorem $1$ of \cite{KJP06} by Kunz-Jacques and Pointcheval implies the generic hardness of
$\ell$-FlexDH. For completeness, appendix \ref{generic} gives an
adaptation of this result   in generic \emph{bilinear} groups.

\begin{remark}
The \emph{knowledge-of-exponent assumption} (KEA1) \cite{BP04} was
introduced in 1991 by Damg\aa{}rd \cite{Dam91}. Roughly speaking,
KEA1 captures the intuition  that any algorithm which, given elements $(g,g^x)\in\mathbb{G}^2$, computes a pair $(h,h^x)\in\mathbb{G}^2$ must
``know'' $\log_{g}(h)$. Under KEA1, the intractability of the
$\ell$-Flexible Diffie-Hellman problem  is easily seen to be boil
down to the Diffie-Hellman assumption. Given $(g,g^a)$, an
adversary outputting $(C_1,D_1^a)=(C_1,C_1^a)$ necessarily
``knows'' $t_1=\log_g C_1$ and thus also
$(C_2,C_2^a)=(C_2,(D_2^a)^{1/t_1})$ as well as $t_2=\log_g C_2$,
which in turn successively yields logarithms of
$C_3,\ldots,C_{\ell}$. Although the KEA1 assumption is inherently
non-falsifiable, it   holds in  generic groups \cite{Dent06,AF07}
and  our results can be seen as resting on the combination
CDH+KEA1.
\end{remark}

\medskip
\noindent\textsc{Modified Diffie-Hellman problem.} The second
assumption that we need is that the CDH problem $(g^a,g^b)$ remains
hard even when $g^{(a^2)}$ is available.
\begin{definition}
The {\bf modified  Computational Diffie-Hellman } problem (mCDH) is,
given $(g,g^a,g^{(a^2)},g^b)\in \mathbb{G}^4$, to compute $g^{ab} \in \mathbb{G}$.
\end{definition}
In fact, we
  use an  equivalent formulation of
the problem which is to find $h^{xy}$ given $(h,h^x,h^{1/x},h^{y})$
(the equivalence is readily observed by  defining $g=h^{1/x}$,
$x=a$, $y=b/a$).

\section{A Multi-Hop Scheme in the Random Oracle
Model} \label{BLS-Version}

   To provide a
better intuition of the underlying idea of our scheme, we first
describe its single-hop version before extending it into a
multi-hop
system. \\
\indent Our approach slightly differs from the one in \cite{AH05}
where signers have a ``strong'' secret and a ``weak'' secret that
are respectively used to produce  first and second level signatures.
In our scheme, users have a single secret but first and second level
signatures retain different shapes. Another
difference is that our re-signature algorithm is probabilistic. \\
\indent   We exploit the idea that, given $g^b  \in \mathbb{G}=\langle g
\rangle$ for some $b\in \mathbb{Z}$, one can hardly generate a
Diffie-Hellman triple $(g^a,g^b,g^{ab})$ without knowing the
corresponding exponent $a$ \cite{Dam91}. A valid BLS signature
\cite{BLS} $(\sigma=H(m)^x,X=g^x)$  can be blinded into
$(\sigma'_1,\sigma_2')=(\sigma^t,X^t)$ using a random exponent $t$.
An extra  element $g^t$   then serves as evidence that
$(\sigma'_1,\sigma_2')$ actually hides a valid pair. This technique
can be iterated several times  by adding two group elements at each
step.   To translate signatures from signer $i$ to signer $j$, the
key idea is to have  the proxy perform an appropriate change of
variable involving the
 translation key during the blinding.

 \indent The scheme is obviously not strongly
unforgeable in the sense of \cite{ADR} (since all but first level
signatures can be publicly re-randomized) but this ``malleability''
of signatures is not a weakness whatsoever. It  even turns out to be
a desirable feature allowing for the unlinkability of translated
signatures w.r.t. original ones.  \\ \vspace{-0.4 cm}

\subsection{The Single Hop Version}

In this scheme, signers' public keys consist of a single group
element $X=g^x \in \mathbb{G}$. Their well-formedness is thus efficiently
verifiable by the certification authority that just has to check
their membership in $\mathbb{G}$. This already improves \cite{AH05} where
public keys $(X_1,X_2)=(g^x,h^{1/x}) \in \mathbb{G}^2$ ($g$ and $h$ being
common parameters) must be validated by testing whether
$e(X_1,X_2)=e(g,h)$.
\begin{description}
\item[\textsf{Global-setup}$(\lambda)$:]   this algorithm
chooses bilinear   groups $(\mathbb{G},\mathbb{G}_T)$ of prime order
$p>2^{\lambda}$. A generator $g \in \mathbb{G}$ and a hash function
$H:\{0,1\}^* \rightarrow \mathbb{G}$ (modeled as a random oracle in the
security proof) are also chosen. Public parameters only consist of
$\mathsf{cp}:=\{\mathbb{G},\mathbb{G}_T,g,H \}.$
\item[\textsf{Keygen}$(\lambda)$:] user $i$'s public key is set as $X_i=g^{x_i}$ for a random $x_i \sample \mathbb{Z}_p^*$.
\item[\textsf{ReKeygen}$(x_j,X_i)$:]  this algorithm outputs the proxy key
$R_{ij}=X_i^{1/x_j}=g^{x_i/x_j}$  which allows
  turning signatures from $i$ into signatures from $j$. \\
\vspace{-0.3 cm}
\item[\textsf{Sign}$(1,x_i,m)$:] to sign   $m \in \{0,1\}^*$ at
level $1$, compute $\sigma^{(1)}=H(m)^{x_i} \in \mathbb{G}$. \\
\vspace{-0.3 cm}
\item[\textsf{Sign}$(2,x_i,m)$:] to sign $m \in \{0,1\}^*$ at level $2$,    choose  $t \sample \mathbb{Z}_p^*$ and
compute
 \begin{eqnarray} \label{yes-ca-marche-1}
 \sigma^{(2)}=(\sigma_0,\sigma_1,\sigma_2)=(H(m)^{x_i t}
,X_i^t,g^t).
 \end{eqnarray}
\item[\textsf{Re-Sign}$(1,m,\sigma^{(1)},R_{ij},X_i,X_j)$:] on input of   $m \in \{0,1\}^*$, the re-signature key
$R_{ij}=g^{x_i/x_j}$, a signature $\sigma^{(1)} \in \mathbb{G}$ and   public
keys  $X_i,X_j$, check the validity of $\sigma^{(1)}$ w.r.t signer
$i$ by testing $e(\sigma^{(1)},g)=e(H(m),X_i)$.
  If valid, $\sigma^{(1)}$ is turned into a signature on behalf of $j$ by choosing $ t \sample \mathbb{Z}_p^*$ and computing
\begin{eqnarray*}
 \sigma^{(2)}=(\sigma_0',\sigma_1',\sigma_2')=({\sigma^{(1)}}^{t}, X_i^t,R_{ij}^t)
  = ( H(m)^{x_it},X_i^t,g^{tx_i/x_j} )
\end{eqnarray*}
  If we set $\tilde{t}=tx_i/x_j$, we have
  \begin{eqnarray} \label{yes-ca-marche-2}
  \sigma^{(2)}=(\sigma_0',\sigma_1',\sigma_2')=(H(m)^{ x_j  \tilde{t} }
 ,X_j^{\tilde{t}},g^{\tilde{t}}).
 \end{eqnarray}
\item[\textsf{Verify}$(1,m,\sigma^{(1)},X_i)$:] this algorithm accepts if $e(\sigma^{(1)},g)=e(H(m),X_i)$.  \\
\vspace{-0.3 cm}
\item[\textsf{Verify}$(2,m,\sigma^{(2)},X_i)$:]   a second level signature
$\sigma^{(2)}=( \sigma_0,\sigma_1,\sigma_2)$ is  accepted for the
public key $X_i$ if the following conditions are true.
\begin{eqnarray*} \label{validity-21-BLS}
e(\sigma_0,g) = e(\sigma_1,H(m)) \qquad e(\sigma_1,g) =
e(X_i,\sigma_2)
\end{eqnarray*}

\end{description}
Relations (\ref{yes-ca-marche-1}) and (\ref{yes-ca-marche-2}) show
that translated signatures have exactly the same distribution  as
signatures directly produced by signers at level $2$. \\
\indent In comparison with the only known  unidirectional PRS with
private re-signing keys (suggested in section 3.4.2 of \cite{AH05}),
this one features shorter second level signatures that must include
a Schnorr-like \cite{Sch} proof of knowledge in addition to $3$
group elements in \cite{AH05}. On the other hand, signatures of
\cite{AH05} are strongly unforgeable unlike ours. \\
\indent It is also worth mentioning that the above scheme only
requires the $1$-Flexible Diffie-Hellman assumption which is more
classical than the general $\ell$-FlexDH.

\subsection{How to Obtain Multiple Hops} \label{sec:ellscheme}

The above construction can be scaled up into a multi-hop PRS
scheme if we iteratively apply the same idea several times. To
prevent the linkability of signatures between successive levels
$\ell+1$ and $\ell+2$, the re-signature algorithm performs a
re-randomization using random exponents $r_1,\ldots,r_{\ell}$.

\begin{description}
\item[\textsf{Sign}$(\ell+1,x_i,m)$:] to sign   $m \in \{0,1\}^*$ at  the
$(\ell+1)^{\textrm{th} }$ level,   user $i$ chooses
$(t_1,\ldots,t_{\ell}) \sample (\mathbb{Z}_p^*)^{\ell}$ and outputs
$\sigma^{(\ell+1)}=(\sigma_0,\ldots,\sigma_{2\ell}) \in
\mathbb{G}^{2\ell+1}$ where
\begin{eqnarray*}
\sigma_0 = H(m)^{x_i t_1 \cdots t_\ell}, \qquad
\left\{
\begin{array}{ll}
\sigma_k  =  g^{x_i t_1 \cdots t_{\ell+1-k}}  & \textrm{ for } k \in
\{1,\ldots, \ell\} \\
\sigma_k  =  g^{t_{k-\ell}} &  \textrm{ for } k \in
\{\ell+1,\ldots,2\ell\}.
\end{array}
   \right.
\end{eqnarray*}
\item[\textsf{Re-Sign}$(\ell+1,m,\sigma^{(\ell+1)},R_{ij},X_i,X_j)$:] on input of a message
  $m \in \{0,1\}^*$, the re-signature key $R_{ij}=g^{x_i/x_j}$, a
  valid
  $(\ell+1)^{\textrm{th}}$
  level signature
  \begin{eqnarray*}
  \sigma^{(\ell+1)} &=& (\sigma_0,\ldots,\sigma_{2\ell}) \\
  &=& (H(m)^{x_i t_1\cdots t_{\ell}}, g^{x_i t_1 \cdots t_{\ell}}, g^{x_i t_1 \cdots t_{\ell-1}}, \ldots,
  g^{x_it_1},g^{t_1},\ldots,g^{t_{\ell}} )  \in \mathbb{G}^{2\ell+1}
  \end{eqnarray*} and  public keys $X_i,X_j$,
  check the validity of $\sigma$ under $X_i$. If valid, $\sigma$  is turned into a $(\ell+2)^{\textrm{th}}$  level signature on behalf of $j$ by
  drawing $(r_0,r_1,\ldots,r_{\ell}) \sample (\mathbb{Z}_p^*)^{\ell+1}$ and
  computing $\sigma^{(\ell+2)}=(\sigma_0',\ldots,\sigma_{2\ell+2}') \in \mathbb{G}^{2\ell+3}$ where
\begin{eqnarray*}
\sigma_0'  =  \sigma_0^{r_0 \cdots r_{\ell}} ~\textrm{ and }~
\left\{
\begin{array}{ll}
\sigma_{k}' =  \sigma_k^{r_0 \cdots r_{\ell+1-k}} &  \textrm{ for } k \in
\{1,\ldots, \ell\} \\
\sigma_{\ell+1}'  =  X_i^{r_{0}}  & \\
\sigma_{\ell+2}'  =  R_{ij}^{r_{0}} & \\
\sigma_k'  =  \sigma_{k-2}^{r_{k-\ell-2}} &  \textrm{ for } k \in
\{\ell+3,\ldots,2\ell+2\}.\\
\end{array}
 \right.
\end{eqnarray*}
If we define $\tilde{t}_0=r_0x_i/x_j$ and $\tilde{t}_k=r_k t_k$
for $k=1,\ldots,\ell$, we  observe that
$$\sigma^{(\ell+2)} =(H(m)^{x_j \tilde{t}_0 \tilde{t}_1\cdots \tilde{t}_{\ell}}, g^{x_j \tilde{t}_0 \tilde{t}_1 \cdots \tilde{t}_{\ell}}, g^{x_j \tilde{t}_0 \tilde{t}_1 \cdots \tilde{t}_{\ell-1}}, \ldots,
  g^{x_j \tilde{t}_0},g^{\tilde{t}_0},\ldots,g^{\tilde{t}_{\ell}} )  \in \mathbb{G}^{2\ell+3} $$
\item[\textsf{Verify}$(\ell+1,m,\sigma^{(\ell+1)},X_i)$:]  the validity  of $\sigma^{(\ell+1)}=(\sigma_0,\ldots,\sigma_{2\ell}) \in
  \mathbb{G}^{2\ell+1}$ at level $(\ell+1)$  is checked by testing if these  equalities  simultaneously hold:
\begin{eqnarray*}
e(\sigma_0,g) & = & e(H(m),\sigma_1), \qquad e(\sigma_{\ell},g) = e(X_i,\sigma_{\ell+1}) \\
e(\sigma_k,g) & = & e(\sigma_{k+1},\sigma_{2\ell-k+1}) \hbox{ for
} k \in
 \{1,\ldots,\ell-1\}
\end{eqnarray*}

\end{description}
\vspace{-0.4 cm}

\subsection{Security}

\begin{theorem} \label{BLS-proof}
The $L$-level scheme  is a secure unidirectional proxy re-signature
under the $(L-1)$-FlexDH and mCDH assumptions in the random oracle
model.
\end{theorem}

\begin{proof}

\noindent\textit{Limited proxy security.} We show that an
adversary $\mathcal{A}_1$ with advantage $\varepsilon$ implies an algorithm
$\mathcal{B}_1$
 solving an $(L-1)$-FlexDH instance $(g,A=g^a,B=g^b)$ with
probability $O(\varepsilon/q_s)$, where $q_s$ is the number of
signing queries made by $\mathcal{A}_1$.

\begin{description}
\item[System parameters:]   $\mathcal{A}_1$ is challenged on parameters
  $\{\mathbb{G},\mathbb{G}_T,g,\mathcal{O}_H\}$ where $\mathcal{O}_H$ is the
  random oracle controlled by the simulator $\mathcal{B}_1$.

\item[Public key generation:] when $\mathcal{A}_1$ asks for the creation of user $i
  \in \{1,\ldots,N\}$, $\mathcal{B}_1$ responds with a newly generated public key
  $X_i=A^{x_i}=g^{ax_i}$, for a random $x_i \sample \mathbb{Z}_p^*$, which
  virtually defines user $i$'s private key as $ax_i$.  For all pairs $(i,j)$,
  re-signature keys $R_{ij}$ are calculated as $R_{ij}=g^{x_i/x_j}=g^{ax_i/ax_j}$. \\ \vspace{-0.3 cm}
\item[Oracle queries:] $\mathcal{A}_1$'s queries are tackled with as follows.
  Following a well-known technique due to Coron \cite{Cor00}, a
  binary coin $c\in \{0,1\}$ with expected value $1-\zeta \in [0,1]$ decides whether
  $\mathcal{B}_1$ introduces the challenge in the output of the random
  oracle or an element of known signature. For the optimal value of
  $\zeta$, this introduces the  loss factor $O(q_s)$ in the success
  probability. \\ \vspace{-0.3 cm}
\begin{itemize}
\item[$\bullet$] {\it Random oracle queries}: To respond to these queries,
  $\mathcal{B}_1$ maintains a list (referred to as the $H$-List) of tuples
  $(m,h,\mu,c)$ as follows:
\begin{enumerate}
\item If the query $m$ already appears in the $H$-List, then $\mathcal{B}_1$ returns
  $h$;
\item Otherwise, $\mathcal{B}_1$ generates a random bit $c$ such that
  $\Pr[c=0] = \zeta$;
\item It picks uniformly at random $\mu \in \mathbb{Z}_p^*$ and computes $h=g^{\mu}$  if $c=0$ and
$h=B^{\mu}$ otherwise;
\item It adds the 4-uple $(m,h,\mu,c)$ to the $H$-List and returns $h$ as
  the answer to the random oracle query.
\end{enumerate}

\item[$\bullet$] {\it Signing queries}: when a signature of signer $i$
  is queried for a  message $m$, $\mathcal{B}_1$ runs the random oracle to obtain
 the 4-uple $(m,h,\mu,c)$ contained in the $H$-List. If $c=1$ then $\mathcal{B}_1$
  reports failure and aborts. Otherwise, the algorithm $\mathcal{B}_1$ returns
  $h^{x_i a} = A^{x_i \mu}$ as a valid signature on $m$. \vspace{-0.2 cm}
\end{itemize}
\end{description}
After a number of queries, $\mathcal{A}_1$ comes up with a message
$m^{\star}$, that was never queried for signature for any signer, an
index $i^\star \in \{1,\ldots,N\}$ and a $L^{\textrm{th}}$ level
forgery
${\sigma^\star}^{(L)}=({\sigma_0^\star},\ldots,{\sigma_{2L-2}}^\star)
\in \mathbb{G}^{2L-1}$. At this stage, $\mathcal{B}_1$ runs the random oracle to
obtain
 the 4-uple $(m^{\star},h^{\star},\mu^{\star},c^{\star})$ contained in the
   $H$-List and fails if $c^{\star} = 0$. Otherwise, if $ {\sigma^\star}^{(L)} $ is valid,
   it may be written
$$
({\sigma_0^\star},\ldots,{\sigma_{2L-2}}^\star)=\Big(B^{\mu^{\star}
x_{i^\star}
 at_1 \ldots t_{L-1}},A^{t_1,
     \ldots t_{L-1}}, \ldots, A^{t_1}, g^{t_1}, \ldots, g^{t_{L-1}} \Big)
$$
which provides $\mathcal{B}_1$ with a valid tuple
$(C_1,\ldots,C_{L-1},D_1^a,\ldots,D_{L-1}^a,D_{L-1}^{ab}) $, where
$D_{L-1}^{ab}={\sigma_0^\star}^{1/\mu^\star x_{i^\star}}$, so that
$\log_g(D_j) = \prod_{i=1}^j \log_g(C_i)$ for $j \in \{1,\ldots,
L-1\}$. A
  similar analysis to \cite{Cor00,BLS} gives the announced bound on
 $\mathcal{B}_1$'s advantage if the optimal probability $\zeta =q_s/(q_s+1)$ is used when answering hash
 queries. \\ \vspace{-0.3 cm}

\paragraph{Delegatee security.} We also show how to break the $(L-1)$-FlexDH assumption  out of a delegatee security adversary $\mathcal{A}_2$.
  Given an input pair $(A=g^a,B=g^b)$, the simulator
$\mathcal{B}_2$   proceeds  as  $\mathcal{B}_1$ did in the proof of limited proxy
security. \vspace{-0.2 cm}

\begin{description}
\item[System parameters and public keys:]   the target delegatee's public key  is set  $X_0=A=g^a$.  For $i=1,\ldots,n$, other
public keys  are defined as $X_i=g^{x_i}$ for a random $x_i \sample
\mathbb{Z}_p^*$. To generate re-signature keys $R_{ij}$, $\mathcal{B}_2$ sets $R_{ij}=g^{x_i/x_j}$ when  $i,j \neq 0$ and $R_{0j}=A^{1/x_j}=g^{a/x_j}$ for $j=1,\ldots,n$.   \\
\vspace{-0.3 cm}
\item[Queries:] $\mathcal{A}_2$'s hash and signing queries are handled   exactly  as in the proof of limited proxy security. Namely,
 $\mathcal{B}_2$  fails if $\mathcal{A}_2$ asks for a signature on a message $m$ for
 which $H(m)=B^{\mu}$ and    responds  consistently otherwise.  \\ \vspace{-0.3 cm}
\end{description}
When $\mathcal{A}_2$  outputs her   forgery ${\sigma^\star}^{(L)}=
(\sigma_0^\star,\ldots,\sigma_{2L-2}^\star)$ at level $L$, $\mathcal{B}_2$ is
successful if $H(m^\star)=B^{\mu^\star}$, for some $\mu^\star  \in
\mathbb{Z}_p^*$, and extracts an admissible $(2L-1)$-uple  as done in the
proof of limited proxy security. \\ \vspace{-0.3 cm}

\paragraph{Delegator security.} This security property is proven under the mCDH assumption. Given an adversary
$\mathcal{A}_3$ with advantage $\varepsilon$, we outline an algorithm
$\mathcal{B}_3$ that has probability $O(\varepsilon/q_s)$ of finding
$g^{ab}$ given $(g,A=g^a,A'=g^{1/a},B=g^b)$.
\begin{description}
\item[Public key generation:] as previously, the target public key is defined as   $X_0=A=g^a$.  Remaining public keys
 are set as $X_i=g^{x_i}$ for a random $x_i
\sample \mathbb{Z}_p^*$ for $i=1,\ldots,n$. This time, $\mathcal{A}_3$ aims at producing a first level forgery and is granted {\it all} re-signature keys,
including $R_{0j}$ and $R_{j0}$. For indexes $(i,j)$ s.t. $i,j \neq 0$,
$\mathcal{B}_3$ sets $R_{ij}=g^{x_i/x_j}$. If $i=0$, it calculates
$R_{0j}=A^{1/x_j}=g^{a/x_j}$. If $j=0$ (and thus $i \neq 0$), $\mathcal{B}_3$
computes $R_{i0}={A'}^{x_i}=g^{x_i/a}$ to $\mathcal{A}_3$.
\end{description}
\indent Hash and signing queries  are dealt with exactly as for previous adversaries. Eventually, $\mathcal{A}_3$  produces a first level
forgery ${\sigma^\star}^{(1)}$ for a new message $m^\star$. Then,
$\mathcal{B}_3$ can extract $g^{ab}$ if $H(m)=(g^b)^{\mu^\star} $ for some
$\mu^\star \in \mathbb{Z}_p^*$, which occurs with probability $O(1/q_s)$
using Coron's technique \cite{Cor00}. Otherwise, $\mathcal{B}_3$ fails. \\
\vspace{-0.3 cm}

\paragraph{External security.} We finally show that an external
security adversary $\mathcal{A}_4$ also allows breaking the $(L-1)$-FlexDH
assumption almost exactly as in the proof of limited proxy security.
The simulator $\mathcal{B}_4$ is given an instance $(g,A=g^a,B=g^b)$.  As
previously, $\mathcal{B}_4$ must ``program'' the random oracle $H$ hoping
that its output will be $H(m^\star)=B^{\mu^\star}$ (where $\mu^\star
\in \mathbb{Z}_p^*$ is known) for the message $m^\star$ that the forgery
${\sigma^\star}^{(L)} $ pertains to. The difficulty is that $\mathcal{B}_4$
must also be able to answer signing queries made on $m^\star$ for
all but one signers. Therefore, $\mathcal{B}_4$ must guess which signer
$i^\star$ will be $\mathcal{A}_4$'s prey beforehand. At the outset of the
game, it thus chooses an index $i^\star \sample \{1,\ldots,N\}$.
Signer $i^\star$'s public key is set as $X_{i^\star}=A=g^a$. All
other signers $i \neq i^\star$ are assigned public keys
$X_i=g^{x_i}$ for which $\mathcal{B}_4$ knows the matching secret $x_i$ and
can thus always answer signing queries.
\\ \indent Hash queries and signing queries involving $i^\star$ are
handled as in the proof of limited proxy security. When faced with
a re-signing query from $i$ to $j$ for a  valid signature
$\sigma^{(\ell)}$ at level $\ell \in \{1,\ldots,L\}$, $\mathcal{B}_4$
ignores $\sigma^{(\ell)}$ and simulates a first level signature
for signer $j$. The resulting signature $ {\sigma'}^{(1)}$ is then
turned into a $(\ell+1)^{\textrm{th}}$ level signature and given
back to $\mathcal{A}_4$. A re-signing query thus triggers a signing query
that only causes failure if  $H(m)$ differs from $g^{\mu}$ for a
known $\mu \in \mathbb{Z}_p^*$.
\\ \indent When $\mathcal{A}_4$ forges a signature at level $L$, $\mathcal{B}_4$   successfully
extract a $(2L-1)$-Flexible Diffie-Hellman tuple (as $\mathcal{B}_1$ and
$\mathcal{B}_2$ did) if $H(m^\star)=(g^b)^{\mu^\star}$ and if it correctly
guessed the identity $i^\star$ of the target signer. If $\mathcal{A}_4$'s
advantage is $\varepsilon$, we find  $O(\varepsilon/(
N(q_s+q_{rs}+1)))$ as a lower bound on $\mathcal{B}_4$'s probability of
success,   $q_{s}$ and $q_{rs}$ being the number of signature and
re-signature queries respectively.
 \qed
\end{proof}

\vspace{-0.4 cm}

\section{Eliminating the Random Oracle} \label{Waters-version}

 Several extensions of BLS signatures   have a
standard model counterpart when  Waters' technique supersedes random
oracle manipulations (e.g. \cite{LOSSW}). Likewise, we can very
simply twist our method and achieve the first unidirectional PRS
scheme (even including single hop ones) that avoids the random
oracle model. {\it Mutatis mutandis}, the scheme is totally similar
to
our first construction and relies on the same assumptions. \\

\subsection{The Single Hop Variant}

As in \cite{Wat05}, $n$ denotes the length of messages to be signed.
Arbitrary long messages can be signed if we first apply a
collision-resistant hash function with $n$-bit outputs, in which
case $n$ is part of the security parameter. \\
\indent The scheme requires a trusted party to generate common
public parameters. However, this party can remain off-line after the
setup phase.

\begin{description}
\item[\textsf{Global-setup}$(\lambda,n)$:] given   security parameters $\lambda,n$, this algorithm
chooses bilinear   groups $(\mathbb{G},\mathbb{G}_T)$ of   order $p>2^{\lambda}$,
generators $g,h \sample \mathbb{G}$ and a random $(n+1)$-vector
$\overline{u}=(u',u_1,\ldots,u_n) \sample \mathbb{G}^{n+1}$. The latter
  defines a     function  $F:\{0,1\}^n \rightarrow \mathbb{G}$
mapping $n$-bit strings $\mathsf{m}=m_1\ldots m_n$ (where $m_i\in
\{0,1\}$ for all $i\in \{0,1\}$) onto $F(\mathsf{m})= u' \cdot \prod_{i=1}^n
u_i^{m_i}$. The  public parameters are
$$\mathsf{cp}:=\{\mathbb{G},\mathbb{G}_T,g,h,\overline{u} \}. $$
\item[\textsf{Keygen}$(\lambda)$:] user $i$ sets his public key as $X_i=g^{x_i}$ for a random $x_i \sample \mathbb{Z}_p^*$.
\item[\textsf{ReKeygen}$(x_j,X_i)$:] given user $j$'s private key
$x_j$ and user $i$'s public key $X_i$, generate the  re-signature
key $R_{ij}=X_i^{1/x_j}=g^{x_i/x_j}$ that will be used to translate
signature from $i$ into signatures from $j$.
\item[\textsf{Sign}$(1,\mathsf{m},x_i)$:] to sign a message $\mathsf{m}=m_1\ldots m_n \in \{0,1\}^n$ at  the first
level, the signer  picks $r  \sample \mathbb{Z}_p^*$ at random and computes
\begin{eqnarray*}
\sigma^{(1)}=(\sigma_0,\sigma_1)=(h^{x_i} \cdot F(\mathsf{m})^r ,g^r)
\end{eqnarray*}
\item[\textsf{Sign}$(2,\mathsf{m},x_i)$:] to generate a second level
signature on  $\mathsf{m}=m_1\ldots m_n \in \{0,1\}^n$, the signer  chooses
$r,t \sample \mathbb{Z}_p^*$ and computes
\begin{eqnarray} \label{ca-marche-0}
 \sigma^{(2)}=(\sigma_0,\sigma_1,\sigma_2,\sigma_3)=(h^{tx_i} \cdot F(\mathsf{m})^r ,g^r,X_i^t,g^t)
\end{eqnarray}
\item[\textsf{Re-Sign}$(1,\mathsf{m},\sigma^{(1)},R_{ij},X_i,X_j)$:] on input of a message $\mathsf{m} \in \{0,1\}^n$, the re-signature key
$R_{ij}=g^{x_i/x_j}$, a signature $\sigma^{(1)}=(
\sigma_0,\sigma_1)$ and   public keys  $X_i,X_j$, check the validity
of $\sigma$ w.r.t signer $i$ by testing
 if
\begin{eqnarray} \label{validity-1}
 e(\sigma_0,g)=e(X_i,h) \cdot e(F(\mathsf{m}),\sigma_1)
\end{eqnarray}
 If $\sigma^{(1)}$ is a valid, it can be turned into a signature on behalf of $j$ by choosing $r',t \sample \mathbb{Z}_p^*$ and computing
\begin{eqnarray*}
 \sigma^{(2)}=(\sigma_0',\sigma_1',\sigma_2',\sigma_3')&=&(\sigma_0^{t} \cdot F(\mathsf{m})^{r'} ,\sigma_1^t \cdot
 g^{r'},X_i^t,R_{ij}^t)\\
  &=& (h^{tx_i} \cdot F(\mathsf{m})^{r''},g^{r''},X_i^t,g^{tx_i/x_j} )
\end{eqnarray*}
where $r''=tr+r'$. If we set $\tilde{t}=tx_i/x_j$, we observe that
\begin{eqnarray} \label{ca-marche}
  \sigma^{(2)}=(\sigma_0',\sigma_1',\sigma_2',\sigma_3')=(h^{\tilde{t}x_j} \cdot F(\mathsf{m})^{r''} ,g^{r''},X_j^{\tilde{t}},g^{\tilde{t}})
\end{eqnarray}
\item[\textsf{Verify}$(1,\mathsf{m},\sigma^{(1)},X_i)$:] the validity of a first level signature $\sigma^{(1)}=(\sigma_1,\sigma_2)$  is
checked by testing if relation (\ref{validity-1}) holds.  \\
\vspace{-0.3 cm}
\item[\textsf{Verify}$(2,\mathsf{m},\sigma^{(2)},X_i)$:]   a second level signature
$\sigma^{(2)}=( \sigma_0,\sigma_1,\sigma_2,\sigma_3)$ is  accepted
for the public key $X_i$ if the following conditions are true.
\begin{eqnarray} \label{validity-21}
e(\sigma_0,g) &=& e(\sigma_2,h) \cdot e(F(\mathsf{m}),\sigma_1') \\
e(\sigma_2,g) &=& e(X_i,\sigma_3)  \label{validity-22}
\end{eqnarray}

\end{description}
To the best of our knowledge, the above scheme is the first
unidirectional PRS in the standard model and   solves another
problem  left open in \cite{AH05} where all constructions require
the random oracle model. Like the scheme of section
\ref{BLS-Version}, this extension of Waters' signature \cite{Wat05}
is scalable into a multi-hop PRS.

\subsection{The Multi-Hop Extension}

At levels $\ell \geq 2$, algorithms $\mathsf{Sign}$,
$\mathsf{Re\textrm{-}Sign}$ and $\mathsf{Verify}$ are generalized as
follows. \\ \vspace{-0.3 cm}

\begin{description}
\item[\textsf{Sign}$(\ell+1,m,x_i)$:] to sign   $\mathsf{m} \in \{0,1\}^n$
at level $\ell+1$,   user $i$ picks $r \sample \mathbb{Z}_p^*$,
$(t_1,\ldots,t_{\ell}) \sample (\mathbb{Z}_p^*)^{\ell}$ and outputs
$\sigma^{(\ell+1)}=(\sigma_0,\ldots,\sigma_{2\ell+1}) \in
\mathbb{G}^{2\ell+2}$ where
\begin{eqnarray*}
\left\{
\begin{array}{ll}
\sigma_0  =  h^{x_i t_1 \cdots t_\ell} \cdot F(\mathsf{m})^r  &  \\
 \sigma_1  =   g^r & \\
\sigma_k  =  g^{x_i t_1 \cdots t_{\ell+2-k}} &  \hbox{ for } k \in
\{2,\ldots, \ell+1 \}\\
\sigma_k  =  g^{t_{k-\ell-1}} & \hbox{ for } k \in
\{\ell+2,\ldots,2\ell+1\}.
\end{array}\right.
\end{eqnarray*}
\item[\textsf{Re-Sign}$(\ell+1,\mathsf{m},\sigma^{(\ell+1)},R_{ij},X_i,X_j)$:] on input of a message
  $\mathsf{m} \in \{0,1\}^*$, the re-signature key $R_{ij}=g^{x_i/x_j}$, a
 purported
  $(\ell+1)^{\textrm{th}}$
  level signature
  \begin{eqnarray*}
  \sigma^{(\ell+1)} &=& (\sigma_0,\ldots,\sigma_{2\ell+1}) \\
  &=& (h^{x_i t_1 \cdots t_{\ell}} \cdot F(\mathsf{m})^r,g^r, g^{x_i t_1 \cdots t_{\ell}}, g^{x_i t_1 \cdots t_{\ell-1}}, \ldots,
  g^{x_it_1},g^{t_1},\cdots,g^{t_{\ell}} )  \in \mathbb{G}^{2\ell+2}
  \end{eqnarray*} and public keys $X_i,X_j$,
  check the correctness of $\sigma^{(\ell+1)}$ under $X_i$. If valid, $\sigma^{(\ell+1)}$ is translated for  $X_j$ by
  sampling $r' \sample \mathbb{Z}_p^*$, $(r_0,r_1,\ldots,r_{\ell}) \sample (\mathbb{Z}_p^*)^{\ell+1}$ and
  setting $\sigma^{(\ell+2)}=(\sigma_0',\ldots,\sigma_{2\ell+3}') \in \mathbb{G}^{2\ell+4}$ where
\begin{eqnarray*}
\left\{
\begin{array}{ll}
 \sigma_0'  =  \sigma_0^{r_0 \cdots r_{\ell}} \cdot F(\mathsf{m})^{r'} &
 \\
  \sigma_1'  =  \sigma_1^{r_0 \cdots r_{\ell}} \cdot g^{r'} & \\

 \sigma_{k}'  =  \sigma_k^{r_0 \cdots r_{\ell+2-k}} & \hbox{ for } k \in
 \{2,\ldots, \ell+1\}\\
 \sigma_{\ell+2}'  =  X_i^{r_{0}} & \\
 \sigma_{\ell+3}'  =  R_{ij}^{r_{0}}  & \\
 \sigma_k'  =  \sigma_{k-2}^{r_{k-\ell-3}}   & \hbox{ for } k \in
 \{\ell+4,\ldots,2\ell+3\}.\\
\end{array}\right.
\end{eqnarray*}
If we define $\tilde{t}_0=r_0x_i/x_j$, $r''=r_0   \cdots
r_{\ell}+r'$ and $\tilde{t}_k=r_k t_k$ for $k=1,\ldots,\ell$, we
observe that
$$\sigma^{(\ell+2)}  =(h^{x_j \tilde{t}_0 \tilde{t}_1\cdots \tilde{t}_{\ell}} \cdot F(\mathsf{m})^{r''},g^{r''}, g^{x_j \tilde{t}_0 \tilde{t}_1 \cdots \tilde{t}_{\ell}}, g^{x_j \tilde{t}_0 \tilde{t}_1 \cdots \tilde{t}_{\ell-1}}, \ldots,
  g^{x_j \tilde{t}_0},g^{\tilde{t}_0},\ldots,g^{\tilde{t}_{\ell}} )  $$
\item[\textsf{Verify}$(\ell+1,\mathsf{m},\sigma^{(\ell+1)},X_i)$:]   a
  candidate signature $\sigma^{(\ell+1)}=(\sigma_0,\ldots,\sigma_{2\ell+1}) $ is verified by testing if the following equalities hold:
\begin{eqnarray*}
e(\sigma_0,g) & = & e(h,\sigma_3) \cdot e(F(\mathsf{m}),\sigma_1) \\
e(\sigma_k,g) & = & e(\sigma_{k+1},\sigma_{2\ell+3-k}) \hbox{ for }
k \in
 \{2,\ldots,\ell\}\\
e(\sigma_{\ell+1},g)& =& e(X_i,\sigma_{\ell+2})
\end{eqnarray*}
\end{description}

\subsection{Security}

\begin{theorem} \label{Waters-proof}
The scheme with $L$ levels (and thus at most $L-1$ hops) is a secure
unidirectional PRS under the $(L-1)$-FlexDH and mCDH assumptions.
\end{theorem}
\begin{proof}
The proof is very similar to the one of theorem \ref{BLS-proof} and
replaces random oracle manipulations by  the tricks  of
\cite{BB2,Wat05}.  We prove the limited proxy and delegatee security
properties under the $(L-1)$-FlexDH assumption. The delegator
security is demonstrated under the mCDH assumption.

\paragraph{Limited proxy security.} We consider an adversary $\mathcal{A}_1$ with advantage $\varepsilon$. We
 describe an algorithm  $\mathcal{B}_1$    solving a
$(L-1)$-FlexDH instance $(A=g^a,B=g^b)$ with probability
$\varepsilon/4q_s(n+1)$, where $q_s$ is the number of signing
queries made by $\mathcal{A}_1$, within a comparable time.

\begin{description}
\item[System parameters:]  The    simulator $\mathcal{B}_1$ prepares common public parameters as
follows. It first sets $h=B=g^{b}$. The $(n+1)$-vector
$\overline{u}=(u',u_1,\ldots,u_n)$ is defined by choosing
$u'=h^{w'-\kappa \tau}\cdot g^{z'}$ and $u_i=h^{w_i} \cdot g^{z_i}$
for $i\in \{1,\ldots,n\}$ using random vectors
$(w',w_1,\ldots,w_n)\sample \mathbb{Z}_{\tau}^{n+1}$, $(z',z_1,\ldots,z_n)
\sample \mathbb{Z}_p^{n+1}$, where   $\kappa \sample \{0,\ldots,n\}$ is
randomly chosen and $\tau =2q_s$. For any message $\mathsf{m}=m_1\ldots m_n
\in \{0,1\}^n$, we have $$F(\mathsf{m})=u' \cdot \prod_{i=1}^n u_i^{m_i}
=h^{J(\mathsf{m})} g^{K(\mathsf{m})}$$ for functions $J:\{0,1\}^n \rightarrow \mathbb{Z}$,
$K:\{0,1\}^n \rightarrow \mathbb{Z}_p$ respectively defined as
$J(\mathsf{m})=w'+\sum_{i=1}^n w_i m_i - \kappa \tau$  and
$K(\mathsf{m})=z'+\sum_{i=1}^n z_i m_i$. As in \cite{Wat05}, $\mathcal{B}_1$ will be
successful if $J(\mathsf{m}^\star)=0 $ for the message $\mathsf{m}^*$ of the forgery
stage whereas $J(\mathsf{m})\neq 0 $ for all messages $\mathsf{m}\neq \mathsf{m}^*$ queried
for signature. Since $|J(.)|\leq \tau (n+1) \ll p$, we have
$J(\mathsf{m}^\star)=0  $ with non-negligible probability $O(1/\tau(n+1))$.
The adversary $\mathcal{A}_1$ is challenged on parameters
  $(g,h,\overline{u})$. \\ \vspace{-0.3 cm}

\item[Key generation:] for
user $i \in \{1,\ldots,N\}$, $\mathcal{B}_1$ defines a public key as
$X_i=A^{x_i}=g^{ax_i}$, for a random $x_i \sample \mathbb{Z}_p^*$, which
virtually defines user $i$'s private key as $ax_i$.  For pairs
$(i,j)$,     re-signature keys are chosen as
$R_{ij}=g^{x_i/x_j}=g^{ax_i/ax_j}$.  \\
\vspace{-0.3 cm}

\item[Signing queries:]  when a signature of signer $i$ is queried for a  message $\mathsf{m}$, $\mathcal{B}_1$   fails if
  $J(\mathsf{m})=0 \bmod p$.
 Otherwise, following the technique of \cite{BB2,Wat05},
 it can construct a signature by picking $r \sample \mathbb{Z}_p$
and computing   \vspace{-0.2 cm} $$\sigma=
(\sigma_1,\sigma_2)=\left(
X_i^{-\frac{K(\mathsf{m})}{J(\mathsf{m})}} \cdot
F(\mathsf{m})^r,X_i^{-\frac{1}{J(\mathsf{m})}} \cdot g^r  \right).
\vspace{-0.2 cm}
 $$ which is returned to $\mathcal{A}_I$.  If we define $\tilde{r}=r-(ax_i)/J(\mathsf{m})$, $\sigma$ has the correct distribution
  as \vspace{-0.2 cm}
\begin{eqnarray*}
\sigma_1 = X_i^{-\frac{K(\mathsf{m})}{J(\mathsf{m})}} \cdot
F(\mathsf{m})^r
    = X_i^{-\frac{K(\mathsf{m})}{J(\mathsf{m})}} \cdot
    F(\mathsf{m})^{\tilde{r}}
    \cdot (h^{J(\mathsf{m})} \cdot g^{K(\mathsf{m})})^{ \frac{ax_i }{J(\mathsf{m})} }    = h^{ax_i} \cdot F(\mathsf{m})^{\tilde{r}} \vspace{-0.2 cm}
\end{eqnarray*}
and $\sigma_2=g^{r -(ax_i)/J(\mathsf{m})}=g^{\tilde{r}}$.
\\ \vspace{-0.3 cm}
\end{description}
After polynomially many queries, $\mathcal{A}_1$ comes up with a message,
that was never queried for signature for any signer, and index
$i^\star \in \{1,\ldots,N\}$ and a   forgery

 \begin{eqnarray*}
  {\sigma^{(L)}}^\star &=& (\sigma_0^\star,\ldots,\sigma_{2L-1}^\star) \\
  &=& (  h^{a
x_{i^\star}  t_1^\star \cdots t_{L-1}^\star} \cdot
F(\mathsf{m})^{r^\star},g^{r^\star}, g^{ a x_{i^\star}  t_1^\star \cdots
t_{L-1}^\star}, g^{a x_{i^\star}  t_1^\star \cdots t_{L-2}^\star},
\\ & & ~ \ldots,
  g^{a
x_{i^\star}  t_1^\star },g^{t_1^\star},\cdots,g^{t_{L-1}^\star} )
\in \mathbb{G}^{2L}
  \end{eqnarray*}
 at level $L$. At this stage, $\mathcal{B}_1$
fails if $J(\mathsf{m}^\star)\neq 0 \bmod p$. Otherwise, if
${\sigma^{(L)}}^\star$ is valid,
$$  {\sigma_0}^\star=     h^{a x_{i^\star} t_1^\star \cdots
t_{L-1}^\star} \cdot  g^{r^\star K(\mathsf{m}^\star)}
$$
 which provides $\mathcal{B}_1$ with a valid $(2L-1)$-uple
 \begin{eqnarray*}
& & (C_1,\ldots,C_{L-1},D_1^a,\ldots,D_{L-1}^a,D_{L-1}^{ab}) \\
&=& \Big(  {\sigma_{L+1}}^\star,\ldots,{\sigma_{2L-1}}^\star,
 {{\sigma_{L}}^\star}^{1/x_{i^\star}}, \ldots ,
,{{\sigma_{2}}^\star}^{1/x_{i^\star}}, \Big( \frac{{\sigma_0}^\star
}{
{{\sigma_1}^\star}^{K(\mathsf{m}^\star)} } \Big)^{1/x_{i^\star}} \Big) \\
&=& \big(g^{t_1^\star},\ldots,g^{t_{L-1}^\star},g^{a
t_1^\star},\ldots, g^{a t_1^\star \cdots t_{L-1}^\star} ,g^{
t_1^\star \cdots t_{L-1}^\star ab} \big).
\end{eqnarray*} A completely
similar analysis to \cite{Wat05} shows that $J(\mathsf{m}^\star)=0$ with
probability $1/4q_s(n+1)$, which yields the   bound on $\mathcal{B}_1$'s
advantage. \\ \vspace{-0.3 cm}

\paragraph{Delegatee security.} A delegatee security adversary
$\mathcal{A}_2$ also implies a breach in the $(L-1)$-FlexDH assumption. The
simulator $\mathcal{B}_2$ is given $(A=g^a,B=g^b)$ and uses a strategy that
is completely analogous to the one of simulator $\mathcal{B}_1$ in the proof
of limited proxy security.

\begin{description}

\item[System parameters and public keys:] $\mathcal{B}_2$ prepares public parameters exactly as in the proof of
limited proxy security. The public key of the target user is defined
as $X_0=A=g^a$. The attacker $\mathcal{A}_2$ must be provided with private
keys for all the delegators of that user. For $i=1,\ldots,n$, other
public keys  are therefore chosen as $X_i=g^{x_i}$ for   randomly
picked $x_i \sample \mathbb{Z}_p^*$. The adversary $\mathcal{A}_2$   then receives
$\{g,h=B,\overline{u},X_0=g^a,x_1,\ldots,x_n\}$ as well as
re-signature keys $R_{ij}$ for $i\in \{0,\ldots,N\}$ and $j \in
\{1,\ldots,N\}$.
 These   are set as $R_{0j}=A^{1/x_j}=g^{a/x_j}$  and $R_{ij}=g^{x_i/x_j}$
 if $i \neq 0$.
   \\
\vspace{-0.3 cm}
\item[Signing queries:]  for all signers $i\neq 0$, $\mathcal{A}_2$ can generate signatures on her
own. When a signature of the target signer  is requested for a
message $\mathsf{m}$, $\mathcal{B}_2$
 proceeds as $\mathcal{B}_1$ did when facing the limited proxy adversary $\mathcal{A}_1$. It  fails if
  $J(\mathsf{m})=0 \bmod p$ and can answer the query otherwise.
\\ \vspace{-0.3 cm}
\end{description}
When $\mathcal{A}_2$ eventually outputs a   forgery $
(\sigma_0^\star,\ldots,\sigma_{2L-1}^\star)$ at level $L$, $\mathcal{B}_2$
is successful if $J(\mathsf{m}^\star)=0$ and  extracts an admissible $(2L-1)$-uple  as $\mathcal{B}_1$ did. \\
\vspace{-0.3 cm}

\paragraph{Delegator security.} A delegator security adversary
$\mathcal{A}_3$ having advantage $\varepsilon$ after $q_s$  signing queries
is finally shown to imply an algorithm $\mathcal{B}_3$ to solve a problem
which is equivalent (under linear time reduction) to the mCDH
problem with probability $\varepsilon/4q_s (n+1)$. Given
$(g,A=g^a,A'=g^{1/a},B=g^b)$, this problem is to find out $g^{ab}$.
\begin{description}
\item[Public parameters and public key generation:] Again, system  parameters are  prepared  as in the proof of
limited proxy security. Namely, $\mathcal{B}_3$ defines $h=B=g^b$ and chooses
$u',u_1,\ldots,u_n$ so as to have $F(\mathsf{m})=h^{J(\mathsf{m})} \cdot g^{K(\mathsf{m})}$
for some functions $J,K:\{0,1\}^n \rightarrow \mathbb{Z}_p$ where $J$
cancels with non-negligible probability. The public key of the
target delegator is
 set as $X_0=A=g^a$.  For
$i=1,\ldots,n$, remaining public keys  are set as $X_i=g^{x_i}$ for
a random    $x_i \sample \mathbb{Z}_p^*$. The adversary $\mathcal{A}_3$ receives
$\{g,h=B,\overline{u},X_0=g^a,x_1,\ldots,x_n\}$. This time, she is
provided with {\it all} re-signature keys (including $R_{0j}$ and
$R_{j0}$) and attempts to produce a first level forgery.  For pairs
$(i,j)$ such that $i,j \neq 0$,   $\mathcal{B}_3$   sets
$R_{ij}=g^{x_i/x_j}$. If $i=0$, it defines
$R_{0j}=A^{1/x_j}=g^{a/x_j}$. If $j=0$ (and thus $i \neq 0$),
$\mathcal{B}_3$ calculates $R_{i0}={A'}^{x_i}=g^{x_i/a}$ and hands $\{R_{ij}\}_{i,j}$ to $\mathcal{A}_3$. \\
\vspace{-0.3 cm}
\item[Signing queries:]   when $\mathcal{A}_3$ asks for a signature from the target delegator  for a
message $\mathsf{m}$, $\mathcal{B}_3$
   fails if
  $J(\mathsf{m})=0 \bmod p$ and can answer the query exactly as in the proof of limited proxy security otherwise.
\\ \vspace{-0.3 cm}
\end{description}
 Eventually, $\mathcal{A}_3$     produces a first level
forgery $ {\sigma^{(1)}}^\star =({\sigma_1}^\star,{\sigma_2}^\star
)$ for a message $\mathsf{m}^\star$ that was never queried for signature. If
$J(\mathsf{m}^\star) \neq 0$, $\mathcal{B}_3$ fails. Otherwise, given that
$({\sigma_1}^\star , {\sigma_2}^\star )=(h^a \cdot g^{r
K(\mathsf{m}^\star)}, g^r)$, $\mathcal{B}_3$ finds
out $g^{ab}={\sigma_1}^\star / {{\sigma_2}^\star}^{K(\mathsf{m}^\star)}$. \\
\vspace{-0.3 cm}

\paragraph{External Security.}

We consider an adversary $\mathcal{A}_4$ with advantage $\varepsilon$. We
 describe an algorithm $\mathcal{B}_4$    solving a
$(L-1)$-FlexDH instance $(A=g^a,B=g^b)$ with probability
$\varepsilon/(4N(q_s+q_{rs})(n+1))$ within  comparable time, where
$q_s$ and $q_{rs}$ are is the number of signing and re-signing
queries.

\begin{description}
\item[System parameters:] The simulator $\mathcal{B}_4 $ prepares  common public
  parameters as in the limited proxy security proof. In addition, it
  picks at random an integer  $i^{\ast} \in \{1,\ldots,N\}$. \\
\vspace{-0.3 cm}

\item[Public key generation:] when $\mathcal{A}_4$ asks for the creation of
user $i \in \{1,\ldots,N\}$, $\mathcal{B}_4$ responds \\ \vspace{-0.3 cm}
\begin{itemize}
\item with a newly generated public key $X_i=g^{x_i}$, for a random
  $x_i \sample \mathbb{Z}_p^*$ if $i \neq i^{\ast}$ (s.t. $x_i$, user $i$'s
  private key, is known to the simulator);
\item with $X_{i^{\ast}} = A$ if $i = i^{\ast}$ (which virtually
  defines user $i$'s private key as $a$). \\ \vspace{-0.3 cm}
\end{itemize}

\item[Oracle queries:] $\mathcal{A}_4$'s queries are tackled with as
follows.\\ \vspace{-0.3 cm}
\begin{itemize}
\item[$\bullet$] {\it Signing queries}: when a signature of signer $i$
  is queried for a message $\mathsf{m}$,
\begin{itemize}
\item[-] $\mathcal{B}_4$ uses its knowledge of $x_i$ to produce the signature if
  $i \neq i^{\ast}$;
\item[-]  $\mathcal{B}_4$ uses the simulation from the limited proxy security proof if
  $i = i^{\ast}$ (and therefore fails if $J(\mathsf{m})=0 \bmod p$).
\end{itemize}
\item[$\bullet$] {\it Re-signing queries}: for such a query on input
  $(\mathsf{m},\sigma^{(\ell)},i,j)$, $\mathcal{B}_4$ checks if $\sigma^{(\ell)}$ is a valid $\ell^{\textrm{th}}$
  level signature on $\mathsf{m}$ for some $\ell \in \{1,\ldots,L-1\}$ with
  respect to the public  key $i$. If yes, $\mathcal{B}_4$ produces a
  first level signature on $\mathsf{m}$ for user $j$ (using the previous
  simulation strategy), increases its level up to $\ell+1$ (for the same
  public key) using the re-signing algorithm (with re-signature key
  simply equal to $g$) and outputs the resulting $(\ell+1)^{\textrm{th}}$ level signature. The simulation only fails  if $J(\mathsf{m})=0
  \bmod p$ and $j = i^{\ast}$.
\end{itemize}
\end{description}
After polynomially many queries, $\mathcal{A}_4$ comes up with a message
$\mathsf{m}^\star$, an index $j^\star \in \{1,\ldots,N\}$ and a forgery $
{\sigma^{(L)}}^\star \in \mathbb{G}^{2L}$ at level $L$. Recall that
$\mathsf{m}^\star$ cannot have been queried to signer $j^\star $. Again,
$\mathcal{B}_4$ fails if $J(\mathsf{m}^\star)\neq 0 \bmod p$ or $j^{\star} \neq
i^{\ast}$. Otherwise, if ${\sigma^{(L)}}^\star $ is valid, $\mathcal{B}_4$
produces a valid $(L-1)$-FlexDH-tuple as in the limited proxy
security proof. A completely similar analysis to this proof ends up
with the announced bound on $\mathcal{B}_4$'s advantage.
 \qed
\end{proof}

\section{Conclusions and Open Problems}

We described the first multi-use unidirectional proxy re-signatures,
which  solves a  problem left open in 2005. The random-oracle-based
proposal also offers efficiency improvements over existing solutions
  at the first level. The other scheme
additionally happens to be the first unidirectional PRS in the
standard model. \\
 \indent Two major open problems remain. First,  it would be
interesting to see if multi-level unidirectional PRS have efficient
realizations under more classical intractability assumptions. A
perhaps more challenging task would be to find out implementations
of such primitives where the size of signatures and the verification
cost grow sub-linearly with the number of translations.

\newpage