# Multi-signer Strong Designated Multi-verifier Signature Schemes based on
Multiple Cryptographic Algorithms

Neha Arora, R. K. Sharma

###### Abstract

A designated verifier signature scheme allows a signer to generate a signature
that only the designated verifier can verify. This paper proposes multi-signer
strong designated multi-verifier signature schemes based on multiple
cryptographic algorithms and has proven their security in the random oracle
model.

Department of Mathematics, Indian Institute of Technology, New Delhi, 110016,
India

Keywords: Multi-signer, designated multi-verifier, bilinear pairing,
factorization, discrete logarithm, Blockchain
2010 Math. Sub. Classification: 94P60, 94A62, 68P25, 68P30 111emails:
<EMAIL_ADDRESS>(Neha<EMAIL_ADDRESS>(Rajendra)

##  1 Introduction

Digital signature [5, 6, 16] is a mathematical algorithm used to validate the
authenticity, integrity, and non-repudiation of a message or document. In
digital signature algorithms, anyone having the signature and signer’s public
key can validate the signature, which is not desired in some cases. Therefore,
the undeniable signature [2] was introduced by David Chaum and Hans van
Antwerpen in 1989. An undeniable signature is a digital signature that
requires the signer’s cooperation to verify signatures. However, the validity
of an undeniable signature can be ascertained by anyone issuing a challenge to
the signer and testing the signer’s response. To solve this problem, Jakobsson
Markus, Kazue Sako, and Russell Impagliazzo introduced a designated verifier
signature scheme [8] in 1996. It provides authentication of a message, and the
signer chooses a designated verifier in advance, which makes it non-
interactive. However, it does not provide non-repudiation property. Also, in
this scheme, the verifier can generate a transcript and convince the third
party that the signer created the signature. In the same year, a stronger
version is introduced as a strong designated verifier signature scheme.
However, in 2003, Guilin Wang designed an attack in [22] on the Jakobsson
scheme. Later, in 2003, an efficient strong designated verifier signature
scheme [17] was introduced by Shahrokh Saeednia, Steve Kremer, and Olivier
Markowitch.
However, in 2007, Ji-Seon Lee and Jik Hyun Chang in [12] found that Saeednia
scheme [17] was not secure, and it would reveal the signer’s identity if the
secret key of the signer is compromised. Later, they provide an improved
version [13]. However, in 2012, Liao Da-jian and Tang Yuan-sheng found that
[13] does not protect the identity of the signer, and it can be revealed if
compromised. Thus, they designed an improved version [3] of [13] which
protects the signer’s identity but lost the security properties of the
designated verifier signature scheme. Also, in 2017, [9] proved that the
scheme [13] is not secure, and signature can be forged without knowing the
signer’s private key and designed a new strong designated verifier signature
scheme.
In 2015, Pankaj Sarde and Amitabh Banerjee reviewed [17] and proposed strong
designated verifier signature scheme based on discrete logarithm problem [18].
In 2018 and later in 2021, Nadiah Shapuan and Eddie Shahril Ismail proposed a
strong designated verifier signature scheme with two hard problems : Factoring
problem and discrete logarithm problem [19, 20].
Simultaneously, Few multi signer designated verifier signature scheme [7, 14,
24], designated multi verifier signature schemes [10, 11, 15, 23] and multi-
signer designated multi-verifier signature schemes [1, 4, 21] were introduced.
In the case of Multi-signer designated multi-verifier signature schemes,
signatures can be generated in two different ways :

  1. 1.

All signers come together and cooperate to generate a new signature.

  2. 2.

All signers generate their signature and make it public to the system, and
then, the system generates a new signature using all available signatures.

Multi-signer designated multi-verifier signature schemes has application in
various areas. A few of them are mentioned below:

  1. 1.

Let A be a group of board of Directors of a company, and they have signed some
crucial and confidential data which may lead to the increase in profits and
price of shares of a company and make its encoded copy public such that each
shareholder can verify if the decisions will benefit them or not.

  2. 2.

Application using Blockchain Technology:
To apply our scheme to the blockchain, we made a few assumptions :

    1. (a)

Our example best suits a small blockchain where participants are limited, and
the transaction information is shared among them only.

    2. (b)

Our platform is a smart contract-enabled permissioned Blockchain Network.

    3. (c)

Each signer and verifier signed a smart contract, and any cheating and
violation led to the blocked account.

    4. (d)

Only designated verifiers are allowed to verify and validate the information.

    5. (e)

For every transaction information shared, the participants will be the
signers, and the remaining will act as verifies.

    6. (f)

Moreover, ownership is not assigned to a single person. Thus, overriding,
editing, or deleting the transaction or any other related information is not
possible without the consent of a fixed number of participants.

    7. (g)

A new block is generated after a fixed predetermined time interval.

    8. (h)

The hash value of all transactions in a fixed interval are merged as a root
hash in Merkle tree.

    9. (i)

Each block is linked with the previous block.

    10. (j)

Each block contains block version, Merkle tree root hash, timestamp, nBits,
nounce, parent block hash.

Block version Merkle tree root hash Parent block hash Timestamp nBits Nounce
TX TX TX Block StructureBlock HeaderTransaction Counter

We shall show it with an example:

    1. (a)

We assume we have 20 participants in our Blockchain Network and each member is
given an identity $P_{i}$ , $1\leq i\leq 20$.

    2. (b)

A new block is generated after every $t^{\prime}$ minutes.

    3. (c)

Let $T_{i,j}$ be the transaction id where $i$ represents the block number and
$j$ represents the transaction number of $i$-th block.

    4. (d)

Let $P_{1}$ transfers some amount to $P_{2},P_{3},P_{5},P_{7}$ and $P_{9}$
transfer some amount to $P_{1},P_{3},P_{5},P_{11}$ in a fixed time interval
$[0,t^{\prime}]$. Let $S_{1}=\\{P_{1},P_{2},P_{3},P_{5},P_{7},P_{9},B_{11}\\}$
be the set of signers. None of them wants to reveal the exact amount, but
their ids, and encoded value of the change in their respective balance. In
this case, each signer creates and sends the signature to the system. The
system generates a new signature and broadcasts it to all remaining
participants, and each verifier, within a specific time, can verify and
validate the transaction.

$P_{1}$$P_{7}$$T_{1,4}$$P_{5}$$T_{1,3}$$P_{3}$$T_{1,2}$$P_{2}$$T_{1,1}$$P_{9}$$P_{11}$$T_{1,8}$$P_{5}$$T_{1,7}$$P_{3}$$T_{1,6}$$P_{1}$$T_{1,5}$

    5. (e)

Let $P_{7}$ transfer some amount to $P_{13},P_{15}$ , $P_{4}$ to
$P_{2},P_{7},P_{13}$ , and $P_{3}$ to $P_{4},P_{5},P_{11},P_{13}$ in a fixed
time interval $[t^{\prime},2t^{\prime}]$. Then,
$S_{2}=\\{P_{2},P_{3},P_{4},P_{5},P_{7},P_{11},P_{13},P_{15}\\}$ be the new
set of signers and remaining participants will act as verifiers and they can
verify and validate the transactions with a specific time.

$P_{7}$$P_{15}$$T_{2,2}$$P_{13}$$T_{2,1}$$P_{4}$$P_{13}$$T_{2,5}$$P_{7}$$T_{2,4}$$P_{2}$$T_{2,3}$$P_{3}$$P_{13}$$T_{2,9}$$P_{11}$$T_{2,8}$$P_{5}$$T_{2,7}$$P_{4}$$T_{2,6}$

This way, we can record and verify multiple transactions compactly. Also, the
privacy of each transaction can be maintained by keeping individual amounts
secret and making hash value the total amount public. It also decreases the
size of the blocks and reduces the storage cost, making it cheaper to operate.

So far, we have seen a few multi-signer designated verifier signature schemes,
designated multi-verifier signature schemes, and multi-signer designated
multi-verifier signature schemes based on either single hard problem or
bilinear pairing. This paper proposes two individual multi-signer strong
designated multi-verifier signature schemes and combines them to enhance their
security. Our final scheme is based on multiple hard problems, and it requires
the authorization of each participating signer. Also, our scheme is non-
interactive as the system will act as an intermediator. Later, we showed that
our scheme is a strong, unforgeable, non-transferable designated verifier
scheme.

This paper is organized as follows: In Section 2, we define factoring problem,
discrete logarithm problem, bilinear pairing, strong designated verifier,
strong designated verifier signature scheme, and multi-signer designated
multi-verifier signature schemes. Section 3 is divided into four subsections.
Section 3.1 is an extension of [24] to multi-verifier scheme, and it is based
on bilinear pairing. Section 3.2 is an extension of [19, 20] to multi-signer
multi-verifier scheme, and it is based on two hard problems: factoring problem
and discrete logarithm problem. Section 3.3 is an improvisation of section 3.2
based on the elliptic curve. Section 3.4 gives a glimpse of the combination of
the first and second algorithm. In section 4, we have done the security
analysis of our scheme.

##  2 Preliminaries

######  Definition 1.

Factoring problem : Let $n$ be a large positive composite integer such that
$n\ =\ pq$, where $p$ and $q$ are large primes. Then, solving to find the
factorization of $n$ is called factoring problem.

######  Definition 2.

Discrete Logarithm problem: Let $p,q$ be primes such that $q$ divides $p-1$.
Let G be a multiplicative group of order $p$, and $g\in G$ such that $|g|=q$
and $y\ \equiv\ g^{x}\ (mod\ n)$, then for given $g$ and $y$, computation of
$x$ is called as discrete logarithm problem.

######  Definition 3.

Bilinear pairing :

Let $G_{1}$ and $G_{2}$ be two cyclic groups (w.r.t. addition) of prime order
$p$ with generators $P_{1}$ and $P_{2}$, respectively. Define a map
$e:G_{1}\times G_{2}\to G_{\mathcal{T}}$, where $G_{\mathcal{T}}$ is a group
(w.r.t. multiplication) of order $p$. Then, the map $e$ is s.t.b.
$\mathbb{F}_{p}$-bilinear if $e(aP_{1},bP_{2})\ =\ e(P_{1},P_{2})^{ab}\ \
\forall a,b\in\mathbb{F}_{p}$, non-degenerate if $e(P_{1},P_{2})\neq
1_{G_{\mathcal{T}}}$, and symmetric if $G_{1}\ =\ G_{2}$.

The pairing $e$ is an admissible bilinear map if it is non-degenerate and it
can be efficiently computable.

######  Definition 4.

([17] ) Strong designated Verifier : Let P(S,V) be a protocol for signer S to
prove the truth of the statement $\omega$ to verifier V. We say that P(S,V) is
strong designated verifier proof if anybody can produce identically
distributed transcripts that are indistinguishable from those of P(S,V) for
everybody, except for Verifier V.

######  Definition 5.

Strong Designated Verifier Signature Scheme : A strong designated verifier
signature scheme consists of the following algorithms:

  1. 1.

Set up : $sp\ \leftarrow\ Setup(K)$, where $K$ is a security parameter, $sp$
is system parameters.

  2. 2.

Key generation : $(sk_{U},pk_{U})\ \leftarrow\ KeyGen(sp,K)$, where $sk_{U}$
and $pk_{U}$ are the secret key and public key of user $U$ respectively.

  3. 3.

Signature Algorithm $Sign_{{S}\ \rightarrow\ {D}}$ :

$sign_{S}\ \leftarrow\ Sign_{{S}\ \rightarrow\ {D}}(M,sk_{S},pk_{D})$

where $M\ \in\ \\{0,1\\}^{*}$ is the message to be signed, $sk_{S}$ denote the
private key of signer $S$ and $pk_{D}$ denote the public key of designated
verifier $D$.

  4. 4.

Verification Algorithm $Verify_{D}$ :

$\\{accept,\ reject\\}\ \leftarrow\ Verify_{D}(M,sk_{D},pk_{S},sign_{S})$

where $sk_{D}$ denote the secret key of designated verifier $D$ and $pk_{S}$
denote the public key of signer $S$.

######  Definition 6.

Multi-signer strong designated Multi-verifier signature scheme : A Multi-
signer strong designated Multi-verifier signature scheme consists of the
following algorithms:

  1. 1.

Set up : $sp\ \leftarrow\ Setup(K)$, where $K$ is a security parameter, $sp$
is system parameters.

  2. 2.

Key generation : $(sk_{U},pk_{U})\ \leftarrow\ KeyGen(sp,K)$, where $sk_{U}$
and $pk_{U}$ are the secret key and public key of user $U$ respectively.

  3. 3.

Signature Algorithm $Sign_{(S_{1},S_{2},...,S_{n})\ \rightarrow\
(D_{1},D_{2},...,D_{m})}$ :

$sign_{A}\ \leftarrow\ Sign_{(S_{1},S_{2},...,S_{n})\ \rightarrow\
(D_{1},D_{2},...,D_{m})}(M,sk_{S_{1}},sk_{S_{2}},...,sk_{S_{n}},pk_{D_{1}},pk_{D_{2}},...,pk_{D_{m}})$

where $M\ \in\ \\{0,1\\}^{*}$ is the message to be signed,
$(sk_{S_{1}},sk_{S_{2}},...,sk_{S_{n}})$ denote the private key of $n$ signers
$(S_{1},S_{2},...,S_{n})$ and $(pk_{D_{1}},pk_{D_{2}},...,pk_{D_{m}})$ denote
the public key of $m$ designated verifiers $(D_{1},D_{2},...,D_{m})$.

  4. 4.

Verification Algorithm $Verify_{(D_{1},D_{2},...,D_{m})}$ :

$\\{accept,\ reject\\}\ \leftarrow\
Verify_{(D_{1},D_{2},...,D_{m})}(M,sk_{D_{1}},sk_{D_{2}},...,sk_{D_{m}},pk_{S_{1}},pk_{S_{2}},...,pk_{S_{n}},sign_{A})$

where $(sk_{D_{1}},sk_{D_{2}},...,sk_{D_{m}})$ denote the secret key of $m$
designated verifiers $(D_{1},D_{2},...,D_{m})$ and
$(pk_{S_{1}},pk_{S_{2}},...,pk_{S_{n}})$ denote the public key of $n$ signers
$(S_{1},S_{2},...,S_{n})$.

##  3 Proposed Schemes

This paper defines a secure, strong designated signature scheme with multi-
signers and multi-verifiers based on multiple hard problems. Our scheme is
divided into four subsections. Section 3.1 is an extension of [24] to multi-
verifier scheme, and it is based on bilinear pairing. Section 3.2 is an
extension of [19, 20] to multi-signer multi-verifier scheme, and it is based
on two hard problems: factoring problem and discrete logarithm problem.
Section 3.3 is an improvisation of section 3.2 based on the elliptic curve. We
have illustrated the algorithm with examples. We can combine the first
algorithms with the second algorithm or an improvised version of the second
algorithm by making minor changes described in section 3.4.

Let $A=\\{S_{1},S_{2},...,S_{n}\\}$ be the group of signers and
$B=\\{D_{1},D_{2},...,D_{m}\\}$ be the group of designated verifiers. Here $A$
and $B$ are systems that stores information which is made public by $S_{i}$
and $D_{j}$ respectively and then they interact with each other $l$ times,
where $l$ is a predetermined number.

###  3.1 Algorithm 1

Set up

Let $K$ be the security parameter and $sp\ =\ (G,G_{\tau},g,p,e,H_{1})\
\leftarrow\ Setup(K)$, where

  * •

$G$ is an additive cyclic group of large prime order $p$ and $g$ is a
generator of $G$,

  * •

$G_{\tau}$ is a multiplicative cyclic group of prime order $p$,

  * •

$e:\ G\times G\ \rightarrow\ G_{\tau}$ is symmetric admissible bilinear
pairing map,

  * •

$H_{1}:\\{0,1\\}^{*}\ \rightarrow\ G$ is a cryptographically secure hash
function.

Key Generation

  * •

Let there are $n$ signers $\\{S_{1},S_{2},...,S_{n}\\}$ and $m$ designated
verifiers $\\{D_{1},D_{2},...,D_{m}\\}$

  * •

Let $M\ \in\ \\{0,1\\}^{*}$ be the message, then $H_{1}(M)\ \in\ G$.

  * •

Let $a_{i}$ be the secret key of signer $S_{i}$ and $p_{i}\ =\ a_{i}g$ be the
corresponding public key of $S_{i}\ \ \ \forall\ \ i\in\\{1,2,...,n\\}$ known
to system $A$.

  * •

System $A$, then, publishes $u\ =\ \displaystyle\sum_{i=1}^{n}p_{i}$.

  * •

Let $b_{i}$ be the secret key of designated verifier $D_{i}$ and $q_{i}\ =\
b_{i}g$ be the corresponding public key of $D_{i}\ \ \ \forall\ \
i\in\\{1,2,...,m\\}$ known to system $B$.

  * •

System $B$, then, publishes $v\ =\ \displaystyle\sum_{i=1}^{m}q_{i}$.

Signature Algorithm

  * •

Each signer $S_{i}$ computes $\sigma_{i}\ =\
Sign(M,a_{i},q_{1},q_{2},...,q_{m})\ =\ e(H_{1}(M),a_{i}v)$ as his signature
and make it public.

  * •

After all signatures $(\sigma_{1},\sigma_{2},...,\sigma_{n})$ has been
collected by the system $A$, it computes $\sigma\ =\
\displaystyle\prod_{i=1}^{n}\sigma_{i}$ and send it to system $B$.

Verification Algorithm

  * •

System $B$ has a message $M$ and $\sigma$.

  * •

Each designated verifier $D_{i}$ computes $\zeta_{i}\ =\
Sign(M,b_{i},p_{1},p_{2},...,p_{n})\ =\ e(H_{1}(M),b_{i}u)$ and make it public
to the system $D$.

  * •

System $B$ computes $\zeta\ =\ \displaystyle\prod_{i=1}^{m}\zeta_{i}$.

  * •

Accept the output if $\sigma\ \equiv\ \zeta$ in $G_{\tau}$, otherwise reject.

Transcript-Simulation

Since, $\sigma\ \equiv\zeta$ in $G_{\tau}$, simulated signature is equivalent
to the signature produced by system A, thus simulation in this case is obvious
.

Example 1

Let, $G\ =\ \mathbb{Z}_{11}$ is an additive cyclic group of prime order $11$
and $2$ is a generator of $G$,

$G_{\tau}\ =\ \\{1,2,3,4,6,8,9,12,13,16,18\\}\ \ \ \bigodot_{23}$ is a
multiplicative cyclic group of prime order $11$,

$e:\ G\times G\ \rightarrow\ G_{\tau}$ is symmetric admissible bilinear
pairing map such that $e(2,2)\ =\ 2$.

Then, for any $a,b\ \in G,\ \ \exists\ \ 0\leq x,y\leq 10$ respectively such
that $a\ =\ 2x$ and $b\ =\ 2y$,

implies $e(a,b)\ =\ e(2,2)^{xy}\ =\ 2^{xy}$

Let, $H_{1}:\\{0,1\\}^{*}\ \rightarrow\ \mathbb{Z}_{11}$ is a
cryptographically secure hash function and $M\ \in\ \\{0,1\\}^{*}$ be the
message, then $H_{1}(M)\ \in\ \mathbb{Z}_{11}\ \ \Rightarrow\ \ H_{1}(M)\ =\
2c$ for some $1\leq c\leq 11$.

Let $A\ =\ \\{S_{1},S_{2},S_{3}\\}$ be three signers and $B\ =\
\\{D_{1},D_{2}\\}$ be two designated verifiers.

Let $a_{1}\ =\ 3$ , $a_{2}\ =\ 7$ , $a_{3}\ =\ 9$ be the secret keys and
$p_{1}\ =\ 6$ , $p_{2}\ =\ 3$ , $p_{3}\ =\ 7$ be public keys (made public to
system $A$ only) of $S_{1},S_{2},S_{3}$ respectively. Then System $A$ will
compute $u\ =\ \displaystyle\sum_{i=1}^{3}p_{i}\ \equiv\ 5$ and make it
public.

Let $b_{1}\ =\ 6$ , $b_{2}\ =\ 8$ be the secret keys and $q_{1}\ =\ 1$ ,
$q_{2}\ =\ 5$ be public keys (made public to system $B$ only) of $D_{1},D_{2}$
respectively. Then System $B$ will compute $v\ =\
\displaystyle\sum_{i=1}^{2}q_{i}\ \equiv\ 6$ and make it public.

Note that

$\sigma_{1}\ =\ e(2,2)^{9c}\ =\ 2^{9c}$ $\sigma_{2}\ =\ e(2,2)^{10c}\ =\
2^{10c}$ $\sigma_{3}\ =\ e(2,2)^{5c}\ =\ 2^{5c}$

implies

$\sigma\ =\ \displaystyle\prod_{i=1}^{3}\sigma_{i}\ =\ 2^{24c}\ \equiv\
2^{2c}\ \ in\ G_{\tau}$

Similarly

$\zeta_{1}\ =\ e(2,2)^{4c}\ =\ 2^{4c}$ $\zeta_{2}\ =\ e(2,2)^{9c}\ =\ 2^{9c}$

implies

$\zeta\ =\ \displaystyle\prod_{i=1}^{2}\zeta_{i}\ =\ 2^{13c}\ \equiv\ 2^{2c}\
\ in\ G_{\tau}$

Example 2

Let, $G\ =\ \mathbb{Z}_{53}$ is an additive cyclic group of prime order $53$
and $g\ =\ 5$ is a generator of $G$,

$G_{\tau}\ =\ <\ 3\ /\ 3^{53}\ =\ 1>\ \ \ \bigodot_{107}$ is a multiplicative
cyclic group of prime order $53$,

$e:\ G\times G\ \rightarrow\ G_{\tau}$ is symmetric admissible bilinear
pairing map such that $e(5,5)\ =\ 3$.

Then, for any $a,b\ \in G,\ \ \exists\ \ 0\leq x,y\leq 52$ respectively such
that $a\ =\ 5x$ and $b\ =\ 5y$,

implies $e(a,b)\ =\ e(5,5)^{xy}\ =\ 3^{xy}$

Let, $H_{1}:\\{0,1\\}^{*}\ \rightarrow\ \mathbb{Z}_{53}$ is a
cryptographically secure hash function and $M\ \in\ \\{0,1\\}^{*}$ be the
message, then $H_{1}(M)\ \in\ \mathbb{Z}_{53}\ \ \Rightarrow\ \ H_{1}(M)\ =\
5c$ for some $1\leq c\leq 52$.

Let $A\ =\ \\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$ be the system having five
signers and $B\ =\ \\{D_{1},D_{2},D_{3},D_{4},D_{5},D_{6},D_{7}\\}$ be the
system having seven designated verifiers.

Let $a_{1}\ =\ 7$ , $a_{2}\ =\ 12$ , $a_{3}\ =\ 15$ , $a_{4}\ =\ 19$ , $a_{5}\
=\ 31$ be the secret keys and $p_{1}\ =\ 35$ , $p_{2}\ =\ 7$ , $p_{3}\ =\ 22$
, $p_{4}\ =\ 42$ , $p_{5}\ =\ 49$ be public keys (made public to system $A$
only) of $S_{1},S_{2},S_{3},S_{4},S_{5}$ respectively. Then System $A$ will
compute $u\ =\ \displaystyle\sum_{i=1}^{5}p_{i}\ \equiv\ 49$ and make it
public.

Let $b_{1}\ =\ 10$ , $b_{2}\ =\ 13$ , $b_{3}\ =\ 17$ , $b_{4}\ =\ 23$ ,
$b_{5}\ =\ 51$ , $b_{6}\ =\ 27$ , $b_{7}\ =\ 36$ be the secret keys and
$q_{1}\ =\ 50$ , $q_{2}\ =\ 12$ , $q_{3}\ =\ 32$ , $q_{4}\ =\ 9$ , $q_{5}\ =\
43$ , $q_{6}\ =\ 29$ , $q_{2}\ =\ 21$ be public keys (made public to system
$B$ only) of $D_{1},D_{2}$ respectively. Then System $B$ will compute $v\ =\
\displaystyle\sum_{i=1}^{6}q_{i}\ \equiv\ 37$ and make it public.

Note that

$\sigma_{1}\ =\ 3^{20c}$ $\sigma_{2}\ =\ 3^{4c}$ $\sigma_{3}\ =\ 3^{5c}$
$\sigma_{4}\ =\ 3^{24c}$ $\sigma_{5}\ =\ 3^{28c}$

implies

$\sigma\ =\ \displaystyle\prod_{i=1}^{5}\sigma_{i}\ \equiv\ 3^{28c}\ \ in\
G_{\tau}$

Similarly

$\zeta_{1}\ =\ 3^{45c}$ $\zeta_{2}\ =\ 3^{32c}$ $\zeta_{3}\ =\ 3^{50c}$
$\zeta_{4}\ =\ 3^{24c}$ $\zeta_{5}\ =\ 3^{44c}$ $\zeta_{6}\ =\ 3^{42c}$
$\zeta_{7}\ =\ 3^{3c}$

implies

$\zeta\ =\ \displaystyle\prod_{i=1}^{7}\zeta_{i}\ \equiv\ 3^{28c}\ \ in\
G_{\tau}$

###  3.2 Algorithm 2

Set up

Let $K$ be the security parameter and $sp\ =\
(\widetilde{G},g_{A},g_{B},p,n_{A},n_{B},H_{2})\ \leftarrow\ Setup(K)$, where

  * •

$p$ be a large prime such that $n_{A}$ and $n_{B}$ are factors of $p-1$,

  * •

$\widetilde{G}\ =\ Z_{p}^{*}$ and $g_{A}\ ,\ g_{B}\ \ \in\ \widetilde{G}$ such
that $|g_{A}|\ =\ n_{A}$, $|g_{B}|\ =\ n_{B}$,

  * •

$H_{2}$ be a cryptographically secured hash function with arbitrary bit
length.

Key Generation

_Key generation algorithm for system $A$:_

  1. 1.

System $A$ chooses prime $p_{A}$ and $q_{A}$, then computes $n_{A}\ =\ p_{A}\
*\ q_{A}$.

  2. 2.

Each $S_{i}$ follow the following steps :

     * •

randomly choose $e_{A_{i}}$ such that g.c.d.$(e_{A_{i}},\phi(n_{A}))\ =\ 1$.

     * •

compute $d_{A_{i}}$ such that $e_{A_{i}}\ d_{A_{i}}\ =\ 1\ (mod\
\phi(n_{A}))$.

     * •

choose an integer $x_{A_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{A_{i}}\ =\ g_{A}^{x_{A_{i}}}\ (mod\ p)$.

     * •

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

     * •

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  3. 3.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

_Key generation algorithm for system $B$:_

  1. 1.

System $B$ chooses prime $p_{B}$ and $q_{B}$, then computes $n_{B}\ =\ p_{B}\
*\ q_{B}$.

  2. 2.

Each $D_{i}$ follow the following steps :

     * •

randomly choose $e_{B_{i}}$ such that g.c.d.$(e_{B_{i}},\phi(n_{B}))\ =\ 1$.

     * •

compute $d_{B_{i}}$ such that $e_{B_{i}}\ d_{B_{i}}\ =\ 1\ (mod\
\phi(n_{B}))$.

     * •

choose an integer $x_{B_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{B_{i}}\ =\ g_{B}^{x_{B_{i}}}\ (mod\ p)$.

     * •

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

     * •

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  3. 3.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

System $A$ generates a signature $(r,s,t,\bar{u})$ for a message $M$ as
follows:

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret.

  2. 2.

Each $S_{i}$ generates $r_{i}\ =\ g_{A}^{k_{i}}(y_{B_{1}}\ y_{B_{2}}\ .\ .\ .\
y_{B_{m}})^{-k_{i}}\ \ (mod\ p)$ , $s_{i}\ =\ g_{B}^{k_{i}}\ \ (mod\ p)$ and
$w_{i}\ =\ g_{A}^{k_{i}}\ \ (mod\ p)$ and make it public to the system $A$.

  3. 3.

System computes :

     * •

$r\ =\ \displaystyle\prod_{i=1}^{n}r_{i}\ \ (mod\ p)$

     * •

$s\ =\ (\displaystyle\prod_{i=1}^{n}s_{i})^{r}\ \ (mod\ p)$

     * •

$w\ =\ (\displaystyle\prod_{i=1}^{n}w_{i})^{r}\ \ (mod\ p)$

     * •

$z\ =\ H_{2}(M,w)$

     * •

$t\ =\ z^{\displaystyle\prod_{i=1}^{m}e_{B_{i}}}\ \ (mod\ n_{B})$

  4. 4.

After computing $(r,s,w,z,t)$, they are made public to all $S_{i}$ and then
each $S_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}r$ and make it public to
the system $A$.

  5. 5.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{n}v_{i}\ \ (mod\ n_{A})$

     * •

$\bar{u}\ =\ (\bar{v})^{\displaystyle\prod_{i=1}^{n}d_{A_{i}}}\ \ (mod\
n_{A})$

System $A$ sends the message $M$ and the signature $(r,s,t,\bar{u})$ to the
system $B$ (and all the designated verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and signature $(r,s,t,\bar{u})$, each
designated verifier $D_{i}$ computes $z_{i}\ =\ s^{x_{B_{i}}}$ and make it
public. Then, each $D_{i}$ can separately or together verify and validate the
signature by checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{n}e_{A_{i}}}\ \ (mod\
n_{A})$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{m}d_{B_{i}}}\ \ (mod\ n_{B})$

  3. 3.

Check $c\ =\ g_{A}^{a}\ (y_{A_{1}}y_{A_{2}}...y_{A_{n}})^{-b}\ \ (mod\ p)\ \
=\ \ r^{r}\displaystyle\prod_{i=1}^{m}z_{i}\ \ (mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{2}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

Transcript-Simulation

System $B$ (or designated verifier $D$) can simulate the correct transcripts
as follows:

  1. 1.

System $B$ chooses a random integer $k^{{}^{\prime}}$ and keep it secret.

  2. 2.

Then $D$ generates :

     * •

$r^{{}^{\prime}}\ =\ g_{B}^{k^{{}^{\prime}}}(y_{A_{1}}\ y_{A_{2}}\ .\ .\ .\
y_{A_{n}})^{-k^{{}^{\prime}}}\ \ (mod\ p)$

     * •

$s^{{}^{\prime}}\ =\ g_{A}^{k^{{}^{\prime}}r^{{}^{\prime}}}\ \ (mod\ p)$

     * •

$w^{{}^{\prime}}\ =\ g_{B}^{k^{{}^{\prime}}r^{{}^{\prime}}}\ \ (mod\ p)$

     * •

$z^{{}^{\prime}}\ =\ H_{2}(M,w^{{}^{\prime}})$

     * •

$t^{{}^{\prime}}\ =\
{z^{{}^{\prime}}}^{\displaystyle\prod_{i=1}^{n}e_{A_{i}}}\ \ (mod\ n_{A})$

     * •

$v^{{}^{\prime}}\ =\ \displaystyle\sum_{i=1}^{m}{v_{i}}^{{}^{\prime}}\ \ (mod\
n_{B})$, where ${v_{i}}^{{}^{\prime}}\ =\ z^{{}^{\prime}}x_{B_{i}}\ +\
k^{{}^{\prime}}r^{{}^{\prime}}$ is made public by $D_{i}$

     * •

$u^{{}^{\prime}}\ =\ ({v^{{}^{\prime}}})^{d_{B}}\ \ (mod\ n_{B})$, where
$d_{B}\ =\ \displaystyle\prod_{i=1}^{m}d_{B_{i}}$

System $B$ simulated signature is
$(r^{{}^{\prime}},s^{{}^{\prime}},t^{{}^{\prime}},u^{{}^{\prime}})$.

Example 1

Let $A=\\{S_{1},S_{2},S_{3}\\}$ be the group of three signers (or provers) and
$B=\\{D_{1},D_{2}\\}$ be the group of two designated verifiers.

Let $p\ =\ 211$ be a prime such that $n_{A}\ =\ 15$ and $n_{B}\ =\ 14$ are
factors of $p-1\ =\ 210$.

Let $\widetilde{G}\ =\ Z_{211}^{*}$ and $g_{A}\ =\ 137\ ,\ g_{B}\ =\ 63$ in
$\widetilde{G}$ such that $|137|\ =\ 15$, $|63|\ =\ 14$.

Let $H_{2}$ be a cryptographically secured hash function with arbitrary bit
length.

Key generation algorithm for system $A$:

  1. 1.

System $A$ chooses prime $p_{A}\ =\ 3$ and $q_{A}\ =\ 5$, then computes
$n_{A}\ =\ 3\ *\ 5$.

  2. 2.

Each $S_{i}$ follow the following steps :

$S_{i}$ | $e_{A_{i}}$ | $d_{A_{i}}$ | $x_{A_{i}}$ | $y_{A_{i}}$
---|---|---|---|---
$S_{1}$ | $13$ | $5$ | $7$ | $150$
$S_{2}$ | $7$ | $7$ | $16$ | $137$
$S_{3}$ | $11$ | $3$ | $21$ | $55$

  3. 3.

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

  4. 4.

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  5. 5.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

Key generation algorithm for system $B$:

  1. 1.

System $B$ chooses prime $p_{B}\ =\ 2$ and $q_{B}\ =\ 7$, then computes
$n_{B}\ =\ 2\ *\ 7$.

  2. 2.

Each $D_{i}$ follow the following steps :

$D_{i}$ | $e_{B_{i}}$ | $d_{B_{i}}$ | $x_{B_{i}}$ | $y_{B_{i}}$
---|---|---|---|---
$D_{1}$ | $5$ | $5$ | $19$ | $153$
$D_{2}$ | $11$ | $5$ | $17$ | $12$

  3. 3.

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

  4. 4.

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  5. 5.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret and then,
generates

$r_{i}\ =\ g_{A}^{k_{i}}(y_{B_{1}}\ y_{B_{2}}\ .\ .\ .\ y_{B_{e}})^{-k_{i}}\ \
(mod\ p)\ ,\ s_{i}\ =\ g_{B}^{k_{i}}\ \ (mod\ p)\ and\ w_{i}\ =\
g_{A}^{k_{i}}\ \ (mod\ p)$

and make it public to the system $A$.

$S_{i}$ | $k_{i}$ | $r_{i}$ | $s_{i}$ | $w_{i}$
---|---|---|---|---
$S_{1}$ | $8$ | $136$ | $148$ | $83$
$S_{2}$ | $12$ | $114$ | $171$ | $71$
$S_{3}$ | $14$ | $134$ | $210$ | $134$

  2. 2.

System computes :

     * •

$r\ =\ \displaystyle\prod_{i=1}^{3}r_{i}\ \equiv\ 30\ \ (mod\ p)$

     * •

$s\ =\ (\displaystyle\prod_{i=1}^{3}s_{i})^{r}\ \equiv\ 144\ \ (mod\ p)$

     * •

$w\ =\ (\displaystyle\prod_{i=1}^{3}w_{i})^{r}\ \equiv\ 1\ \ (mod\ p)$

     * •

$z\ =\ H_{2}(M,w)$

     * •

$t\ =\ z^{\displaystyle\prod_{i=1}^{2}e_{B_{i}}}\ \equiv\ z^{55}\ \equiv z\ \
(mod\ 14)$

  3. 3.

After computing $(r,s,w,z,t)$, they are made public to all $P_{i}$ and then
each $P_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}r$ and make it public to
the system $A$.

$v_{1}\ =\ 7z+240\ ,\ v_{2}\ =\ 16z+360\ ,\ v_{3}\ =\ 21z+420$

  4. 4.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{3}v_{i}\ \equiv 44z\ \ (mod\ 15)$

     * •

$\bar{u}\ =\ (\bar{v})^{\displaystyle\prod_{i=1}^{3}d_{A_{i}}}\ \equiv\
(\bar{v})^{5*7*3}\ \equiv\ \bar{v}\ \ (mod\ 15)$

System $A$ sends the message $M$ and the signature $(r,s,t,\bar{u})$ to the
system $B$ (and all the verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(r,s,t,\bar{u})$, each
designated verifier $D_{i}$ computes $z_{i}\ =\ s^{x_{B_{i}}}$ and make it
public. Then, each $D_{i}$ can separately or together verify and validate the
signature by checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{3}e_{A_{i}}}\ \ (mod\
n_{A})$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{2}d_{B_{i}}}\ \ (mod\ n_{B})$

  3. 3.

Check $c\ =\ g_{A}^{a}\ (y_{A_{1}}y_{A_{2}}y_{A_{3}})^{-b}\ \ (mod\ p)\ \ =\ \
r^{r}\displaystyle\prod_{i=1}^{2}z_{i}\ \ (mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{2}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

Example 2

Let $A=\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$ be the group of five signers (or
provers) and $B=\\{D_{1},D_{2},D_{3},D_{4},D_{5},D_{6},D_{7}\\}$ be the group
of seven designated verifiers.

Let $p\ =\ 102103$ be a prime such that $n_{A}\ =\ 91$ and $n_{B}\ =\ 187$ are
factors of $p-1\ =\ 102102$.

Let $\widetilde{G}\ =\ Z_{102103}^{*}$ and $g_{A}\ =\ 44494\ ,\ g_{B}\ =\
12733$ in $\widetilde{G}$ such that $|44494|\ =\ 91$, $|12733|\ =\ 187$.

Let $H_{2}$ be a cryptographically secured hash function with arbitrary bit
length.

Key generation algorithm for system $A$:

  1. 1.

System $A$ chooses prime $p_{A}\ =\ 7$ and $q_{A}\ =\ 13$, then computes
$n_{A}\ =\ 7\ *\ 13$.

  2. 2.

Each $S_{i}$ follow the following steps :

$S_{i}$ | $e_{A_{i}}$ | $d_{A_{i}}$ | $x_{A_{i}}$ | $y_{A_{i}}$
---|---|---|---|---
$S_{1}$ | $5$ | $29$ | $15$ | $58327$
$S_{2}$ | $11$ | $59$ | $19$ | $69494$
$S_{3}$ | $7$ | $31$ | $24$ | $69058$
$S_{4}$ | $23$ | $47$ | $18$ | $88515$
$S_{5}$ | $35$ | $35$ | $32$ | $26123$

  3. 3.

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

  4. 4.

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  5. 5.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

Key generation algorithm for system $A$:

  1. 1.

System $B$ chooses prime $p_{B}\ =\ 11$ and $q_{B}\ =\ 17$, then computes
$n_{B}\ =\ 11\ *\ 17$.

  2. 2.

Each $D_{i}$ follow the following steps :

$D_{i}$ | $e_{B_{i}}$ | $d_{B_{i}}$ | $x_{B_{i}}$ | $y_{B_{i}}$
---|---|---|---|---
$D_{1}$ | $3$ | $107$ | $32$ | $37552$
$D_{2}$ | $7$ | $23$ | $17$ | $64089$
$D_{3}$ | $11$ | $131$ | $22$ | $63449$
$D_{4}$ | $19$ | $59$ | $27$ | $93579$
$D_{5}$ | $51$ | $91$ | $18$ | $38061$
$D_{6}$ | $27$ | $83$ | $21$ | $91435$
$D_{7}$ | $91$ | $51$ | $51$ | $30671$

  3. 3.

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

  4. 4.

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  5. 5.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret and then,
generates

$r_{i}\ =\ g_{A}^{k_{i}}(y_{B_{1}}\ y_{B_{2}}\ .\ .\ .\ y_{B_{e}})^{-k_{i}}\ \
(mod\ p)\ ,\ s_{i}\ =\ g_{B}^{k_{i}}\ \ (mod\ p)\ and\ w_{i}\ =\
g_{A}^{k_{i}}\ \ (mod\ p)$

and make it public to the system $A$.

$S_{i}$ | $k_{i}$ | $r_{i}$ | $s_{i}$ | $w_{i}$
---|---|---|---|---
$S_{1}$ | $42980$ | $22513$ | $68227$ | $59022$
$S_{2}$ | $68841$ | $77234$ | $67990$ | $84473$
$S_{3}$ | $82718$ | $60319$ | $8171$ | $15368$
$S_{4}$ | $90739$ | $49375$ | $58517$ | $68284$
$S_{5}$ | $19344$ | $40471$ | $35552$ | $91619$

  2. 2.

System computes :

     * •

$r\ =\ \displaystyle\prod_{i=1}^{5}r_{i}\ \equiv\ 41707\ \ (mod\ p)$

     * •

$s\ =\ (\displaystyle\prod_{i=1}^{5}s_{i})^{r}\ \equiv\ 90653\ \ (mod\ p)$

     * •

$w\ =\ (\displaystyle\prod_{i=1}^{5}w_{i})^{r}\ \equiv\ 91371\ \ (mod\ p)$

     * •

$z\ =\ H_{2}(M,w)$

     * •

$t\ =\ z^{\displaystyle\prod_{i=1}^{7}e_{B_{i}}}\ \equiv\ z^{549972423}\
\equiv z^{103}\ \ (mod\ 187)$, provided $g.c.d.(z,187)\ =\ 1$

  3. 3.

After computing $(r,s,w,z,t)$, they are made public to all $S_{i}$ and then
each $S_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}r$ and make it public to
the system $A$.

$v_{1}\ =\ 15z+42980r\ ,\ v_{2}\ =\ 19z+68841r\ ,\ v_{3}\ =\ 24z+82718r\ ,\
v_{4}\ =\ 18z+90739r\ ,\ v_{5}\ =\ 32z+19344r$

  4. 4.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{5}v_{i}\ \equiv 17z+31\ \ (mod\ 91)$

     * •

$\bar{u}\ =\ (\bar{v})^{\displaystyle\prod_{i=1}^{5}d_{A_{i}}}\ \equiv\
(\bar{v})^{87252445}\ \equiv\ (\bar{v})^{37}\ \ (mod\ 91)$

System $A$ sends the message $M$ and the signature $(r,s,t,\bar{u})$ to the
system $B$ (and all the verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(r,s,t,\bar{u})$, each
verifier $D_{i}$ computes $z_{i}\ =\ s^{x_{B_{i}}}$ and make it public. Then,
each $D_{i}$ can separately or together verify and validate the signature by
checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{5}e_{A_{i}}}\ \ (mod\
n_{A})$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{7}d_{B_{i}}}\ \ (mod\ n_{B})$

  3. 3.

Check $c\ =\ g_{A}^{a}\ (y_{A_{1}}y_{A_{2}}y_{A_{3}}y_{A_{4}}y_{A_{5}})^{-b}\
\ (mod\ p)\ \ =\ \ r^{r}\displaystyle\prod_{i=1}^{7}z_{i}\ \ (mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{2}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

###  3.3 Algorithm 3

Set up

Let $K$ be the security parameter and $sp\ =\ (E,P,Q,p,n_{A},n_{B},H_{3})\
\leftarrow\ Setup(K)$, where

  * •

$p$ be a large prime,

  * •

$E$ be an elliptic curve over $Z_{p}$ such that $n_{A}$ and $n_{B}$ are
factors of $|E|$, where $n_{A}$ and $n_{B}$ are product of two large primes,

  * •

$P\ ,\ Q\ \ \in\ E$ such that $|P|\ =\ n_{A}$, $|Q|\ =\ n_{B}$,

  * •

$H_{3}$ be a cryptographically secured hash function with arbitrary bit
length.

Key Generation

_Key generation algorithm for system $A$:_

  1. 1.

System $A$ chooses prime $p_{A}$ and $q_{A}$, then computes $n_{A}\ =\ p_{A}\
*\ q_{A}$.

  2. 2.

Each $S_{i}$ follow the following steps :

     * •

randomly choose $e_{A_{i}}$ such that g.c.d.$(e_{A_{i}},\phi(n_{A}))\ =\ 1$.

     * •

compute $d_{A_{i}}$ such that $e_{A_{i}}\ d_{A_{i}}\ =\ 1\ (mod\
\phi(n_{A}))$.

     * •

choose an integer $x_{A_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{A_{i}}\ =\ [x_{A_{i}}]P\ (mod\ p)$.

     * •

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

     * •

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  3. 3.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

_Key generation algorithm for system $B$:_

  1. 1.

System $B$ chooses prime $p_{B}$ and $q_{B}$, then computes $n_{B}\ =\ p_{B}\
*\ q_{B}$.

  2. 2.

Each $D_{i}$ follow the following steps :

     * •

randomly choose $e_{B_{i}}$ such that g.c.d.$(e_{B_{i}},\phi(n_{B}))\ =\ 1$.

     * •

compute $d_{B_{i}}$ such that $e_{B_{i}}\ d_{B_{i}}\ =\ 1\ (mod\
\phi(n_{B}))$.

     * •

choose an integer $x_{B_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{B_{i}}\ =\ [x_{B_{i}}]Q\ (mod\ p)$.

     * •

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

     * •

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  3. 3.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

System $A$ generates a signature $(r,s,t,\bar{u})$ for a message $M$ as
follows:

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret.

  2. 2.

Each $S_{i}$ generates $r_{i}\ =\ [{k_{i}}]P-[{k_{i}}](y_{B_{1}}\ +\
y_{B_{2}}\ +\ .\ .\ .\ +\ y_{B_{m}})\ \ (mod\ p)$ , $s_{i}\ =\ [{k_{i}}]Q\ \
(mod\ p)$ and $w_{i}\ =\ [{k_{i}}]P\ \ (mod\ p)$ and make it public to the
system $A$.

  3. 3.

System computes :

     * •

$r\ =\ \displaystyle\sum_{i=1}^{n}r_{i}\ \ (mod\ p)$

     * •

$s\ =\ \displaystyle\sum_{i=1}^{n}s_{i}\ \ (mod\ p)$

     * •

$w\ =\ \displaystyle\sum_{i=1}^{n}w_{i}\ \ (mod\ p)$

     * •

$z\ =\ H_{3}(M,w)$

     * •

$t\ =\ z^{\displaystyle\prod_{i=1}^{m}e_{B_{i}}}\ \ (mod\ n_{B})$

  4. 4.

After computing $(r,s,w,z,t)$, they are made public to all $S_{i}$ and then
each $S_{i}$ computes $v_{i}\ =\ z.x_{A_{i}}\ +\ k_{i}$ and make it public to
the system $A$.

  5. 5.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{n}v_{i}\ \ (mod\ n_{A})$

     * •

$\bar{u}\ =\ (\bar{v})^{\displaystyle\prod_{i=1}^{n}d_{A_{i}}}\ \ (mod\
n_{A})$

System $A$ sends the message $M$ and the signature $(r,s,t,\bar{u})$ to the
system $B$ (and all the verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(r,s,t,\bar{u})$, each
verifier $D_{i}$ computes $z_{i}\ =\ [x_{B_{i}}]s$ and make it public. Then,
each $D_{i}$ can separately or together verify and validate the signature by
checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{n}e_{A_{i}}}\ \ (mod\
n_{A})$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{m}d_{B_{i}}}\ \ (mod\ n_{B})$

  3. 3.

Check $c\ =\ [a]P\ -\ b(y_{A_{1}}\ +\ y_{A_{2}}\ +\ ...\ +\ y_{A_{n}})\ \
(mod\ p)\ \ =\ \ r\ +\ \displaystyle\sum_{i=1}^{m}z_{i}\ \ (mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{3}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

Transcript Simulation

System $B$ (or designated verifier $D$) can simulate the correct transcripts
as follows:

  1. 1.

System $B$ chooses a random integer $k^{{}^{\prime}}$ and keep it secret.

  2. 2.

Then $B$ generates :

     * •

$r^{{}^{\prime}}\ =\ [{k^{{}^{\prime}}}]Q-[{k^{{}^{\prime}}}](y_{A_{1}}\ +\
y_{A_{2}}\ +\ .\ .\ .\ +\ y_{A_{n}})\ \ (mod\ p)$

     * •

$s^{{}^{\prime}}\ =\ [{k^{{}^{\prime}}}]P\ \ (mod\ p)$

     * •

$w^{{}^{\prime}}\ =\ [{k^{{}^{\prime}}}]Q\ \ (mod\ p)$

     * •

$z^{{}^{\prime}}\ =\ H(m,w^{{}^{\prime}})$

     * •

$t^{{}^{\prime}}\ =\
{z^{{}^{\prime}}}^{(\displaystyle\prod_{i=1}^{n}e_{A_{i}})}\ \ (mod\ n_{A})$

     * •

$v^{{}^{\prime}}\ =\ \displaystyle\sum_{i=1}^{m}{v_{i}}^{{}^{\prime}}\ \ (mod\
n_{B})$, where ${v_{i}}^{{}^{\prime}}\ =\ z^{{}^{\prime}}x_{B_{i}}\ +\
k^{{}^{\prime}}$ is made public by $D_{i}$

     * •

$u^{{}^{\prime}}\ =\ ({v^{{}^{\prime}}})^{d_{B}}\ \ (mod\ n_{B})$, where
$d_{B}\ =\ \displaystyle\prod_{i=1}^{m}d_{B_{i}}$

System $B$ simulated signature is
$(r^{{}^{\prime}},s^{{}^{\prime}},t^{{}^{\prime}},u^{{}^{\prime}})$.

Example 1

Let $A=\\{S_{1},S_{2},S_{3}\\}$ be the group of three signers (or provers) and
$B=\\{D_{1},D_{2}\\}$ be the group of two designated verifiers.

Let $p\ =\ 419$ be a prime and $E$ be an elliptic curve over $\mathbb{Z}_{p}$
such that

$E\ =\ E_{\mathbb{Z}_{p}}\ =\ \\{(x,y)\in\mathbb{Z}_{p}\times\mathbb{Z}_{p}\
/\ y^{2}=x^{3}+2\\}$

Note that $|E|\ =\ 420$ and $E$ is a cyclic group . Also $n_{A}\ =\ 15$ and
$n_{B}\ =\ 14$ are factors of $|E|$.

Let $P\ =\ (22,151)\ ,\ Q\ =\ (55,156)$ in $E$ such that $|P|\ =\ 15$, $|Q|\
=\ 14$.

Let $H_{3}$ be a cryptographically secured hash function with arbitrary bit
length.

Key generation algorithm for system $A$:

  1. 1.

System $A$ chooses prime $p_{A}\ =\ 3$ and $q_{A}\ =\ 5$, then computes
$n_{A}\ =\ 3\ *\ 5$.

  2. 2.

Each $S_{i}$ follow the following steps :

$S_{i}$ | $e_{A_{i}}$ | $d_{A_{i}}$ | $x_{A_{i}}$ | $y_{A_{i}}$
---|---|---|---|---
$S_{1}$ | $13$ | $5$ | $7$ | $7P$
$S_{2}$ | $7$ | $7$ | $16$ | $P$
$S_{3}$ | $11$ | $3$ | $21$ | $6P$

  3. 3.

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

  4. 4.

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  5. 5.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

Key generation algorithm for system $B$:

  1. 1.

System $B$ chooses prime $p_{B}\ =\ 2$ and $q_{B}\ =\ 7$, then computes
$n_{B}\ =\ 2\ *\ 7$.

  2. 2.

Each $D_{i}$ follow the following steps :

$D_{i}$ | $e_{B_{i}}$ | $d_{B_{i}}$ | $x_{B_{i}}$ | $y_{B_{i}}$
---|---|---|---|---
$D_{1}$ | $5$ | $5$ | $19$ | $5Q$
$D_{2}$ | $11$ | $5$ | $17$ | $3Q$

  3. 3.

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

  4. 4.

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  5. 5.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret and then,
generates

$r_{i}\ =[{k_{i}}]P-[{k_{i}}](y_{B_{1}}\ +\ y_{B_{2}}\ +\ .\ .\ .\ +\
y_{B_{e}})\ \ (mod\ p)\ \ ,\ \ s_{i}\ =\ [{k_{i}}]Q\ \ (mod\ p)\ \ and\ \
w_{i}\ =\ [{k_{i}}]P\ \ (mod\ p)$

and make it public to the system $A$ :

$S_{i}$ | $k_{i}$ | $r_{i}$ | $s_{i}$ | $w_{i}$
---|---|---|---|---
$S_{1}$ | $8$ | $8P-8Q$ | $8Q$ | $8P$
$S_{2}$ | $12$ | $12P-12Q$ | $12Q$ | $12P$
$S_{3}$ | $14$ | $14P$ | $14Q$ | $14P$

  2. 2.

System computes :

     * •

$r\ =\ \displaystyle\sum_{i=1}^{3}r_{i}\ \equiv\ 4P-6Q\ \ (mod\ p)$

     * •

$s\ =\ \displaystyle\sum_{i=1}^{3}s_{i}\ \equiv\ 6Q\ \ (mod\ p)$

     * •

$w\ =\ \displaystyle\prod_{i=1}^{3}w_{i}\ \equiv\ 4P\ \ (mod\ p)$

     * •

$z\ =\ H_{3}(M,w)$

     * •

$t\ =\ z^{(\displaystyle\prod_{i=1}^{2}e_{B_{i}})}\ \equiv\ z^{55}\ \equiv z\
\ (mod\ 14)$

  3. 3.

After computing $(r,s,w,z,t)$, they are made public to all $S_{i}$ and then
each $S_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}$ and make it public to
the system $A$.

$v_{1}\ =\ 7z+8\ ,\ v_{2}\ =\ 16z+12\ ,\ v_{3}\ =\ 21z+14$

  4. 4.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{3}v_{i}\ \equiv 14z+4\ \ (mod\ 15)$

     * •

$\bar{u}\ =\ (\bar{v})^{(\displaystyle\prod_{i=1}^{3}d_{A_{i}})}\ \equiv\
(\bar{v})^{5*7*3}\ \equiv\ \bar{v}\ \ (mod\ 15)$

System $A$ sends the message $M$ and signature $(r,s,t,\bar{u})$ to the system
$B$ (and all the verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(r,s,t,\bar{u})$, each
verifier $D_{i}$ computes $z_{i}\ =\ [x_{B_{i}}]s$ and make it public. Then,
each verifier $D_{i}$ can separately or together verify and validate the
signature by checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{3}e_{A_{i}}}\ \ (mod\
n_{A})$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{2}d_{B_{i}}}\ \ (mod\ n_{B})$

  3. 3.

Check $c\ =\ [a]P\ -\ b(y_{A_{1}}\ +\ y_{A_{2}}\ +\ y_{A_{3}})\ \ (mod\ p)\ \
=\ \ r\ +\ \displaystyle\sum_{i=1}^{2}z_{i}\ \ (mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{3}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

Example 2

Let $A=\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$ be the group of five signers (or
provers) and $B=\\{D_{1},D_{2},D_{3},D_{4},D_{5},D_{6},D_{7}\\}$ be the group
of seven designated verifiers.

Let $p\ =\ 6793$ be a prime and $E$ be an elliptic curve over $\mathbb{Z}_{p}$
such that

$E\ =\ E_{\mathbb{Z}_{p}}\ =\ \\{(x,y)\in\mathbb{Z}_{p}\times\mathbb{Z}_{p}\
/\ y^{2}=x^{3}+5\\}$

Note that $|E|\ =\ 6916$ and $E$ is a cyclic group. Also $n_{A}\ =\ 91$ and
$n_{B}\ =\ 38$ are factors of $|E|$.

Let $P\ =\ (3245,4097)\ ,\ Q\ =\ (5223,4702)$ in $E$ such that $|P|\ =\ 91$,
$|Q|\ =\ 38$.

Let $H_{3}$ be a cryptographically secured hash function with arbitrary bit
length.

Key generation algorithm for system $A$:

  1. 1.

System $A$ chooses prime $p_{A}\ =\ 7$ and $q_{A}\ =\ 13$, then computes
$n_{A}\ =\ 7\ *\ 13$.

  2. 2.

Each $S_{i}$ follow the following steps :

$S_{i}$ | $e_{A_{i}}$ | $d_{A_{i}}$ | $x_{A_{i}}$ | $y_{A_{i}}$
---|---|---|---|---
$S_{1}$ | $5$ | $29$ | $15$ | $15P$
$S_{2}$ | $11$ | $59$ | $19$ | $19P$
$S_{3}$ | $7$ | $31$ | $24$ | $24P$
$S_{4}$ | $23$ | $47$ | $18$ | $18P$
$S_{5}$ | $35$ | $35$ | $32$ | $32P$

  3. 3.

public key of $S_{i}$ is $(e_{A_{i}},y_{A_{i}})$.

  4. 4.

private key of $S_{i}$ is $(d_{A_{i}},x_{A_{i}})$.

  5. 5.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$.

Key generation algorithm for system $B$:

  1. 1.

System $B$ chooses prime $p_{B}\ =\ 2$ and $q_{B}\ =\ 19$, then computes
$n_{B}\ =\ 2\ *\ 19$.

  2. 2.

Each $D_{i}$ follow the following steps :

$D_{i}$ | $e_{B_{i}}$ | $d_{B_{i}}$ | $x_{B_{i}}$ | $y_{B_{i}}$
---|---|---|---|---
$D_{1}$ | $5$ | $11$ | $32$ | $32Q$
$D_{2}$ | $7$ | $13$ | $17$ | $17Q$
$D_{3}$ | $11$ | $5$ | $22$ | $22Q$
$D_{4}$ | $13$ | $7$ | $27$ | $27Q$
$D_{5}$ | $17$ | $17$ | $18$ | $18Q$
$D_{6}$ | $13$ | $7$ | $21$ | $21Q$
$D_{7}$ | $7$ | $13$ | $51$ | $51Q$

  3. 3.

public key of $D_{i}$ is $(e_{B_{i}},y_{B_{i}})$.

  4. 4.

private key of $D_{i}$ is $(d_{B_{i}},x_{B_{i}})$.

  5. 5.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$.

Signature Algorithm

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret and then,
generates

$r_{i}\ =[{k_{i}}]P-[{k_{i}}](y_{B_{1}}\ +\ y_{B_{2}}\ +\ .\ .\ .\ +\
y_{B_{e}})\ \ (mod\ p)\ \ ,\ \ s_{i}\ =\ [{k_{i}}]Q\ \ (mod\ p)\ \ and\ \
w_{i}\ =\ [{k_{i}}]P\ \ (mod\ p)$

and make it public to the system $A$ :

$S_{i}$ | $k_{i}$ | $r_{i}$ | $s_{i}$ | $w_{i}$
---|---|---|---|---
$S_{1}$ | $5770$ | $37P-12Q$ | $32Q$ | $37P$
$S_{2}$ | $2769$ | $39P-10Q$ | $33Q$ | $39P$
$S_{3}$ | $6476$ | $15P-6Q$ | $16Q$ | $15P$
$S_{4}$ | $1751$ | $22P-32Q$ | $3Q$ | $22P$
$S_{5}$ | $88$ | $88P-14Q$ | $12Q$ | $88P$

  2. 2.

System computes :

     * •

$r\ =\ \displaystyle\sum_{i=1}^{5}r_{i}\ \equiv\ 19P-36Q\ \ (mod\ p)$

     * •

$s\ =\ \displaystyle\sum_{i=1}^{5}s_{i}\ \equiv\ 20Q\ \ (mod\ p)$

     * •

$w\ =\ \displaystyle\prod_{i=1}^{5}w_{i}\ \equiv\ 19P\ \ (mod\ p)$

     * •

$z\ =\ H_{3}(M,w)$

     * •

$t\ =\ z^{(\displaystyle\prod_{i=1}^{7}e_{B_{i}})}\ (mod\ 38)$

  3. 3.

After computing $(r,s,w,z,t)$, they are made public to all $S_{i}$ and then
each $S_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}$ and make it public to
the system $A$.

$v_{1}\ =\ 15z+5770\ ,\ v_{2}\ =\ 19z+2769\ ,\ v_{3}\ =\ 24z+6476\ ,\ v_{4}\
=\ 18z+1751\ ,\ v_{5}\ =\ 32z+88$

  4. 4.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{5}v_{i}\ \equiv 17z+19\ \ (mod\ 91)$

     * •

$\bar{u}\ =\ (\bar{v})^{(\displaystyle\prod_{i=1}^{5}d_{A_{i}})}\ (mod\ 91)$

System $A$ sends the message $M$ and the signature $(r,s,t,\bar{u})$ to the
system $B$ (and all the verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(r,s,t,\bar{u})$, each
verifier $D_{i}$ computes $z_{i}\ =\ [x_{B_{i}}]s$ and make it public. Then,
each $D_{i}$ can separately or together verify and validate the signature by
checking the following equations:

  1. 1.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{5}e_{A_{i}}}\ \ (mod\
91)$

  2. 2.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{7}d_{B_{i}}}\ \ (mod\ 38)$

  3. 3.

Check $c\ =\ [a]P\ -\ b(y_{A_{1}}\ +\ y_{A_{2}}\ +\ y_{A_{3}}\ +\ y_{A_{4}}\
+\ y_{A_{5}})\ \ (mod\ p)\ \ =\ \ r\ +\ \displaystyle\sum_{i=1}^{7}z_{i}\ \
(mod\ p)$

  4. 4.

Lastly, signatures are accepted if $b\ =\ H_{3}(M,c)$.

  5. 5.

If any of the condition from above two conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

###  3.4 Final Algorithm

In this section, we have combined algorithm 1 and 2 to enhance the security of
the algorithm.

Set up

Let $K$ be the security parameter and $sp\ =\
(G,G_{\tau},\widetilde{G},g,g_{A},g_{B},p,e,n_{A},n_{B},H_{1},H_{2})\
\leftarrow\ Setup(K)$, where

  * •

$p$ be a large prime such that $n_{A}$ and $n_{B}$ are factors of $p-1$,

  * •

$G$ is an additive cyclic group of large prime order $p$ and $g$ is a
generator of $G$,

  * •

$G_{\tau}$ is a multiplicative cyclic group of prime order $p$,

  * •

$\widetilde{G}\ =\ Z_{p}^{*}$ and $g_{A}\ ,\ g_{B}\ \ \in\ \widetilde{G}$ such
that $|g_{A}|\ =\ n_{A}$, $|g_{B}|\ =\ n_{B}$,

  * •

$e:\ G\times G\ \rightarrow\ G_{\tau}$ is symmetric admissible bilinear
pairing map,

  * •

$H_{1}:\\{0,1\\}^{*}\ \rightarrow\ G$ is a cryptographically secure hash
function,

  * •

$H_{2}$ be a cryptographically secured hash function with arbitrary bit
length.

Key Generation

_Key generation algorithm for system $A$:_

  1. 1.

System $A$ chooses prime $p_{A}$ and $q_{A}$, then computes $n_{A}\ =\ p_{A}\
*\ q_{A}$.

  2. 2.

Each $S_{i}$ follow the following steps :

     * •

choose $a_{i}\ \in\ G$.

     * •

calculate $p_{i}\ =\ a_{i}g\ (mod\ p)$.

     * •

randomly choose $e_{A_{i}}$ such that g.c.d.$(e_{A_{i}},\phi(n_{A}))\ =\ 1$.

     * •

compute $d_{A_{i}}$ such that $e_{A_{i}}\ d_{A_{i}}\ =\ 1\ (mod\
\phi(n_{A}))$.

     * •

choose an integer $x_{A_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{A_{i}}\ =\ g_{A}^{x_{A_{i}}}\ (mod\ p)$.

     * •

public key of $S_{i}$ is $(p_{i},e_{A_{i}},y_{A_{i}})$.

     * •

private key of $S_{i}$ is $(a_{i},d_{A_{i}},x_{A_{i}})$.

  3. 3.

System $A$, then, publishes $u\ =\ \displaystyle\sum_{i=1}^{n}p_{i}$.

  4. 4.

Note : Since, each member in system $A$ knows $\phi(n_{A})$ and $e_{A_{i}}\ \
\forall i$, they can compute $d_{A_{i}}$. Thus, $d_{A_{i}}$ is private for
members of system $B$ but not for members of system $A$. Similarly, $p_{i}$ is
public to system $A$ only.

_Key generation algorithm for system $B$:_

  1. 1.

System $B$ chooses prime $p_{B}$ and $q_{B}$, then computes $n_{B}\ =\ p_{B}\
*\ q_{B}$.

  2. 2.

Each $D_{i}$ follow the following steps :

     * •

choose $b_{i}\ \in\ G$.

     * •

calculate $q_{i}\ =\ b_{i}g\ (mod\ p)$.

     * •

randomly choose $e_{B_{i}}$ such that g.c.d.$(e_{B_{i}},\phi(n_{B}))\ =\ 1$.

     * •

compute $d_{B_{i}}$ such that $e_{B_{i}}\ d_{B_{i}}\ =\ 1\ (mod\
\phi(n_{B}))$.

     * •

choose an integer $x_{B_{i}}\ \in\ Z_{p}^{*}$.

     * •

calculate $y_{B_{i}}\ =\ g_{B}^{x_{B_{i}}}\ (mod\ p)$.

     * •

public key of $D_{i}$ is $(q_{i},e_{B_{i}},y_{B_{i}})$.

     * •

private key of $D_{i}$ is $(b_{i},d_{B_{i}},x_{B_{i}})$.

  3. 3.

System $B$, then, publishes $v\ =\ \displaystyle\sum_{i=1}^{m}q_{i}$.

  4. 4.

Note : Since, each member in system $B$ knows $\phi(n_{B})$ and $e_{B_{i}}\ \
\forall i$, they can compute $d_{B_{i}}$. Thus, $d_{B_{i}}$ is private for
members of system $A$ but not for members of system $B$. Similarly, $q_{i}$ is
public to system $B$ only.

Signature Algorithm

System $A$ generates a signature $(\sigma,r,s,t,\bar{u})$ for a message $M$ as
follows:

  1. 1.

Each $S_{i}$ chooses a random integer $k_{i}$ and keep it secret.

  2. 2.

Each $S_{i}$ generates $\sigma_{i}\ =\ e(H_{1}(M),a_{i}v)\in\ G_{\tau}$ ,
$r_{i}\ =\ g_{A}^{k_{i}}(y_{B_{1}}\ y_{B_{2}}\ .\ .\ .\ y_{B_{m}})^{-k_{i}}\ \
(mod\ p)$ , $s_{i}\ =\ g_{B}^{k_{i}}\ \ (mod\ p)$ and $w_{i}\ =\
g_{A}^{k_{i}}\ \ (mod\ p)$ and make it public to the system $A$.

  3. 3.

System computes :

     * •

$\sigma\ =\ \displaystyle\prod_{i=1}^{n}\sigma_{i}\ \in\ G_{\tau}$

     * •

$r\ =\ \displaystyle\prod_{i=1}^{n}r_{i}\ \ (mod\ p)$

     * •

$s\ =\ (\displaystyle\prod_{i=1}^{n}s_{i})^{r}\ \ (mod\ p)$

     * •

$w\ =\ (\displaystyle\prod_{i=1}^{n}w_{i})^{r}\ \ (mod\ p)$

     * •

$z\ =\ H_{2}(M,w)$

     * •

$t\ =\ z^{\displaystyle\prod_{i=1}^{m}e_{B_{i}}}\ \ (mod\ n_{B})$

  4. 4.

After computing $(\sigma,r,s,w,z,t)$, they are made public to all $S_{i}$ and
then each $S_{i}$ computes $v_{i}\ =\ zx_{A_{i}}\ +\ k_{i}r$ and make it
public to the system $A$.

  5. 5.

System computes

     * •

$\bar{v}\ =\ \displaystyle\sum_{i=1}^{n}v_{i}\ \ (mod\ n_{A})$

     * •

$\bar{u}\ =\ (\bar{v})^{\displaystyle\prod_{i=1}^{n}d_{A_{i}}}\ \ (mod\
n_{A})$

System $A$ sends the message $M$ and the signature $(\sigma,r,s,t,\bar{u})$ to
the system $B$ (and all the designated verifiers $D_{i}$).

Verification Algorithm

Upon receiving the message $M$ and the signature $(\sigma,r,s,t,\bar{u})$,
each designated verifier $D_{i}$ computes $\zeta_{i}\ =\ e(H_{1}(M),b_{i}u)\
\in\ G_{\tau}$ and $z_{i}\ =\ s^{x_{B_{i}}}\ (mod\ p)$ and make it public.
Then, each $D_{i}$ can separately or together verify and validate the
signature by checking the following equations:

  1. 1.

Computes $\zeta\ =\ \displaystyle\prod_{i=1}^{m}\zeta_{i}\ \in\ G_{\tau}$.

  2. 2.

Computes $a\ =\ (\bar{u})^{\displaystyle\prod_{i=1}^{n}e_{A_{i}}}\ \ (mod\
n_{A})$

  3. 3.

Computes $b\ =\ t^{\displaystyle\prod_{i=1}^{m}d_{B_{i}}}\ \ (mod\ n_{B})$

  4. 4.

Check $\sigma\ \equiv\ \zeta$ in $G_{\tau}$.

  5. 5.

Check $c\ =\ g_{A}^{a}\ (y_{A_{1}}y_{A_{2}}...y_{A_{n}})^{-b}\ \ (mod\ p)\ \
=\ \ r^{r}\displaystyle\prod_{i=1}^{m}z_{i}\ \ (mod\ p)$

  6. 6.

Lastly, signatures are accepted if $b\ =\ H_{2}(M,c)$ and $\sigma\ \equiv\
\zeta$ in $G_{\tau}$.

  7. 7.

If any of the condition from above conditions fail, verifier can deny to
accept the signature. In case of more than $2$ verifiers, if $50\%$ or more
verifiers deny the signature, system $B$ will return the signature to system
$A$.

##  4 Security Analysis

Now, we show the security properties for this scheme:

######  Theorem 4.1.

Our MSMV-SDVS scheme is correct if it runs smoothly.

###### Proof.

The signature verification procedure is correct since:

  1. 1.

$\sigma\ \ \equiv\ \displaystyle\prod_{i=1}^{n}\sigma_{i}\ \ \equiv\
\displaystyle\prod_{i=1}^{n}e(H_{1}(M),a_{i}v)\ \ \equiv\
e(H_{1}(M),\displaystyle\sum_{i=1}^{n}a_{i}v)\ \ \equiv\
e(H_{1}(M),\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}a_{i}b_{j}g)$

$\ \ \ \ \equiv\ e(H_{1}(M),\displaystyle\sum_{j=1}^{m}b_{j}u)\ \ \equiv\
\displaystyle\prod_{j=1}^{m}e(H_{1}(M),b_{j}u)\ \ \equiv\
\displaystyle\prod_{j=1}^{m}\zeta_{j}\ \equiv\ \zeta$ in $G_{\tau}$

  2. 2.

$a\ \ \equiv\ (\bar{u})^{\displaystyle\prod_{i=1}^{n}e_{A_{i}}}\ \ \equiv\
(\bar{v})^{(\displaystyle\prod_{i=1}^{n}d_{A_{i}})(\displaystyle\prod_{i=1}^{n}e_{A_{i}})}\
\ \equiv\ \bar{v}\ (mod\ n_{A})$

  3. 3.

$b\ \ \equiv\ t^{\displaystyle\prod_{i=1}^{m}d_{B_{i}}}\ \ \equiv\
z^{(\displaystyle\prod_{i=1}^{m}e_{B_{i}})(\displaystyle\prod_{i=1}^{m}d_{B_{i}})}\
\ \equiv\ z\ (mod\ n_{B})$

  4. 4.

${g_{A}}^{a}(y_{A_{1}}\ .\ .\ .\ y_{A_{n}})^{-b}\ \ \equiv\
{g_{A}}^{a}({g_{A}}^{x_{A_{1}}}\ .\ .\ .\ {g_{A}}^{x_{A_{n}}})^{-b}\ \ \equiv\
{g_{A}}^{\bar{v}}\ ({g_{A}}^{-b\displaystyle\sum_{i=1}^{n}x_{A_{i}}})\ \
\equiv\ {g_{A}}^{r\displaystyle\sum_{i=1}^{n}k_{i}}\ (mod\ p)$

  5. 5.

$r^{r}\displaystyle\prod_{i=1}^{m}z_{i}\ \ \equiv\ \
r^{r}\displaystyle\prod_{i=1}^{m}s^{x_{B_{i}}}\ \ \equiv\ \
(\displaystyle\prod_{j=1}^{n}r_{j})^{r}\
s^{\displaystyle\sum_{i=1}^{m}x_{B_{i}}}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \equiv\
({g_{A}}^{\displaystyle\sum_{j=1}^{n}k_{j}}(y_{B_{1}}\ .\ .\ .\
Y_{B_{m}})^{-\displaystyle\sum_{j=1}^{n}k_{j}})^{r}\
({g_{B}}^{r\displaystyle\sum_{j=1}^{n}k_{j}})^{\displaystyle\sum_{i=1}^{m}x_{B_{i}}}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \equiv\
{g_{A}}^{r\displaystyle\sum_{j=1}^{n}k_{j}}\ (mod\ p)$

∎

######  Theorem 4.2.

Our MSMV-SDVS scheme is strong designated verifier signature scheme.

###### Proof.

We have seen that the simulated signature produced by system $B$ (or
designated verifier $D$) is indistinguishable from the signature generated by
system $A$. Also, the probability that the simulated signature produced
randomly from the set of system $A$’s signature depends upon the randomness of
$k^{\prime}\ \in\ {\mathbb{Z}_{n_{B}}^{*}}$ and it is $1/{n_{B}}$. Thus the
two signatures have the same probability distribution, and hence the proposed
scheme is a designated verifier signature scheme.

Our scheme involves each designated verifier and their secret keys ($b_{i}$,
$x_{B_{i}}$) in the verification process. Moreover, the signature ($\sigma,\
r,\ s,\ t,\ \bar{u}$) produced by system $A$ is indistinguishable from the
signature ($\zeta,\ r^{\prime},\ s^{\prime},\ t^{\prime},\
\bar{u}^{{}^{\prime}}$) generated by system $B$. Thus, system $B$ can not
convince any third party whether a signature is created by signers or
verifiers. Thus, our scheme satisfies the strongness property.

∎

######  Theorem 4.3.

Our MSMV-SDVS scheme is unforgeable unless an adversary has access to the
secret keys of all signers and verifiers.

###### Proof.

Any adversary, who does not know the private key of all signers and designated
verifiers, can not forge the signature. It is computationally infeasible to
forge the signature in polynomial time.

Notation : $1\leq i\leq n$, $1\leq j\leq m$, where $n$ and $m$ are number of
signers and designated verifiers respectively.

  * •

If attacker knows all $p_{i}$ or $q_{j}$, it is infeasible to compute all
$a_{i}$ or $b_{j}$ in polynomial time.

  * •

If attacker knows all $a_{i}$ or $b_{j}$, signature $\sigma$ or $\zeta$ can be
created but to compute $r,s,t,\bar{u}$, he further require
$d_{A_{i}},x_{A_{i}},d_{B_{j}},x_{B_{j}}\ \ \ \forall i,j$

Since our scheme is based on bilinear pairing, factorization problem, and
discrete logarithm problem, it is computationally infeasible to compute
$\sigma,r,s,t,\bar{u}$ in polynomial time. ∎

######  Theorem 4.4.

Our MSMV-SDVS scheme is non-transferable, and protects the identity of the
actual signer.

###### Proof.

In this scheme, signature ($\zeta,\ r^{\prime},\ s^{\prime},\ t^{\prime},\
\bar{u}^{{}^{\prime}}$) produced by system B is indistinguishable from the
signature ($\sigma,\ r,\ s,\ t,\ \bar{u}$) generated by system A. Thus,
individually or collectively, Verifiers can not convince anyone that the
signer generated the signature, and any third party can not determine who
generated which signature. Thus our scheme is non-transferable and protects
the identity of the actual signer. ∎

##  5 Conclusion

This paper presents a multi-signer strong designated multi-verifier signature
scheme based on multiple cryptographic algorithms. Since all the signers
generate their signatures individually and make them public to the system to
generate a common signature, this scheme is non-interactive. Also, our scheme
requires the authorization of each participating signer, making it applicable
to various dimensions using blockchain technology. Our scheme satisfies
strongness, unforgeability, and non-transferability properties in the random
oracle model.

## References

  * [1] Ting-Yi Chang.  An id-based multi-signer universal designated multi-verifier signature scheme.  Information and Computation, 209(7):1007–1015, 2011.
  * [2] David Chaum and Hans Van Antwerpen.  Undeniable signatures.  In Conference on the Theory and Application of Cryptology, pages 212–216. Springer, 1989.
  * [3] Liao Da-jian and Tang Yuan-sheng.  Comment on lee et al.’s strong designated verifier signature scheme and its improvement.  In Advances in Technology and Management, pages 309–314. Springer, 2012.
  * [4] Lunzhi Deng, Jiwen Zeng, and Huawei Huang.  Id-based multi-signer universal designated multi-verifier signature based on discrete logarithm.  Chiang MAI J. Sci, 45(1):617–624, 2018.
  * [5] Whitfield Diffie and Martin Hellman.  New directions in cryptography.  IEEE transactions on Information Theory, 22(6):644–654, 1976.
  * [6] Taher ElGamal.  A public key cryptosystem and a signature scheme based on discrete logarithms.  IEEE transactions on information theory, 31(4):469–472, 1985.
  * [7] SK Hafizul Islam and GP Biswas.  Certificateless strong designated verifier multisignature scheme using bilinear pairings.  In Proceedings of the international conference on advances in computing, communications and informatics, pages 540–546, 2012.
  * [8] Markus Jakobsson, Kazue Sako, and Russell Impagliazzo.  Designated verifier proofs and their applications.  In International Conference on the Theory and Applications of Cryptographic Techniques, pages 143–154. Springer, 1996.
  * [9] Asif Uddin Khan and Bikram Kesari Ratha.  A secure strong designated verifier signature scheme.  Int. J. Netw. Secur., 19(4):599–604, 2017.
  * [10] Fabien Laguillaumie and Damien Vergnaud.  Multi-designated verifiers signatures.  In International Conference on Information and Communications Security, pages 495–507. Springer, 2004.
  * [11] Fabien Laguillaumie and Damien Vergnaud.  Multi-designated verifiers signatures: anonymity without encryption.  Information Processing Letters, 102(2-3):127–132, 2007.
  * [12] Ji-Seon Lee and Jik Hyun Chang.  Strong designated verifier signature scheme with message recovery.  In The 9th International Conference on Advanced Communication Technology, volume 1, pages 801–803. IEEE, 2007.
  * [13] Ji-Seon Lee and Jik Hyun Chang.  Comment on saeednia et al.’s strong designated verifier signature scheme.  Computer Standards & Interfaces, 31(1):258–260, 2009.
  * [14] Xiangxue Li and Kefei Chen.  Id-based multi-proxy signature, proxy multi-signature and multi-proxy multi-signature schemes from bilinear pairings.  Applied Mathematics and Computation, 169(1):437–450, 2005.
  * [15] Yang Ming and Yumin Wang.  Universal designated multi verifier signature scheme without random oracles.  Wuhan University Journal of Natural Sciences, 13(6):685–691, 2008\.
  * [16] Ronald L Rivest, Adi Shamir, and Leonard Adleman.  A method for obtaining digital signatures and public-key cryptosystems.  Communications of the ACM, 21(2):120–126, 1978.
  * [17] Shahrokh Saeednia, Steve Kremer, and Olivier Markowitch.  An efficient strong designated verifier signature scheme.  In International conference on information security and cryptology, pages 40–54. Springer, 2003.
  * [18] Pankaj Sarde and Amitabh Banerjee.  Strong designated verifier signature scheme based on discrete logarithm problem.  Journal of Discrete Mathematical Sciences and Cryptography, 18(6):877–885, 2015.
  * [19] N Shapuan and ES Ismail.  A new strong designated verifier signature scheme.  In AIP Conference Proceedings, volume 1940, page 020122. AIP Publishing LLC, 2018.
  * [20] Nadiah Shapuan and Eddie Shahril Ismail.  A strong designated verifier signature scheme with hybrid cryptographic hard problems.  Journal of Applied Security Research, pages 1–13, 2021.
  * [21] Shiang-Feng Tzeng, Cheng-Ying Yang, and Min-Shiang Hwang.  A nonrepudiable threshold multi-proxy multi-signature scheme with shared verification.  Future Generation Computer Systems, 20(5):887–893, 2004.
  * [22] Guilin Wang.  An attack on not-interactive designated verifier proofs for undeniable signatures.  IACR Cryptol. ePrint Arch., 2003:243, 2003.
  * [23] Bo Yang, Zibi Xiao, Yixian Yang, Zhengming Hu, and Xinxin Niu.  A strong multi-designated verifiers signature scheme.  Frontiers of Electrical and Electronic Engineering in China, 3(2):167–170, 2008.
  * [24] Yaling Zhang, Jing Zhang, and Yikun Zhang.  Multi-signers strong designated verifier signature scheme.  In 2008 Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pages 324–328. IEEE, 2008.


Estimating the Attack Ratio of Dengue Epidemics under Time-varying Force of
Infection using Aggregated Notification Data

Flavio Codeço Coelho1∗, Luiz Max de Carvalho2,

1 Escola de Matemática Aplicada , Fundação Getulio Vargas (FGV), Rio de
Janeiro – RJ, Brazil.
2 Programa de Computação Científica (PROCC), Fundação Oswaldo Cruz, Rio de
Janeiro – RJ, Brazil.
$\ast$ E-mail<EMAIL_ADDRESS>
## Abstract

Quantifying the attack ratio of disease is key to epidemiological inference
and Public Health planning. For multi-serotype pathogens, however, different
levels of serotype-specific immunity make it difficult to assess the
population at risk. In this paper we propose a Bayesian method for estimation
of the attack ratio of an epidemic and the initial fraction of susceptibles
using aggregated incidence data. We derive the probability distribution of the
effective reproductive number, $R_{t}\>$, and use MCMC to obtain posterior
distributions of the parameters of a single-strain SIR transmission model with
time-varying force of infection. Our method is showcased in a data set
consisting of 18 years of dengue incidence in the city of Rio de Janeiro,
Brazil. We demonstrate that it is possible to learn about the initial fraction
of susceptibles and the attack ratio even in the absence of serotype specific
data. On the other hand, the information provided by this approach is limited,
stressing the need for detailed serological surveys to characterise the
distribution of serotype-specific immunity in the population.

## Introduction

Dengue is an arthropod-borne febrile disease caused by a flavivirus with four
serotypes which causes an estimated $50$ million infections each year [1]. In
humans, immunity against a particular serotype is considered permanent after
the exposure and cross immunity to there serotypes is considered short lived
[2]. As a consequence, the proportions of viral serotypes co-circulating at
any point in time are strongly dependent on previous incidence patterns of the
disease, which determine the number of individuals susceptible to each
serotype at any point in time.

Dengue transmission is also modulated by environmental conditions, among
which, temperature, due to its effects on the vector reproduction, stands out
as a strong predictor of incidence [3, 4]. In places with sufficient seasonal
temperature variation, dengue is predominantly a summer disease. So it is fair
to say that these environmental fluctuations play a key role in determining
beginning and end of epidemic periods. This climatic influence is exerted
mainly through its effects on the force of infection, which cannot be taken as
constant [5] but rather as a seasonal (oscillating) function of time. The long
term dynamics of dengue is also modulated by the alternation of virus types in
circulation. Demographics also plays a role in replenishing the population of
susceptibles.

The attack ratio (AR) of a disease is a measure of morbidity defined as the
number of new cases divided by the population at risk. For dengue epidemics,
it can be difficult to calculate the AR due to the lack of knowledge of the
population at risk. The population at risk in this case is the number of
susceptibles to the circulating virus type(s) before a given epidemic. Thus,
in order to calculate the attack ratio, we need to determine the number of
susceptibles to the circulating virus types right before the epidemic, which
is virtually impossible without regular virological surveys.

The attack ratio is also influenced by the reproductive number of the disease
[6, 7], which is closely associated with the force of infection. Thus the
incorporation of the effective reproduction number, $R_{t}\>$, as a function
of time, is crucial to an accurate estimation of the AR of seasonal diseases
like dengue and Influenza.

Other methods for estimating the number of susceptibles while accommodating
time-varying force of infection have been proposed before, for measles [8, 9],
a disease that shows remarkable seasonality. These methods try to reconstruct
the entire series of infectious and susceptibles from case data using
deterministic models and generally work well for measles because there is a
one-to-one relationship between exposure and immunity, since measles is caused
by a single-strain pathogen. Recently, methods in the same fashion were
developed for dengue when serotype-specific data is available [10]. When such
data is not available, the series of susceptibles to all possible serotypes,
cannot be reconstructed based solely on a deterministic transmission model,
since the arrival/re-emergence of new serotypes, an intrinsically stochastic
events, can drastically change the pool of susceptibles, throwing off any
sequential estimation based on the incidence dynamics.

In this paper, we propose a new approach to estimate the number (fraction) of
susceptibles using a simplified model of dengue transmission based on a
single-strain Susceptible-Infectious-Removed (SIR) model with time-varying
infection rate. In order to bypass the limitations of not knowing the
serotype-specific seroprevalence and the exact behaviour of the force of
infection through time, we propose to inform the time-varying transmissibility
using the $R_{t}\>$series derived from the notification data [11]. We extend a
Bayesian framework previously used to estimate the number of susceptibles in
Influenza epidemics in Europe [12] to include time-varying force of infection
and derive a probability distribution for $R_{t}\>$to accommodate uncertainty
in the estimates. Then, from the incidence series and the population at risk,
we calculate the attack ratio for each epidemic. We apply our method to
estimate $S_{0}$ before every major dengue epidemic in the city of Rio de
Janeiro, Brazil in the last 18 years.

## Methods

In this section we will start by describing the data and then the method used
to estimate the effective reproductive number, $R_{t}$, from the data and
obtain its posterior distribution. We then proceed to describe the
Susceptible-Infectious-Recovered (SIR) model used to represent the aggregated
disease incidence and how $R_{t}$ can be integrated into the model to allow
for time varying force of infection. Next, an approach to approximate the
posterior distributions of the numbers of susceptible to the main circulating
dengue viruses for each epidemic is detailed. Finally, we discuss how to
estimate the attack ratio of each epidemic using the estimated susceptible
fraction and the observed incidence.

### Data

The data used in this paper consists of time series of weekly notified cases
of dengue for the city of Rio de Janeiro from 1996 to 2014. The cases are
notified based only on clinical criteria. Laboratory confirmation and serotype
information are available only for a very small sample and only on recent
years (2010-2013). For the parameter estimation procedures incidence was
normalized by dividing the number of cases reported by the total city
population at each year as given by the census (Census Bureau, Brazilian
Institute of Geography and Statistics, http://www.ibge.gov.br/english/).

### Estimating the effective reproductive number ($R_{t}$)

In monitoring of infectious diseases, it is important to assess whether the
incidence of a particular disease is increasing significantly, in order to
decide to take preventive measures. The effective reproductive number at time
$t$, $R_{t}\>$, can be understood as a real-time estimate of the basic
reproductive number ($R_{0}$) and is defined as the average number of
secondary cases per primary case at time $t$.

Let $Y_{t}$ be the number of reported disease cases for a particular time
$t\in(0,T)$. Nishiura el al. (2010) [11] extend the theory developed by
Stallybrass et al. (1931) [13] and propose to estimate $R_{t}\>$as

$R_{t}=\left(\frac{Y_{t+1}}{Y_{t}}\right)^{1/n}$ (1)

where $n$ is taken to be the ratio between the length of reporting interval
and the mean generation time of the disease. Here we are interested in the
simpler case $n=1$. If $R_{t}\>$is to be used as a decision tool, however, one
needs to be able to quantify the uncertainty about estimate in equation 1.
Here we detail how to obtain credibility intervals for $R_{t}\>$under the
assumption that the counts $Y_{t}$ are Poisson distributed for all $t$.

We explore the approach of Ederer and Mantel [14], whose objective is to
obtain confidence intervals for the ratio of two Poisson counts. Let
$Y_{t}\sim Poisson(\lambda_{t})$ and $Y_{t+1}\sim Poisson(\lambda_{t+1})$ and
define $S=Y_{t}+Y_{t+1}$. The authors note that by conditioning on the sum $S$

$\displaystyle Y_{t+1}|S$ $\displaystyle\sim Binomial(S,\theta_{t})$ (2)
$\displaystyle\theta_{t}$
$\displaystyle=\frac{\lambda_{t+1}}{\lambda_{t}+\lambda_{t+1}}$ (3)

Let $c_{\alpha}(\theta_{t})=\\{\theta_{t}^{(L)},\theta_{t}^{(U)}\\}$ be such
that $Pr(\theta_{t}^{(L)}<\theta_{t}<\theta_{t}^{(U)})=\alpha$. Analogously,
define $c_{\alpha}(R_{t})=\\{R_{t}^{(L)},R_{t}^{(U)}\\}$ such that
$Pr(R_{t}^{(L)}<R_{t}<R_{t}^{(U)})=\alpha$. Ederer and Mantel (1974) [14] show
that one can construct a $100\alpha\%$ confidence interval for $R_{t}\>$by
noting that

$R_{t}^{(L)}=\frac{\theta_{t}^{(L)}}{(1-\theta_{t}^{(L)})}\quad\text{and}\quad
R_{t}^{(U)}=\frac{\theta_{t}^{(U)}}{(1-\theta_{t}^{(U)})}\\\ $ (4)

Because the transform from $\theta$ to $R_{t}\>$is monotonically increasing,
the result holds for confidence and credibility intervals alike.

Many authors have chosen to quantify the uncertainty about $\theta$ following
orthodox approaches (see for example [15] and [16]) mainly for simplicity. We
choose instead to take a Bayesian approach and use the $100\alpha\%$ posterior
credibility interval for $\theta_{t}$ as $c_{\alpha}(\theta_{t})$. If we
choose the conjugate beta prior with parameters $a_{0}$ and $b_{0}$ for the
binomial likelihood in (2), the posterior distribution for $\theta_{t}$ is

$p(\theta_{t}|Y_{t+1},S)\sim Beta(Y_{t+1}+a_{0},Y_{t}+b_{0})$ (5)

Combining equations (4) and (5) tells us that the induced posterior
distribution of $R_{t}$ is a beta prime (or inverted beta) with parameters
$a_{1}=Y_{t+1}+a_{0}$ and $b_{1}=Y_{t}+b_{0}$ [17]. The density of the induced
distribution is then

$f_{P}(R_{t}|a_{1},b_{1})=\frac{\Gamma(a_{1}+b_{1})}{\Gamma(a_{1})\Gamma(b_{1})}R_{t}^{a_{1}-1}(1+R_{t})^{-(a_{1}+b_{1})}$
(6)

Thus, the expectation of $R_{t}\>$is $a_{1}/(b_{1}-1)$ and its variance is
$a_{1}(a_{1}+b_{1}-1)/\left((b_{1}-2)(b_{1}-1)^{2}\right)$. Note that this
result holds only for $n=1$. Sampling from the posterior in (6) can be made
straightforward by first sampling from (5) and then applying the transform in
(4). Also, one can choose $a_{0}$ and $b_{0}$ so as to elicit meaningful prior
distributions for $R_{t}$. We show how to elicit the prior for $R_{t}$ from
specified prior mean and variance or coefficient of variation in the Appendix.

Also, since $R_{t}>1$ indicates sustained transmission, one may be interested
in computing the probability of this event. This can be easily achieved by
integrating (6) over the appropriate interval. By noting that

$\displaystyle Pr(R_{t}>1)$ $\displaystyle=1-\int_{0}^{1}f_{P}(r)dr$ (7)
$\displaystyle=1-Pr(\theta_{t}<\frac{1}{2})$ (8)

one can compute the desired probability while avoiding dealing with the
density in (6) directly.

### Mathematical modelling

A Susceptible-Infectious-Removed (SIR) model is proposed to model dengue
dynamics. In the traditional formulation of the model, transmission is
governed by a constant transmission rate $\beta$ and recovery happens at a
rate $\tau$.

For our analysis we chose to let the force of infection vary with time, just
as it does in the actual epidemics, as seen in the data. So as the epidemic
progresses, the effective transmission rate changes and is given by

$\beta(t)=\frac{R_{t}\cdot\tau}{S_{0}}$ (9)

where $R_{t}$ is the effective reproductive number, estimated as in 1. The
complete model with the time-varying force of infection is given by the system
of ordinary differential equations:

$\displaystyle\frac{dS}{dt}$ $\displaystyle=-\beta(t)SI$ (10)
$\displaystyle\frac{dI}{dt}$ $\displaystyle=\beta(t)SI-\tau I$
$\displaystyle\frac{dR}{dt}$ $\displaystyle=\tau I$

where $S+I+R=1\>\forall\>t$. Of course, this is a rather simplified model, in
which, for instance, the vector is omitted. The rationale for this
simplification is based on the ability of the empirically derived $R_{t}$ to
incorporate the effects of the fluctuating vector populations. Also, although
there are multiple circulating serotypes, our approach can not discriminate
between them due to the lack of serotype-specific data. Nevertheless, this
modelling strategy can still provide some insight into the disease dynamics
and allows us to estimate the initial fraction of susceptibles $S_{0}$, a key
epidemiological parameter.

### Bayesian parameter estimation

We take a Bayesian approach to the estimation of $S_{0}$. First the incidence
time series was divided into $J=13$ epidemic windows that corresponded to
significant raises in incidence and normalized to lie on the $[0,1]$ interval.
For a given interval $j=\\{t_{j}^{\text{start}},t_{j}^{\text{end}}\\}$ we
observe an incidence time series $\mathbf{Y_{j}}$. We are thus interested in
the posterior distribution

$p(S_{0j}|\mathbf{Y_{j}})\propto
l(\mathbf{Y_{j}}|S_{0j},R_{t},m,\tau)\pi(S_{0j})$ (11)

The likelihood $l(\mathbf{Y_{j}}|\cdot)$ is assumed to be a Normal
distribution with fixed variance $\sigma^{2}$. In this estimation procedure we
kept $R_{t}$ fixed at fixed at the posterior mean obtained as described above
and fixed $\tau=1/7\>\text{days}^{-1}$. To complete the inference, we need to
specify prior distributions for the parameters of interest. We place a flat
$\text{Beta}(1,1)$ prior on $S_{0j}\>\forall j$

To approximate the posterior in (11) we use Markov chain Monte Carlo
techniques implemented in the Bayesian inference with Python (BIP) [12]
available at http://code.google.com/p/bayesian-inference/. BIP uses a
Differential Evolution Adaptive Metropolis (DREAM) [18] scheme that
efficiently samples from high-dimensional joint distributions using multiple
adaptive chains running in parallel with delayed rejection. Also, as the
numerical integration routine implemented within BIP needs $\beta(t)$ to be
available at arbitrary values of $t$, i.e., as continuous function of time
because of the variable step size, we used linear interpolation to obtain
values of $R_{t}$ for any time point. In this study we used one chain per
parameter, i.e, 3 chains for each run. The chains were run until $5000$
samples were obtained after discarding $500$ burn-in samples. Convergence of
the parallel chains was verified at every 100 iterations by the calculation of
the Gelman-Rubin’s R (potential scale reduction factor), which approaches $1$
at convergence [19].

### Calculating the attack ratio

The attack ratio of an epidemic is defined by the number of infections divided
by the size of the population at risk.

$A=\frac{\text{\\# cases}}{\text{Population at risk}}$ (12)

Based on what has been discussed so far, we can rewrite (12) for each epidemic
$j$ as

$A_{j}=\frac{\sum Y_{j}}{S_{0j}}$ (13)

where $S_{0j}$ is the number of susceptibles before each epidemic $j$, which
we estimated before.

Python and R code to perform all the analyses described above is publicly
available at https://github.com/fccoelho/paperLM1.

## Results and Discussion

In this paper we propose a method to bypass the lack of serotype-specific case
data by informing the time-varying force of infection with the instantaneous
reproductive number, $R_{t}\>$which we calculate from aggregated data. The
main contribution of this paper can be summarized in the following items: (i)
we show a method to quantify uncertainty about $R_{t}\>$that is readily
applicable to other diseases and; (ii) we propose to use $R_{t}\>$to inform a
dynamic epidemic model with time-varying force of infection in order to gain
insight into the attack ratio of each epidemic; (iii) We propose an estimation
procedure for circulating serotype’s $S_{0}$ from aggregate case data, which
is robust to epidemic sizes; We estimate the AR for 18 years of Dengue
epidemics.

Figure 1 shows the $R_{t}$ series, according to (1) [11] along with the
confidence bands derived in this paper. It can be seen that the inter-epidemic
periods are characterized by $R_{t}$ being indistinguishable from 1. Due to
the intrinsic variability of the $R_{t}\>$series, the examination of its
credible intervals is essential to identify periods of sustained transmission.
The wider intervals between epidemics are due to the scarcity of cases during
these periods. The method to quantify uncertainty proposed here provides more
conservative credibility intervals, and therefore offers protection against
false alarms.

Figure 1: Estimated time-series for $R_{t}$, along with 95% credible
intervals. Top panel show reported cases from which $R_{t}$ is estimated. As
expected, uncertainty about $R_{t}\>$is greater when the case counts are low,
for instance in the period $2003$–$2006$, which represented a big hiatus
between major epidemics. The intrinsic variability of $R_{t}\>$can be used to
inform the time-varying force of infection, since it reflects variation in the
vector population and other environmental factors such as temperature and
seasonal variation.

A key epidemiological quantity is the attack ratio (AR) of an epidemic, a
measure of morbidity and speed of spread which can be used to predict epidemic
size and help efficient Public Health planning. The AR depends fundamentally
on the population at risk, which in the case of dengue is every naive (to a
particular serotype) individual in the population. Estimating the initial
susceptible fraction $S_{0}$ for each epidemic is thus central to the
estimation of the AR. Methods for estimating the number of susceptibles have
been proposed before, for other diseases [8, 9]. These methods try to
reconstruct the entire series of infectious and susceptibles for measles
outbreaks from case data. In the case of dengue, the full (multi-year/multi-
epidemic) series of susceptibles to all possible serotypes, cannot be
reconstructed based solely on a deterministic transmission model, since the
arrival/re-emergence of new serotypes (which are a stochastic events) can
change drastically the pool of susceptibles throwing off any sequential
estimation based on the incidence dynamics.

Since there is very limited information regarding the actual proportions of
each virus in circulation and most information available is about the
predominant serotypes for some epidemics in the period of study only [20], we
propose the use of a simplified a single strain model. The main argument we
put forward is that by conditioning on the $R_{t}\>$series, we implicitly take
into account the variability introduced by the co-circulation of multiple
serotypes and heterogeneous levels of immunity in the general population. We
sought to deal with all important sources of uncertainty impinging on the
estimation of the AR of a dengue epidemic, but not all could be satisfactorily
addressed in this analysis. For instance, in any given epidemic there is a
large number of mild and asymptomatic cases, which nevertheless acquire
immunity. It is estimated that for every case reported, up to 10-20 are not
seen by health authorities [21]. Another source of uncertainty is under-
reporting of diagnosed cases, which is a serious issue in the health care
systems of many developing countries such as Brazil. Duarte and França (2006)
[22], estimated the sensitivity of Dengue reporting for hospitalized patients
in Belo-Horizonte, Brazil to be of 63%, meaning that approximately 37% of the
suspected Dengue cases go unreported. Lastly, demography and migrations affect
the number of susceptible in ways which are not easy to fully determine.

Figure 3, shows the model from (10) fitted to the data. Despite its
limitations, our simplified model fits the data well. In it we can see that
the susceptibles series in each epidemic starts at the estimated level of
$S_{0}$. The proportion of susceptibles may seem low, but we must remember
that these estimates are being affected by an unknown under-reporting factor,
which experts suggest is somewhere between 5 and 10, i.e. for every case
observed there are 5 or 10 unobserved. Since this under-reporting affects both
the numerator and denominator of (13), its effects should cancel out, giving
us an unbiased attack ratio estimate. One other possible source of bias which
would lead to the underestimation of $S_{0}$ could come from a significant
part of the population not being exposed to the disease. However, as we can
see in Figure 2, despite the differences in intensity (incidence), the entire
city seems to be at risk, with no particularly “protected” areas, at least in
the last four epidemics.

(a) 2010

(b) 2011

(c) 2012

(d) 2013

Figure 2: Maps showing the incidence of dengue in the city of Rio de Janeiro
from 2010 to 2013. Circles indicate individual notified cases. A heatmap is
overlayed on the maps showing absolute density of cases. It can be seen that
several areas of the city were affected and no region seems to be free of
transmission risk. This suggests that although transmission risk varies
spatially, there is significant exposure over the entire city.

Table 1 contains the attack ratios and medians of the $S_{0}$ estimated for
each epidemic/outbreak. It is interesting to notice that the larger epidemics,
in terms of peak size are not the one with the greater attack ratios. This
stresses the importance of knowing the immunological structure of the
population. Knowing the $S_{0}$ for the circulating viruses we can order to
more accurately assess the potential impact of a coming epidemic, since
particularly virulent types, can be rendered less of a threat by a low
$S_{0}$.

We hope that the results presented in paper will motivate public health
authorities to invest in annual serological surveys, to determine the
susceptibility profile to each dengue virus as well as to estimate the under-
reporting factor of the notification system.

Figure 3:  Susceptibles and Infectious posterior curves. The curves were estimated only for the periods where $R_{t}>1$. The susceptible curves in the top panel reflect the prevalence of fraction of susceptibles to circulating strain(s) for each epidemic/outbreak. In the lower panel, we see the posterior distribution of infectious curves, represented by its median and 95% credible interval. Credible intervals are very narrow, and can be hard to distinguish from the median line. Dots show the observed cases, scaled as fractions of the entire population.  Table 1:  Median attack ratio and 95% credibility intervals calculated according to (13). Values are presented as percentage of total population. †: Year corresponds to the start of the epidemic, however the peak of cases may occur in the following year. ‡: Susceptible fraction. These results show considerable variation in AR between epidemics, consistent with the accquiring and loss of serotype-specific immunity. Year† | median Attack Ratio | $S_{0}^{\ddagger}$
---|---|---
1996 | 0.39 (0.17-0.54) | 0.00171(0.0012-0.0038)
1997 | 0.87 (0.74-0.87) | 0.00273(0.0027-0.0032)
1998 | 0.5 (0.49-0.5) | 0.00142(0.0014-0.0014)
1999 | 0.11 (0.037-0.2) | 0.00345(0.0018-0.01)
2000 | 0.25 (0.24-0.27) | 0.0155(0.015-0.016)
2001 | 0.48 (0.47-0.49) | 0.0495(0.048-0.051)
2005 | 0.15 (0.1-0.21) | 0.0147(0.01-0.021)
2006 | 0.11 (0.08-0.14) | 0.0281(0.022-0.037)
2007 | 0.15 (0.15-0.15) | 0.135(0.13-0.14)
2008 | 0.14 (0.031-0.31) | 0.00672(0.003-0.024)
2010 | 0.18 (0.17-0.19) | 0.0454(0.043-0.048)
2011 | 0.086 (0.082-0.094) | 0.215(0.2-0.23)
2012 | 0.14 (0.13-0.15) | 0.0621(0.058-0.068)

## Acknowledgements

LMC is grateful to Dr. Leonardo Bastos for useful discussions on the posterior
inference for $R_{t}\>$. The authors are also grateful to Claudia T. Codeço
for helpful discussions about the manuscript.

## References

  * 1. Guzman MG, Halstead SB, Artsob H, Buchy P, Farrar J, et al. (2010) Dengue: a continuing global threat.  Nat Rev Microbiol 8: 7–16.
  * 2. Halstead SB (2007) Dengue.  The Lancet 370: 1644–1652.
  * 3. Honório NA, Codeço CT, Alves FC, Magalhães M, Lourenço-De-Oliveira R (2009) Temporal distribution of aedes aegypti in different districts of rio de janeiro, brazil, measured by two types of traps.  Journal of Medical Entomology 46: 1001–1014.
  * 4. Wu PC, Lay JG, Guo HR, Lin CY, Lung SC, et al. (2009) Higher temperature and urbanization affect the spatial patterns of dengue fever transmission in subtropical taiwan.  Science of The Total Environment 407: 2224–2233.
  * 5. Reiner RC, Stoddard ST, Forshey BM, King AA, Ellis AM, et al. (2014) Time-varying, serotype-specific force of infection of dengue virus.  Proceedings of the National Academy of Sciences of the United States of America 111: E2694–E2702.
  * 6. Bacaër N, Gomes MGM (2009) On the final size of epidemics with seasonality.  Bulletin of Mathematical Biology 71: 1954–1966.
  * 7. Katriel G, Stone L (2012) Attack rates of seasonal epidemics.  Mathematical Biosciences 235: 56–65.
  * 8. Bjørnstad O, Finkenstädt B, Grenfell B (2002) Dynamics of measles epidemics: Estimating scaling of transmission rates using a time series SIR model.  Ecological Monographs 72: 169–184.
  * 9. Wallinga J, Teunis P, Kretzschmar M (2003) Reconstruction of measles dynamics in a vaccinated population.  Vaccine 21: 2643–2650.
  * 10. Reiner RC, Stoddard ST, Forshey BM, King AA, Ellis AM, et al. (2014) Time-varying, serotype-specific force of infection of dengue virus.  Proc Natl Acad Sci USA 111: E2694–2702.
  * 11. Nishiura H, Chowell G, Heesterbeek H, Wallinga J (2010) The ideal reporting interval for an epidemic to objectively interpret the epidemiological time course.  J R Soc Interface 7: 297–307.
  * 12. Coelho FC, Codeço CT, Gomes MG (2011) A Bayesian framework for parameter estimation in dynamical models.  PLoS ONE 6: e19616.
  * 13. Stallybrass CO, et al. (1931) The principles of epidemiology and the process of infection.  The Principles of Epidemiology and the Process of Infection .
  * 14. Ederer F, Mantel N (1974) Confidence limits on the ratio of two poisson variables.  American Journal of Epidemiology 100: 165–167.
  * 15. Wilson EB (1927) Probable inference, the law of succession, and statistical inference.  Journal of the American Statistical Association 22: 209–212.
  * 16. Clopper C, Pearson ES (1934) The use of confidence or fiducial limits illustrated in the case of the binomial.  Biometrika : 404–413.
  * 17. Dubey SD (1970) Compound gamma, beta and f distributions.  Metrika 16: 27–31.
  * 18. Vrugt JA, ter Braak CJF, Diks CGH, Higdon D, Robinson B, et al. (2008) Accelerating markov chain monte carlo simulation by differential evolution with self-adaptive randomized subspace sampling.  Technical report, Citeseer.
  * 19. Brooks SP, Gelman A (1998) General methods for monitoring convergence of iterative simulations.  Journal of computational and graphical statistics 7: 434–455.
  * 20. Macedo GA, de Araújo JMGa, Schatzmayr HG, Costa FAC, de Filippis AMB, et al. (2013) Virological surveillance for early warning of dengue epidemics in the state of rio de janeiro, brazil.  Transactions of the Royal Society of Tropical Medicine and Hygiene 107: 141–146.
  * 21. Luz PM, Grinsztejn B, Galvani AP (2009) Disability adjusted life years lost to dengue in brazil.  Tropical Medicine & International Health 14: 237–246.
  * 22. Duarte HHP, França EB (2006) Data quality of dengue epidemiological surveillance in belo horizonte, southeastern brazil.  Revista de Saúde Pública 40: 134–142.

## Appendix

### A remark on prior distributions and tail behaviour of the distribution of
$R_{t}$

There are a number of approaches to deriving the distribution of $R_{t}\>$.
Alternatively to the approach described in the main text [14], one could use
the conditional distribution of $R_{t}\>$on $Y_{t+1}$ and $Y_{t}$ as defined
in equation A7 of Nishiura et al. [11]:

$f_{R}(R_{t})=(Y_{t}R_{t})^{Y_{t+1}}e^{-Y_{t}R_{t}}$ (14)

Noticing the kernel of (14) is that of a gamma distribution with
$a_{2}=Y_{t+1}+1$ and $b_{2}=Y_{t}$, we obtain a proper density from which to
construct $c_{\alpha}(R_{t})$, simply by computing the appropriate quantiles
of said distribution. This density is

$f_{N}(R_{t}|a_{2},b_{2})=\frac{b_{2}^{a_{2}}}{\Gamma(a_{2})}R_{t}^{a_{2}-1}e^{-b_{2}R_{t}}$
(15)

In order to decide which approach to take, it may be of use analysing the tail
behaviour of the derived distributions for $R_{t}\>$. Consider the case of
using a flat $Uniform(0,1)$ prior for $\theta_{t}$. With $a_{0}=b_{0}=1$,
$a_{1}=a_{2}$ and $b_{1}=b_{2}+1$. The beta prime (inverse beta distribution)
will have heavier tails compared to the conditional distribution proposed by
[11], thus providing more conservative confidence/credibility intervals. To
see that one needs simply take the ratio of the Beta prime and Gamma
(unnormalized) densities and evaluate the limit as $R_{t}$ goes to infinity:

$\lim_{R_{t}\to\infty}\frac{f_{P}(R_{t}|a_{1},b_{1})}{f_{N}(R_{t}|a_{2},b_{2})}=\lim_{R_{t}\to\infty}\frac{e^{Y_{t}R_{t}}}{(1+R_{t})^{Y_{t}+Y_{t+1}+2}}=\infty$
(16)

Finally, note that we deliberately construct $c_{\alpha}(R_{t})$ as a equal-
tailed $100\alpha\%$ credible set, rather than a less conservative highest
posterior density (HPD) interval.

As a side note, the Bayesian approach presented in this paper will give
similar results to orthodox confidence intervals [15] and [16] for $Y_{t+1}$
and $Y_{t}>>1$. Under the flat uniform prior for $\theta_{t}$, the Bayesian
posterior credibility interval is nearly indistinguishable from the confidence
interval proposed by Clopper & Pearson (1931) [16] for $Y_{t+1},Y_{t}>20$.
Note also that the uniform prior ($Beta(1,1)$) for $\theta_{t}$ constitutes a
poor prior choice mainly because the induced distribution for $R_{t}\>$is only
well-defined for $b_{0}>2$.

An advantage of the Bayesian approach is that one can devise prior
distributions for $\theta_{t}$ taking advantage of the intuitive
parametrization and flexibility of the beta family of distributions. Prior
elicitation can also be done for $R_{t}\>$and the hyper-parameters directly
plugged into the prior for $\theta_{t}$. One can, for example, choose prior
mean and variance for $R_{t}\>$and find $a_{0}$ and $b_{0}$ that satisfy those
conditions. Let $m_{0}$ and $v_{0}$ be the prior expectation and variance for
$R_{t}$. After some tedious algebra one finds

$\displaystyle a_{0}$
$\displaystyle=\frac{m_{0}v_{0}+m_{0}^{3}+m_{0}^{2}}{v_{0}}$ (17)
$\displaystyle b_{0}$ $\displaystyle=\frac{2v_{0}+m_{0}^{2}+m_{0}}{v_{0}}$
(18)

If one wants only to specify $m_{0}$ and the coefficient of variation
$c=\sqrt{v_{0}}/m_{0}$ for $R_{t}$ a priori, some less boring algebra gives:

$\displaystyle a_{0}$
$\displaystyle=\frac{m_{0}^{3}c^{2}+m_{0}^{3}+m_{0}^{2}}{m_{0}^{2}c^{2}}$ (19)
$\displaystyle b_{0}$
$\displaystyle=\frac{2m_{0}^{2}c^{2}+m^{2}+m}{m_{0}^{2}c^{2}}$ (20)

This approach thus makes it possible to incorporate epidemiological knowledge
about disease Biology (e.g. the magnitude of $R_{0}$) into the computation of
$R_{t}\>$. This may prove particularly important when disease counts are low
and/or close to the detection threshold. We provide an R script to perform the
above elicitation at
https://github.com/fccoelho/paperLM1/blob/master/R/elicit_Rt_prior.R.