Certificate-based signatures: New definitions and a generic construction from certificateless signatures

Certificate-based encryption was introduced in Eurocrypt’03 to solve the certificate management problem in public key encryption. Recently, this idea has been extended to certificate-based signatures. To date, several new schemes and security models of certificate-based signatures have been proposed. In this paper, we first introduce a new security model of certificate-based signatures. Our model is not only more elaborated when compared with the existing ones, but also defines several new types of adversaries in certificate-based signatures. We then investigate the relationship between certificate-based signatures and certificateless signatures, by proposing a generic construction of certificate-based signatures from certificateless signatures. Our generic construction is secure (in the random oracle model) under the security model defined in this paper, assuming the underlying certificateless signatures satisfying certain security notions.

Certificate-based signatures revisited

Certificate-based encryption was introduced in Eurocrypt '03 to solve the certificate management problem in public key encryption. Recently, this idea was extended to certificate-based signatures. Several new schemes and security models of certificate-based signature by comparing it with digital signatures in other popular public key systems. We introduce a new security model of certificate-based signature, which defines several new types of adversaries against certificate-based signature, which defines several new types of adversaries against certificate-based signatures, along with the security model of certificate-based signatures against them. The new model is clearer and more elaborated compared with other existing ones. We then investigate the relationship between certificate-based signatures and certificate-less signatures, and propose a generic construction of certificate-based signatures and certificate less signatures, and propose a generic construction of certificate-based signatures. We prove that the generic construction is secure (in the random oracle model) against all types of adversaries defined in this paper, assuming the underlying certificateless signatures satisfying certain security notions. Based on our generic construction, we are able to construct new certificate-based signatures schemes, which are more effiecient in comparison with other schemes with similar security levels

Performance and scalability assessment for non-certificate-based public key management in VANETS

Current research in secure messaging for Vehicular Ad hoc Networks (VANETs) appears to focus on employing a digital certificate-based Public Key Cryptosystem (PKC) to support security. The security overhead of such a scheme, however, creates a transmission delay and introduces a time-consuming verification process to VANET communications. This paper proposes a non-certificate-based public key management for VANETs. A comprehensive evaluation of performance and scalability of the proposed public key management regime is presented, which is compared to a certificate-based PKC by employing a number of quantified analyses and simulations. Not only does this paper demonstrate that the proposal can maintain security, but it also asserts that it can improve overall performance and scalability at a lower cost, compared to the certificate-based PKC. It is believed that the proposed scheme will add a new dimension to the key management and verification services for VANETs.

Certificate-based signature : security model and efficient construction

In Eurocrypt 2003, Gentry introduced the notion of certificate-based encryption. The merit of certificate-based encryption lies in the following features: (1) providing more efficient public-key infrastructure (PKI) that requires less infrastructure, (2) solving the certificate revocation problem, and (3) eliminating third-party queries in the traditional PKI. In addition, it also solves the inherent key escrow problem in the identity-based cryptography. In this paper, we first introduce a new attack called the “Key Replacement Attack” in the certificate-based system and refine the security model of certificate-based signature. We show that the certificate-based signature scheme presented by Kang, Park and Hahn in CT-RSA 2004 is insecure against key replacement attacks. We then propose a new certificate-based signature scheme, which is shown to be existentially unforgeable against adaptive chosen message attacks under the computational Diffie-Hellman assumption in the random oracle model. Compared with the certificate-based signature scheme in CT-RSA 2004, our scheme enjoys shorter signature length and less operation cost, and hence, our scheme outperforms the existing schemes in the literature.

Forward secure attribute-based signatures

Attribute-Based Signatures (ABS) is a versatile primitive which allows an entity to sign a message with fine-grained control over identifying information. A valid ABS only attests to the fact that “A single user, whose attributes satisfy the predicate, has endorsed the message”. While ABS has been well investigated since its introduction, it is unfortunate that key exposure–an inherent weakness of digital signatures–has never been formally studied in the scenario of ABS. We fill this gap by proposing a new notion called forward secure ABS, its formal security models and a generic (also the first) design based on well established crypto primitives.

Attribute-based signatures with efficient revocation

Based signatures (ABS for short) allow an entity to sign messages with a fine-grained control over identity information. The signature attests not to the identity of the individual who endorsed a message, but instead to a claim regarding the attributes he/she holds. ABS has been well investigated since its introduction but little has been done on the revocation in ABS. In this paper, we divide ABS revocation as fine-grained attribute-revocation and coarse-grained user-revocation. The latter is the focus of this paper, and we present a concrete design-to address the issue of coarse-grained user-revocation in ABS without the need of any other third parties.

An efficient short certificate-based signature scheme

 FEBRUARY SPECIAL ISSUE : with selected papers from the 23rd Brazilian Symposium on Software Engineering

A provably secure construction of certificate-based encryption from certificateless encryption

Certificate-based encryption (CBE) and certificateless encryption (CLE) are proposed to lessen the certificate management problem in a traditional public-key encryption setting. Although they are two different notions, CBE and CLE are closely related and possess several common features. The encryption in CBE and CLE does not require authenticity verification of the recipient's public key. The decryption in both notions requires two secrets that are generated by the third party and the public key owner, respectively. Recently a generic conversion from CLE to CBE was given, but unfortunately its security proof is flawed. This paper provides an elaborate security model of CBE, based on which a provably secure generic construction of CBE from CLE is proposed. A concrete instantiation is also presented to demonstrate the application of our generic construction.

Secure outsourced attribute-based signatures

Attribute-based signature (ABS) enables users to sign messages over attributes without revealing any information other than the fact that they have attested to the messages. However, heavy computational cost is required during signing in existing work of ABS, which grows linearly with the size of the predicate formula. As a result, this presents a significant challenge for resource-constrained devices (such as mobile devices or RFID tags) to perform such heavy computations independently. Aiming at tackling the challenge above, we first propose and formalize a new paradigm called Outsourced ABS, i.e., OABS, in which the computational overhead at user side is greatly reduced through outsourcing intensive computations to an untrusted signing-cloud service provider (S-CSP). Furthermore, we apply this novel paradigm to existing ABS schemes to reduce the complexity. As a result, we present two concrete OABS schemes: i) in the first OABS scheme, the number of exponentiations involving in signing is reduced from O(d) to O(1) (nearly three), where d is the upper bound of threshold value defined in the predicate; ii) our second scheme is built on Herranz et al.'s construction with constant-size signatures. The number of exponentiations in signing is reduced from O(d2) to O(d) and the communication overhead is O(1). Security analysis demonstrates that both OABS schemes are secure in terms of the unforgeability and attribute-signer privacy definitions specified in the proposed security model. Finally, to allow for high efficiency and flexibility, we discuss extensions of OABS and show how to achieve accountability as well.

Certificate-based encryption resilient to key leakage

Certificate-based encryption (CBE) is an important class of public key encryption but the existing schemes are secure only under the premise that the decryption key (or private key) and master secret key are absolutely secret. In fact, a lot of side channel attacks and cold boot attacks can leak secret information of a cryptographic system. In this case, the security of the cryptographic system is destroyed, so a new model called leakage-resilient (LR) cryptography is introduced to solve this problem. While some traditional public key encryption and identity-based encryption with resilient-leakage schemes have been constructed, as far as we know, there is no leakage-resilient scheme in certificate-based cryptosystems. This paper puts forward the first certificate-based encryption scheme which can resist not only the decryption key leakage but also the master secret key leakage. Based on composite order bilinear group assumption, the security of the scheme is proved by using dual system encryption. The relative leakage rate of key is close to 1/3.

Network signatures based on gene pair expression ratios improve classification and the analysis of muscle-invasive urothelial cancer

Urothelial cancer (UC) is highly recurrent and can progress from non-invasive (NMIUC) to a more aggressive muscle-invasive (MIUC) subtype that invades the muscle tissue layer of the bladder. We present a proof of principle study that network-based features of gene pairs can be used to improve classifier performance and the functional analysis of urothelial cancer gene expression data. In the first step of our procedure each individual sample of a UC gene expression dataset is inflated by gene pair expression ratios that are defined based on a given network structure. In the second step an elastic net feature selection procedure for network-based signatures is applied to discriminate between NMIUC and MIUC samples. We performed a repeated random subsampling cross validation in three independent datasets. The network signatures were characterized by a functional enrichment analysis and studied for the enrichment of known cancer genes. We observed that the network-based gene signatures from meta collections of proteinprotein interaction (PPI) databases such as CPDB and the PPI databases HPRD and BioGrid improved the classification performance compared to single gene based signatures. The network based signatures that were derived from PPI databases showed a prominent enrichment of cancer genes (e.g., TP53, TRIM27 and HNRNPA2Bl). We provide a novel integrative approach for large-scale gene expression analysis for the identification and development of novel diagnostical targets in bladder cancer. Further, our method allowed to link cancer gene associations to network-based expression signatures that are not observed in gene-based expression signatures.

Sealing the leak on classical NTRU signatures

Initial attempts to obtain lattice based signatures were closely related to reducing a vector modulo the fundamental parallelepiped of a secret basis (like GGH [9], or NTRUSign [12]). This approach leaked some information on the secret, namely the shape of the parallelepiped, which has been exploited on practical attacks [24]. NTRUSign was an extremely efficient scheme, and thus there has been a noticeable interest on developing countermeasures to the attacks, but with little success [6]. In [8] Gentry, Peikert and Vaikuntanathan proposed a randomized version of Babai’s nearest plane algorithm such that the distribution of a reduced vector modulo a secret parallelepiped only depended on the size of the base used. Using this algorithm and generating large, close to uniform, public keys they managed to get provably secure GGH-like lattice-based signatures. Recently, Stehlé and Steinfeld obtained a provably secure scheme very close to NTRUSign [26] (from a theoretical point of view). In this paper we present an alternative approach to seal the leak of NTRUSign. Instead of modifying the lattices and algorithms used, we do a classic leaky NTRUSign signature and hide it with gaussian noise using techniques present in Lyubashevky’s signatures. Our main contributions are thus a set of strong NTRUSign parameters, obtained by taking into account latest known attacks against the scheme, a statistical way to hide the leaky NTRU signature so that this particular instantiation of CVP-based signature scheme becomes zero-knowledge and secure against forgeries, based on the worst-case hardness of the O~(N1.5)-Shortest Independent Vector Problem over NTRU lattices. Finally, we give a set of concrete parameters to gauge the efficiency of the obtained signature scheme.

identity based threshold proxy signature

IEEE Computer Society

Control flow-based malware variant detection

Static detection of malware variants plays an important role in system security and control flow has been shown as an effective characteristic that represents polymorphic malware. In our research, we propose a similarity search of malware to detect these variants using novel distance metrics. We describe a malware signature by the set of control flowgraphs the malware contains. We use a distance metric based on the distance between feature vectors of string-based signatures. The feature vector is a decomposition of the set of graphs into either fixed size k-subgraphs, or q-gram strings of the high-level source after decompilation. We use this distance metric to perform pre-filtering. We also propose a more effective but less computationally efficient distance metric based on the minimum matching distance. The minimum matching distance uses the string edit distances between programs' decompiled flowgraphs, and the linear sum assignment problem to construct a minimum sum weight matching between two sets of graphs. We implement the distance metrics in a complete malware variant detection system. The evaluation shows that our approach is highly effective in terms of a limited false positive rate and our system detects more malware variants when compared to the detection rates of other algorithms. © 2013 IEEE.