36775607
Short Signature and Universal Designated Verifier Signature Without Random Oracles
We propose the first universal designated verifier signature (UDVS) scheme whose security can be proven without random oracles, whereas the security of all previously known UDVS schemes are proven only when random oracles are assumed. To achieve our goal, we present a new short signature scheme without random oracles, which is a variant of BB04 scheme [4]. We also give new security definitions to UDVS. We note that our weakest security definitions are even stronger than any of previously known security definitions: We allow adversaries to behave more adaptively in oracle accessing and we also consider adaptive chosen public key attacks. The security of our UDVS scheme is then proven according to the new security definitions.
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.
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.
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.
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.
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.
18170201
Streaming multiple aggregations using phantoms
Data streams characterize the high speed and large volume input of a new class of applications such as network monitoring, web content analysis and sensor networks. Among these applications, network monitoring may be the most compelling one—the backbone of a large internet service provider can generate 1 petabyte of data per day. For many network monitoring tasks such as traffic analysis and statistics collection, aggregation is a primitive operation. Various analytical and statistical needs naturally lead to related aggregate queries. In this article, we address the problem of efficiently computing multiple aggregations over high-speed data streams based on the two-level query processing architecture of GS, a real data stream management system deployed in AT & T. We discern that additionally computing and maintaining fine-granularity aggregations (called phantoms) has the benefit of supporting shared computation. Based on a thorough analysis, we propose algorithms to identify the best set of phantoms to maintain and determine allocation of resources (particularly, space) to compute the aggregations. Experiments show that our algorithm achieves near-optimal computation costs, which outperforms the best adapted algorithm by more than an order of magnitude.
7619448
Generalized multidimensional data mapping and query processing
Multidimensional data points can be mapped to one-dimensional space to exploit single dimensional indexing structures such as the B+-tree. In this article we present a Generalized structure for data Mapping and query Processing (GiMP), which supports extensible mapping methods and query processing. GiMP can be easily customized to behave like many competent indexing mechanisms for multi-dimensional indexing, such as the UB-Tree, the Pyramid technique, the iMinMax, and the iDistance. Besides being an extendible indexing structure, GiMP also serves as a framework to study the characteristics of the mapping and hence the efficiency of the indexing scheme. Specifically, we introduce a metric called mapping redundancy to characterize the efficiency of a mapping method in terms of disk page accesses and analyze its behavior for point, range and kNN queries. We also address the fundamental problem of whether an efficient mapping exists and how to define such a mapping for a given data set.
15606709
Mining distribution change in stock order streams
Detecting changes in stock prices is a well known problem in finance with important implications for monitoring and business intelligence. Forewarning of changes in stock price, can be made by the early detection of changes in the distributions of stock order numbers. In this paper, we address the change detection problem for streams of stock order numbers and propose a novel incremental detection algorithm. Our algorithm gains high accuracy and low delay by employing a natural Poisson distribution assumption about the nature of stock order streams. We establish that our algorithm is highly scalable and has linear complexity. We also experimentally demonstrate its effectiveness for detecting change points, via experiments using both synthetic and real-world datasets.
18801795
When Does Online BP Training Converge?
The backpropogation (BP) neural networks have been widely applied in scientific research and engineering. The success of the application, however, relies upon the convergence of the training procedure involved in the neural network learning. We settle down the convergence analysis issue through proving two fundamental theorems on the convergence of the online BP training procedure. One theorem claims that under mild conditions, the gradient sequence of the error function will converge to zero (the weak convergence), and another theorem concludes the convergence of the weight sequence defined by the procedure to a fixed value at which the error function attains its minimum (the strong convergence). The weak convergence theorem sharpens and generalizes the existing convergence analysis conducted before, while the strong convergence theorem provides new analysis results on convergence of the online BP training procedure. The results obtained reveal that with any analytic sigmoid activation function, the online BP training procedure is always convergent, which then underlies successful application of the BP neural networks.