Search

Mean hitting time for random walks on a network, defined as the average of hitting times over all possible pairs of nodes, has found a large variety of applications in many areas. In this paper, we first prove that among all $N$ -node networks, the complete graph has the minimum mean hitting time $N-1$ , which scales linearly with network size. We then study a random walk mobility model with location heterogeneity, modeled by scale-free networks, which are ubiquitous in realistic systems such as P2P networks. For this purpose, we consider random walks on two sparse scale-free small-world networks. By using the connection between random walks and electrical networks, we derive explicit formulas about mean hitting time for both networks, the dominant scaling of which exhibits the same behavior as that of complete graphs. This paper demonstrates that heterogeneous sparse networks can have low-mean hitting time with a behavior similar to that of dense complete graphs, which is instrumental in designing networks, where search is fast between any pair of nodes. [ABSTRACT FROM AUTHOR]

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta $ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta $ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$ , and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$ ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper. [ABSTRACT FROM AUTHOR]

The inverse function x → x−1 on F2n, is one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x−1) + L2(x) over F2n if n ≥ 5, where L1,L2 are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics. [ABSTRACT FROM AUTHOR]

Linear complementary dual (LCD) codes are a class of linear codes introduced by Massey in 1964. LCD codes have been extensively studied in literature recently. In addition to their applications in data storage, communications systems, and consumer electronics, LCD codes have been employed in cryptography. More specifically, it has been shown that LCD codes can also help improve the security of the information processed by sensitive devices, especially against so-called side-channel attacks (SCA) and fault non-invasive attacks. In this paper, we are interested in the construction of particular algebraic geometry LCD codes which could be good candidates to be resistant against SCA. We firstly provide a construction scheme for obtaining LCD codes from any algebraic curve. Then, some explicit LCD codes from elliptic curves are presented. Maximum distance separable (MDS) codes are of the most importance in coding theory due to their theoretical significance and practical interests. In this paper, all the constructed LCD codes from elliptic curves are MDS or almost MDS. Some infinite classes of LCD codes from elliptic curves are optimal due to the Griesmer bound. Finally, we also derive some explicit LCD codes from hyperelliptic curves and Hermitian curves. [ABSTRACT FROM AUTHOR]

In this paper, we show that the maximum number of bent component functions of a vectorial function F:GF(2)^n\to GF(2)^n is 2^n-2^n/2 . We also show that it is very easy to construct such functions. However, it is a much more challenging task to find such functions in polynomial form F\in GF(2^n)[x] , where F has only a few terms. The only known power functions having such a large number of bent components are x^{d} , where d=2^{n/2}+1 . In this paper, we show that the binomials F^i(x)=x^2^i(x+x^2^n/2) also have such a large number of bent components, and these binomials are inequivalent to the monomials x^2^n/2+1 if 0

In a memristor crossbar array, functioning as a memory array, a memristor is positioned on each row–column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this paper, we study the sneak path problem in crossbar arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are modeling the error channel induced by sneak paths, a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method, we match a constraint on the array content that guarantees sneak-path free readout, determine the resulting capacity, and provide an efficient encoder that achieves the capacity. [ABSTRACT FROM PUBLISHER]

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure a Boolean function’s resistance to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. Some of the binary LCD codes presented in this paper are optimal. These binary LCD codes have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems. [ABSTRACT FROM AUTHOR]

This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n,m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Tr_{m}^{n} (\lambda x^{d}) from \mathbb {F}_{2^{n}} to \mathbb F2^{m} (where m is a divisor of n ) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratović-Ribić et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n,m) -functions. No tight upper bound is known when \frac n2

Let $n$ be a positive integer and $p$ a prime. The power mapping $x^{p^{n}-3}$ over ${\mathbb {F}}_{p^{n}}$ has desirable differential properties, and its differential spectra for $p=2,\,3$ have been determined. In this paper, for any odd prime $p$ , by investigating certain quadratic character sums and some equations over ${\mathbb {F}}_{p^{n}}$ , we determine the differential spectrum of $x^{p^{n}-3}$ with a unified approach. The obtained result shows that for any given odd prime $p$ , the differential spectrum can be expressed explicitly in terms of $n$. Compared with previous results, a special elliptic curve over ${\mathbb {F}}_{p}$ plays an important role in our computation for the general case $p \ge 5$. [ABSTRACT FROM AUTHOR]

In this paper, we present two new families of APN functions. The first family is in bivariate form $\big (x^{3}+xy^{2}+ y^{3}+xy, x^{5}+x^{4}y+y^{5}+xy+x^{2}y^{2} \big)\,\,\vphantom {_{\int _{\int }}}$ over ${\mathbb F}_{2^{m}}^{2}$. It is obtained by adding certain terms of the form $\sum _{i}(a_{i}x^{2^{i}}y^{2^{i}},b_{i}x^{2^{i}}y^{2^{i}})$ to a family of APN functions recently proposed by Gölo&gcaron;lu. The $\vphantom {_{\int _{\int }}}$ second family has the form $L(z)^{2^{m}+1}+vz^{2^{m}+1}$ over ${\mathbb F}_{{2^{3m}}}$ , which generalizes a family of APN functions by Bracken et al. from 2011. By calculating the $\Gamma $ -rank of the constructed APN functions over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , we demonstrate that the two families are CCZ-inequivalent to all known families. In addition, the two new families cover two known sporadic APN instances over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , which were found by Edel and Pott in 2009 and by Beierle and Leander in 2021, respectively. [ABSTRACT FROM AUTHOR]

Highly nonlinear functions (perfect nonlinear, maximum nonlinear, etc.) between finite fields have been studied in numerous papers. These concepts have been generalized first to finite abelian groups and then to finite nonabelian groups. In 2011, Poinsot and Pott introduced a new class of highly nonlinear functions between finite nonabelian groups, which are closely related to maximum nonlinear functions. They found such a function by a computer search, and proposed to find more such functions by theoretical constructions. Since then there is no progress in this topic. In this paper we continue the research in the direction proposed by Poinsot and Pott. Our purpose is to study the properties and constructions of this new class of highly nonlinear functions, called the absolute maximum nonlinear functions in this paper. In particular, for arbitrary finite (abelian or nonabelian) groups $K$ and $N$ with an absolute maximum nonlinear function $f: K \to N$ , we will prove that $N$ has to be abelian, and $f$ cannot be perfect nonlinear if $K$ is not abelian. Then we investigate the numerical constraints on the groups that have absolute maximum nonlinear functions. These constraints will eliminate the existence of absolute maximum nonlinear functions for many finite nonabelian groups. More importantly, using these constraints we will develop a method to construct absolute maximum nonlinear functions for some groups. In particular, we will determine all absolute maximum nonlinear functions on $A_4$ (the alternating group of degree 4). Furthermore, a general method to construct new absolute maximum nonlinear functions from the old ones will be given. [ABSTRACT FROM AUTHOR]

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called $t$ -private if the identity of the file remains concealed even if $t$ of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases. [ABSTRACT FROM AUTHOR]

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.’s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate $P_{5}$ and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.’s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258 (278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance. [ABSTRACT FROM AUTHOR]

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 27, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight. [ABSTRACT FROM AUTHOR]

In this paper, by the Hasse-Weil bound, we determine the necessary and sufficient condition on coefficients $a_{1},a_{2},a_{3}\in {\mathbb F} _{2^{n}}$ with $n=2m$ such that $f(x) = {x}^{3\cdot 2^{m}} + a_{1}x^{2^{m+1}+1} + a_{2} x^{2^{m}+2} + a_{3}x^{3}$ is an APN function over ${\mathbb F}_{2^{n}}$. Our work together with the follow-up work by Chase and Lisoněk indicates that all such APN quadrinomials $f(x)$ are affine equivalent to two instances of Gold functions, which resolves the first half of an open problem by Carlet at the International Workshop on the Arithmetic of Finite Fields, 83-107, 2014. [ABSTRACT FROM AUTHOR]

In a prior paper (Ellingsen et al., 2020), two of us, along with P. Ellingsen, P. Felke, and A. Tkachenko, defined a new (output) multiplicative differential and the corresponding $c$ -differential uniformity, which has the potential of extending differential cryptanalysis. Here, we continue the work by looking at some APN functions through the mentioned concept and showing that their $c$ -differential uniformity increases significantly in some cases. [ABSTRACT FROM AUTHOR]

Resistive memories store information in a crossbar arrangement of two-terminal devices that can be programmed to patterns of high or low resistance. While extremely compact, this technology suffers from the “sneak-path” problem: certain information patterns cannot be recovered, as multiple low resistances in parallel make a high resistance indistinguishable from a low resistance. In this paper, a multi-layer device is considered, and the number of bits it can store is derived exactly and asymptotic bounds are developed. The information density of a series of isolated arrays with extreme aspect ratios is derived in the single- and multi-layer cases with and without peripheral selection circuitry. This density is shown to be non-zero in the limit, unlike that of the arrays with moderate aspect ratios previously considered. A simple encoding scheme that achieves capacity asymptotically is presented. [ABSTRACT FROM AUTHOR]

Non-volatile memories suffer from two challenges due to their physical and system-level constraints. One challenge is limited memory lifetime, also called the endurance problem. The other is the difficulty in deleting data securely, called the insecure deletion problem. This paper proposes a coding scheme that addresses both challenges jointly. It studies the secure write-efficient memory (WEM) by analyzing its rewriting-rate equivocation region and secrecy rewriting capacity. It also presents an optimal code construction for a large family of secure WEM channels. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]

In EUROCRYPT 2018, Cid et al. introduced a new concept on the cryptographic property of S-boxes: boomerang connectivity table (BCT for short) for evaluating the subtleties of boomerang-style attacks. Very recently, BCT and the boomerang uniformity, the maximum value in BCT, were further studied by Boura and Canteaut. In this paper, aiming at providing new insights, we show some new results about BCT and the boomerang uniformity of permutations in terms of theory and experiment. First, we present an equivalent technique to compute BCT and the boomerang uniformity, which seems to be much simpler than the original definition by Cid et al. Second, thanks to Carlet’s idea, we give a characterization of functions $f$ from $ {\mathbb F}_{2}^{n}$ to itself with boomerang uniformity $\delta _{f}$ by means of the Walsh transform. Third, by our method, we consider boomerang uniformities of some specific permutations, mainly the ones with low differential uniformity. Finally, we obtain another class of 4-uniform BCT permutation polynomials over $ {\mathbb F}_{2^{n}}$. [ABSTRACT FROM AUTHOR]

Functions with low differential uniformity have important applications in cryptography, coding theory, and sequence design. The differential spectrum of a cryptographic function is of great interest for estimating its resistance to some variants of differential cryptanalysis. Finding power permutations (i.e., monomial bijective mappings) over finite fields with low differential uniformity and determining their differential spectra have received a lot of attention over the past two decades. The objective of this paper is to study the differential properties of the well-known Kasami power permutations $x^{p^{2k}-p^{k}+1}$ over $ {\mathrm {GF}}(p^{n})$ , where $p$ is an odd prime and $k$ is an integer with $\gcd (n,k)=1$. It turns out that this family of monomials is differentially $(p+1)$ -uniform. Our result in the case of $p=3$ gives an affirmative solution to a recent conjecture by Xu, Cao, and Xu. Most notably, the differential spectrum of this family of power permutations is completely determined. [ABSTRACT FROM AUTHOR]

We introduce a new transform on Boolean functions generalizing the Walsh–Hadamard transform. For Boolean functions $q$ and $f$ , the $q$ -transform of $f$ measures the proximity of $f$ to the set of functions obtained from $q$ by change of basis. This has implications for security against certain algebraic attacks. In this paper, we derive the expected value and second moment (Parseval’s equation) of the $q$ -transform, leading to a notion of $q$ -bentness. We also develop a Poisson summation formula, which leads to a proof that the $q$ -transform is invertible. [ABSTRACT FROM AUTHOR]

Substitution boxes (S-boxes) play a central role in the modern design of iterative block ciphers. While in substitution-permutation networks the S-boxes are bijective, thus ensuring the invertibility of the encryption algorithm, the property of being bijective is not mandatory for Feistel kind of networks. In this paper, two methods of constructing highly nonlinear balanced S-boxes (whose nonlinearity > 2^n-1-2^n/2 is better than the nonlinearity of the commonly used inverse S-box) with good algebraic and differential properties are given. The first method employs two vectorial Boolean functions from the Maiorana–McFarland class that need to fulfill certain conditions. In particular, these conditions are shown to be satisfied by maximum length sequences. The second method is based on a suitable modification of a certain class of vectorial bent functions. The differential properties of these boxes, measured as a deviation from an optimal uniform distribution, also appear to be better than those of the inverse S-box. Both methods are susceptible to further optimizations of the relevant cryptographic parameters due to the underlying design ideas. [ABSTRACT FROM AUTHOR]

The existence of almost perfect nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in 2009. However it is still unknown whether this example can be generalized to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on $(4k+2)$ variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalize this family, and we completely solve the two open problems raised by Perrin et al. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four. [ABSTRACT FROM PUBLISHER]

For every positive integers $n$ and $m$ and every even positive integer $\delta $ , we derive inequalities satisfied by the Walsh transforms of all vectorial $(n,m)$ -functions and prove that the case of equality characterizes differential $\delta $ -uniformity. This provides a generalization to all differentially $\delta $ -uniform functions of the characterization of Almost Perfect Nonlinear (APN) functions due to Chabaud and Vaudenay, by means of the fourth moment of the Walsh transform. Such generalization has been missing since the introduction of the notion of differential uniformity by Nyberg in 1994 and since Chabaud-Vaudenay’s result in the same year. Moreover, for each even $\delta \geq 2$ , we find several (in fact, an infinity of) such characterizations. In particular, when $\delta =2$ and $\delta =4$ , we have that, for any $(n,n)$ -function [resp. any $(n,n-1)$ -function)], the arithmetic mean of $W_{F}^{2}(u_{1},v_{1})W_{F}^{2}(u_{2},v_{2})W_{F}^{2}(u_{1}+u_{2},v_{1}+v_{2})$ when $u_{1},u_{2}$ range independently over ${\mathbb F}_{2}^{n}$ and $v_{1},v_{2}$ are nonzero and distinct and range independently over ${\mathbb F}_{2}^{m}$ is at least $2^{3n}$ , and that $F$ is APN (resp. is differentially 4-uniform) if and only if this arithmetic mean equals $2^{3n}$ (which is the value we would get with a bent function if such function could exist). These inequalities give more knowledge on the Walsh spectrum of $(n,m)$ -functions. We deduce in particular a property of the Walsh support of highly nonlinear functions. We also consider the completely open question of knowing if the nonlinearity of APN functions is necessarily non-weak (as it is the case for known APN functions); we prove new lower bounds which cover all power APN functions (and hence a large part of known APN functions), which explain why their nonlinearities are not bad, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic). [ABSTRACT FROM AUTHOR]

We present STeP-archives, a novel and practical data archival architecture, where an attacker who wants to censor or tamper with a data object must cause obvious collateral damage to a large number of other objects in the system. We use maximum distance separable erasure codes to entangle unrelated data blocks and provide redundancy against storage failures, which results in an archive with constant time read–write operations. We show a tradeoff for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the problem is asymmetric between attackers and defenders; while a defender can efficiently recover from imperfect attacks, an attacker must solve an NP-hard problem to find a perfect (irrecoverable) attack that minimizes collateral damage to other data objects, or even approximate its size. We then study efficient sample-heuristic attack algorithms that lead to irrecoverable but large damage and demonstrate how some strategies and parameter choices allow to resist these sample attacks. Finally, we provide empirical evidence that an attacker who wants to irrecoverably tamper with a document archived long enough must destroy a constant fraction of the archive. [ABSTRACT FROM PUBLISHER]

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^{i} \circ x^{1/j}$ of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions $x^{i} \circ L \circ x^{1/j}$ for a linear polynomial $L$ , show how the Kasami functions in odd dimension can be expressed in this way with $i=j$ being a Gold exponent and compute all APN functions of this form for $n \le 9$ and for $L$ with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent $\sum _{i = 1}^{k-1} 2^{2ni} - 1$ which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for $n \le 35$ , and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for $n\leq 21$ show that these points cover about 2/3 of the field. [ABSTRACT FROM AUTHOR]

We study second-order consensus dynamics with random additive disturbances. To quantify the robustness of these networks, we investigate three different performance measures: the steady-state variance of pairwise differences between vertex states, the steady-state variance of the deviation of each vertex state from the average, and the total steady-state variance of the system. We show that these performance measures are closely related to the concept of biharmonic distance; the square of the biharmonic distance plays a similar role in the system performance as resistance distance plays in the performance of first-order noisy consensus dynamics. We then define the new concepts of biharmonic Kirchhoff index and vertex centrality based on the biharmonic distance. We further derive analytical results for the performance measures and concepts for complete graphs, star graphs, cycles, and paths, and we use this analysis to compare the asymptotic behavior of the steady-state variance in first- and second-order systems. Finally, we propose a theoretically guaranteed approximation algorithm to estimate the total steady-state variance, which has a complexity of nearly linear time with respect to the number of edges. Extensive experiments results validate both efficiency and accuracy of our algorithm. [ABSTRACT FROM AUTHOR]

The Difference Distribution Table (DDT) and the differential uniformity play a major role for the design of substitution boxes in block ciphers, since they indicate the function’s resistance against differential cryptanalysis. This concept was extended recently to $c$ -DDT and $c$ -differential uniformity, which have the potential of extending differential cryptanalysis. Recently, a new theoretical tool, the Boomerang Connectivity Table (BCT) and the corresponding boomerang uniformity were introduced to quantify the resistance of a block cipher against boomerang-style attacks. Here we concentrate on two classes (introduced recently) of permutation polynomials over finite fields of even characteristic. For one of these, which is an involution used to construct a 4-uniform permutation, we explicitly determine the $c$ -DDT entries and BCT entries. For the second type of function, which is a differentially 4-uniform function, we give bounds for its $c$ -differential and boomerang uniformities. [ABSTRACT FROM AUTHOR]

A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length $2^{2m}-1$ with relative decimation $d=2^{m+2}-3$ , where $m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation $f(x)=x^{d}$ over a finite field of order $2^{2m}$ and at most five distinct nonzero weights in the cyclic code of length $2^{2m}-1$ with two primitive nonzeros $\alpha $ and $\alpha ^{d}$. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when $m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values. [ABSTRACT FROM AUTHOR]

All almost perfect nonlinear (APN) permutations that we know to date admit a special kind of linear self-equivalence, i.e., there exists a permutation G in their CCZ-equivalence class and two linear permutations A and B, such that G ° A = B ° G. After providing a survey on the known APN functions with a focus on the existence of self-equivalences, we search for APN permutations in dimension 6, 7, and 8 that admit such a linear self-equivalence. In dimension six, we were able to conduct an exhaustive search and obtain that there is only one such APN permutation up to CCZ-equivalence. In dimensions 7 and 8, we performed an exhaustive search for all but a few classes of linear self-equivalences and we did not find any new APN permutation. As one interesting result in dimension 7, we obtain that all APN permutation polynomials with coefficients in F2 must be (up to CCZ-equivalence) monomial functions. [ABSTRACT FROM AUTHOR]

We investigate the differential properties of a vectorial Boolean function $G$ obtained by modifying an APN function $F$. This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of $G$ via the derivatives of $F$ , and deduce an algorithm for searching for APN functions whose values differ from those of $F$ only on a given set $U \subseteq \mathbb {F}_{2^{n}}$. We introduce a value $\Pi _{F}$ associated with any $F$ , which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function $F$ and the closest APN function in terms of $\Pi _{F}$. We show how $\Pi _{F}$ can be computed efficiently for $F$ quadratic. We compute $\Pi _{F}$ for all known APN functions over $\mathbb {F}_{2^{n}}$ up to $n \le 8$. This is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function $F(x) = x^{3}$ , and observe that it tends to infinity with $n$. Finally, we describe how to efficiently find all sets $U$ such that, taking $G(x) = F(x) + v$ for $x \in U$ and $G(x) = F(x)$ for $x \notin U$ , $G(x)$ is APN. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing the number of spanning trees in a connected graph with $n$ vertices and $m$ edges, by adding at most $k$ edges from a given set of $q$ candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of $(1 - 1/e - \epsilon)$ in the exponent of the number of spanning trees for any $\epsilon > 0$ in time $\widetilde {O}(m \epsilon ^{-1} + (n + q) \epsilon ^{-3})$ , where $\widetilde {O}(\cdot)$ hides ${\mathrm{ poly}}\log (n)$ factors. Our running time is optimal with respect to the input size, up to logarithmic factors, and improves on the $O(n^{3})$ running time of the previous proposed greedy algorithm with an approximation ratio $(1 - 1/e)$ in the exponent. Notably, the independence of our running time of $k$ is novel, compared to conventional top- $k$ selections on graphs that usually run in $\Omega (mk)$ time. 2) We show the exponential inapproximability of this problem by proving that there exists a constant $c > 0$ such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within $(1 - c)$. [ABSTRACT FROM AUTHOR]

We study the problem of existence of APN functions of algebraic degree n over {\mathbb F}_{2^{n}} . We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over \mathbb F2^{n} the function x^{2^{n}-1}+F(x) is not APN, and changing a value of $F$ in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree $n$ . [ABSTRACT FROM AUTHOR]