# Strong Designated Verifier Signature Schemes with Undeniable Property and Their Applications

Authors: Xiaoming Hu; Wenan Tan; Huajie Xu; Jian Wang; Chuang Ma
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Most of the strong designated verifier signature (SDVS) schemes cannot tell the real signature generator when the signer and the designated verifier dispute on a signature. In other words, most of the SDVS schemes do not have the undeniability property. In this paper, we propose two SDVS schemes which hold the undeniability property, namely, strong designated verifier signature with undeniability property (SDVSUP). Our two schemes are called SDVSUP-1 and SDVSUP-2. In our two SDVSUP schemes, the signer not only can designate a verifier but also can designate an arbiter who can judge the signature when the signer and the designated verifier dispute on the signature. What is more, the judgment procedure can be performed by the arbiter alone without help from the signer or the designated verifier, which increases the judgment efficiency and reduces the complexity of signature confirmation. We also demonstrate a real instance of applying our SDVSUP scheme to electronic bidding system.


---

## Body

## 1. Introduction

In traditional digital signature (TDS), anyone who knows the public key of the signer can verify the validity of a signature. However, the public verification of TDS is not a desirable property in some applications. For example, the owner of some privacy information such as a health report from hospital or a bill from company and so on wishes that the signature on these privacy information can only be verified by himself. There are some solutions to this problem. One of them is to use the undeniable signature which was proposed first by Chaum and Antwerpen [1, 2]. In undeniable signature (US) [3–7], the signature verification needs the help from the signer. In other words, the validity verification of a signature is an interactive proof between the signer and the verifier which leads to the inefficiency and infeasibility if the signer rejects to cooperate. Another solution is to use the designated verifier signature (DVS) which was proposed first by Jakobsson et al. [8]. In DVS, the signer can designate a person as the signature verifier called designated verifier who can convince the signature to be generated by the signer. But the designated verifier cannot transfer the conviction to any third party since the designated verifier can generate a indistinguishable signature with the signer. This is called nontransferability. Therefore, though a signature is publicly verifiable in DVS but no one can tell that the signature is generated by the signer or the designated verifier. Jakobsson et al. also proposed a variant of DVS called strong designated verifier signature (SDVS) [8]. In SDVS, the signature verification needs the private key of the designated verifier. Thus, no one other than the signer and the designated verifier can verify the validity of signature which further protects the privacy information of the signer.However, if the signer and the designated verifier dispute on a signature, no one can tell the real generator of the signature either the signer or the designated verifier. Yang et al. [9, 10] gave an instance on this situation. In an electronic bidding system, some companies use SDVS to submit their prices to the institution for a project. Using the SDVS, the institution can confirm the submission but cannot transfer the submission to other companies for lower price since the institution also can generate an indistinguishable submission with the company. But if the winning company denies the submission due to some reasons, such as economic crisis, bankrupt, and even malicious competition. The institution can do nothing on it. This is undesirable to the institution. However, in almost all SDVS schemes [11–17] proposed till now this problem exists. Namely, these SDVS schemes have no undeniability property. Without undeniability property, SDVS is like more a message authentication code rather than a digital signature [9, 10].


### 1.1. Related Work

Jakobsson et al. first proposed the concept of DVS and presented a DVS scheme which was based on trapdoor commitments [8]. In Jakobsson et al.’s DVS scheme, a signature generated by the signer with the form of s=mxS while s was a random element in the signature generated by the designated verifier. Therefore, with the help from the signer, a person could distinguish the signature by an interactive proof between the signer and this person. So, Jakobsson et al.’s DVS scheme held the undeniability property. However, Jakobsson et al. did not explain the property explicitly and consider it as a necessary property. What is more, Lipmaa et al. [18] showed that Jakobsson et al.’s DVS scheme was not undeniable since the signer could construct a valid signature where s was a random element which made the third party confirm the signature from the designated verifier. Lipmaa et al. also proposed a DVS scheme based on Decisional Diffie-Hellman problem. However, their DVS scheme yet did not have the undeniability property.In order to protect the identity of the signer further, Jakobsson et al.’s [8] extended DVS to present the concept of SDVS. In Jakobsson et al.’s SDVS scheme, the designated verifier must use the private key of himself to verify the validity of the signature. From then, many SDVS were proposed [15, 19–21]. Some other variants of DVS included universal designated verifier signature (UDVS) [7, 22, 23], in which the owner of the standard signature could designate any third party as the designated verifier, identity-based designated verifier signature (IBDVS) [13, 16, 24], in which the private keys of the signer and the designated verifier were generated by the Key Generator Center (KGC), and so on.In 2012, Yang et al. [9, 10] proposed an SDVS scheme with the undeniability property based on Chameleon hash function [25]. In their SDVS scheme, when the signer and the designated verifier disputed on a signature, the signer confirmed a signature (r,s,ρ,h) if the following two situations held: (1) the signer could find r^ to hold r = H(r^), where r was one component of the signature and r^ was the preimage of r and was stored by the signer in advance; (2) the signer could find an original signature (r′,s′,ρ′,h′) of (r,s,ρ,h) where r′≠r, s′≠s, ρ′=ρ, h′=h, and (r′,s′,ρ′,h′) was stored by the signer in advance. Thus, the signer needed to store all original signature data in order to confirm the signature later which added a large storage cost. What is more, anyone could distinguish a signature by the above similar method as the signer, that is, collecting and storing all signature data. And the confirmation procedure of signature was performed only by the signer alone. It was unfair to the designated verifier. What is more, if the signer did not want to cooperate for some reasons, the confirmation procedure could not continue and was forced to stop.


### 1.2. Our Work

To our knowledge, Jakobsson et al.’s SDVS scheme [8] and Yang et al.’s SDVS scheme [9, 10] are only two SDVS schemes with undeniability property. However, in the two SDVS schemes, it needs a complex judgment procedure when the signer and the designated verifier dispute on a signature. What is more, the judgment needs the help from the signer. In other words, the judgment is an interactive procedure between the signer and the judger. If the signer rejects to cooperate, the judgment procedure cannot be continued and must be stopped. In our work, we propose two SDVS schemes which can solve the above problem. In other words, in our SDVS schemes, the judger or the arbiter can alone complete the judgment: who generates the signature? Either the signer or the designated verifier does. We also make a comparison between our schemes and other similar schemes in terms of computational cost, signature size, and other aspects. At the same time, we present one application instance of our schemes in the electronic bidding system.The remainder of this paper is organized as follows. In Section2, some preliminaries are given including Computational Diffie-Hellman problem and assumption, the concept of SDVS, and the security properties of SDVS. In Section 3, two SDVSUP schemes are proposed. The security analysis of two SDVSUP schemes and the comparison are presented. Section 4 concludes this paper.


## 1.1. Related Work

Jakobsson et al. first proposed the concept of DVS and presented a DVS scheme which was based on trapdoor commitments [8]. In Jakobsson et al.’s DVS scheme, a signature generated by the signer with the form of s=mxS while s was a random element in the signature generated by the designated verifier. Therefore, with the help from the signer, a person could distinguish the signature by an interactive proof between the signer and this person. So, Jakobsson et al.’s DVS scheme held the undeniability property. However, Jakobsson et al. did not explain the property explicitly and consider it as a necessary property. What is more, Lipmaa et al. [18] showed that Jakobsson et al.’s DVS scheme was not undeniable since the signer could construct a valid signature where s was a random element which made the third party confirm the signature from the designated verifier. Lipmaa et al. also proposed a DVS scheme based on Decisional Diffie-Hellman problem. However, their DVS scheme yet did not have the undeniability property.In order to protect the identity of the signer further, Jakobsson et al.’s [8] extended DVS to present the concept of SDVS. In Jakobsson et al.’s SDVS scheme, the designated verifier must use the private key of himself to verify the validity of the signature. From then, many SDVS were proposed [15, 19–21]. Some other variants of DVS included universal designated verifier signature (UDVS) [7, 22, 23], in which the owner of the standard signature could designate any third party as the designated verifier, identity-based designated verifier signature (IBDVS) [13, 16, 24], in which the private keys of the signer and the designated verifier were generated by the Key Generator Center (KGC), and so on.In 2012, Yang et al. [9, 10] proposed an SDVS scheme with the undeniability property based on Chameleon hash function [25]. In their SDVS scheme, when the signer and the designated verifier disputed on a signature, the signer confirmed a signature (r,s,ρ,h) if the following two situations held: (1) the signer could find r^ to hold r = H(r^), where r was one component of the signature and r^ was the preimage of r and was stored by the signer in advance; (2) the signer could find an original signature (r′,s′,ρ′,h′) of (r,s,ρ,h) where r′≠r, s′≠s, ρ′=ρ, h′=h, and (r′,s′,ρ′,h′) was stored by the signer in advance. Thus, the signer needed to store all original signature data in order to confirm the signature later which added a large storage cost. What is more, anyone could distinguish a signature by the above similar method as the signer, that is, collecting and storing all signature data. And the confirmation procedure of signature was performed only by the signer alone. It was unfair to the designated verifier. What is more, if the signer did not want to cooperate for some reasons, the confirmation procedure could not continue and was forced to stop.


## 1.2. Our Work

To our knowledge, Jakobsson et al.’s SDVS scheme [8] and Yang et al.’s SDVS scheme [9, 10] are only two SDVS schemes with undeniability property. However, in the two SDVS schemes, it needs a complex judgment procedure when the signer and the designated verifier dispute on a signature. What is more, the judgment needs the help from the signer. In other words, the judgment is an interactive procedure between the signer and the judger. If the signer rejects to cooperate, the judgment procedure cannot be continued and must be stopped. In our work, we propose two SDVS schemes which can solve the above problem. In other words, in our SDVS schemes, the judger or the arbiter can alone complete the judgment: who generates the signature? Either the signer or the designated verifier does. We also make a comparison between our schemes and other similar schemes in terms of computational cost, signature size, and other aspects. At the same time, we present one application instance of our schemes in the electronic bidding system.The remainder of this paper is organized as follows. In Section2, some preliminaries are given including Computational Diffie-Hellman problem and assumption, the concept of SDVS, and the security properties of SDVS. In Section 3, two SDVSUP schemes are proposed. The security analysis of two SDVSUP schemes and the comparison are presented. Section 4 concludes this paper.


## 2. Preliminaries

### 2.1. Computational Diffie-Hellman (CDH) Problem and CDH Assumption

Letp and q be two large primes which hold p=2q+1. Let Zq be a subgroup of Zp∗ with the prime order q and a generator g. Given (g,ga,gb) where a and b belong to Zq∗ are two unknown elements, the CDH problem is to compute gab.The CDH assumption (t,ϵ) holds in Zp∗ if there is not any algorithm A which can solve the CDH problem with running time at most t and the probability at least ϵ.


### 2.2. Strong Designated Verifier Signature

A strong designated verifier signature (SDVS) consists of four algorithms, including System Setup, Key Generate, Signature Generate, and Signature Verify.System Setup (SetSDV). Inputting 1k where k is a security parameter, the SetSDV algorithm outputs the system parameter params and publishes params publicly.Key Generate (KeySDV). Inputting the system parameter params, the KeySDV algorithm outputs the public and private key pair (Ts,ts) of the signer S, the one (Tv,tv) of the designated verifier V, and the one (Ta,ta) of the arbiter A.Signature Generate (SigSDV). Inputting params, the public keys of S, V, and A, the private key ts of S, and a message m, the SigSDV algorithm outputs a signature σ on m.Signature Verify (VerSDV). Inputting params, the public keys of S, V, and A, the private key tv of V, and a signature σ on a message m, the VerSDV algorithm outputs “Accept” if σ is a valid signature or “Reject.”If one can verify a signature without the private keytv of V, then it is called designated verifier signature (DVS) not strong DVS. Namely, inputting params, the public keys of S, V, and A and a signature σ on a message m, the VerSDV algorithm outputs “Accept” if σ is a valid signature or “Reject.”A secure strong designated verifier signature with undeniable property (SDVSUP) should hold unforgeability, computationally nontransferability, and undeniability.


### 2.3. Unforgeability

The unforgeability of an SDVSUP scheme is defined by the following game between the challengerC and an adversary R. The game includes three stages: setup, query, and output.Setup. The challenger C creates the public system parameter params and the public/private key pair (Ts,ts) of the signer S, the one (Tv,tv) of the designated verifier V, and the one (Ta,ta) of the arbiter A. Then, send params and (Ts,Tv,Ta) to the adversary R.Query. Next, R makes the following oracle queries.(1)
Signing Query:R submits a message m to request a signature on m; C generates a valid signature σ on m and returns σ to R.(2)
Verifying Query:R submits a signature σ on a message m; C returns “True” to R if the signature σ is valid. Otherwise, it returns “False” to R.Output. Finally, R outputs a forged signature σ∗ on a message m∗. R wins the above game if(1)
σ∗ is a valid signature on m∗,(2)
m∗ has never been queried to Signing Query.An SDVSUP scheme is(t,ϵ,qs,qv) unforgeable if no adversary R can win the above game with the time at most t, the probability at least ϵ, making at most qs signing queries, and making at most qv verifying queries.


### 2.4. Nontransferability

According to the work of [18, 22], the nontransferability of SDVSUP can be classified into two types: computational nontransferability and perfect nontransferability. Based on the concept of nontransferability for SDVS given by [18, 22], we add a participator called arbiter A into the original definition to present a description of nontransferability for SDVSUP.An SDVSUP scheme is computationally nontransferable if given a pair of message and signature (m,σ); it is infeasible for any probabilistic polynomial-time (PPT) algorithm to distinguish that the signature σ is generated by the signer S or the designated verifier V without the knowledge of the secret key of the signer S, the secret key of the designated verifier V, and the secret key of the arbiter A.An SDVSUP scheme is perfectly nontransferable if one cannot distinguish the signatureσ from the signer or the designated verifier even if one knows the secret keys of the signer S, the designated verifier V, and the arbiter A.Next, we give a definition of computationally nontransferable for SDVSUP scheme. An SDVSUP scheme is computationally nontransferable if there exists a PPT algorithm: Simulate Signature (SimSDV) in which the designated verifierV can use SimSDV to simulate a signature σ1. σ1 is indistinguishable from the real signature which is generated by the signer S without knowing the secret key ts of S, the secret key tv of V, and the secret key ta of A. In other words, there is not any PPT distinguisher B that is inputting the public key Ts of S, the public key Tv of V, the public key Ta of the arbiter A, and a signature σx to tell the signature σx from S or V with a nonnegligible probability ϵ, namely,(1)PrTi,ti⟵KeySDV1k,i∈s,v,a,σ0⟵SigSDVTs,Tv,Ta,ts,m,x=x′σ1⟵SimSDVTs,Tv,Ta,tv,m,x⟵R0,1,x′⟵BTs,Tv,Ta,σx=ϵ.Similarly, we can define the perfectly nontransferable of SDVSUP scheme with changing the inputting ofB into the public/private key (Ts,ts) of S, the public/private key (Tv,tv) of V, the public/private key (Ta,ta) of the arbiter A, and a signature σx.Since there is not any trapdoor information that can be used by the arbiterA even if S and V are in perfect nontransferability, an SDVSUP scheme only holds the computational nontransferability not perfect nontransferability [18].


### 2.5. Undeniability

An SDVSUP scheme holds the undeniability property if there exists a PPT algorithm: Arbitrate Signature (ArbSDV) with inputting the signatureσ on m, the public keys of the signer S and the designated verifier V, and the private key of the arbiter A; the ArbSDV outputs “S” if the signature is generated by the signer S or returns “V” that denotes the signature from the designated verifier V; that is,(2)N⟵ArbSDVTs,Tv,ta,σ,N∈S,V.


## 2.1. Computational Diffie-Hellman (CDH) Problem and CDH Assumption

Letp and q be two large primes which hold p=2q+1. Let Zq be a subgroup of Zp∗ with the prime order q and a generator g. Given (g,ga,gb) where a and b belong to Zq∗ are two unknown elements, the CDH problem is to compute gab.The CDH assumption (t,ϵ) holds in Zp∗ if there is not any algorithm A which can solve the CDH problem with running time at most t and the probability at least ϵ.


## 2.2. Strong Designated Verifier Signature

A strong designated verifier signature (SDVS) consists of four algorithms, including System Setup, Key Generate, Signature Generate, and Signature Verify.System Setup (SetSDV). Inputting 1k where k is a security parameter, the SetSDV algorithm outputs the system parameter params and publishes params publicly.Key Generate (KeySDV). Inputting the system parameter params, the KeySDV algorithm outputs the public and private key pair (Ts,ts) of the signer S, the one (Tv,tv) of the designated verifier V, and the one (Ta,ta) of the arbiter A.Signature Generate (SigSDV). Inputting params, the public keys of S, V, and A, the private key ts of S, and a message m, the SigSDV algorithm outputs a signature σ on m.Signature Verify (VerSDV). Inputting params, the public keys of S, V, and A, the private key tv of V, and a signature σ on a message m, the VerSDV algorithm outputs “Accept” if σ is a valid signature or “Reject.”If one can verify a signature without the private keytv of V, then it is called designated verifier signature (DVS) not strong DVS. Namely, inputting params, the public keys of S, V, and A and a signature σ on a message m, the VerSDV algorithm outputs “Accept” if σ is a valid signature or “Reject.”A secure strong designated verifier signature with undeniable property (SDVSUP) should hold unforgeability, computationally nontransferability, and undeniability.


## 2.3. Unforgeability

The unforgeability of an SDVSUP scheme is defined by the following game between the challengerC and an adversary R. The game includes three stages: setup, query, and output.Setup. The challenger C creates the public system parameter params and the public/private key pair (Ts,ts) of the signer S, the one (Tv,tv) of the designated verifier V, and the one (Ta,ta) of the arbiter A. Then, send params and (Ts,Tv,Ta) to the adversary R.Query. Next, R makes the following oracle queries.(1)
Signing Query:R submits a message m to request a signature on m; C generates a valid signature σ on m and returns σ to R.(2)
Verifying Query:R submits a signature σ on a message m; C returns “True” to R if the signature σ is valid. Otherwise, it returns “False” to R.Output. Finally, R outputs a forged signature σ∗ on a message m∗. R wins the above game if(1)
σ∗ is a valid signature on m∗,(2)
m∗ has never been queried to Signing Query.An SDVSUP scheme is(t,ϵ,qs,qv) unforgeable if no adversary R can win the above game with the time at most t, the probability at least ϵ, making at most qs signing queries, and making at most qv verifying queries.


## 2.4. Nontransferability

According to the work of [18, 22], the nontransferability of SDVSUP can be classified into two types: computational nontransferability and perfect nontransferability. Based on the concept of nontransferability for SDVS given by [18, 22], we add a participator called arbiter A into the original definition to present a description of nontransferability for SDVSUP.An SDVSUP scheme is computationally nontransferable if given a pair of message and signature (m,σ); it is infeasible for any probabilistic polynomial-time (PPT) algorithm to distinguish that the signature σ is generated by the signer S or the designated verifier V without the knowledge of the secret key of the signer S, the secret key of the designated verifier V, and the secret key of the arbiter A.An SDVSUP scheme is perfectly nontransferable if one cannot distinguish the signatureσ from the signer or the designated verifier even if one knows the secret keys of the signer S, the designated verifier V, and the arbiter A.Next, we give a definition of computationally nontransferable for SDVSUP scheme. An SDVSUP scheme is computationally nontransferable if there exists a PPT algorithm: Simulate Signature (SimSDV) in which the designated verifierV can use SimSDV to simulate a signature σ1. σ1 is indistinguishable from the real signature which is generated by the signer S without knowing the secret key ts of S, the secret key tv of V, and the secret key ta of A. In other words, there is not any PPT distinguisher B that is inputting the public key Ts of S, the public key Tv of V, the public key Ta of the arbiter A, and a signature σx to tell the signature σx from S or V with a nonnegligible probability ϵ, namely,(1)PrTi,ti⟵KeySDV1k,i∈s,v,a,σ0⟵SigSDVTs,Tv,Ta,ts,m,x=x′σ1⟵SimSDVTs,Tv,Ta,tv,m,x⟵R0,1,x′⟵BTs,Tv,Ta,σx=ϵ.Similarly, we can define the perfectly nontransferable of SDVSUP scheme with changing the inputting ofB into the public/private key (Ts,ts) of S, the public/private key (Tv,tv) of V, the public/private key (Ta,ta) of the arbiter A, and a signature σx.Since there is not any trapdoor information that can be used by the arbiterA even if S and V are in perfect nontransferability, an SDVSUP scheme only holds the computational nontransferability not perfect nontransferability [18].


## 2.5. Undeniability

An SDVSUP scheme holds the undeniability property if there exists a PPT algorithm: Arbitrate Signature (ArbSDV) with inputting the signatureσ on m, the public keys of the signer S and the designated verifier V, and the private key of the arbiter A; the ArbSDV outputs “S” if the signature is generated by the signer S or returns “V” that denotes the signature from the designated verifier V; that is,(2)N⟵ArbSDVTs,Tv,ta,σ,N∈S,V.


## 3. The Proposed Strong Designated Verifier Signature Schemes with Undeniable Property

In this section, we provide two strong designated verifier signature schemes with undeniable property. The first one is called SDVSUP-1 scheme and the another is called SDVSUP-2 scheme.


### 3.1. The Proposed SDVSUP-1 Scheme

Based on Jakobsson et al.’s scheme [8], we propose a new strong designated verifier signature scheme with undeniable property (SDVSUP-1 scheme). In our SDVSUP-1 scheme, there exists three participators: the signer S, the designated verifier V, and the arbiter A. Our SDVSUP-1 scheme performs according to the following process.System Setup (SetSDV). Let p and q be two large primes which hold p=2q+1. Let Zq be a subgroup of Zp∗ with the prime order q and a generator g. Define three hash functions which hold F1: {0,1}∗→Zq∗, F2: {0,1}∗×Zq∗→Zq∗, and F3: (Zq∗)5×{0,1}∗→Zq∗. Then, the system parameters are L=(p,q,g,F1,F2,andF3).Key Generate (KeySDV). The signer S selects randomly two numbers ts,1 and ts,2∈Zq∗ as the private keys of S. And compute Ts,1=gts,1 mod p and Ts,2=gts,1 mod p as its public keys. Similarly, the designated verifier V generates its public keys (Tv,1,Tv,2) and private keys (tv,1,tv,2), where tv,1 and tv,2∈Zq∗ are two random numbers, and Tv,1 = gtv,1 mod p; Tv,2 = gtv,2 mod p. The arbiter A generates its public keys (Ta,1,Ta,2) and private keys (ta,1,ta,2), where ta,1 and ta,2∈Zq∗ are two random numbers, and Ta,1=gta,1 mod p and Ta,2=gta,2 mod p.Signature Generate (SigSDV). The signer S constructs a signature on a message m as follows. S selects randomly k1,k2,k3∈Zq∗ and computes(3)K1=Ta,1k1modp.K2=gk1modpK3=gk2Tv,1k3modpM=Ta,1F1mts,1+F2m,gts,2modpM1=Tv,1ts,1modph=F3K1,K2,K3,M,M1,mr=k1+Fmts,1+Fm∥gts,2h+k2modq.The final signature on the message m is σ = (k2, k3, h, r, M).Signature Verify (VerSDV). The designated verifier V checks the validity of a signature σ = (k2,k3,h,r,M) on message m as follows. V computes(4)K1′=Ta,1rM-h+k2modpK2′=grTs,1F1mTs,2F2m,g-h+k2modpK3′=gk2Tv,1k3modpM1′=Tv,1ts,1modph′=F3K1′,K2′,K3′,M,M1′,m.If h=h′, then V accepts the signature or rejects it.


### 3.2. Correctness of SDVSUP-1 Scheme

The above signature generated byS is correct because(5)Ta,1rM-h+k2modp=Ta,1k1+F1mts,1+F2m,gts,2h+k2M-h+k2modp=Ta,1k1Ta,1F1mts,1+F2m,gts,2h+k2·Ta,1F1mts,1+F2m,gts,2-h+k2modp=Ta,1k1modp.grTs,1F1mTs,2F2m,g-h+k2modp=gk1+F1mts,1+F2m,gts,2h+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1gF1mts,1+F2m,gts,2h+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1Ts,1F1mTs,2F2m,gh+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1modp.Tv,1ts,1=Ts,1tv,1modp.The above signature simulated by V is correct because(6)Ta,1rM-h+k2modp=Ta,1rM-h+x1-hmodp=Ta,1rM-x1modp.grTs,1F1mTs,2F2m,g-h+k2modp=grTs,1F1mTs,2F2m,g-h+x1-hmodp=grTs,1F1mTs,2F2m,g-x1modp.gk2Tv,1k3modp=gx1-hTv,1x2-k2tv,1-1modp=gx1-hgx2-k2modp=gx1-hgx2-x1-hmodp=gx2modp.


### 3.3. Security Analysis of SDVSUP-1 Scheme

Theorem 1.
If the CDH assumption (tcdh, ϵcdh) holds, then our proposed SDVSUP-1 scheme is (tsdv1, qf1, qf2, qf3, qs, qv, and ϵsdv1) unforgeable, where(7)tcdh≈tsdv1+τexp6qs+6qv+7+4τmulqs+qv+1,ϵcdh≥ϵsdv1-qF3qsq-2q.And τexp is one exponent operation in Zp∗ and τmul is one multiplication operation in Zp∗. qf1, qf2, qf3, qs, and qv denote, respectively, that the adversary R is allowed to make at most qf1F1 queries, qf2F2 queries, qf3F3 queries, qs signing queries, and qv verifying queries.Proof.
Given a CDH problem instance (g, gx, gy), the aim of challenger C is to obtain gxy. Next, C performs the following process with the adversary R.
Setup. C selects randomly λ1,λ2,λ3,λ4,λ5,λ6∈Zq∗ and sets Ts,1=gxλ1 mod p, Ts,2=gλ2 mod p, Tv,1=gyλ3 mod p, Tv,2=gλ4modp, Ta,1=gλ5 mod p, and Ta,2=gλ6modp. C publishes the system parameters L = (p, q, g, F1, F2, F3) and the public keys (Ts,1, Ts,2), (Tv,1, Tv,2), and (Ta,1, Ta,2).
Query. The adversary R makes the following queries to C.
Random Oracle Query (i)
WhenR asks a query on F1 oracle with inputting mi, C searches mi in table T1 that is empty initially. If there exists a tuple (mi, l1,i) in T1, C returns l1,i to R as the value of F1(mi). Otherwise, C selects randomly l1,i∈Zq∗ and records (mi, l1,i) in T1 and returns l1,i to R. (ii)
WhenR asks a query on F2 oracle with inputting (mi, g), C searches (mi, g) in table T2 that is empty initially. If there exists a tuple (mi, g, l2,i) in T2, C returns l2,i to R as the value of F2(mi,g). Otherwise, C selects randomly l2,i∈Zq∗ and records (mi, g, l2,i) in T2 and returns l2,i to R. (iii)
WhenR asks a query on F3 oracle with inputting (K1,i, K2,i, K3,i, Mi, M1,i, mi), C searches (K1,i, K2,i, K3,i, Mi, ∗, mi) in table T3 that is empty initially. If there exists a tuple (K1,i, K2,i, K3,i, Mi, ∗, mi, l3,i) in T3, C returns l3,i to R as the value of F2(K1,i, K2,i, K3,i, Mi, M1,i, mi). Otherwise, C selects randomly l3,i∈Zq∗ and records (K1,i, K2,i, K3,i, Mi, M1,i, mi, l3,i) in T3 and returns l3,i to R.
Signing Query (i)
WhenR asks a signature query with inputting mi, C searches mi in table T4 that is empty initially. If there exists a tuple (mi, k2,i, k3,i, hi, ri, Mi, ⊥) in T4, C returns (k2,i, k3,i, hi, ri, Mi) to R as the signature on message mi. Otherwise, C searches T1 on mi and T2 on (mi, g). If mi and (mi, g) have not existed in T1 and T2, then C performs the above F1 oracle and F2 oracle to obtain l1,i and l2,i. Then,C chooses randomly ri, k2,i, k3,i, l3,i∈Zq∗, and Mi∈Zp∗. Compute(8)K1,i=Ta,1riMi-l3,i+k2,imodpK2,i=griTs,1l1,iTs,2l2,i-l3,i+k2,imodpK3,i=gk2,iTv,1k3,imodp and setF3(K1,i,K2,i,K3,i,Mi,⊥,mi) = l3,i. If there exists a tuple (K1,i, K2,i, K3,i, Mi, M1,i, mi, l3,i′) in T3 and l3,i′≠l3,i, then C fails and aborts. Otherwise, C records (mi, k2,i, k3,i, hi, ri, Mi) in T4 and returns (k2,i, k3,i, hi, ri, Mi) to R. And record (K1,i, K2,i, K3,i, Mi, ⊥, mi, l3,i) in T3. The probability of failure for C is qF3qs/q.
Verifying Query (i)
WhenR asks a signature verification query with σ = (k2,i, k3,i, hi, ri, Mi) on the message mi, C searches (k2,i, k3,i, hi, ri, Mi) in table T4. If there exists a tuple (mi, k2,i, k3,i, hi, ri, Mi) in T4, C returns “true.” Otherwise, C computes(9)K1,i=Ta,1riM-hi+k2,imodpK2,i=griTs,1F1miTs,2F2mi,g-hi+k2,imodpK3,i=gk2,iTv,1k3,imodp. ThenC searches (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) in T3. If (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) exits in T3, then C returns false. Otherwise, (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) has not existed in T3; then C outputs “false” and aborts. The probability which σ = (k2,i, k3,i, hi, ri, Mi) is a valid signature and did not make a F3 query is 1/q.
Forge. Finally, R outputs a forged signature σ∗ = (k2∗, k3∗, h∗, r∗, M∗) on a message m∗. After C gets σ∗, C first computes(10)K1∗=Ta,1r∗M-h∗+k2∗modpK2∗=gr∗Ts,1F1m∗Ts,2F2m∗,g-h∗+k2∗modpK3∗=gk2∗Tv,1k3∗modp.Then, C searches (K1∗, K2∗, K3∗, M∗, m∗, h∗) in T3. Because σ∗ is a valid signature, R must query F3 on (K1∗, K2∗, K3∗, M∗, M1∗, m∗, h∗) previously. Thus, C can get M1∗ = Tv,1ts,1 mod p = gyλ3xλ1 mod p. So, gxy mod p = M1∗(λ1λ3)-1 mod p. The probability which σ∗ = (k2∗, k3∗, h∗, r∗, M∗) is a valid signature and did not make a F3 query previously is 1/q.Theorem 2.
The proposed SDVSUP-1 scheme is computationally nontransferable.Proof.
The designated verifierV can simulate a valid signature σ′ on the message m by the following SimSDV algorithm. V chooses randomly x1,x2,r∈Zq∗, and M∈Zp∗. Then compute(11)K1=Ta,1rM-x1modpK2=grTs,1F1mTs,2F2m,g-x1modpK3=gx2modpM1=Ts,1tv,1modp.h=F3K1,K2,K3,M,M1,mk2=x1-hmodqk3=x2-k2tv,1-1modq.The simulating signature of V is σ′ = (k2,k3,h,r,M). Since we need the private key of S or V to verify Ts,1tv,1 and need the private key of S or A to verify M, anyone cannot distinguish the original signature σ and the simulating signature σ′ without knowing the private keys of S, V, and A.Theorem 3.
The proposed SDVSUP-1 scheme is undeniable.Proof.
When the signerS and the designated verifier V dispute who generates the signature σ on the message m, S or V submits the signature σ = (k2, k3, h, r, M) on m to the arbiter A. Then, A runs the following ArbSDV algorithm. Namely, compute(12)M′=Ts,1ta,1F1mTs,2ta,1F2m,gmodp.Then, A checks if M = M′. If it is true, then A confirms that the signature σ on the message m is generated by the signer S. Otherwise, the signature σ is generated by the designated verifier V. Since M is a random number in simulating signature ϵ′ while M = Ta,1F1(m)ts,1+F2(m,g)ts,2modp in the real signature ϵ. Therefore, the arbiter A can use the ArbSDV algorithm to tell the real signer.


### 3.4. The Proposed SDVSUP-2 Scheme

The above SDVSUP-1 scheme is a strong designated verifier signature scheme which has the undeniable property. In the SDVSUP-1 scheme, the arbiterA judges the signature generator by checking the format of M in the signature σ = (k2, k3, h, r, M) on m because only M from the signer S has the format Ta,1F(m)ts,1+F(m∥g)ts,2, while M from the designated verifier V is a random number in Zp∗.Because of this fact “onlyM from the signer S has the special format, namely, Ta,1F(m)ts,1+F(m∥g)ts,2, while M from the designated verifier V is a random number in Zp∗.” Thus, the arbiterA only can check the format of M with the public key (Ts,1, Ts,2) of the signer to judge the result, which is a little unfair to the designated verifier V. In other words, the designed verifier can do nothing and it even has some doubts on the judge result. Therefore, in this subsection, we present another scheme where S and V can both construct M with their own characteristic respectively. Namely, in our SDVSUP-2 scheme, M generated by the signer S is the format M = Ta,1F1(m)ts,1+F2(m,g)ts,2, while M generated by the designated verifier V is the format M = Ta,1F1(m)tv,1+F2(m,g)tv,2. Thus, the arbiter A can check the format of M with the public key (Ts,1, Ts,2) of the signer (by computing M = (Ts,1F1(m)Ts,2F2(m,g))ta,1) or with the public key (Tv,1, Tv,2) of the designated verifier (by computing M = (Tv,1F1(m)Tv,2F2(m,g))ta,1) to judge the result, which make the arbiter A distinguish the signature easier, fairer, and more convenient. Next, we show the construction of our SDVSUP-2 scheme which is a modification of SDVSUP-1 scheme.SetSDV. The algorithm works as the above SDVSUP-1 scheme except F3: (Zq∗)4×{0,1}∗→Zq∗. Finally, the system parameters are L = (p, q, g, F1, F2, F3).KeySDV. The algorithm works as the SDVSUP-1 scheme. Finally, S, V, and A obtain their private keys and public keys ((ts,1, ts,2), (Ts,1, Ts,2)), ((tv,1, tv,2), (Tv,1, Tv,2)), ((ta,1, ta,2), and (Ta,1, Ta,2)), respectively.SigSDV. S chooses randomly t2,r2∈Zq∗ and computes(13)K1=Ts,1F1mTs,2F2m,gt2Tv,1F1mTv,2F2m,gr2modpK2=Ta,1F1mts,1+F2m,gts,2r2+t2modpM=Ta,1F1mts,1+F2m,gts,2modpM1=Tv,1ts,1modph=F3K1,K2,M,M1,mr1=t2+hF1mts,1+F2m,gts,2-1modq.The final signature on the message m is σ = (r1, r2, h, M).VerSDV. For a signature σ = (r1, r2, h, M) on the message m, V computes(14)K1′=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modpK2′=Ta,1-hMr1+r2modpM1=Ts,1tv,1modph′=F3K1′,K2′,M,M1,m.If h = h′, then V accepts the signature or rejects it.Note that if we drop the inputtingM1 in the F3() of the above SDVSUP-2 scheme, namely, h = F3(K1,K2,M,m), then the SDVSUP-2 scheme can become a designated verifier signature not a strong scheme (namely, designated verifier signature with undeniability property (DVSUP), we call it DVSUP-2 scheme) because anyone can check the validity of the signature σ generated by DVSUP-2 scheme. Similarly, the SDVSUP-1 scheme also can become a designated verifier scheme (we call it DVSUP-1 scheme) by dropping the M1, namely, h = F3(K1,K2,K3,M,m).


### 3.5. Correctness of SDVSUP-2 Scheme

The above signatureσ generated by S of SDVSUP-2 scheme is correct because(15)g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gt2+hF1mts,1+F2m,gts,2-1·Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gt2ghTv,1F1mTv,2F2m,gr2modp=Ts,1F1mTs,2F2m,gt2Tv,1F1mTv,2F2m,gr2modp.Ta,1-hMr1+r2modp=Ta,1-hMt2+hF1mts,1+F2m,gts,2-1+r2modp=Ta,1-hTa,1F1mts,1+F2m,gts,2t2+r2·Ta,1F1mts,1+F2m,gts,2hF1mts,1+F2m,gts,2-1modp=Ta,1-hTa,1F1mts,1+F2m,gts,2t2+r2Ta,1hmodp=Ta,1F1mts,1+F2m,gts,2t2+r2modp.The above signature σ simulated by V of SDVSUP-2 scheme is correct because(16)g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gr1·Tv,1F1mTv,2F2m,gt2+hF1mtv,1+F2m,gtv,2-1modp=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2·Tv,1F1mTv,2F2m,ghF1mtv,1+F2m,gtv,2-1modp=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2ghmodp=Ts,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2modp.Ta,1-hMr1+r2modp=Ta,1-hMr1+t2+hF1mtv,1+F2m,gtv,2-1modp=Ta,1-hTa,1F1mtv,1+F2m,gtv,2r1+t2·Ta,1F1mtv,1+F2m,gtv,2hF1mtv,1+F2m,gtv,2-1modp=Ta,1-hTa,1F1mtv,1+F2m,gtv,2r1+t2Ta,1hmodp=Ta,1F1mtv,1+F2m,gtv,2r1+t2modp.Theorem 4.
The proposed SDVSUP-2 scheme is computationally nontransferable.Proof.
In order to simulate a valid signature on the messagem, the designated verifier V chooses randomly t2,r1∈Zq∗ and computes(17)K1=Ts,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2modpK2=Ta,1F1mtv,1+F2m,gtv,2r1+t2modpM=Ta,1F1mtv,1+F2m,gtv,2modpM1=Ts,1tv,1modph=F3K1,K2,M,M1,mr2=t2+hF1mtv,1+F2m,gtv,2-1modq.The final simulating signature on the message m is σ′ = (r1, r2, h, M). Since we need the private key of S or V to verify Ts,1tv,1 and need the private key of S or A to verify M, anyone cannot distinguish the original signature σ and the simulating signature σ′ without knowing the private keys of S, V, and A.Theorem 5.
The proposed SDVSUP-2 scheme is undeniable.Proof.
The arbiterA adapts the following method to judge the signature. A first gets the public keys of the signer and the designated verifier. Then, A uses the private ta,1 to compute(18)M′=Ts,1F1mTs,2F2m,gta,1modpM′′=Tv,1F1mTv,2F2m,gta,1modp.Then, A checks if M = M′ or M = M′′. If M = M′, then A confirms the signature σ on the message m is generated by the signer S. If M = M′′, then the signature σ is generated by the designated verifier V. Since M = Ta,1F1(m)tv,1+F2(m,g)tv,2modp in the simulating signature ϵ′, M = Ta,1F1(m)ts,1+F2(m,g)ts,2modp in the real signature ϵ. Therefore, the arbiter A can use the ArbSDV algorithm to tell the real signer.Theorem 6.
If the CDH assumption (tcdh, ϵcdh) holds, then the proposed SDVSUP-2 scheme is (tsdv1, qf1, qf2, qf3, qs, qv, ϵsdv1) unforgeable.Proof.
The proof method is very similar to the Theorem1. So, we omit it.


### 3.6. Comparison

In Tables1 and 2, we compare our schemes with other similar schemes in terms of performance and security features. “Computational cost” denotes the totally computational cost of signing and verifying. “Signature length” denotes the signature size. “Unforg.” denotes if the scheme satisfies the unforgeability property. “Nontransf.” denotes if the scheme holds the nontransferability property. “Unden.” denotes if the scheme holds the undeniability property. “Help from signer” denotes if it needs the help from the signer when the arbiter judges a signature’s generator. “E” denotes one exponentiation computation in Zp∗. “GE” denotes one exponentiation computation in G where G is a bilinear group. “P” denotes one paring computation in G. “Zq”, “Zp,” and “G” denote the length of one element from “Zq”, “Zp,” and “G,” respectively.Table 1
Performance comparison with other schemes.
Scheme Computational cost Signature length Jakobsson et al. [8] 11E 3 Z q + 3 Z p Yang et al. [10] 9E 4 Z q Tian et al. [11] 11GE + 2P 1 Z q + 4 G Islam and Biswas [12] 6GE + 4P 1 Z q + 2 G SDVSUP-1 14E 4 Z q + 1 Z p SDVSUP-2 15E 3 Z q + 1 Z pTable 2
Security features comparison with other schemes.
Scheme Unforg. Non-transf. Unden. Help from signer Jakobsson et al. [8] √ √ × √ Yang et al. [10] √ × √ √ Tian et al. [11] √ √ × × Islam and Biswas [12] √ √ × × SDVSUP-1 √ √ √ × SDVSUP-2 √ √ √ ×From Table2, it can be seen that our schemes including SDVSUP-1 and SDVSUP-2 not only hold the features of unforgeability and nontransferability but also have the undeniability property. What is more, the arbiter can alone judge the generator in our two schemes, while any other schemes do not have the property. Therefore, our two schemes have better security features. In terms of signature size, from Table 1, it can be seen that our schemes outperform the schemes in [8, 11] and also are comparable with the schemes in [10, 12]. In terms of computational cost, our schemes can perform many recomputations on some operations such as Ts,1tv,1. Therefore, our schemes also have comparable computational complexity as other schemes [8, 10–12].


### 3.7. Applications

SDVS has many applications such as electronic voting (e-voting) system, bidding system in business, and electronic will. Next, we demonstrate an example on how to apply our SDVSUP scheme to the bidding system in business.We assume thatBi is a bidder on behalf of a company to make a project compete with other bidders, V is the tenderee on behalf of the enterprise to choose the most suitable company for performing the project. J is a trust third party to perform judging. Then, the bidding system consists of the following components.Initialization Phase. Generate the system parameter L according to the SetSDV. Bi, V, and J obtain the public/private keys ((TBi,1, TBi,2), (tBi,1, tBi,2)), ((TV,1, TV,2), (tV,1, tV,2)), ((TJ,1, TJ,2), and (tJ,1, tJ,2)), respectively, according to the KeySDV. V publishes the notice on the project for bidding.Bidding Phase. The company Bi who wants to perform the project prepares the biding document mi and signs on mi with the private (tBi,1, tBi,2) to obtain the signature σi according to the SigSDV. Then Bi sends σi to V.Choosing Phase. V verifies the validity of σi for all receiving biding documents. Then V chooses the most suitable bidder as the winner according to the price or other reasons presented in biding document.Note. In order to obtain lowest price, V maybe show the bidding document of Bi to Bj. Thus, Bj must set lower price than Bi to obtain the project. By the similar method, V can show the bidding document of Bj to Bk who is forced to set lower price than Bj and so on, which causes a vicious cycle. An SDVS scheme can solve this problem since the V also can generate a valid signature on mi which is indistinguishable from the original signature generated by Bi. However, if Bi and V dispute the signature σi on mi or both deny the signature, then the ordinary SDVS scheme cannot solve the judge problem. But there is no such problem in our SDVSUP schemes.Judging Phase. Given a signature σi on mi, the judger J determines the signature by computing M′ = (TBi,1F1(mi)TBi,2F2(mi,g))tJ,1modp and M′′ = (TV,1F1(mi)TV,2F2(mi,g))tJ,1modp. If M = M′, then σi is generated by the Bi. If M = M′′, then σi is generated by the V.Using the similar method to the above, our SDVSUP can be applied in electronic voting (e-voting) system, electronic will, and so on.


## 3.1. The Proposed SDVSUP-1 Scheme

Based on Jakobsson et al.’s scheme [8], we propose a new strong designated verifier signature scheme with undeniable property (SDVSUP-1 scheme). In our SDVSUP-1 scheme, there exists three participators: the signer S, the designated verifier V, and the arbiter A. Our SDVSUP-1 scheme performs according to the following process.System Setup (SetSDV). Let p and q be two large primes which hold p=2q+1. Let Zq be a subgroup of Zp∗ with the prime order q and a generator g. Define three hash functions which hold F1: {0,1}∗→Zq∗, F2: {0,1}∗×Zq∗→Zq∗, and F3: (Zq∗)5×{0,1}∗→Zq∗. Then, the system parameters are L=(p,q,g,F1,F2,andF3).Key Generate (KeySDV). The signer S selects randomly two numbers ts,1 and ts,2∈Zq∗ as the private keys of S. And compute Ts,1=gts,1 mod p and Ts,2=gts,1 mod p as its public keys. Similarly, the designated verifier V generates its public keys (Tv,1,Tv,2) and private keys (tv,1,tv,2), where tv,1 and tv,2∈Zq∗ are two random numbers, and Tv,1 = gtv,1 mod p; Tv,2 = gtv,2 mod p. The arbiter A generates its public keys (Ta,1,Ta,2) and private keys (ta,1,ta,2), where ta,1 and ta,2∈Zq∗ are two random numbers, and Ta,1=gta,1 mod p and Ta,2=gta,2 mod p.Signature Generate (SigSDV). The signer S constructs a signature on a message m as follows. S selects randomly k1,k2,k3∈Zq∗ and computes(3)K1=Ta,1k1modp.K2=gk1modpK3=gk2Tv,1k3modpM=Ta,1F1mts,1+F2m,gts,2modpM1=Tv,1ts,1modph=F3K1,K2,K3,M,M1,mr=k1+Fmts,1+Fm∥gts,2h+k2modq.The final signature on the message m is σ = (k2, k3, h, r, M).Signature Verify (VerSDV). The designated verifier V checks the validity of a signature σ = (k2,k3,h,r,M) on message m as follows. V computes(4)K1′=Ta,1rM-h+k2modpK2′=grTs,1F1mTs,2F2m,g-h+k2modpK3′=gk2Tv,1k3modpM1′=Tv,1ts,1modph′=F3K1′,K2′,K3′,M,M1′,m.If h=h′, then V accepts the signature or rejects it.


## 3.2. Correctness of SDVSUP-1 Scheme

The above signature generated byS is correct because(5)Ta,1rM-h+k2modp=Ta,1k1+F1mts,1+F2m,gts,2h+k2M-h+k2modp=Ta,1k1Ta,1F1mts,1+F2m,gts,2h+k2·Ta,1F1mts,1+F2m,gts,2-h+k2modp=Ta,1k1modp.grTs,1F1mTs,2F2m,g-h+k2modp=gk1+F1mts,1+F2m,gts,2h+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1gF1mts,1+F2m,gts,2h+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1Ts,1F1mTs,2F2m,gh+k2Ts,1F1mTs,2F2m,g-h+k2modp=gk1modp.Tv,1ts,1=Ts,1tv,1modp.The above signature simulated by V is correct because(6)Ta,1rM-h+k2modp=Ta,1rM-h+x1-hmodp=Ta,1rM-x1modp.grTs,1F1mTs,2F2m,g-h+k2modp=grTs,1F1mTs,2F2m,g-h+x1-hmodp=grTs,1F1mTs,2F2m,g-x1modp.gk2Tv,1k3modp=gx1-hTv,1x2-k2tv,1-1modp=gx1-hgx2-k2modp=gx1-hgx2-x1-hmodp=gx2modp.


## 3.3. Security Analysis of SDVSUP-1 Scheme

Theorem 1.
If the CDH assumption (tcdh, ϵcdh) holds, then our proposed SDVSUP-1 scheme is (tsdv1, qf1, qf2, qf3, qs, qv, and ϵsdv1) unforgeable, where(7)tcdh≈tsdv1+τexp6qs+6qv+7+4τmulqs+qv+1,ϵcdh≥ϵsdv1-qF3qsq-2q.And τexp is one exponent operation in Zp∗ and τmul is one multiplication operation in Zp∗. qf1, qf2, qf3, qs, and qv denote, respectively, that the adversary R is allowed to make at most qf1F1 queries, qf2F2 queries, qf3F3 queries, qs signing queries, and qv verifying queries.Proof.
Given a CDH problem instance (g, gx, gy), the aim of challenger C is to obtain gxy. Next, C performs the following process with the adversary R.
Setup. C selects randomly λ1,λ2,λ3,λ4,λ5,λ6∈Zq∗ and sets Ts,1=gxλ1 mod p, Ts,2=gλ2 mod p, Tv,1=gyλ3 mod p, Tv,2=gλ4modp, Ta,1=gλ5 mod p, and Ta,2=gλ6modp. C publishes the system parameters L = (p, q, g, F1, F2, F3) and the public keys (Ts,1, Ts,2), (Tv,1, Tv,2), and (Ta,1, Ta,2).
Query. The adversary R makes the following queries to C.
Random Oracle Query (i)
WhenR asks a query on F1 oracle with inputting mi, C searches mi in table T1 that is empty initially. If there exists a tuple (mi, l1,i) in T1, C returns l1,i to R as the value of F1(mi). Otherwise, C selects randomly l1,i∈Zq∗ and records (mi, l1,i) in T1 and returns l1,i to R. (ii)
WhenR asks a query on F2 oracle with inputting (mi, g), C searches (mi, g) in table T2 that is empty initially. If there exists a tuple (mi, g, l2,i) in T2, C returns l2,i to R as the value of F2(mi,g). Otherwise, C selects randomly l2,i∈Zq∗ and records (mi, g, l2,i) in T2 and returns l2,i to R. (iii)
WhenR asks a query on F3 oracle with inputting (K1,i, K2,i, K3,i, Mi, M1,i, mi), C searches (K1,i, K2,i, K3,i, Mi, ∗, mi) in table T3 that is empty initially. If there exists a tuple (K1,i, K2,i, K3,i, Mi, ∗, mi, l3,i) in T3, C returns l3,i to R as the value of F2(K1,i, K2,i, K3,i, Mi, M1,i, mi). Otherwise, C selects randomly l3,i∈Zq∗ and records (K1,i, K2,i, K3,i, Mi, M1,i, mi, l3,i) in T3 and returns l3,i to R.
Signing Query (i)
WhenR asks a signature query with inputting mi, C searches mi in table T4 that is empty initially. If there exists a tuple (mi, k2,i, k3,i, hi, ri, Mi, ⊥) in T4, C returns (k2,i, k3,i, hi, ri, Mi) to R as the signature on message mi. Otherwise, C searches T1 on mi and T2 on (mi, g). If mi and (mi, g) have not existed in T1 and T2, then C performs the above F1 oracle and F2 oracle to obtain l1,i and l2,i. Then,C chooses randomly ri, k2,i, k3,i, l3,i∈Zq∗, and Mi∈Zp∗. Compute(8)K1,i=Ta,1riMi-l3,i+k2,imodpK2,i=griTs,1l1,iTs,2l2,i-l3,i+k2,imodpK3,i=gk2,iTv,1k3,imodp and setF3(K1,i,K2,i,K3,i,Mi,⊥,mi) = l3,i. If there exists a tuple (K1,i, K2,i, K3,i, Mi, M1,i, mi, l3,i′) in T3 and l3,i′≠l3,i, then C fails and aborts. Otherwise, C records (mi, k2,i, k3,i, hi, ri, Mi) in T4 and returns (k2,i, k3,i, hi, ri, Mi) to R. And record (K1,i, K2,i, K3,i, Mi, ⊥, mi, l3,i) in T3. The probability of failure for C is qF3qs/q.
Verifying Query (i)
WhenR asks a signature verification query with σ = (k2,i, k3,i, hi, ri, Mi) on the message mi, C searches (k2,i, k3,i, hi, ri, Mi) in table T4. If there exists a tuple (mi, k2,i, k3,i, hi, ri, Mi) in T4, C returns “true.” Otherwise, C computes(9)K1,i=Ta,1riM-hi+k2,imodpK2,i=griTs,1F1miTs,2F2mi,g-hi+k2,imodpK3,i=gk2,iTv,1k3,imodp. ThenC searches (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) in T3. If (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) exits in T3, then C returns false. Otherwise, (K1,i, K2,i, K3,i, Mi, ∗, mi, hi) has not existed in T3; then C outputs “false” and aborts. The probability which σ = (k2,i, k3,i, hi, ri, Mi) is a valid signature and did not make a F3 query is 1/q.
Forge. Finally, R outputs a forged signature σ∗ = (k2∗, k3∗, h∗, r∗, M∗) on a message m∗. After C gets σ∗, C first computes(10)K1∗=Ta,1r∗M-h∗+k2∗modpK2∗=gr∗Ts,1F1m∗Ts,2F2m∗,g-h∗+k2∗modpK3∗=gk2∗Tv,1k3∗modp.Then, C searches (K1∗, K2∗, K3∗, M∗, m∗, h∗) in T3. Because σ∗ is a valid signature, R must query F3 on (K1∗, K2∗, K3∗, M∗, M1∗, m∗, h∗) previously. Thus, C can get M1∗ = Tv,1ts,1 mod p = gyλ3xλ1 mod p. So, gxy mod p = M1∗(λ1λ3)-1 mod p. The probability which σ∗ = (k2∗, k3∗, h∗, r∗, M∗) is a valid signature and did not make a F3 query previously is 1/q.Theorem 2.
The proposed SDVSUP-1 scheme is computationally nontransferable.Proof.
The designated verifierV can simulate a valid signature σ′ on the message m by the following SimSDV algorithm. V chooses randomly x1,x2,r∈Zq∗, and M∈Zp∗. Then compute(11)K1=Ta,1rM-x1modpK2=grTs,1F1mTs,2F2m,g-x1modpK3=gx2modpM1=Ts,1tv,1modp.h=F3K1,K2,K3,M,M1,mk2=x1-hmodqk3=x2-k2tv,1-1modq.The simulating signature of V is σ′ = (k2,k3,h,r,M). Since we need the private key of S or V to verify Ts,1tv,1 and need the private key of S or A to verify M, anyone cannot distinguish the original signature σ and the simulating signature σ′ without knowing the private keys of S, V, and A.Theorem 3.
The proposed SDVSUP-1 scheme is undeniable.Proof.
When the signerS and the designated verifier V dispute who generates the signature σ on the message m, S or V submits the signature σ = (k2, k3, h, r, M) on m to the arbiter A. Then, A runs the following ArbSDV algorithm. Namely, compute(12)M′=Ts,1ta,1F1mTs,2ta,1F2m,gmodp.Then, A checks if M = M′. If it is true, then A confirms that the signature σ on the message m is generated by the signer S. Otherwise, the signature σ is generated by the designated verifier V. Since M is a random number in simulating signature ϵ′ while M = Ta,1F1(m)ts,1+F2(m,g)ts,2modp in the real signature ϵ. Therefore, the arbiter A can use the ArbSDV algorithm to tell the real signer.


## 3.4. The Proposed SDVSUP-2 Scheme

The above SDVSUP-1 scheme is a strong designated verifier signature scheme which has the undeniable property. In the SDVSUP-1 scheme, the arbiterA judges the signature generator by checking the format of M in the signature σ = (k2, k3, h, r, M) on m because only M from the signer S has the format Ta,1F(m)ts,1+F(m∥g)ts,2, while M from the designated verifier V is a random number in Zp∗.Because of this fact “onlyM from the signer S has the special format, namely, Ta,1F(m)ts,1+F(m∥g)ts,2, while M from the designated verifier V is a random number in Zp∗.” Thus, the arbiterA only can check the format of M with the public key (Ts,1, Ts,2) of the signer to judge the result, which is a little unfair to the designated verifier V. In other words, the designed verifier can do nothing and it even has some doubts on the judge result. Therefore, in this subsection, we present another scheme where S and V can both construct M with their own characteristic respectively. Namely, in our SDVSUP-2 scheme, M generated by the signer S is the format M = Ta,1F1(m)ts,1+F2(m,g)ts,2, while M generated by the designated verifier V is the format M = Ta,1F1(m)tv,1+F2(m,g)tv,2. Thus, the arbiter A can check the format of M with the public key (Ts,1, Ts,2) of the signer (by computing M = (Ts,1F1(m)Ts,2F2(m,g))ta,1) or with the public key (Tv,1, Tv,2) of the designated verifier (by computing M = (Tv,1F1(m)Tv,2F2(m,g))ta,1) to judge the result, which make the arbiter A distinguish the signature easier, fairer, and more convenient. Next, we show the construction of our SDVSUP-2 scheme which is a modification of SDVSUP-1 scheme.SetSDV. The algorithm works as the above SDVSUP-1 scheme except F3: (Zq∗)4×{0,1}∗→Zq∗. Finally, the system parameters are L = (p, q, g, F1, F2, F3).KeySDV. The algorithm works as the SDVSUP-1 scheme. Finally, S, V, and A obtain their private keys and public keys ((ts,1, ts,2), (Ts,1, Ts,2)), ((tv,1, tv,2), (Tv,1, Tv,2)), ((ta,1, ta,2), and (Ta,1, Ta,2)), respectively.SigSDV. S chooses randomly t2,r2∈Zq∗ and computes(13)K1=Ts,1F1mTs,2F2m,gt2Tv,1F1mTv,2F2m,gr2modpK2=Ta,1F1mts,1+F2m,gts,2r2+t2modpM=Ta,1F1mts,1+F2m,gts,2modpM1=Tv,1ts,1modph=F3K1,K2,M,M1,mr1=t2+hF1mts,1+F2m,gts,2-1modq.The final signature on the message m is σ = (r1, r2, h, M).VerSDV. For a signature σ = (r1, r2, h, M) on the message m, V computes(14)K1′=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modpK2′=Ta,1-hMr1+r2modpM1=Ts,1tv,1modph′=F3K1′,K2′,M,M1,m.If h = h′, then V accepts the signature or rejects it.Note that if we drop the inputtingM1 in the F3() of the above SDVSUP-2 scheme, namely, h = F3(K1,K2,M,m), then the SDVSUP-2 scheme can become a designated verifier signature not a strong scheme (namely, designated verifier signature with undeniability property (DVSUP), we call it DVSUP-2 scheme) because anyone can check the validity of the signature σ generated by DVSUP-2 scheme. Similarly, the SDVSUP-1 scheme also can become a designated verifier scheme (we call it DVSUP-1 scheme) by dropping the M1, namely, h = F3(K1,K2,K3,M,m).


## 3.5. Correctness of SDVSUP-2 Scheme

The above signatureσ generated by S of SDVSUP-2 scheme is correct because(15)g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gt2+hF1mts,1+F2m,gts,2-1·Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gt2ghTv,1F1mTv,2F2m,gr2modp=Ts,1F1mTs,2F2m,gt2Tv,1F1mTv,2F2m,gr2modp.Ta,1-hMr1+r2modp=Ta,1-hMt2+hF1mts,1+F2m,gts,2-1+r2modp=Ta,1-hTa,1F1mts,1+F2m,gts,2t2+r2·Ta,1F1mts,1+F2m,gts,2hF1mts,1+F2m,gts,2-1modp=Ta,1-hTa,1F1mts,1+F2m,gts,2t2+r2Ta,1hmodp=Ta,1F1mts,1+F2m,gts,2t2+r2modp.The above signature σ simulated by V of SDVSUP-2 scheme is correct because(16)g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gr2modp=g-hTs,1F1mTs,2F2m,gr1·Tv,1F1mTv,2F2m,gt2+hF1mtv,1+F2m,gtv,2-1modp=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2·Tv,1F1mTv,2F2m,ghF1mtv,1+F2m,gtv,2-1modp=g-hTs,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2ghmodp=Ts,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2modp.Ta,1-hMr1+r2modp=Ta,1-hMr1+t2+hF1mtv,1+F2m,gtv,2-1modp=Ta,1-hTa,1F1mtv,1+F2m,gtv,2r1+t2·Ta,1F1mtv,1+F2m,gtv,2hF1mtv,1+F2m,gtv,2-1modp=Ta,1-hTa,1F1mtv,1+F2m,gtv,2r1+t2Ta,1hmodp=Ta,1F1mtv,1+F2m,gtv,2r1+t2modp.Theorem 4.
The proposed SDVSUP-2 scheme is computationally nontransferable.Proof.
In order to simulate a valid signature on the messagem, the designated verifier V chooses randomly t2,r1∈Zq∗ and computes(17)K1=Ts,1F1mTs,2F2m,gr1Tv,1F1mTv,2F2m,gt2modpK2=Ta,1F1mtv,1+F2m,gtv,2r1+t2modpM=Ta,1F1mtv,1+F2m,gtv,2modpM1=Ts,1tv,1modph=F3K1,K2,M,M1,mr2=t2+hF1mtv,1+F2m,gtv,2-1modq.The final simulating signature on the message m is σ′ = (r1, r2, h, M). Since we need the private key of S or V to verify Ts,1tv,1 and need the private key of S or A to verify M, anyone cannot distinguish the original signature σ and the simulating signature σ′ without knowing the private keys of S, V, and A.Theorem 5.
The proposed SDVSUP-2 scheme is undeniable.Proof.
The arbiterA adapts the following method to judge the signature. A first gets the public keys of the signer and the designated verifier. Then, A uses the private ta,1 to compute(18)M′=Ts,1F1mTs,2F2m,gta,1modpM′′=Tv,1F1mTv,2F2m,gta,1modp.Then, A checks if M = M′ or M = M′′. If M = M′, then A confirms the signature σ on the message m is generated by the signer S. If M = M′′, then the signature σ is generated by the designated verifier V. Since M = Ta,1F1(m)tv,1+F2(m,g)tv,2modp in the simulating signature ϵ′, M = Ta,1F1(m)ts,1+F2(m,g)ts,2modp in the real signature ϵ. Therefore, the arbiter A can use the ArbSDV algorithm to tell the real signer.Theorem 6.
If the CDH assumption (tcdh, ϵcdh) holds, then the proposed SDVSUP-2 scheme is (tsdv1, qf1, qf2, qf3, qs, qv, ϵsdv1) unforgeable.Proof.
The proof method is very similar to the Theorem1. So, we omit it.


## 3.6. Comparison

In Tables1 and 2, we compare our schemes with other similar schemes in terms of performance and security features. “Computational cost” denotes the totally computational cost of signing and verifying. “Signature length” denotes the signature size. “Unforg.” denotes if the scheme satisfies the unforgeability property. “Nontransf.” denotes if the scheme holds the nontransferability property. “Unden.” denotes if the scheme holds the undeniability property. “Help from signer” denotes if it needs the help from the signer when the arbiter judges a signature’s generator. “E” denotes one exponentiation computation in Zp∗. “GE” denotes one exponentiation computation in G where G is a bilinear group. “P” denotes one paring computation in G. “Zq”, “Zp,” and “G” denote the length of one element from “Zq”, “Zp,” and “G,” respectively.Table 1
Performance comparison with other schemes.
Scheme Computational cost Signature length Jakobsson et al. [8] 11E 3 Z q + 3 Z p Yang et al. [10] 9E 4 Z q Tian et al. [11] 11GE + 2P 1 Z q + 4 G Islam and Biswas [12] 6GE + 4P 1 Z q + 2 G SDVSUP-1 14E 4 Z q + 1 Z p SDVSUP-2 15E 3 Z q + 1 Z pTable 2
Security features comparison with other schemes.
Scheme Unforg. Non-transf. Unden. Help from signer Jakobsson et al. [8] √ √ × √ Yang et al. [10] √ × √ √ Tian et al. [11] √ √ × × Islam and Biswas [12] √ √ × × SDVSUP-1 √ √ √ × SDVSUP-2 √ √ √ ×From Table2, it can be seen that our schemes including SDVSUP-1 and SDVSUP-2 not only hold the features of unforgeability and nontransferability but also have the undeniability property. What is more, the arbiter can alone judge the generator in our two schemes, while any other schemes do not have the property. Therefore, our two schemes have better security features. In terms of signature size, from Table 1, it can be seen that our schemes outperform the schemes in [8, 11] and also are comparable with the schemes in [10, 12]. In terms of computational cost, our schemes can perform many recomputations on some operations such as Ts,1tv,1. Therefore, our schemes also have comparable computational complexity as other schemes [8, 10–12].


## 3.7. Applications

SDVS has many applications such as electronic voting (e-voting) system, bidding system in business, and electronic will. Next, we demonstrate an example on how to apply our SDVSUP scheme to the bidding system in business.We assume thatBi is a bidder on behalf of a company to make a project compete with other bidders, V is the tenderee on behalf of the enterprise to choose the most suitable company for performing the project. J is a trust third party to perform judging. Then, the bidding system consists of the following components.Initialization Phase. Generate the system parameter L according to the SetSDV. Bi, V, and J obtain the public/private keys ((TBi,1, TBi,2), (tBi,1, tBi,2)), ((TV,1, TV,2), (tV,1, tV,2)), ((TJ,1, TJ,2), and (tJ,1, tJ,2)), respectively, according to the KeySDV. V publishes the notice on the project for bidding.Bidding Phase. The company Bi who wants to perform the project prepares the biding document mi and signs on mi with the private (tBi,1, tBi,2) to obtain the signature σi according to the SigSDV. Then Bi sends σi to V.Choosing Phase. V verifies the validity of σi for all receiving biding documents. Then V chooses the most suitable bidder as the winner according to the price or other reasons presented in biding document.Note. In order to obtain lowest price, V maybe show the bidding document of Bi to Bj. Thus, Bj must set lower price than Bi to obtain the project. By the similar method, V can show the bidding document of Bj to Bk who is forced to set lower price than Bj and so on, which causes a vicious cycle. An SDVS scheme can solve this problem since the V also can generate a valid signature on mi which is indistinguishable from the original signature generated by Bi. However, if Bi and V dispute the signature σi on mi or both deny the signature, then the ordinary SDVS scheme cannot solve the judge problem. But there is no such problem in our SDVSUP schemes.Judging Phase. Given a signature σi on mi, the judger J determines the signature by computing M′ = (TBi,1F1(mi)TBi,2F2(mi,g))tJ,1modp and M′′ = (TV,1F1(mi)TV,2F2(mi,g))tJ,1modp. If M = M′, then σi is generated by the Bi. If M = M′′, then σi is generated by the V.Using the similar method to the above, our SDVSUP can be applied in electronic voting (e-voting) system, electronic will, and so on.


## 4. Conclusion

In this paper, we propose two strong designated verifier signature schemes including SDVSUP-1 and SDVSUP-2. Our two SDVS schemes achieve the unforgeability property, the undeniability property, and the nontransferability property. Specially, our SDVS schemes can solve the dispute of the signature ownership between the signer and the designated verifier by introducing a third party as the arbiter. The whole procedure of judgment removes the dependence on the signer and can be completed by the arbiter alone. We also present an instance on how to apply our SDVS schemes in a real situation.



---

*Source: 7921782-2017-01-24.xml*