Search

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ?(n-1)/3? out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems. [ABSTRACT FROM AUTHOR]

The objectives of this special issue are advanced security technologies and services for future computing environments, including, but not limited to, security primitives, protocols and security applications and services. Recent advances in security technologies and services for future computing environments have created a new class of the following: (i) Wireless sensor networks and radio-frequency identification security and privacy; (ii) security architectures for distributed network systems, P2P systems, cloud and grid systems; and (iii) security in e-commerce, mobile and wireless networks, and finally, security standards and assurance methods. All papers are expected to focus on novel approaches for advanced security technologies and services for future computing environments and to present high-quality results for tackling problems arising from the ever-growing advanced security technologies and services for future computing environments. [ABSTRACT FROM AUTHOR]

Advances in quantum computers threaten the security of public-key cryptosystems whose security is based on the hardness of factoring or on the discrete logarithm problem. Multivariate encryption schemes are promising alternatives to traditional cryptosystems. Tao et al. proposed a new Multivariate Public-Key Cryptosystem for encryption called simple matrix encryption scheme (ABC for short). Further, they proposed an improved simple matrix encryption schemes and a cubic simple matrix encryption scheme. In this paper, we show that the three schemes are vulnerable to a structural key recovery attack by tensor and vectorization notation and associated algebraic re-writing rules. We derive a set of linear equations from the public key whose solution yields an equivalent key pair that hide the central map. The proposed cryptanalysis approaches require polynomial computational complexity to achieve some equivalent keys from associated public keys. In addition, we provide an example to illustrate feasibility of proposed analysis method. [ABSTRACT FROM AUTHOR]

For cloud data storage, data privacy and security are two key concerns. Although sensitive data can be encrypted before they are stored in the cloud, the encrypted data can hardly be processed efficiently. Hence, a lightweight solution is required to satisfy both high security and high efficiency requirements. In this paper, we study the problem of range query over encrypted data. The main idea is to transform the range comparison to a privacy-preserving set intersection operation. To protect record privacy, our scheme builds searchable encrypted indexes for records that are secure against inference attack. To ensure the privacy of range queries, non-deterministic encryption, which has not been achieved in range query before, is proposed to hide the search pattern of queries. During range comparison, our scheme neither leaks the order relationship between the upper/lower bound of a range query and the encrypted index, nor produces false positives in the query results. We have implemented our scheme and evaluated its performance in comparison with other schemes. The comparison results indicate that our scheme has a shorter index size and search time than the order-revealing encryption (ORE) scheme when the processing unit is large. Meanwhile, our scheme only leaks the access pattern, and is proved to be more secure than existing schemes. [ABSTRACT FROM AUTHOR]

With the progress of cloud computing, many users hope in time to upload their data into cloud for sharing. For sensitive data, the owner must encrypt it before sending it to cloud server. The state of the art method for fine-grained access control on encrypted data is attribute-based encryption (ABE). Though ABE is believed to be an outstanding technique for secure data sharing, it has many efficiency drawbacks. For example, its ciphertext size and decryption time increase linearly with the number of attributes used during encryption and decryption, and it is hard to revoke a user’s access ability. In this paper, we propose a method to outsource the decryption of ABE via public cloud computing, and to control a user’s decryption capacity through a bounded revocation technique. The public cloud server can transform any user’s ABE ciphertexts into short ElGamal-type ciphertexts via the user’s public transformation key. The transformed ciphertexts are actually ElGamal-type identity-based ciphertexts obtained through a bounded-collision identity-based encryption scheme, and the decryption time only requires one exponentiation. Our scheme can revoke user’s decryption ability. But it limits to scenario with bounded number of revocation. [ABSTRACT FROM AUTHOR]

Provably secure identity-based encryption (IBE) schemes in the presence of key-leakage have attracted a lot of attention recently. However, most of them were designed in the bounded-leakage model, and might not be able to meet the claimed security under the continuous-leakage attacks. The main issue is that the most of previous leakage-resilient IBE schemes could not ensure the randomness of all elements in the ciphertext, because some elements can be written as a function on the private key of user; therefore, the adversary can obtain the leakage on the private key of user from the corresponding given ciphertext. In this paper, a new construction of CCA-secure IBE scheme tolerating continuous-leakage attacks in the standard model is proposed, and its security is proved in the selective-ID security model based on the hardness of decisional bilinear Diffie-Hellman assumption, which is a classical static assumption. In our construction, the adversary cannot obtain any leakage on the private key from the corresponding ciphertext, since all elements in the ciphertext are random in the adversary's view. The striking advantage of our constructions is the key leakage ratio, which is the best one among the previous leakage-resilient IBE constructions. [ABSTRACT FROM AUTHOR]

In this paper, we introduce new methods to evaluate integer polynomials with the Gentry-Sahai-Waters fully homomorphic encryption (GSW FHE) scheme. Our solution has much slower noise growth and per homomorphic integer multiplication cost, with a ratio O((logk)w+1 / kw⋅n) in comparison to the original GSW scheme where k is the input plaintext width, n is the LWE dimension and ω=2.373. Technically, we reduce the integer multiplication noise by restricting the evaluation to be between two kinds of ciphertexts: one is for the message space ℤq and the other is for message space 픽2 [log q]. To achieve generality, we propose an integer bootstrapping scheme which converts these two kinds of ciphertexts into each other. To solve the ciphertext expansion problem due to ciphertexts in 픽2 [log q], we propose a solution based on symmetric-key encryption with stream ciphers. [ABSTRACT FROM AUTHOR]

While designing ring signature and group signature is a relatively mature area, few published schemes are both efficient and quantum attack-resilience. In this paper, we present two new signature schemes based on coding theory. First, we present two new zero-knowledge (ZK) identification protocols based on the construction of (Cayrel, P.L., Véron, P. and Alaoui, S.M.E.Y. (2010) A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem. Proceedings of SAC 2010, Waterloo, Ontario, Canada, August 12-13, pp. 171-186. Springer, Berlin) in order to improve efficiency of code-based digital signature schemes. We then transform the newly proposed ZK protocols into a ring signature scheme and a group signature scheme. Our schemes enjoy a significant improvement in efficiency since reducing the cheating probability decreases the interaction rounds. Specially, with the security level of 2-87, the sizes of public key and signature are 14.5 KB and 52 KB in our ring signature scheme, while the corresponding sizes are 400 KB and 2384 KB in the scheme of (Cayrel, P. L., Alaoui, S. M. E. Y., Hoffmann, G. and Véron, P. (2012) An improved threshold ring signature scheme based on error correcting codes. Proceedings of WAIFI 2012, Bochum, Germany, July 16-19, pp. 45-63. Springer, Berlin). At the security level of 2-80, the sizes of public key and signature are 32 KB and 113.8 KB in our group signature scheme, as compared with 2.5 MB and 20 MB in the scheme of (Alamélou, Q., Blazy, O., Cauchie, S. and Gaborit, P. (2017) A codebased group signature scheme. Des. Codes Cryptogr., 82, 469-493) and 642 KB and 114 KB in the scheme of (Ezerman, M.F., Lee, H.T., Ling, S., Nguyen, K. and Wang, H. (2015) A provably secure group signature scheme from code-based assumptions. Proc. ASIACRYPT 2015, Auckland, New Zealand, November 29-December 3, pp. 260-285. Springer, Berlin). [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of cheating for visual cryptography schemes. Although the problem of cheating has been extensively studied for secret sharing schemes, little work has been done for visual secret sharing. We provide a formal definition of cheating for visual cryptography and new (2, n)-threshold and (n, n)-threshold schemes that are immune to deterministic cheating. [ABSTRACT FROM PUBLISHER]

Presently, many identity-based proxy signature (IBPS) schemes have been proposed, but most of them are constructed in the random oracle model. Also, the proposed security model for IBPS is not enough complete according to Boldyreva's work. Cao and Cao proposed an IBPS scheme in the standard model. However, their scheme is not secure because of not resisting the attack of delegator and requires more computation cost. In this paper, we present a framework for IBPS and show a detailed security model for IBPS. Under our framework, we present an efficient IBPS scheme in the standard model. Compared with other IBPS schemes, the proposed scheme has more complete security and is more efficient. [ABSTRACT FROM AUTHOR]

A related-key attack (RKA) occurs when an adversary tampers the private key stored in a cryptographic hardware device, and observes the result of the cryptographic primitive under this modified private key. In this paper, we consider the security of signcryption schemes under linear RKAs, where an adversary is allowed to tamper the private keys of the receiver and the sender, and subsequently observe the outcome of a signcryption system under these modified private keys of both parties. We define two security notions for RKA-secure signcryption schemes: chosen ciphertext RKA and chosen message RKA. We require that a signcryption scheme remains secure even when an adversary is allowed to access the designcryption oracle and the signcryption oracle on linear shifts of the private keys of the receiver and the sender, respectively. After reviewing some basic definitions related to our construction, we give a specific signcryption scheme from bilinear Diffie–Hellman which is secure against RKAs. Furthermore, we extend the security model of signcryption with anonymity, where the ciphertext is anonymous to others except the real receiver given the honest sender and the honest receiver. Fortunately, with a trivial modification to the original signcryption scheme, our proposed signcryption scheme can protect the privacy of both the sender and the receiver. [ABSTRACT FROM PUBLISHER]

Secrecy of decryption keys is an important pre-requisite for security of any encryption scheme and compromised private keys must be immediately replaced. Forward Security (FS), introduced to Public Key Encryption (PKE) by Canetti et al. (Eurocrypt 2003), reduces damage from compromised keys by guaranteeing confidentiality of messages that were encrypted prior to the compromise event. The FS property was also shown to be achievable in (Hierarchical) Identity-Based Encryption (HIBE) by Yao et al. (ACM CCS 2004). Yet, for emerging encryption techniques, offering flexible access control to encrypted data, by means of functional relationships between ciphertexts and decryption keys, FS protection was not known to exist. In this paper, we introduce FS to the powerful setting of Hierarchical Predicate Encryption (HPE), proposed by Okamoto and Takashima (Asiacrypt 2009). Anticipated applications of FS-HPE schemes can be found in searchable encryption and in fully private communication. Considering the dependencies among the concepts, our FS-HPE scheme implies forward-secure flavors of Predicate Encryption and (Hierarchical) Attribute-Based Encryption. Our FS-HPE scheme guarantees FS for plaintexts and for attributes that are hidden in HPE ciphertexts. It further allows delegation of decrypting abilities at any point in time, independent of FS time evolution. It realizes zero-inner-product predicates and is proved adaptively secure under standard assumptions. As the ‘cross-product’ approach taken in FS-HIBE is not directly applicable to the HPE setting, our construction resorts to techniques that are specific to existing HPE schemes and extends them with what can be seen as a reminiscent of binary tree encryption from FS-PKE. [ABSTRACT FROM AUTHOR]

The security of ordinary digital signature schemes relies on a computational assumption. Fail-stop signature schemes provide security for a sender against a forger with unlimited computational power by enabling the sender to provide a proof of forgery if it occurs. In this paper we give an efficient fail-stop signature scheme that uses two hard problems, discrete logarithm and factorization, as the basis of a receiver's security. We show that the scheme has provable security against adaptively chosen message attack, and is the most efficient scheme with respect to the ratio of the message length to the signature length. The scheme provides an efficient solution to signing messages up to 1881 bits. [ABSTRACT FROM PUBLISHER]

In this paper the author shows that the group key agreement protocol proposed by Tseng suffers from a number of serious security vulnerabilities. [ABSTRACT FROM AUTHOR]

The Visual cryptography scheme (VCS) is a perfect secure method that encrypts a secret image by breaking it into shadow images. A distinctive property of VCS is that one can visually, without computation, decode the secret by superimposing shadow images. However, much of the contrast of the reconstructed image is lost. A different kind of VCS has been recently proposed by Viet and Kurosawa, called VCS with reversing, allowing participants to perform a reversing operation (reverse black and white) on shadow images. Two drawbacks of the Viet–Kurosawa VCS are: (1) one can only reconstruct an almost ideal contrast image but not an ideal contrast image and (2) the Viet–Kurosawa VCS is constructed just from a perfect black VCS. This paper shows a real perfect contrast VCS such that the black and white pixels are perfectly reconstructed within finite runs, no matter what VCS (perfect black or non-perfect black) is used. [ABSTRACT FROM AUTHOR]

Conventionally, a verified digital signature releases information about both the signing event and the signed content simultaneously, where the signing event proves the truth that someone actually signed something. However, in many cases, the information of the signing event and the signed content have different uses and distinct degrees of importance on various occasions. In such cases, the conventional digital signature, the current authenticated encryption schemes and the current signcryption schemes cannot satisfy the needs of selectively releasing either the information about the signing event or that about the signed content or both depending on the situation. In this paper, we shall propose a selectively convertible authenticated encryption scheme where either the sender or the designated receiver can selectively convert the encryption such that the signing event and that of the signed content can be released adaptively. The security of the scheme is proved in the random oracle model. Applications based on the proposed scheme are also introduced. [ABSTRACT FROM AUTHOR]

We propose a fully homomorphic encryption (FHE) scheme that encrypts matrices. Our scheme supports homomorphic matrix addition, multiplication and Hadamard product. In PKC 2015, Hiromasa et al. constructed the only FHE scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. Compared with their work, the advantages of our scheme are the following: (1) Small ciphertext size : For a plaintext matrix M ∈ {0,1} r × r ⁠, the size of ciphertext matrix is r × (n + r) ⁠, in contrast to (n + r) × (n + r) ⌈ log q ⌉ in their work. (2) Standard assumption : The security is based on LWE assumption merely, while the security of scheme in their work depends additionally on some special kind of circular security assumption. (3) Supporting homomorphic matrix Hadamard product. We show how to apply the proposed scheme to optimize the bootstrapping procedure of Alperin-Sheriff and Peikert, in a way similar to the work of Hiromasa, Abe and Okamoto. Due to smaller ciphertext matrices, the bootstrapping key of our optimized bootstrapping procedure is smaller than that in the work of Hiromasa, Abe and Okamoto by a factor of (n / r + 1) ⌈ log q ⌉ ⁠. [ABSTRACT FROM AUTHOR]

As a new variant of digital signature, attribute-based signature (ABS) is appealing for many scenarios, where both authentication and anonymity are desired. However, in such a paradigm, a user's secret key is not linkable to an authenticated identity, and the same set of attributes might be shared among multiple users. Consequently, a malicious user would leak his secret key for some purposes without the risk of being identified among these equal users. On the other hand, for a cryptosystem with a large number of users, there should be an efficient revocation mechanism to further inform that a user's credential is abolished. We note that none of the existing ABS schemes simultaneously supports traceability and revocability, which are crucial towards the practicability of ABS. In this work, we first give a formal security model for traceable and revocable ABS. Next, we provide a concrete construction that admits flexible threshold signing predicates. Finally, we prove the anonymity and traceability of the proposed scheme in the standard model. To the best of our knowledge, our construction is the first ABS scheme that enjoys the functionalities of traceability and revocability simultaneously, and thus is more feasible for practical applications. [ABSTRACT FROM AUTHOR]

In an identity-based encryption (IBE) scheme, how to revoke users from the system is a difficult problem when their private keys are compromised. The private key generator (PKG) updates the private keys for all unrevoked users and has high computation load when a large number of users are included. We propose an IBE scheme with verifiable outsourced revocation based on the onemalicious model of two servers. In the proposed scheme, PKG delegates the key update operations to the two servers for all unrevoked users. The PKG can detect the failure with probability 1 if one of the servers misbehaves. Our scheme is proven fully secure and verifiable against chosenplaintext attack (CPA) without random oracles. The servers cannot execute the key update operations for any revoked user even if they collude. The experiment shows the time cost for PKG in the outsourcing algorithm is much smaller than that for directly updating the private keys for all unrevoked users. [ABSTRACT FROM AUTHOR]

Certificateless encryption (CLE) effectively solves the inherent key escrow problem in identity-based encryption while retaining its keeping certificate-free property. Although a number of CLE schemes have been available in the literature, little attention has been paid to the problem of user revocation in the certificateless setting. In this work, we study CLE systems with user revocation capabilities. At first, we establish reasonable security models for revocable CLE (RCLE) schemes. Then we put forward the first efficient and CCA2-secure RCLE scheme in the standard model. A rigorous security proof of our RCLE scheme is presented based on the decisional truncated q-ABDHE assumption and decisional bilinear Diffie–Hellman (DBDH) assumption. [ABSTRACT FROM PUBLISHER]