In the paper we define three new complexity classes for Turing Machine
undecidable problems inspired by the famous Cook/Levin's NP-complete complexity
class for intractable problems. These are U-complete (Universal complete),
D-complete (Diagonalization complete) and H-complete (Hypercomputation
complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started
the population process of these new classes assigning several undecidable
problems to them. We justify that some super-Turing models of computation,
i.e., models going beyond Turing machines, are tremendously expressive and they
allow to accept arbitrary languages over a given alphabet including those
undecidable ones. We prove also that one of such super-Turing models of
computation - the \$-Calculus, designed as a tool for automatic problem solving
and automatic programming, has also such tremendous expressiveness. We
investigate also completeness of cost metrics and meta-search algorithms in
\$-calculus.
The notion of aggregator oblivious (AO) security for privacy preserving data
aggregation was formalized with a specific construction of AO-secure blinding
technique over a cyclic group by Shi et al. Some of proposals of data
aggregation protocols use the blinding technique of Shi et al. for BGN
cryptosystem, an additive homomorphic encryption. Previously, there have been
some security analysis on some of BGN based data aggregation protocols in the
context of integrity or authenticity of data. Even with such security analysis,
the BGN cryptosystem has been a popular building block of privacy preserving
data aggregation protocol. In this paper, we study the privacy issues in the
blinding technique of Shi et al. used for BGN cryptosystem. We show that the
blinding techniques for the BGN cryptosystem used in several protocols are not
privacy preserving against the recipient, the decryptor. Our analysis is based
on the fact that the BGN cryptosystem uses a pairing e:GxG-->G_T and the
existence of the pairing makes the DDH problem on G easy to solve. We also
suggest how to prevent such privacy leakage in the blinding technique of Shi et
al. used for BGN cryptosystem.
Indexing is a well-known database technique used to facilitate data access
and speed up query processing. Nevertheless, the construction and modification
of indexes are very expensive. In traditional approaches, all records in the
database table are equally covered by the index. It is not effective, since
some records may be queried very often and some never. To avoid this problem,
adaptive merging has been introduced. The key idea is to create index
adaptively and incrementally as a side-product of query processing. As a
result, the database table is indexed partially depending on the query
workload. This paper faces a problem of adaptive merging for phase change
memory (PCM). The most important features of this memory type are: limited
write endurance and high write latency. As a consequence, adaptive merging
should be investigated from the scratch. We solve this problem in two steps.
First, we apply several PCM optimization techniques to the traditional adaptive
merging approach. We prove that the proposed method (eAM) outperforms a
traditional approach by 60%. After that, we invent the framework for adaptive
merging (PAM) and a new PCM-optimized index. It further improves the system
performance by 20% for databases where search queries interleave with data
modifications.