Volume 188, Issue 2

1. On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

Eugene Eberbach.
In the paper we define three new complexity classes for Turing Machineundecidable problems inspired by the famous Cook/Levin's NP-complete complexityclass for intractable problems. These are U-complete (Universal complete),D-complete (Diagonalization complete) and H-complete (Hypercomputationcomplete) classes. In the paper, in the spirit of Cook/Levin/Karp, we startedthe population process of these new classes assigning several undecidableproblems to them. We justify that some super-Turing models of computation,i.e., models going beyond Turing machines, are tremendously expressive and theyallow to accept arbitrary languages over a given alphabet including thoseundecidable ones. We prove also that one of such super-Turing models ofcomputation - the \$-Calculus, designed as a tool for automatic problem solvingand automatic programming, has also such tremendous expressiveness. Weinvestigate also completeness of cost metrics and meta-search algorithms in\$-calculus.

2. On Insecure Uses of BGN for Privacy Preserving Data Aggregation Protocols

Hyang-Sook Lee ; Seongan Lim ; Ikkwon Yie ; Aaram Yun.
The notion of aggregator oblivious (AO) security for privacy preserving dataaggregation was formalized with a specific construction of AO-secure blindingtechnique over a cyclic group by Shi et al. Some of proposals of dataaggregation protocols use the blinding technique of Shi et al. for BGNcryptosystem, an additive homomorphic encryption. Previously, there have beensome security analysis on some of BGN based data aggregation protocols in thecontext of integrity or authenticity of data. Even with such security analysis,the BGN cryptosystem has been a popular building block of privacy preservingdata aggregation protocol. In this paper, we study the privacy issues in theblinding technique of Shi et al. used for BGN cryptosystem. We show that theblinding techniques for the BGN cryptosystem used in several protocols are notprivacy preserving against the recipient, the decryptor. Our analysis is basedon the fact that the BGN cryptosystem uses a pairing e:GxG-->G_T and theexistence of the pairing makes the DDH problem on G easy to solve. We alsosuggest how to prevent such privacy leakage in the blinding technique of Shi etal. used for BGN cryptosystem.

3. Adaptive Merging on Phase Change Memory

Wojciech Macyna ; Michal Kukowski.
Indexing is a well-known database technique used to facilitate data accessand speed up query processing. Nevertheless, the construction and modificationof indexes are very expensive. In traditional approaches, all records in thedatabase table are equally covered by the index. It is not effective, sincesome records may be queried very often and some never. To avoid this problem,adaptive merging has been introduced. The key idea is to create indexadaptively and incrementally as a side-product of query processing. As aresult, the database table is indexed partially depending on the queryworkload. This paper faces a problem of adaptive merging for phase changememory (PCM). The most important features of this memory type are: limitedwrite endurance and high write latency. As a consequence, adaptive mergingshould be investigated from the scratch. We solve this problem in two steps.First, we apply several PCM optimization techniques to the traditional adaptivemerging approach. We prove that the proposed method (eAM) outperforms atraditional approach by 60%. After that, we invent the framework for adaptivemerging (PAM) and a new PCM-optimized index. It further improves the systemperformance by 20% for databases where search queries interleave with datamodifications.