Search

In this paper, we present the communication complexity results of several chosen-ciphertext attack (CCA2) secure public key cryptosystems that are resilient to certain classes of secret key leakage attacks. In particular, we discuss the communication complexity trade-off between cryptosystems and generic transformations that rely on the random oracle model and those that are designed under the standard model. For this purpose, we propose a communication complexity measure for public key cryptosystems that equals the total amount of bits involving the receiver's public key and a ciphertext transmission by the sender. Using this complexity measure, we show that random oracle model-based cryptosystems and transformations are more efficient in terms of communication complexity, albeit relying on the stronger assumption that some cryptographic primitives behave like truly random functions. As corollaries of our results, we also address the problem of establishing communication complexity lower bounds by which leakage-secure communication between two parties can occur, and show that our cryptosystems and generic transformations achieve polynomial lower bounds in communication complexity relative to the security parameter of an adversary. [ABSTRACT FROM AUTHOR]

In this paper, we investigate simulations of transition P systems (TP systems) in evolution-communication P systems with energy (ECPe systems). We only focus on TP systems where an object that triggers a cooperative rule also triggers a non-cooperative rule. In this way, the presence of a rule trigger always implies that a rule will be applied. In our constructed ECPe systems, a transition in the TP system is simulated by a k-step computation where k is a factor of the cardinality of the alphabet in the original system. Also, the maximum energy needed for communication rules depends on the number of copies of a trigger in a cooperative rule. [ABSTRACT FROM AUTHOR]

This paper explores the relation of computations in Evolution-Communication P systems with energy (ECPe systems) and non-cooperative Transition P systems without dissolution (TP systems). We have shown that for every non-cooperative TP system, we can construct an ECPe system that, (i) generates the same language, and (ii) each halting computation that takes τ steps in the TP system can be simulated in at most 3τ + 1 steps in its corresponding ECPe system. [ABSTRACT FROM AUTHOR]

A spiking neural P system (SN P system) is a model of computation inspired by the mechanism of a network of spiking neurons. A homogeneous SN P system is an SN P system whose neurons have identical rule set. In this work, we introduced an algorithm that, under certain condition, transforms a non-homogeneous SN P system Π to a homogeneous SN P system Π ′ that computes the same set as the system Π. Two transformation operations called neuron translation and neuron scaling are introduced which are then used by the homogenization algorithm. [ABSTRACT FROM AUTHOR]

It is already known that the 1-Poset and 2-Poset Cover Problems are in 𝑷. In this paper, we extended the previous results and devised an algorithm for the 𝒌-Poset Cover Problem, for any 𝒌 number of posets that cover the input. The algorithm runs in 𝑶(𝒎2k 𝒏2), where 𝒎 and 𝒏 are the input size. With this running time, we can say that the problem belongs to XP (slicewise polynomial). The algorithm runs efficiently for small fixed 𝒌 but runs exponentially for large 𝒌. While the algorithm running time has yet not to be efficient for large 𝒌, we have shown a significant improvement from a brute-force solution, which runs in 2𝒎 𝒏2 + 𝑶(􀷌𝒌 𝒊 􀰸 1 2𝒎𝒊𝒏) - exponential even for small fixed [ABSTRACT FROM AUTHOR]

• A novel parallel framework for evolving spiking neural P systems. • GPU implementation of the genetic algorithm employed in the parallel framework. • Adapting CuSNP design for the efficient simulation of spiking neural P systems in the parallel framework. • Reporting up to 9x of speedup of the GPU implementation versus the CPU counterpart for the parallel step, and up to 3x for the overall process. Methods for optimizing and evolving spiking neural P systems (in short, SN P systems) have been previously developed with the use of a genetic algorithm framework. So far, these computations, both evolving and simulating, were done only sequentially. Due to the non-deterministic and parallel nature of SN P systems, it is natural to harness parallel processors in implementing its evolution and simulation. In this work, a parallel framework for the evolution of SN P Systems is presented. This is the result of extending our previous work by implementing it on a CUDA-enabled graphics processing unit and adapting CuSNP design in simulations. Using binary addition and binary subtraction with 3 different categories each as initial SN P systems, the GPU-based evolution runs up to 9x faster with respect to its CPU-based evolution counterparts. Overall, when considering the whole process, the GPU framework is up to 3 times faster than the CPU version. [ABSTRACT FROM AUTHOR]

The Hammock-Poset Cover Problem is a variation of the Poset Cover Problem with the same input - set (...) of linear orders over the set {L1, L2, ...,L3}, but the solution is restricted to a set of simple hammock (...) posets. The problem is NP-Hard when K ≥ 3 but is in P when k = 1. The computational complexity of the problem when k = 2 is not yet known. In this paper, we determine the approximation complexity of the cases that have been shown to be NP-Hard. We show that the Hammock (...)-Poset Cover Problem is in APX and, in particular, (1 + 1/2k)-approximable, for k ≥ 3. On the other hand, we also explore the computational complexity for the case where k = 2 [Hammock(2,2)-Poset Cover Problem]. We show that it is in P when the transposition graph of the input set of linear orders is rectangular. [ABSTRACT FROM AUTHOR]

The Hammock(2, 2 ,..., 2/k)-Poset Cover Problem is a variation of the Poset Cover Problem with the same input - set {L1, L2, ..., Lm} of linear orders over the set {1, 2, ..., n}, but the solution is restricted to a set of simple hammock(2, 2 ,..., 2/k) posets. The problem is NP-Hard when k = 3 but is in P when k = 1. The computational complexity of the problem when k = 2 is not yet known. In this paper, we determine the approximation complexity of the cases that have been shown to be NP-Hard. We show that the Hammock(2, 2 ,..., 2/k)-Poset Cover Problem is in APX and, in particular, (1 + 1/2K)-approximable, for k = 3. On the other hand, we also explore the computational complexity for the case where k = 2 [Hammock(2,2)-Poset Cover Problem]. We show that it is in P when the transposition graph of the input set of linear orders is rectangular. [ABSTRACT FROM AUTHOR]

The N-Queens problem consists of placing N queens on an N × N chessboard such that no two queens threaten each other (i.e. same row, column, or diagonal). P systems solutions to the N-Queens problem and related problems (e.g. SAT) are often in a nondistributed way , i.e. the complete input to the problem enters the system through a single input membrane and the problem is solved. dP systems involve using more than one P system to solve problems in a distributed way , i.e. the problem input is partitioned and each partition enters the system using distinct components (which are also P systems). In this work, we solve the N-Queens problem using dP systems where the components are P systems with active membranes. Our 2-component and 3-component solutions partition the elements of the input multiset based on the clauses they represent. Compared to the nondistributed solution, our 2-component and 3-component solutions reduce the computation time by a half and by a third, respectively. Besides the analysis of the computation time, we also analyze communication costs. C o m N , indicating the number of computation steps where communication occurred, is constant for both solutions. C o m R , the number of intercomponent communication rules used, and C o m W , the number of object communicated, are in terms of S , where S is the number of solutions to the problem instance. [ABSTRACT FROM AUTHOR]