Fundamenta Informaticae - Volume 188, issue 2

Authors: Eberbach, Eugene

Article Type: Research Article

Abstract: 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. Show more

Keywords: automatic problem solving, automatic programming, undecidability, intractablity, recursive algorithms, recursively enumerable but not recursive algorithms, non-recursively enumerable algorithms, super-Turing computation, super-recursive algorithms, p-decidability, e-decidability, a-decidability, i-decidability, reduction techniques, U-completeness, D-completeness, H-completeness, $-calculus, cost metrics completeness, meta-search algorithms completeness

DOI: 10.3233/FI-222142

Citation: Fundamenta Informaticae, vol. 188, no. 2, pp. 63-90, 2022

Authors: Lee, Hyang-Sook | Lim, Seongan | Yie, Ikkwon | Yun, Aaram

Article Type: Research Article

Abstract: 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 : G × G → 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. Show more

Keywords: data aggregation protocol, additive homomorphic encryption, BGN cryptosystem

DOI: 10.3233/FI-222143

Citation: Fundamenta Informaticae, vol. 188, no. 2, pp. 91-101, 2022

Authors: Macyna, Wojciech | Kukowski, Michal

Article Type: Research Article

Abstract: 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 an 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 …the 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 propose a new variant of the PCM-optimized index. It further improves the system performance by 20% for databases where search queries interleave with data modifications. Show more

Keywords: phase change memory, adaptive merging, database indexing

DOI: 10.3233/FI-222144

Citation: Fundamenta Informaticae, vol. 188, no. 2, pp. 103-126, 2022