Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own public keys. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this article, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our result is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with a key-and-signature size independent of the number of signers without a restart during the signing process.

In a one-way secret key agreement (OW-SKA) protocol in source model, Alice and Bob have private samples of two correlated variables X and Y that are partially leaked to Eve through the variable Z, and use a single message from Alice to Bob to obtain a shared secret key. We propose an efficient secure OW-SKA when the sent message over the public channel can be tampered with by an active adversary. Our construction uses a specially designed hash function that is used for reconciliation, as well as detection of tampering. In detection of tampering the function is a Message Authentication Code (MAC) that maintains its security when the key is partially leaked. We prove the secrecy of the established key and robustness of the protocol, and discuss our results.

In this paper, a novel message authentication model using the same key over wiretap channel is proposed to achieveinformation-theoretic security. Specifically, in the proposed model, there is a discrete memoryless channelW1:X→Ybetween transmitter Alice and receiver Bob, while an attacker Oscar is connected with Alice via discrete memoryless channelW2:X→Z. Alice encodes messageMto codeword (S,Xn), using an encoding function with secret keyK. Then,Sis sent to Bob over a one-way noiseless channel (fully controlled by Oscar), andXnis sent over the wiretap channel, sayX→(Y,Z). Building on this model, a new message authentication scheme is proposed. The scheme incorporates a secure channel coding, which uses random coding techniques to detect man-in-the-middle (MITM) attacks. The authentication channel capacity is studied in a specific channel model whenW2is not less noisy thanW1. We theoretically demonstrate that the authentication channel capacity is much larger than the secrecy capacity, since Bob does not need to recover information transmitted over the noisy channel.

An approximate message authentication scheme is a primitive that allows a sender Alice to send a source state to a receiver Bob such that the latter is assured of its authenticity, where the source state is considered as authentic if it only undergoes a minor change. Here, the authors propose an efficient scheme for this problem and prove its security under a rigorous model. Our scheme only needs a lightweight computation cost and hence is very efficient. As the authentication message is transmitted over a noisy channel, we also value the channel efficiency (i.e. the coding rate). For a fixed coding method, this is determined by the admissible decoding bit error probability . A larger admits a shorter codeword length and hence a larger coding rate. It turns out that the can be set to be a significantly large constant (determined by the legal distortion level for the source state). Compared with existing schemes, the advantage in is evident.

We consider a message authentication with distortion (DMA), where Alice encodes a source state and sends it over an unknown channel to Bob, who then tries to recover it, up to a small distortion. We formulate a formal model for this problem and define the authentication rate for DMA as the number of source symbols transmitted for each channel use. We characterize the best possible authentication rate (called authentication capacity) for a general DMA. We also obtain a lower bound on the adversarial success probability for a typical class of DMA.

Provable security is an important research area in modern cryptography. Cryptographic primitives or protocols without rigorous proofs cannot be regarded as secure even in practice. In fact, many schemes were originally thought as secure but were broken subsequently. This clearly indicates the necessity of formal security analysis. For real-world applications, provable security provides us with a strong confidence in using cryptographic solutions. For a theoretical study, provable security sometimes provides a clear answer to the (in)feasibility issue of a certain security mechanism. This special issue offers a platform for security researchers and practitioners to exchange their new ideas for studying information systems in provably secure manners. We have included eighteen high-quality papers. Among them, six papers were selected from accepted papers at the 6th International Conference on Provable Security (ProvSec 2012), and the remaining 12 papers were selected from new invited submissions. All of them have gone through stringent reviews in two rounds. Further, any selected paper that has a preliminary version at ProvSec 2012 or somewhere else must have been extensively expanded to include new contributions. The included articles highlight recent advances in provable security by presenting many novel techniques in this area. We now give a short summary of them, through six categories. The first category is public-key encryption (PKE). It considers the formal models, constructions, and analysis of PKE under various security concerns. In the leakage-resiliency model, one considers the security of PKE when a partial secret key has been leaked (e.g., through a side-channel attack). Paper “continual key-leakage tolerant encryption from extensible-set delegation functionality” by Bo Yang and Mingwu Zhang proposes a leakage-resilient functional encryption and shows that its provable security under a continual leakage of the secret key. Motivated by the threat from malware such as RAM scrapers, the paper “stronger public key encryption system withstanding RAM scraper like attacks” by S. Sree Vivek, S. Sharmila Deva Selvi, Akshayaram Srinivasan and C. Pandu Rangan proposes a public-key security notion that is stronger than adaptive chosen-ciphertext (CCA2) security. They show that the traditionally CCA2 secure schemes are no longer secure in the new model. They also propose a new scheme that is provably secure in the new model without a random oracle. The paper “a limitation on security evaluation of cryptographic primitives with fixed keys” by Yutaka Kawai, Goichiro Hanaoka, Kazuo Ohta, and Noboru Kunihiro studies the security of public-key system when the public key is fixed. They have obtained some impossibility results for this setting. A key encapsulation mechanism is an efficient tool to construct a public-key encryption through a paradigm of a hybrid encryption. The paper “efficient key encapsulation mechanisms with tight security reductions to standard assumptions in the two security models” by Yoshikazu Hanatani, Goichiro Hanaoka, Takahiro Matsuda, and Takashi Yamakawa presents two constructions of efficient key encapsulation mechanisms. Their schemes can be proven CCA secure under a strong hardness assumption without random oracle or under a weaker assumption in the random oracle model. A hash proof system is a general cryptographic structure proposed by Cramer-Shoup in Eurotypt 2002 to construct public-key systems. The paper “generalized (identity-based) hash proof system and its applications” by Yu Chen, Zongyang Zhang, Dongdai Lin, and Zhenfu Cao generalizes this concept to admit an anonymity property. They use this generalized structure to propose public-key encryptions with leakage resilience and anonymity. They further study it in the identity-based setting. The second category is searchable encryption. It considers the public key or the symmetric key cryptosystems that allow keywords search over encrypted data. Usually, the search encryption requires a complete match on the keyword during the search. The paper “character-based symmetric searchable encryption and its implementation on mobile devices” by Takanori Suga, Takashi Nishide, and Kouichi Sakurai proposes a scheme that admits a partial keyword match for the search, and their scheme uses a symmetric encryption. They also have implemented the solution over a mobile device. The paper “searchable symmetric encryption capable of searching for an arbitrary string” by Yoshinao Uchide and Noboru Kunihiro further studies the partial keyword match problem and proposes a searchable encryption that admits a search query of an arbitrary string. Their main technique is an oblivious cross tag protocol by Cash et al. at CRYPTO 2013. The third category is a re-encryption. This considers to re-encrypt a ciphertext without using a decryption key. This is to reuse the ciphertext for a certain security or privacy purpose. The paper “strongly average-case secure obfuscation: achieving input privacy and circuit obscurity” by Mingwu Zhang, Yi Mu, Yixin Su, and Xinyi Huang studies the obfuscation for a re-encryption program with strong security such that an attacker, when executing an obfuscated re-encryption program, cannot obtain any information about the private key and the plaintext. Here, an obfuscation is an algorithm that converts a program into another with the same functionality while difficult to understand. An attribute-based encryption is a public-key cryptosystem that classifies a user using attributes such that a user can decrypt a ciphertext if and only if his attribute collection satisfies the desired requirement in the ciphertext. This achieves the access control functionality for the encryption. Attribute-based proxy re-encryption (PRE) is a useful technique for a delegation of access rights to encrypted data, which is useful in a public cloud storage. The paper “verifiable attribute-based proxy re-encryption for secure public cloud data sharing” by Suqing Lin, Rui Zhang, and Mingsheng Wang proposes a generic construction for attribute-based PRE and presents three realizations for it. The paper “on the application of generic CCA-secure transformations to proxy re-encryption” by David Nuñez, Isaac Agudo, and Javier Lopez studies the generic transformation for PRE from weak security to CCA security. For a regular public-key encryption, it is well known that a Fujisaki–Okamoto technique can transform a chosen-plaintext secure scheme into a CCA2 secure scheme. But the authors found out that this does not work for PRE. Instead, they achieve a weak form of CCA security for PRE using a generalized Fujisaki–Okamoto. The paper “proxy re-encryption via indistinguishability obfuscation” by Satsuya Ohata and Kanta Matsuura presents a technique for achieving PRE from obfuscation. Their idea is to carefully modify the public-key encryption scheme of Sahai and Waters at STOC 2014. The fourth category is a digital signature. This studies the models, constructions, and their analysis under various security concerns. A nominative signature is a signature that is generated by a signer A and a user B jointly. When the signature is to be verified by a user C, C will run a disavowal/confirmation protocol with B. The paper “one-move convertible nominative signature in the standard model” by Dennis Y. W. Liu and Duncan S. Wong proposes an efficient nominative signature that is provably secure in the standard model with a constant size of key for any party in the system. A ring signature is a signature, where a signer remains fully anonymous among a group of members (called a ring). The paper “non-interactive deniable ring signature without random oracles” by Shengke Zeng and Qinyi Li considers a variant of a ring signature, where the signer anonymity is conditional in the sense that a signer can confirm the authorship of the signature while a non-signer can disprove the authorship of a signature. They propose a new scheme for this model using the Boneh and Boyen signature and shows its security in the standard model. A blind signature is a special signature that allows one to obtain a signature on a message from a signature without leaking the message to the latter. This primitive has many applications in systems such as e-cash and e-voting schemes. The paper “a lattice based partially blind signature” by Haibo Tian, Fangguo Zhang, and Baodian Wei proposes the first latticed-based blind signature with partial blindness using the technique of Lyubashevsky from EUROCRYPT 2012 and the technique of Abe and Okamoto from CRYPTO 2000. The paper “generic transformations for existentially unforgeable signature schemes in the bounded leakage model” by Yuyu Wang and Keisuke Tanaka studies how to obtain strongly secure digital signatures. They propose two transformations that convert a regular weakly secure signature into a strongly secure signature in the bounded leakage model. The fifth category is a key exchange. A key exchange is a procedure that allows two or more parties to share a secret key securely. The paper “authenticated key exchange with entities from different settings and varied groups” by Yanfei Guo and Zhenfeng Zhang proposes several key exchange protocols with an initiator being identity based and the responder being certificate based. They consider the constructions with an identity-based system from a bilinear group and a prime residue group both. The last category is the symmetric key cryptography. It studies the cryptographic structure that does not use any public-key tool. A lightweight cryptographic primitive is such an example. It only incurs a very small computation cost. A lightweight primitive with provable security has a very important impact in the real world. The paper “two new message authentication codes based on APN functions and stream ciphers” by Teng Wu and Guang Gong proposes two lightweight message authentication codes and quantifies the insecurity upper bounds against a substitution attack. The paper “two-level security for message streams” by Mohsen Alimomeni and Reihaneh Safavi-Naini studies the information theoretic security of a private key encryption. They formalize a new model to quantify the security of many ciphertexts, where they require the message in the most recent ciphertext to be perfectly secure while messages in older ciphertexts have a lower level of security. They propose a non-trivial construction with provable security under their model. We would like to thank editor-in-chiefs Prof. Hsiao-Hwa Chen and Prof. Hamid R. Sharif for agreeing to this special issue and supporting us throughout the process. We also would like to thank all authors who submitted their papers to this special issue and reviewers who spent their precious time on the submissions and provided us with their insights that help us in an essential way to make the decisions.

In this paper, we study a group key agreement problem where a user is only aware of his neighbors while the connectivity graph is arbitrary. In our problem, there is no centralized initialization for users. A group key agreement with these features is very suitable for social networks. Under our setting, we construct two efficient protocols with passive security. We obtain lower bounds on the round complexity for this type of protocol, which demonstrates that our constructions are round efficient. Finally, we construct an actively secure protocol from a passively secure one.

Message Authentication Code (MAC) is a keyed function fKsuch that when Alice, who shares the secret K with Bob, sends fK(M) to the latter, Bob will be assured of the integrity and authenticity of M. Traditionally, it is assumed that the channel is noiseless. Unfortunately, Maurer showed that in this case an attacker can succeed with probability equation after authenticating ∓ messages, where H(K) is the entropy of K. In this paper, we consider the setting where the channel is noisy. Specifically, Alice and Bob are connected by a discrete memoryless channel (DMC) W1and a noiseless but insecure channel. In addition, there is a DMC W2between Alice and attacker Oscar. We regard the noisy channel as an expensive resource and define the authentication rate ρauthas the ratio of message length to the number n of channel W1uses. The security of this model depends on the channel coding for fK(M). A natural coding scheme is to use the secrecy capacity achieving code of Csiszár and Körner. Intuitively, this is also the optimal strategy. However, we propose a coding scheme that achieves a higher ρauth. Our crucial point is that under a secrecy capacity code, Bob can fully recover fK(M) while in our model this is not necessary as we only need to detect the existence of the modification. How to detect the malicious modification without recovering fK(M) is the main contribution of this work. We achieve this through random coding techniques.

We further study the keyless authentication problem in a noisy model in our previous work, where no secret setup is available for sender Alice and receiver Bob while there is discrete memoryless channel (DMC) W1 from Alice to Bob and a two-way noiseless but insecure channel between them. We propose a construction such that the message length over DMC W1 does not depend on the size of the source space. If the source space is S and the number of channel W1 uses is n, then our protocol only has a round complexity of log* |S| - log* n + 4. In addition, we show that the round complexity of any secure protocol in our model is lower bounded by log* |S| - log* n - 5. We also obtain a lower bound on the success probability when the message size on DMC W1 is given. Finally, we derive the capacity for a noninteractive authentication protocol under general DMCs, which extends the result under Binary Symmetric Channels in our previous work.

A message authentication code (MAC) is (t, ε) secure if an attacker cannot forge a valid message with probability better than ε after adaptively obtaining t valid messages. For a fixed key space K, it is important for an MAC to support a source space S as large as possible, because this implies a bandwidth saving in practice. Hence, we study the possible size of S in an MAC through |S| or equivalently (to our convenience) the ratio (log |S|/|K|) for a fixed K. Our novelty in the methodology is to regard the MAC function of a given source state as a partition mapping for K. Under this view, we obtain an upper bound on |S| for a (t, ε)-secure MAC. Then, by analyzing a randomized partition of K, we prove the existence of an approximately optimal (t, ε)-secure MAC (in the sense of a large |S|). Our ratio (log |S|/|K|) is much larger than the previous results, where the previous results usually considered only case t = 1 by proposing a good universal hashing. This method is hard to extend to the case of a general t as a universal hashing relates only two inputs, while the general case needs to relate t inputs. Finally, we construct a selectively (1, ε)-secure MAC, where an attacker fixes two source states in advance with one for his forgery and the other for his inquiry for a valid message. Our ratio (log |S|/|K|) in this construction is close to the upper bound of its kind and is significantly larger than our existential result above for case t = 1.

Motivated by perfect guessing security for private key encryption by Alimomeni and Safavi-Naini (ICITS 2012), we study the relations between various unconditional ε-security notions, including $\epsilon$-guess security, ε-min entropic security and ε-Shannon security. We characterize the relations between these security notions. Our results stem from the essential mathematical properties of the underlying measures (i.e. guessing probability, min entropy and Shannon mutual information). We also prove the lower bound on either key entropy or key size or key min entropy for these models. Our results show that the ε-security under these models has a large key size or (min) entropy and hence impossible to be efficient.

Conditionally anonymous ring signatures are a variant of ring signatures such that the anonymity is conditional: if a user is the true signer, then he can claim this through a confirmation protocol; if he is not the signer, he can prove this through a disavowal protocol. Hence, this can preserve the anonymity of a signer while reserving the right to trace it when necessary. The security of such a signature also requires that an innocent non-signer will not be framed as a signer. In this paper, we propose a new framework for this type of signature without random oracles. Our construction can be realized under general complexity assumptions and has a simple structure. In contrast, previous works are based on non-standard assumptions or proved secure in the random oracle model.

We study a keyless authentication problem in a new noisy model, where there is a discrete memoryless channel (DMC) W1from sender Alice to receiver Bob and a DMC W2from adversary Oscar to Bob. In addition, there is an insecure noiseless channel between Alice and Bob. Under this model, we characterize the condition under which an authentication from Alice to Bob is possible. We also construct a secure authentication protocol that has an authentication rate approaching infinity. Finally, we prove that the authentication capacity of a noninteractive authentication over binary symmetric channels is exactly 1. This is an interesting result as Shannon capacity of channel W1is strictly less than 1 while the noiseless channel is completely unreliable.

In this paper, we study the commitment over a discrete memoryless channel W : X → Y, where both a sender and a receiver are deterministic. We call it (δh, δb)-secure if it has a hiding error δhand binding error δb. For any c ∈ (0, log |X|) and any σ ∈ (0, c), we propose a framework for a message domain of size 2n(c-σ)such that any δh> minPX:H(X)=c(I(X; Y)/H(X) - c) with an exponentially (in n) small δbcan be achieved, where Y is the output of W with input X and n is the number of channel uses. We show that limc→0minPX:H(X)=c(I(X; Y)/H(X)) = 0 if and only if a very weak condition on W holds. Note that when limc→0minPX:H(X)=c(I(X; Y)/H(X)) = 0, we are guaranteed that our framework can commit to a message from a domain of size approximately 2ncfor small c with a nearly zero hiding error δhand an exponentially small binding error δb. The price for this is a small commitment rate. We obtain some impossibility results for (δb, δh). For the space M of the commitment input, we show that when |M| = O(1), then (z, o(1))-security is impossible for any zhb= 2-nαis impossible where γ = lim supn→∞(log |M|/n) and α > 0.

In a secure message transmission (SMT) scenario, a sender wants to send a message in a private and reliable way to a receiver. Sender and receiver are connected by n wires, t of which can be controlled by an adaptive adversary with unlimited computational resources. In Eurocrypt 2008, Garay and Ostrovsky considered an SMT scenario where sender and receiver have access to a public discussion channel and showed that secure and reliable communication is possible when n ≥ t + 1. In this paper, we will show that a secure protocol requires at least three rounds of communication and two rounds invocation of the public channel and hence give a complete answer to the open question raised by Garay and Ostrovsky. We also describe a round optimal protocol that has constant transmission rate over the public channel.

Secure message transmission assumes n channels between a sender and a receiver such that up to t channels are under the control of a computationally unlimited adversary. In secure message transmission by public discussion protocol, sender and receiver have access to a public authenticated channel. In this paper we show that if n ¿ t + 1, a secure protocol requires at least 3 rounds of communication and 2 rounds invocation of the public channel. This gives a complete answer to a question raised by Garay and Ostrovsky in Eurocrypt 2008. We also describe a round optimal protocol that has constant transmission rate over the public channel.

Abstract. A non-interactive conference key distribution system (or, a NICKDS for short) allows conference members to calculate a shared key without interacting with each other. NICKDSs have been studied in unconditional and computational settings. In both cases security has been evaluated against an adversary who can corrupt participants. In this paper we consider an adaptive adversary who can both corrupt participants and also access the keys of conference of his choice. We revisit security of a number of known NICKDSs in this new model and present characterizations and conditions that guarantee security of the system in the new model. We also give a generic construction for computationally secure (in the new model) NICKDSs, from unconditionally secure ones in corruption only model. To show the usefulness of the new security model, we consider two composition constructions. First, we compose a secure NICKDS with a secure MAC by using the key obtained from the NICKDS as the MAC key, and show that this results in a ring authentication that guarantees authenticity of the received message while the sender remains anonymous and this anonymity is unconditional. The security theorem for the composition guarantees security for unconditional and computational settings, both. We also consider composition of a NICKDS with a secure (CCA2 secure) encryption system and show this results in a broadcast encryption system (BES) that is CCA2 secure. This is the first CCA2 secure BES in symmetric key setting. We discuss future works and open problems. 1

This paper describes the asymptotic behavior of normalized linear complexity of ultimately nonperiodic binary sequence. The linear complexity of s/sup n/, L/sub s/(n), is defined as the length of the shortest linear feedback shift register which generates s/sup n/. The research method and results studied in this paper seem to be very useful in characterizing the purely random sequence and distinguishing a key stream generator from a uniformly random sequence.

For an ultimately nonperiodic binary sequence s={s/sub t/}/sub t/spl ges/0/, it is shown that the set of the accumulation values of the normalized linear complexity, L/sub s/(n)/n, is a closed interval centered at 1/2, where L/sub s/(n) is the linear complexity of the length n prefix s/sup n/=(s/sub 0/,s/sub 1/,...,s/sub n-1/) of the sequence s. It was known that the limit value of the normalized linear complexity is equal to 0 or 1/2 if it exists. A method is also given for constructing a sequence to have the closed interval [1/2-/spl Delta/, 1/2+/spl Delta/](0/spl les//spl Delta//spl les/1/2) as the set of the accumulation values of its normalized linear complexity.

A unified derivation of the bounds of the linear complexity is given for a sequence obtained from a periodic sequence over GF(q) by either substituting, inserting, or deleting k symbols within one period. The lower bounds are useful in case of n