### Article

## Feebly secure cryptographic primitives

In 1992, A. Hiltgen provided first constructions of provably (slightly) secure cryptographic primitives, namely feebly one-way functions. These functions are provably harder to invert than to compute, but the complexity (viewed as the circuit complexity over circuits with arbitrary binary gates) is amplified only by a constant factor (in Hiltgen’s works, the factor approaches 2). In traditional cryptography, one-way functions are the basic primitive of private-key schemes, while public-key schemes are constructed using trapdoor functions. We continue Hiltgen’s work by providing examples of feebly secure trapdoor functions where the adversary is guaranteed to spend more time than honest participants (also by a constant factor). We give both a (simpler) linear and a (better) non-linear construction.

The volume contains proceedings of the XIII International symposium on problems of redundancy in information and control systems.

The volume is to contain the proceedings of the 13th conference AGCT as well as the proceedings of the conference Geocrypt. The conferences focus on various aspects of arithmetic and algebraic geometry, number theory, coding theory and cryptography. The main topics discussed at conferences include the theory of curves over finite fields, theory of abelian varieties both over global and finite fields, theory of zeta-functions and L-functions, asymptotic problems in number theory and algebraic geometry, algorithmic aspects of the theory of curves and abelian varieties, the theory of error-correcting coding and particularly that of algebro-geometric codes, cryptographic issues related to algebraic curves and abelian varieties.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.

The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only nonmonotone element was completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates sufficient for realization of any Boolean function 𝑓 (the inversion complexity of the function 𝑓) is ]log_2(𝑑(𝑓) + 1)[. Here 𝑑(𝑓) is the maximum number of the changes of the function 𝑓 from larger to smaller values over all increasing chains of tuples of variables values. In the present paper, Markov’s result is extended to the case of realization of 𝑘-valued logic functions. We show that the minimum number of Post negations (that is, functions of the form 𝑥 + 1 (mod 𝑘)) that is sufficient to realize an arbitrary function of 𝑘-valued logic is ]log_2(𝑑(𝑓) + 1)[ and the minimum number of Łukasiewicz negation (that is, functions of the form 𝑘 − 1 − 𝑥) that is sufficient to realize an arbitrary 𝑘-valued logic function is ]log_𝑘(𝑑(𝑓)+1)[. In addition, another classical Markov’s result on the inversion complexity of systems of Boolean functions is extended to the setting of systems of functions of 𝑘-valued logic.

Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The non-monotone part of the basis consist of the only negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function *f* equal ]log2(*d*(*f*)+1)[. Here *d*(*f*) is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples.mThe aim of this paper is to prove that the complexity of a boolean function *f* realization equal ρ]log2(*d*(*f*)+1)[-O(1), where ρ is the minimum weight of non-monotone basis elements. Similar generalization of classical Markov result concerning realization of boolean funciton systems was obtained.

Mobile social networks (MSNs) are the networks of individuals with similar interests connected to each other through their mobile devices. Recently, MSNs are proliferating fast supported by emerging wireless technologies that allow to achieve more efficient communication and better networking performance across the key parameters, such as lower delay, higher data rate, and better coverage. At the same time, most of the MSN users do not fully recognize the importance of security on their handheld mobile devices. Due to this fact, multiple attacks aimed at capturing personal information and sensitive user data become a growing concern, fueled by the avalanche of new MSN applications and services. Therefore, the goal of this work is to understand whether the contemporary user equipment is susceptible to compromising its sensitive information to the attackers. As an example, various information security algorithms implemented in modern smartphones are thus tested to attempt the extraction of the said private data based on the traces registered with inexpensive contemporary audio cards. Our obtained results indicate that the sampling frequency, which constitutes the strongest limitation of the off-the-shelf side-channel attack equipment, only delivers low-informative traces. However, the success chances to recover sensitive data stored within a mobile device may increase significantly when utilizing more efficient analytical techniques as well as employing more complex attack equipment. Finally, we elaborate on the possible utilization of neural networks to improve the corresponding encrypted data extraction process, while the latter part of this paper outlines solutions and practical recommendations to protect from malicious side-channel attacks and keep the personal user information protected.

Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work. To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary. Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.