Search

The paper studies mappings F of binary vector spaces of large dimensions. The mappings are assumed to be represented by deep branching superpositions of local non-linear mappings of low-dimensional spaces. We propose and investigate the methods for construction of probabilistic linear and differential relations connecting the arguments and the values of a mapping F. Relation selection is based on optimization not the exact probability of satisfying these relations, but some approximation of it since it is easier to estimate. We prove theorems on exact values of the probability of satisfying the relations obtained, identify the shortcomings and features of the proposed approach to the relation construction and illustrate them by a number of examples. We discuss the role of the developed theory for cryptographic synthesis. [ABSTRACT FROM AUTHOR]

The paper is concerned with relations between the correlation-immunity (stability) and the perfectly balancedness of Boolean functions. It is shown that an arbitrary perfectly balanced Boolean function fails to satisfy a certain property that is weaker than the 1-stability. This result refutes some assertions by Markus Dichtl. On the other hand, we present new results on barriers of perfectly balanced Boolean functions which show that any perfectly balanced function such that the sum of the lengths of barriers is smaller than the length of variables, is 1-stable. [ABSTRACT FROM AUTHOR]

The paper is concerned with problems in steganography on the detection of embeddings and statistical estimation of positions at which message bits are embedded. Binary stationary Markov chains with known or unknown matrices of transition probabilities are used as mathematical models of cover sequences (container files). Based on the runs statistics and the likelihood ratio statistic, statistical tests are constructed for detecting the presence of embeddings. For a family of contiguous alternatives, the asymptotic power of statistical tests based on the runs statistics is found. An algorithm of polynomial complexity is developed for the statistical estimation of positions with embedded bits. Results of computer experiments are presented. [ABSTRACT FROM AUTHOR]

The paper is concerned with n-place Boolean functions not admitting implicents of k variables, 1 ¢ k < n. Estimates for the minimal possible weight w(n, k) of such functions are obtained. It is shown that w(n, 1) = 2, n = 2, 3,…, and w(n, 2) È log2n as n Ù ∞, and moreover, for k > 2 there exists n0 such that w(n, k) > 2k-2 - log2n for all n > n0. [ABSTRACT FROM AUTHOR]

In this paper we suggest a combined method for solving systems of Boolean polynomial equations based on testing a part of variables and using monomial compatibility criteria for dropping out some values of the tested variables. The complexity of the method is estimated for various parameters of the system. [ABSTRACT FROM AUTHOR]

The McEliece cryptosystem is one of the oldest public-key cryptosystems. It was proposed by R. J. McEliece in 1978. The McEliece cryptosystem is based on a certain NP-hard problem in the coding theory. In this paper we consider a generalisation of the McEliece cryptosystem proposed by V. M. Sidelnikov in 1994. The McEliece–Sidelnikov cryptosystem is based on u-fold use of the Reed–Muller codes RM( r, m). This research is devoted to questions related to the space of equivalent secret keys of the new cryptosystem, that is, secret keys generating identical public keys. We study the structure of the set of public keys of the McEliece–Sidelnikov cryptosystem for an arbitrary number u of blocks. For the case of two blocks we describe all equivalence classes of secret keys with representatives of a special form. [ABSTRACT FROM AUTHOR]

Proofs of security for practical signature schemes are known in idealised models only. In the present paper, we consider the tamper-proof device model that does not use ideal primitives. Instead of access to a random oracle each participant is provided with tamper-proof device implementing a private-key cryptosystem. The hash-value of a message to be signed is submitted to the tamper-proof device for encryption and this encrypted value is used in the signature generation algorithm. In this model, we prove, modulo a physical assumption, a necessary and sufficient condition for security of the GOST signature scheme. [ABSTRACT FROM AUTHOR]

The strict avalanche criterion was introduced by Webster and Tavares while studying some cryptographic functions. We say that a binary function f(x), x ∈ Vn, satisfies this criterion if replacing any coordinate of the vector x by its complement changes the values of f(x) exactly in a half of cases. In this paper we establish an upper bound for the number of such functions for n large enough. [ABSTRACT FROM AUTHOR]

Nonlinear invariants of round transformations in XSL-schemes are studied. The emphasis is on invariants which may be found by means of the approach suggested at the conference ASIACRYPT 2016. Some known results on the inertia groups of decomposable functions are used to describe conditions on S-boxes and matrices of XSL-schemes which are necessary for the existence of such invariants. It is shown that for a number of schemes these conditions are not satisfied. [ABSTRACT FROM AUTHOR]

We consider polynomials over rings such that the polynomials represent Latin squares and define a group operation over the ring. We introduce the notion of a group polynomial, describe a number of properties of these polynomials and the groups generated. For the case of residue rings ℤrn, where r is a prime number, we give a description of groups specified by polynomials and identify a class of group polynomials that can be used to construct controlled cryptographic transformations. [ABSTRACT FROM AUTHOR]

A new approach to the study of algebraic, combinatorial, and cryptographic properties of Boolean functions is proposed. New relations between functions have been revealed by consideration of an injective mapping of the set of Boolean functions onto the sphere in a Euclidean space. Moreover, under this mapping some classes of functions have extremely regular localizations on the sphere. We introduce the concept of curvature of a Boolean function, which characterizes its proximity (in some sense) to maximally nonlinear functions. [ABSTRACT FROM AUTHOR]

We consider the functional system of vector functions of many-valued logic with the naturally defined operation of superposition and construct examples of closed classes of special type without a basis and with a countable basis. [ABSTRACT FROM AUTHOR]

We consider a sequence of almost critical branching processes with immigration supposing that the immigration process is weakly stationary. The rate of growth and asymptotic properties of fluctuations of such branching processes are investigated. [ABSTRACT FROM AUTHOR]

A classification of correlation-immune and minimal corelation-immune Boolean function of 4 and 5 variables with respect to the Jevons group is given. Representatives of the equivalence classes of correlationimmune functions of 4 and 5 variables are decomposed into minimal correlation-immune functions. Characteristics of various decompositions of the constant function 1 into minimal correlation-immune functions are presented. [ABSTRACT FROM AUTHOR]

The multiplicative (or conjunctive) complexity of a Boolean function f(x1, . . . , xn) (respectively, of a system of Boolean functions F = {f1, . . . , fm}) is the smallest number of AND gates in circuits in the basis {x&y, x ⊕ y, 1} implementing the function f (respectively, all the functions of system F). The multiplicative complexity of a function f (of a system of functions F) will be denoted by μ(f) (respectively, μ(F)). It will be shown that μ(f) = n − 1 if a function f(x1, . . . , xn) is representable as x1x2 . . . xn ⊕ q(x1, . . . , xn), where q is a function of degree two (n ≥ 3).Moreover,we show that μ(f) ≤ n−1 if a function f(x1, . . . , xn) is representable as a XOR sum of two multiaffine functions. Furthermore, μ(F) = n−1 if F = {x1x2 . . . xn , f(x1, . . . , xn)},where f is a function of degree two or a multiaffine function. [ABSTRACT FROM AUTHOR]

The hash algorithms of the MDx family involve cyclic shifts, computation of primitive Boolean functions, and addition of constants. So far, very few works have been published in which the authors attempt to explain the impact that the choice of constants, shifts, and Boolean functions has on the cryptographic properties of the algorithms. G. A. Karpunin and H. T. Nguyen suggested a model in which the resistance against differential cryptanalysis may be quantitatively estimated in terms of the number of solutions of a special equation. In this work, in the framework of the aforementioned model, an equation for the MD5 hash function is derived. Examination of one Boolean function and one value of the cyclic shift through exhaustive search requires 2128 operations of computation of the step of the hash function. The formulas suggested in the present work allow to reduce the complexity of the examination to 244 arithmetic operations. [ABSTRACT FROM AUTHOR]

In the context of the approach given in Shannon's research [[Bell Syst. Tech. J. 28: 656--715, 1949]], of interest are the mixing properties of operations in a finite field, in particular, the action of each operation on cosets with respect to the action of the second operation. The good mixing properties give a possibility to construct on this base good cryptographic algorithms. [ABSTRACT FROM AUTHOR]

The pseudorandom number generator (PRNG) based on the transformation Fc( x) == x ++ ( x2 ∨∨ c) (mod 2 n) was suggested by Klimov and Shamir in 2002. The function Fc( x) is transitive modulo 2 n if and only if either c ≡≡ 5 (mod 8) or c≡≡ 7 (mod 8). We consider properties of the distribution of the pairs ( xi, Fc( xi)) for various c ∈∈ Z/2 n Z and demonstrate that their statistical properties are unsatisfactory, most notably for c ≥≥ 2 n/3. We show that in the case n == 32, at most 9 distinct pairs ( xi, Fc( xi)) are needed to find the value of c with probability P≥≥ 0.999. [ABSTRACT FROM AUTHOR]

We study properties of Boolean functions with a finite-length barrier and suggest a criterion for a function to possess a barrier. We introduce the notion of a Boolean function without prediction which describes certain positive cryptographic properties of the corresponding transformations of binary sequences. We suggest a criterion for a Boolean function to belong to the class of functions without prediction. [ABSTRACT FROM AUTHOR]

We consider a statistical model of the so-called steganography, which is a new rapidly developing field of information protection. We suggest one possible variant of a hidden embedding of a secret information into nonsecret data transmitted and analyse probabilistic properties of the model. [ABSTRACT FROM AUTHOR]

We consider the relations between the level of affinity and other cryptographic parameters of Boolean functions such as nonlinearity, the order of correlation, and algebraic immunity. It is proved that the problem of finding the level of affinity for certain class of functions is an NP-hard problem. [ABSTRACT FROM AUTHOR]

Homomorphisms of many-sorted algebraic systems are considered, under which the elements of basic sets, operators, and predicates may be related; such homomorphisms are used for setting and solving equations (relations) over many-sorted algebraic systems among the unknowns of which may occur the elements of basic sets, operators, and predicates. [ABSTRACT FROM AUTHOR]

We study the McEliece cryptosystem with u-fold use of binary Reed–Muller codes RM(r, m). This modification of the McEliece cryptosystem was proposed by V. M. Sidelnikov in 1994 and combines high cryptographic security, transmission rate close to one, and moderate complexity of both enciphering and deciphering. For arbitrary values of the parameters u, r, and m we give an upper bound for the cardinality of the set of public keys of this cryptosystem and calculate its exact value in the case of u = 2 and r = 1. [ABSTRACT FROM AUTHOR]