Recently, the Ethereum blockchain changed its consensus algorithm from Proof-of-Work (PoW) to Proof-of-Stake (PoS). This change has greatly reduced overall energy consumption but has paved the way for the profiling of numerous mechanisms and actors that can operate off-chain to achieve Maximal Extractable Value (MEV). This raises questions about how transparent such a scenario is, both from the point of view of block validation power and from the point of view of the rewards achieved by distinct actors within the platform. To address this concern and to mitigate potential negative externalities, a permissionless ecosystem has recently been proposed, which should be transparent and fair for the extraction of MEV. In this article, after briefly describing the new ecosystem, we conduct an in-depth analysis of Ethereum blocks and other information about the actors operating in the ecosystem, to highlight potential critical situations.

The Proof-of-Stake (PoS) consensus algorithm has been criticized, in the literature and in several cryptocurrencies communities, due to the so-called compounding effect: who is richer has more coins to stake, therefore higher probability of being selected as a block validator and obtaining the corresponding rewards, thus becoming even richer. In this paper, we present a PoS simulator written in the Julia language that allows one to test several variants of PoS-based consensus algorithms, tweaking their parameters, and observe how the distribution of cryptocurrency coins among the users evolves over time. Such a tool can be used to investigate which combinations of parameters values allow to obtain a “fair” and stable consensus algorithm, in which, over the long term, no one gets richer or poorer by the mere act of validating blocks. Based on this investigation, we also introduce a new PoS-based consensus mechanism that allows the system to keep the wealth distribution stable even after a large number of epochs.

Classifying images has become a straightforward and accessible task, thanks to the advent of Deep Neural Networks. Nevertheless, not much attention is given to the privacy concerns associated with sensitive data contained in images. In this study, we propose a solution to this issue by exploring an intersection between Machine Learning and cryptography. In particular, Fully Homomorphic Encryption (FHE) emerges as a promising solution, as it enables computations to be performed on encrypted data. We therefore propose a Residual Network implementation based on FHE which allows the classification of encrypted images, ensuring that only the user can see the result. We suggest a circuit which reduces the memory requirements by more than [Formula: see text] compared to the most recent works, while maintaining a high level of accuracy and a short computational time. We implement the circuit using the well-known Cheon-Kim-Kim-Song (CKKS) scheme, which enables approximate encrypted computations. We evaluate the results from three perspectives: memory requirements, computational time and calculations precision. We demonstrate that it is possible to evaluate an encrypted ResNet20 in less than five minutes on a laptop using approximately 15[Formula: see text]GB of memory, achieving an accuracy of 91.67% on the CIFAR-10 dataset, which is almost equivalent to the accuracy of the plain model (92.60%).

Finding Boolean functions suitable for cryptographic primitives is a complex combinatorial optimization problem, since they must satisfy several properties to resist cryptanalytic attacks, and the space is very large, which grows super exponentially with the number of input variables. Recent research has focused on the study of Boolean functions that satisfy properties on restricted sets of inputs due to their importance in the development of the FLIP stream cipher. In this paper, we consider one such property, perfect balancedness, and investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy this property along with a good nonlinearity profile. We formulate the related optimization problem and define two encodings for the candidate solutions, namely the truth table and the weightwise balanced representations. Somewhat surprisingly, the results show that GA with the weightwise balanced representation outperforms GP with the classical truth table phenotype in finding highly nonlinear Weightwise Perfectly Balanced (WPB) functions. This is in stark contrast to previous findings on the evolution of balanced Boolean functions, where GP always performs best.

Spiking neural membrane systems are models of computation inspired by the natural functioning of the brain using the concepts of neurons and synapses, and represent a way of building computational systems of a biological inspiration. A variant of such a model, allowing to create new neurons and synapses during the computation, has been considered in the literature to attack computationally hard problems, like problems in the class NP. In this work, we investigate the computational properties of this variant, by proposing three solutions to computationally hard problems, by models with different features, and comparing them with those present in the literature. In particular, we first propose a nondeterministic solution for the NP-complete problem 3-SAT, by a model using dynamic organization of synapses. Then, we propose a deterministic solution for the same problem, by a model using neuron division and dissolution rules. Finally, we show that dissolution rules are not strictly necessary (by accepting a certain amount of slowdown in computing time), and that also problems beyond the class NP can be solved by systems with neuron division alone.

Abstract Spiking neural P systems are parallel and distributed computation devices which are inspired by the neuro-physiological behavior of biological neurons. In this paper we will present, with a tutorial approach, the main underlying ideas and the most interesting variants that have been proposed in the literature. In particular, we will discuss the results on the computational power of these models, both in terms of Turing completeness and of efficiency in solving hard problems, under different assumptions for information encoding, form and application of rules, and bounds on the main parameters defining the systems.

Abstract An interesting thread in the research of Boolean functions for cryptography and coding theory is the study of secondary constructions: given a known function with a good cryptographic profile, the aim is to extend it to a (usually larger) function possessing analogous properties. In this work, we continue the investigation of a secondary construction based on cellular automata (CA), focusing on the classes of bent and semi-bent functions. We prove that our construction preserves the algebraic degree of the local rule, and we narrow our attention to the subclass of quadratic functions, performing several experiments based on exhaustive combinatorial search and heuristic optimization through Evolutionary Strategies (ES). Finally, we classify the obtained results up to permutation equivalence, remarking that the number of equivalence classes that our CA-XOR construction can successfully extend grows very quickly with respect to the CA diameter.

Reaction systems are a computational model inspired by the bio-chemical reactions that happen inside biological cells. They have been and currently are studied for their many nice theoretical properties. They are also a useful modeling tool for biochemical systems, but in order to be able to employ them effectively in the field the presence of efficient and widely available simulators is essential. Here we explore three different algorithms and implementations of the simulation, comparing them to the current state of the art. We also show that we can obtain performances comparable to GPU-based simulations on real-world systems by using a carefully tuned CPU-based simulator.

Boolean functions have a prominent role in many real-world applications, which makes them a very active research domain. Throughout the years, various heuristic techniques proved to be an attractive choice for the construction of Boolean functions with different properties. One of the most important properties is nonlinearity, and in particular maximally nonlinear Boolean functions are also called bent functions. In this paper, instead of considering Boolean functions, we experiment with quaternary functions. The corresponding problem is much more difficult and presents an interesting benchmark as well as realworld applications. The results we obtain show that evolutionary metaheuristics, especially genetic programming, succeed in finding quaternary functions with the desired properties. The obtained results in the quaternary domain can also be translated into the binary domain, in which case this approach compares favorably with the state-of-the-art in Boolean optimization. Our techniques are able to find quaternary bent functions for up to 8 inputs, which corresponds to obtaining Boolean bent functions of 16 inputs.

We investigate the design of Orthogonal Latin Squares (OLS) by means of Genetic Algorithms (GA) and Genetic Programming (GP). Since we focus on Latin squares generated by Cellular Automata (CA), the problem can be reduced to the search of pairs of Boolean functions that give rise to OLS when used as CA local rules. As it is already known how to design CA-based OLS with linear Boolean functions, we adopt the evolutionary approach to address the nonlinear case, experimenting with different encodings for the candidate solutions. In particular, for GA we consider single bitstring, double bitstring and quaternary string encodings, while for GP we adopt a double tree representation. We test the two metaheuristics on the spaces of local rules pairs with n = 7 and n = 8 variables, using two fitness functions. The results show that GP is always able to generate OLS, even if the optimal solutions found with the first fitness function are mostly linear. On the other hand, GA achieves a remarkably lower success rate than GP in evolving OLS, but the corresponding Boolean functions are always nonlinear.

Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP-complete problems in polynomial time. In this paper we investigate families of tissue P systems with cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP-complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP-complete problem in polynomial time with logarithmic cell volume implies P = NP.

Self-protection mechanisms aim to improve security of software systems at runtime. They are able to automatically prevent and/or react to security threats by observing the state of a system and its execution environment, by reasoning on the observed state, and by applying enhanced security strategies appropriate for the current threat. Self-protection mechanisms complement traditional security solutions which are mostly static and focus on the boundaries of a system, missing in this way the overall picture of a system's security. This paper presents several self-protection mechanisms which have been developed in the context of a case study concerning a home banking system. Essentially, the mechanisms described in this paper aim to improve the security of the system in the following two scenarios: users' login and bank operations. Furthermore, the proposed self-protection mechanisms are presented through the taxonomy proposed in (Yuan, 2014).

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to P PP = P #P , the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between P PP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k.

Membrane systems, also called P systems, are an interesting class of parallel and distributed models of computation inspired by cell biology. They have been thoroughly investigated in the literature, both from the theoretical standpoint—analysing their computing power and efficiency—and as tools to model natural phenomena. In this article, we focus on the complexity theory of P systems with active membranes, a variant of P systems where the membranes themselves affect the applicability of rules and change (both in number and structurally) during computations. We summarize the main results on their space complexity, and describe some recent improvements related to time complexity, proved via a few general proof techniques.

We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition o

We consider the structure of the intestinal epithelial tissue and of cell–cell junctions as the biological model inspiring a new class of P systems. First we define the concept of cell polarity, a formal property derived from epithelial cells, which present morphologically and functionally distinct regions of the plasma membrane. Then we show two preliminary results for this new model of computation: on the theoretical side, we show that P systems with cell polarity are computationally (Turing) complete; on the modelling side, we show that the transepithelial movement of glucose from the intestinal lumen into the blood can be described by such a formal system. Finally, we define tissue P systems with cell polarity, where each cell has fixed connections to the neighbouring cells and to the environment, according to both the cell polarity and specific cell–cell junctions.