13 4 5 6 7 8 1 0 11 12 13 14 15 16 17 18 19 Authentication encryption scheme 20 Security proof 21 Message recovery 22 2 3 24 25 26 27 28 29 30 31 32 33large message, which is secure against the message block being reordered, replicated or 34 35 36 37 38 39 40 tion o 41 me an 42 l sign 43 ole in 44 posed 45 ich sm 46 47 48 49 50 51 encryption schemes [4,2,12,13,15,7,14] have been proposed. 52 cure and a 53 cation enc 54 scheme should satisfy the following security properties. 55 (1) Confidentiality: it is computationally infeasible for an adaptive adversary to obtain any secret information 56 ciphertext. http://dx.doi.org/10.1016/j.ins.2015.04.036 0020-0255/ 2015 Published by Elsevier Inc. ⇑ Corresponding author. Tel./fax: +86 10 88803275.

E-mail address: jhzhangs@163.com (J. Zhang).

Information Sciences xxx (2015) xxx–xxx

Contents lists available at ScienceDirect

Information Sciences

INS 11537 No. of Pages 6, Model 3G 25 April 2015An authentication encryption scheme is a message transmission protocol, which sends messages in a se tic way. In other words, it can achieve authentication and encryption in a logic step. Usually, an authentiPlease cite this article in press as: J. Zhang et al., A novel authenticated encryption scheme and its extension, Inform. Sci. (2015) dx.doi.org/10.1016/j.ins.2015.04.036uthenryption from aand identifier are signed in certified email services and time stamping services. Subsequently, Horster et al. [6] proposed an authentication encryption scheme that is modification of Nyberg–Rueppels scheme. In an authentication encryption scheme, the signer may generate the signature on a message and send it to a specified receiver, and only the specified receiver can recover and verify the message. Therefore, an authentication encryption scheme can be regarded as the combination of a data encryption scheme and a digital signature scheme and raise efficiency of communication. Many authenticated1. Introduction

With the rapid-increasing popula insecure channel. Hence, it has beca transmitted message. Because digita employed and plays an important r storage, Nyberg and Rueppel [3] pro is useful for many applications in whpartially deleted during transmission. 2015 Published by Elsevier Inc. f Internet, people tend to communicate with each other through the common but important issue about how to prove the source and confirm the integrity of the ature can provide integrity, non- repudiation and authentication of data, it is often electronic commerce. To adapt to the demand of a limited bandwidth and low a new signature scheme: digital signature scheme with message recovery, which all messages should be signed. For example, small messages including time, dateA novel authenticated encryption scheme and its extension

Jianhong Zhang ⇑, Xubing Zhao, Cheng Ji

College of Sciences, North China University of Technology, Beijing 100144, China a r t i c l e i n f o

Article history:

Received 12 November 2006

Received in revised form 14 April 2015

Accepted 17 April 2015

Available online xxxx

Keywords:

Digital signature

Random oracle a b s t r a c t

An authenticated encryption scheme is a message transmission scheme, which can send a message in a secure and authentic way, and allows the specified recipient to simultaneously recover and verify the validity of a message. In the large message transmission, traditional authenticated encryption schemes have the disadvantages that communication overheads and the computation costs are too high. In this work, we propose a secure authentication encryption scheme and show that the scheme is secure in the random oracle model. In comparison with Lv et al.’s scheme and Li et al.’s scheme, our proposed scheme is the most efficient one in terms of computation complexity and communication cost. Finally, we extend our proposed scheme to adapt to the authenticated encryption for a journal homepage: www.elsevier .com/locate / ins, http:// 57 58 59 60 61 62 63 64 65 66 67 68 an efficient authentication encryption scheme with message linkage for message flow, which link up the message blocks to 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 Lemma 1 (the Forking Lemma [10]). Let ðG;R;VÞ be a generic digital signature scheme with security parameter k. Let A be a 87 Probabilistic Polynomial Time Turing machine, given only the public data as input. If A can find a valid signature ðm; r;h; dÞ with 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 2 J. Zhang et al. / Information Sciences xxx (2015) xxx–xxx

INS 11537 No. of Pages 6, Model 3G 25 April 2015non-negligible probability, then, with non-negligible probability, a replay of this machine, with the same random tape and a different oracle, outputs two valid signatures ðm; r;h; dÞ and ðm; r;h; d0Þ such that h– h in excepted time.

Definition 1. The Authenticated Encryption Scheme with Message Linkage is defined as follows: System parameters generation: on input a security parameter k, outputs the common system parameters SP. Key generation: on input the common system parameters SP, outputs a secret/public key pair ðsk; pkÞ for each user. Authenticated encryption algorithm: on input the key pair (sks; pks) of the signer, message m and the public key pkv of the recipient, outputs an authenticated encryption signature d. Decryption and verification algorithm: first the recipient recovers the message m by his private key skv, then on input the key pair ðskv ; pkvÞ of the recipient, the public key pks of the signer, and an authenticated encryption signature, outputs a verification decision b 2 f0;1g. If b ¼ 1, the verifier accepts the signature, otherwise, rejects it.

Definition 2. An authenticated encryption scheme with message linkage is said to secure against an existential forgery for adaptive chosen message attack if no polynomial bounded adversary A win the following game with a non-negligible advantage. (1) The challenger C runs the System Parameter Generation algorithm with a security parameter k and sends the system parameters SP to the adversary A. (2) The Designated recipient V runs the Key Generation algorithm to generate his key pair ðpkV ; skVÞ and publishes pkV.