Related Work

Our method is basically by employing signature-chaining and using a signature with message recovery as the primitive. Concretely, our contributions are:

1. We define a signature scheme for a sequence of digital document by including more features to the standard signature, so that it can be used to generate the signature sequentially and also verifying the order of the members in the sequence.

2. We propose a variant of the signature with message recovery originally pro-posed by Bellare et al.

3. We propose a signature scheme for the sequence of digital documents using a signature with message recovery as the primitive.

4. We propose the security model of the scheme in the form of Extended Ex-istential Unforgeability under Chosen Message Attack (EEUF-CMA) and Order Unforgeability Under Chosen Message Attack (OUF-CMA).

5. We prove the security of the scheme in the random oracle model.

sequence. The signature produced in the second method can be used to prove the order of the sequence. However, it has a major disadvantage: each time we include a new member, the signer should recreate the new signature which is not efficient in term of computation and not applicable if the previous documents are inacessible.

Another strategy to sign the sequence of the documents with a plain signature is by including a counter or timestamp in the signature [119]. Let Sign be a standard signature, andc_i be a trusted counter or timestamp, the signature onm_i is σ_i ←Sign(m_ikc_i). However, as described in Section 5.1.3, this method requires the existence of the trusted counter or timestamp server.

5.2.2 Signature Chain

The other possible methods to sign the sequence of the digital documents are by using the signature-chaining method. The signature chain ensures integrity of a sequence of document by storing the signature of previous document in the next document. The basic form of the signature chain is: letSign be a standard signa-ture, then the signature chain for a sequence of messages M ={m1, m2, . . . , mn} is a set of the signature σ ={σ₁, σ₂, . . . , σ_n} where σ_i =Sign(m_ikσi−1).

The signature chain can be used to verify authenticity and the order of the docu-ments in the sequence, however it has a main disadvantage where we need to keep the full signature for each document and to verify the order the documents, in the worst case, we need to have access to all members of the documents. The signature chain is an extension of the hash chain proposed in [105]. Recently, the signature chain is famous in the form of block-chain that is used to record transactions of a digital money (i.e., bitcoin) [65].

5.2.3 Signature Aggregate

Signature aggregate technique is used to combine many signature into one fix signature. Some aggregate signature schemes have a restriction about the messages where the signed messages should be distinct, the other schemes have a restriction about the signer where the same signer cannot signed the messages more than one

times [120]. In our scheme, we are focusing on the method to sign a sequence of distinct messages by a specific signer.

The RSA signatures produced by a party can be aggregated/condensed into a succinct signature by simply computing the product of each individual signature.

Bellare et al. use the aggregation method for fast verification of batch RSA. For the signatures σ₁, σ₂, ...σ_t [95, 121], we compute the aggregate as follows:

σ =

t

Y

i=1

σ_i mod n

where σ_i ≡h^d_i mod N and h_i =H(m_i).

The short signature proposed in [93] can be easily aggregated by computing the product of the each signature [96] (exactly the same method as batch RSA). For the input n signatures σ₁, σ₂, ..., σ_n, compute the aggregate:

σ =

n

Y

i=1

σ_i ∈G₁

To verify the n messages m₁, m₂, ..., m_n, for a public keyg^x₂ check whether

e(σ, g₂) =

n

Y

i=1

e(H(m_i), g₂^x)

We need to assume the existence of the bilinear maps e:G₁×G₂ →G_T where for allu∈G₁, v ∈G₂ and a, b∈Zp and e(u^a, v^b) =e(u, v)^ab.

There are some significant research on the techniques to aggregate the signature with some more specific properties. The first property is the possibility to check the order of aggregating each signature as have been proposed in the form of se-quential aggregate signature schemes [122–131]. Another interesting property is the history-free characteristics of the sequential aggregate signature, where ag-gregation algorithm does not need to have access all previous signed messages [132, 133]. However, during the verification, we still need to have access to all of the signed messages.

Recently, Gentry et al [134] classified three main methods for the sequential ag-gregate signature (SAS) schemes. These methods are (1) LMRS (the methods

proposed in [122]), (2) Neven (proposed in [127]), and (3) BGR (proposed by Brogle et al. [128]). They also proposed a unified framework for the sequential aggregate signature scheme by using two functions (an ideal cipher π and claw-free trapdoor permutation F), where the first function π is first called by taking inputs the previous signature (the aggregate so-far – σi−1) and also the concate-nation of the outputs of permutation used to sign each previous message with all of the previous messages. The second step takes the outputs of the first function π and uses an inverse of the permutation generated byF. They also proposed the randomized and the history-free variants of their scheme.

Hohenberger et al. discussed a synchronized aggregate signature where each party is provided with a message and a time period t. The party can only sign at most once for each t [135]. The uses the RSA function as the primitive with the RSA modulusN =p·qand using a keyed hashHK to map the time periodt∈[1..T] to a specific value e_t and computes E =QT

j=1e_j mod φ(N). Their scheme exploits the characteristics of the multiplication of signed messages using the RSA with the same modulus.

The sequential aggregate signature, similar to the signature chain, can prove the authenticity and the order of the sequence and we only need to store one aggregate signature for all members. The main advantage is we can compress many signature into practically one signature. However, the disadvantage is, normally during the verification we need to have access to all of the documents in the sequence.

5.2.4 Signature with Message-Recovery

Signature with message-recovery is a signature scheme that can recover the original or a part of the signed message. The plain RSA without hash is an example of the message-recovery signature, however, the plain RSA is not resistant to EUF-CMA attacks. Bellare proposed the message recovery variant of the RSA-PSS [89]. The other proposed signatures with message recovery (for discrete log-based digital signature) can be found in the work of Nyberg et al. [136–138], and also the work of Miyaji [139], and Abe et al. [140].