20077755
Efficient Identity-Based Encryption with Tight Security Reduction
In this paper, we present an efficient variant of the Boneh-Franklin scheme that achieves a tight security reduction. Our scheme is basically an IBE scheme under two keys, one of which is randomly chosen and given to the user. It can be viewed as a continuation of an idea introduced by Katz and Wang; however, unlike the Katz-Wang variant, our scheme is quite efficient, as its ciphertext size is roughly comparable to that of the original full Boneh-Franklin scheme. The security of our scheme can be based on either the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) assumptions.
10170990
Tweaking TBE/IBE to PKE Transforms with Chameleon Hash Functions
We present two transforms to acquire chosen ciphertext security from tag based techniques. The first one requires the separability of underlying primitives. By separability, informally, we mean the encryption algorithm has special structures and can process the identity and the message independently. Compared with generic transforms [8],it significantly reduces the ciphertext size overhead with only marginal computation cost. Compared with [11], the only known technique which directly achieves chosen ciphertext secure public key encryption from separable identity based primitives, it only requires selective-Tag/ID security of underlying primitives. Our second transform is less efficient but performs generically. Both transforms preserve the public verifiability of underlying primitives, and can be extended to hierarchical identity based encryption (HIBE) and threshold settings. As an independent interest, we also investigate the security requirements of chameleon hash functions to build strongly unforgeable one-time signatures.
15662668
Orthogonality between Key Privacy and Data Privacy, Revisited
Key privacy is a notion regarding the privacy of the owner of a public key, which has important applications in building (receiver) anonymous channels, or privacy-enhanced authentication/signature schemes. Key privacy is considered to be an orthogonal (i.e., independent), notion from data privacy, while the key privacy of many public key encryption schemes has not been explored, though their data privacy is comparatively well understood. In this paper, we study key privacy of many practical encryption schemes and identify evidences that key privacy is not comparable to data privacy. We also formalize key privacy in the plaintext checking attack model and point out some generic transforms to enhance the key privacy of an encryption scheme. Interestingly, these well-known techniques have been used to enhance data security. Finally, we give detailed security analyses on the signed hashed-ElGamal encryption [27] in the random oracle model, of both key privacy and data security against chosen ciphertext attack. Again, this specific example supports our claim on the relation of two notions.
711993
On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?
In a practical system, a message is often encrypted more than once by different encryptions, here called multiple encryption, to enhance its security. Additionally, new features may be achieved by multiple encrypting a message, such as the key-insulated cryptosystems and anonymous channels. Intuitively, a multiple encryption should remain “secure”, whenever there is one component cipher unbreakable in it. In NESSIE’s latest Portfolio of recommended cryptographic primitives (Feb. 2003), it is suggested to use multiple encryption with component ciphers based on different assumptions to acquire long term security. However, in this paper we show this needs careful discussion, especially, this may not be true according to adaptive chosen ciphertext attack (CCA), even with all component ciphers CCA-secure. We define an extended model of (standard) CCA called chosen ciphertext attack for multiple encryption (ME-CCA) emulating partial breaking of assumptions, and give constructions of multiple encryption satisfying ME-CCA-security. We further relax CCA by introducing weak ME-CCA (ME-wCCA) and study the relations among these definitions, proving ME-wCCA-security can be acquired by combining IND-CCA-secure component ciphers together. We then apply these results to key-insulated cryptosystem.
37850409
Round Optimal Distributed Key Generation of Threshold Cryptosystem Based on Discrete Logarithm Problem
We propose a distributed key generation protocol for discrete logarithm problem based threshold cryptosystems by introducing an efficient (publicly) verifiable encryption scheme from any homomorphic encryption with a non-interactive proof of fairness. Previous constructions of the same kind are either only based on a narrow definition of homomorphism or only a unique encryption scheme is considered. Our construction generalizes the scope of such design to a broader range of encryption schemes with efficient constructions of proofs of fairness. Since the protocol is round optimal (one-round) in the distributed fashion, adaptive adversary is not different from a static adversary, thus a simplified protocol design is possible. Our scheme is extremely capable for an environment with already built public key infrastructure. The verifiable encryption with fairness developed here can be used as building blocks of a variety of cryptographical applications like publicly verifiable secret sharing (PVSS), e-voting and auction schemes.
4696945
Combining Public Key Encryption with Keyword Search and Public Key Encryption
In this paper, we study the problem of secure integrating public key encryption with keyword search (PEKS) with public key data encryption (PKE). We argue the previous security model is not complete regarding keyword privacy and the previous constructions are secure only in the random oracle model. We solve these problems by first defining a new security model, then give a generic construction which is secure in the new security model without random oracles. Our construction is based on secure PEKS and tag-KEM/DEM schemes and achieves modular design. We also give some applications and extensions for our construction. For example, instantiate our construction with proper components, we have a concrete scheme without random oracles, whose performance is even competitive to the previous schemes with random oracles.
10078749
RoleVAT: Visual Assessment of Practical Need for Role Based Access Control
Role based access control (RBAC) is a powerful security administration concept that can simplify permission assignment management. Migration to and maintenance of RBAC requires role engineering, the identification of a set of roles that offer administrative benefit. However, establishing that RBAC is desirable in a given enterprise is lacking in current role engineering processes. To help identify the practical need for RBAC, we propose RoleVAT, a Role engineering tool for the Visual Assessment of user and permission Tendencies. User and permission clusters can be visually identified as potential user groups or roles. The benefit and impact of this visual analysis in enterprise environments is discussed and demonstrated through testing on real life as well as synthetic datasets. Our experimental results show the effectiveness of RoleVAT as well as interesting user and role tendencies in real enterprise environments.
2552624
Approximate NN queries on Streams with Guaranteed Error/performance Bounds
In data stream applications, data arrive continuously and can only be scanned once as the query processor has very limited memory (relative to the size of the stream) to work with. Hence, queries on data streams do not have access to the entire data set and query answers are typically approximate. While there have been many studies on the k Nearest Neighbors (kNN) problem in conventional multi-dimensional databases, the solutions cannot be directly applied to data streams for the above reasons. In this paper, we investigate the kNN problem over data streams. We first introduce the e-approximate kNN (ekNN) problem that finds the approximate kNN answers of a query point Q such that the absolute error of the k-th nearest neighbor distance is bounded by e. To support ekNN queries over streams, we propose a technique called DISC (aDaptive Indexing on Streams by space-filling Curves). DISC can adapt to different data distributions to either (a) optimize memory utilization to answer ekNN queries under certain accuracy requirements or (b) achieve the best accuracy under a given memory constraint. At the same time, DISC provide efficient updates and query processing which are important requirements in data stream applications. Extensive experiments were conducted using both synthetic and real data sets and the results confirm the effectiveness and efficiency of DISC.
8910317
Continuous Intersection Joins Over Moving Objects
The continuous intersection join query is computationally expensive yet important for various applications on moving objects. No previous study has specifically addressed this query type. We can adopt a naive algorithm or extend an existing technique (TP-Join) to process the query. However, they compute the answer for either too long or too short a time interval, which results in either a very large computation cost per object update or too frequent answer updates, respectively. This motivates us to optimize the query processing in the time dimension. In this study, we achieve this optimization by introducing the new concept of time-constrained (TC) processing. Further, TC processing enables a set of effective improvement techniques on traditional intersection join algorithms. With a thorough experimental study, we show that our algorithm outperforms the best adapted existing solution by several orders of magnitude.
28180483
Using Time Decompositions to Analyze PubMed Abstracts
Constructing time decompositions of time stamped documents is an important step for uncovering temporal relationships and trends of keywords and topics contained in the document set. This paper describes the use of time decompositions to extract temporal information from a small set of PubMed abstracts related to the Wnt signaling pathway. A time decomposition of the document set is constructed to identify temporal information such as keywords/topics significant in some time interval and to also identify temporal progression of the significant keywords. Keywords were assigned temporal significance values using two different measure functions based on notions of entropy and ratio. It is shown how optimal lossy decompositions of the document set are effective in reducing noise both in terms of the number of keywords as well as in terms of smoothing out the temporal progressions of keywords. Several optimal lossy decompositions for the document set are constructed and it is shown that the temporal information captured by an optimal lossy decomposition increases as its size (number of intervals) increases
44262524
Enhancing the B+-tree by dynamic node popularity caching
We propose the Cache Coherent B^+-tree (CCB^+-tree), an indexing structure that can improve search performance compared to the traditional B^+-tree. The CCB^+-tree makes use of the unused space in the internal nodes of a B^+-tree to cache frequently queried leaf node addresses, thus saving node accesses. An experimental study shows that the CCB^+-tree can outperform the traditional B^+-tree on workloads where certain queries are much more popular than the others.