A Secure Non-Interactive Deniable Authentication Protocol with Strong Deniability Based on Discrete Logarithm Problem and its Application on Internet Voting Protocol

INTRODUCTION

With the development of internet technology many transactions can be processed through internet. Own to that the parties involved in the transactions communicate through the internet they are not face to face. At this scenario how to authenticate their identifications is a key questions. So, many authentication protocols are introduced. The authentication protocol which generally uses the cryptographic technologies can be used to authenticate identification of communicated parties.

But let’s consider the following two special scenarios:

Scenario 1 (Deng et al., 2001): In electronic commerce through internet a customer wants to order an goods from a merchant, the customer should give an order to the merchant and create an authenticator for the order owning to that the merchant must be sure that this order really comes from the intended customer. At the same time, the merchant wants to be able to prevent the customer from showing this order to another party in order to elicit a better deal. At this scenario, we need a protocol that enables a receiver to verify the source of a given message, but prevents a third party from knowing the sender’s identity.

In scenario 1, the customer and merchant need a deniable authentication protocol to satisfy this requirement. Deniable authentication protocols allow a sender to authenticate a message for a receiver, in a way that the receiver can’t convince a third party that such authentication (or any authentication) ever took place. Deniable authentication has two characteristics that differ from traditional authentication:

Scenario 2 (Raimondo and Gennaro, 2005): Alice and Bob are involved in some illegal transaction, such as drug, Alice wants to make sure that her communications to Bob cannot be later linked to her, so she uses deniable authentication. Bob thinks that such communication is indeed deniable, stores all the messages in his hard disk. Later the transaction is opened by the police. At the same time Bob’s computer is seized. Alice is forced to produces some piece of secret information, for example, her secret key, that indeed shows that the transcripts in Bob’s hard disk are actually authentic and not simulations. Bob ends up in jail.

In the second scenario the privacy of sender is need to consider. That is the strong and weak deniability proposed by Raimondo and Gennaro (2005).

So, a secure and practical deniable authentication protocol should have the following properties:

These properties are very useful for providing secure transactions over the internet.

In the past several non-interactive deniable authentication protocols have been proposed (Shao, 2004; Lee et al., 2007; Lu and Cao, 2005a, b; Qian et al., 2005; Shi and Li, 2005). To our knowledge these non-interactive deniable authentication protocols have not strong deniability.

The main contributions of this paper are summarized as follows:

In the past, the deniable authentication protocol has been studied. The deniable authentication protocol can be fall into two categories: interactive deniable authentication protocol (Deng et al., 2001; Raimondo and Gennaro, 2005; Han et al., 2004; Dwork et al., 1998; Aumann and Rabin, 1998; Fan et al., 2002; Feng and Ma, 2007) and non-interactive deniable authentication protocol (Shao, 2004; Lee et al., 2007; Lu and Cao, 2005a, b; Qian et al., 2005; Shi and Li, 2005).

Dwork et al. (1998) proposed an interactive deniable authentication protocol based on the concurrent zero-knowledge proof. Aumann and Rabin (1998) proposed an interactive deniable authentication protocol based on factoring problem. Deng et al. (2001) proposed two interactive deniable authentication protocols based on factoring and the discrete logarithm problem, respectively. Zhu et al. (2006) analyzed the security of Deng et al. (2001) and Aumann and Rabin (1998) and point out they are vulnerability to the person-in-the-middle attack. Fan et al. (2002) proposed another simple interactive deniable authentication protocol based on the Diffie-Hellman key distribution protocol. Han et al. (2004) proposed an interactive deniable authentication protocol resisting man-in-the-middle attack based on Diffie-Hellman key exchange protocol. Feng and Ma (2007) proposed a concurrent deniable authentication based on witness indistinguish-able which can support strong deniability.

The interactive deniable authentication protocols are inefficient. Hence several non-interactive deniable authentication protocols are proposed. Fan et al. (2002) proposed a non-interactive deniable authentication protocol based on Diffie-Hellman algorithm. Shao, 2004 pointed out there are three weakness in study (Fan et al., 2002) and give an improved a generalized ElGamal signature scheme. Lu and Cao (2005a, b) proposed a non-interactive deniable authentication protocol based on bilinear pairings and factoring, respectively. Lee et al., 2007 point that protocols (Shao, 2004; Lu and Cao, 2005a, b) can not protect against compromising session secret attack and introduce a new deniable authentication protocol using generalized El-Gamal signature scheme. Qian et al. (2005) proposed a generic method to construct efficient deniable authentication protocols based RSA trapdoor permutations,which has security against of impersonated attack, completeness and weak deniability. Shi and Li (2005) proposed non-interactive deniable authentication protocol a secure signature scheme which is correctness, security of impersonate attacks and deniability. According to present analysis, these non-interactive deniable authentication protocols have not strong deniability.

In this study, firstly the properties of deniable authentication protocol and the status in deniable authentication protocol are discussed and then a secure non-interactive deniable authentication protocol based on discrete logarithm problem to support completeness, strong deniability, weak deniability, security of forgery attack, security of impersonate attack, security of compromising session secret attack, security of man-in-the-middle attack is developed. We also prove that the proposed protocol have these secure properties. The security properties of the (Shao, 2004; Shi and Lee, 2005; Qian et al., 2005; Lee et al., 2007; Lu and Cao, 2005a, b) protocols and present proposed protocol are compared. In the last, an internet voting protocol with receipt-freeness without strong physical assumption based on our proposed deniable authentication protocol is proposed.

THE PROPOSED PROTOCOL

It is supposed that the attacker can’t monitor the communication between the sender and receiver in the non-interactive deniable authentication protocol. The proposed protocol (Fig. 1) consists of authority, the sender and the receiver. The proposed non-interactive deniable authentication protocol is described as the following:

Initialized phrase: The Authority performs the following steps:

Fig. 1:	The proposed protocol

The sender performs the following steps:

•	Pick a serial random numbers
•	Compute his public key by:
•	Send the to the bullet board
	The receiver performs the following steps:
•	Pick a random numbers
•	Compute his public key by:
•	Send the RPU to the bullet board

When finishing the initialized phrase the sender has serial public and private keys , at the same time receiver has his public and private keys .

Hash (m) is a collision-free hash function with an input of m and output of q bits:q = Hash (m).

Execution of protocol phrase: M is the message sent to the receiver.

The sender computes:

•	Choose randomly a public and private key . the private and public keys of each run of the propose protocol are different.
•	Compute:

and forget after a certain time

•	Send to the receiver

The receiver compute:

•
•	Verify the , if the result is true, the receiver accepts it. Otherwise the receiver rejects it

The following proof demonstrates that k’ = k

Proof 1:

Thus the receiver can derive the session secret key generated by the sender.

PROOFS OF SECURITY

Here, we will show that the proposed protocol has properties introduced earlier: completeness, strong deniability, weak deniability, security of forgery attack, security of impersonate attack, security of compromising session secret attack and security of man-in-the-middle attack.

Property 1: Completeness or authentication: If the sender and the receiver follow the protocol, the receiver is always able to identify the source of the message.

Proof: According to the protocol if the sender and receiver are honest, they execute the protocol strictly. The receiver can authenticate the source of the message. According to the protocol the sender sends to the receiver. After the receiver receives he can compute with , m and his private key R_PR. So, he can get the k according to the proof 1, which means that the receiver can get the k, which is generated with the equation k = (R_PU)^δ modp and sent to the receiver, with the equation . Thus the receiver can verify the and get the positive result: the source message is sent by the sender who has the public key .

Property 2: Weak deniability: The proposed protocol is deniable. The receiver can prove to have spoken to the sender but not the content of what the sender authenticated in a way that the receiver cannot convince a third party that such authentication.

Fig. 2:	Generate fake message

Proof: After receiving , the receiver can authenticate the source of the message m which being sent by the sender with his private key R_PR. But the receiver cannot prove the source of m to a third party for the following reasons.

According to the protocol the receiver has the ability to generate many fake messages which can be authenticate with the equation and m’ because the receiver has know his private key R_PR (Fig. 2). The third party can verify the fake with the k’ and m’ according to the protocol. So, the third party ca not assure that the m’ is sent by the sender Hence the proposed protocol has the weak deniability.

Property 3: Strong deniability: After the execution of the protocol the sender can deny to have ever authenticated anything to receiver.

Proof: The sender’s public key on the bullet board is available at the time of execution of the protocol by anyone. So, the receiver can get the public key of sender. After the execution of the protocol the sender forgets his public and private key . According to the protocol in order to prove that is sent by the sender, the judge must force the sender to provide the transcript of . Because the sender forgets his private key he can not provide the transcript of . At the same time anyone can not get the sender’s private key from his public key because that is a hard problem in cryptography. So, the sender can deny to have ever authenticated anything to receiver.

Property 4: Security of forgery attack: When an attacker wants to forge the valid deniable authentication information and then send it to the intended receiver, the proposed protocol can protocol against the forgery attack.

Proof: The attacker want to launch a forgery attack, firstly he must forge valid deniable authentication information: . According to the equations: and the attacker must know the δ. According to the equation: , the attacker must know the private key of sender . So, the attacker must get the from the public key of sender . But that is impossible because it is a hard problem. So no one can forge δ without knowing the sender’s private key . Consequently the proposed protocol can protect against the forgery attack.

Property 5: Security of impersonate attacks: The protocol can protect against impersonate attacks if an attacker wants to impersonate the intended receiver in order to identify the source of a given message.

Proof: An attacker can obtain the message from the deniable authentication information sent by the sender. When the attacker wants to impersonate the intended receiver to verify the message that is sent by the sender, he must derive the session secret from equation first. However, it is impossible for the attacker to accomplish this without knowing the receiver’s private key R_PR. Therefore, the proposed protocol can be secure against an impersonation attack.

Property 6: Security of compromising session secret: A compromised session secret does not affect the security of the proposed deniable authentication protocol.

Proof: The session secret can be derived from if an attacker wants to forge the deniable information with the forged message M by using the compromised session secret k’, the receiver will derive a different session secret from the forged information. This is because the message and its corresponding session secret are interdependent. Owning to that is different each round, the session secret for each round must be independent. Thereby, a compromised session secret does not affect the security of other sessions.

Property 7: Security of man-in-the-middle attack: A authentication protocol is secure against a man-in-the-middle attack, if man-in-the-middle attack can not establish any session key with either the sender or the receiver.

Proof: According to the proposed protocol, if the attacker can establish any session key k = (R_PU)^δ modp, he must know . But that is impossible because the attacker can not get the sender’s private key and the receiver’s private key from its public key, respectively. That is a hard problem. So, the attacker can not pretend to be the sender and the receiver. Hence the proposed protocol is security against man-in-the-middle attack.

APPLICATION ON INTERNET VOTING PROTOCOL

With the progress of society and development of democracy of nation, the needs of the voting are more and more intense. Owning to the popularity of internet and many transactions are processed through internet, the people have the higher requirements of internet voting. The internet voting protocols is the base of the internet voting system.

The internet voting protocols can be categorized by different technologies into three classes. homomorphic cryptosystem, blind signature, mix net-based protocols.

The secure and practical internet voting protocols should have the following properties:

A lot of protocols use ad hoc physical assumption or the trusted third party to accomplish receipt-freeness. Papers (Juels and Jakobsson, 2002; Acquisti, 2004; Meng, 2007) are better in the implementation of the expanded properties. They don’t use strong physical assumption. Research on the coercion-resistance is at the beginning. It is firstly researched in papers (Juels and Jakobsson, 2002; Acquisti, 2004). They mainly applied the credential of voter and designated verifier proof to accomplish receipt-freeness and coercion-resistance.

Owning to the properties of non-interactive deniable authentication protocol we proposed a new internet voting protocol that applied the proposed protocol to implement receipt-freeness. At the same time the El-Gamal cryptosystem, mix net (Chaum, 1981) and proof of knowledge that two ciphertexts are encryption of the same plaintext (Baudron et al., 2001; Acquisti, 2004; Goulet and Zitelli, 2004) are used in the proposed internet voting protocol.

The proposed internet voting protocol with receipt-freeness based on the proposed deniable authentication protocol: The idea of the proposed internet voting protocol with receipt-freeness is that: if everyone knows that the voter has the ability that generates the fake evidence, when the voter provides the evidence to the vote-buyer, the voter-buyer has not the ability to verify the evidence, so the vote-buyer does not give the money to the voter. So, the proposed internet voting protocol has receipt-freeness.

Fig. 3:	Model of the proposed internet voting protocol

How to make the voter to have ability that generates the fake evidence? Owning to the strong deniability of the proposed non-interactive deniable authentication protocol we can use it to implement the ability.

In order to express the idea clearly and simplify the protocol we suppose there is only one authority in the proposed internet voting protocol. The proposed internet voting protocol includes four phases: preparation phase, registration phase, voting phase and tallying phase (Fig. 3).

In , m is the non-interactive proof of knowledge that E^C(c_j) and E^V(c_j) are encryption of the same c_j (Goulet and Zitelli, 2004), which is the credential of voter V_j produced by A for V_j.

The other notations can be found in study of Meng (2008).

Preparation phase: Authority and voters generate the public/private ElGamal keys. The private keys of voter and authorities are secret. At the same time they generate the public and private keys according to the proposed deniable authentication protocol.

Authorities generate the ballot B^t and send B^t and its digital signature to bulletin board denoted by BB.

Registration phase: First voter V_j registries to authority A. Then Authority A generates E^V(c_j) and . At last Authority A generates . Voter V_j receives and verifies it through the proposed deniable authentication protocol and the method in paper (Goulet and Zitelli, 2004). If it is true, voter V_j goes to vote. Registration phase is shown in Fig. 4.

Voting phase: Voting phase is shown in Fig. 5. Voter V_j choose his favorite ballot and generate E^V(B^t_j) and send E^V(c_j) randomly in BB.

Tallying phase: According to the rules the authorities tallies the ballot and publish its results.

The tallying algorithm can be found in study of Meng (2007).

Analysis of receipt-freeness: The proposed internet voting protocol accomplishes receipt-freeness by confidentiality of voter credential and the proposed deniable authentication protocol.

Voter checks equality between credential from authority and credential in BB by proof of knowledge that two ciphertexts are encryption of the same plaintext . The other people can not check owning to the specialty of the proposed deniable authentication protocol. According to the proposed deniable authentication protocol voter has the ability of generation of a fake . The vote buyer can not check and can not verify E^V(c_j). So, the vote buyers do not give the money to the voter. So, the protocol is receipt-freeness.

Fig. 4:	Registration phase

Fig. 5:	Voting phase