Search

This paper describes new, simple, recursive methods of construction for orientable sequences, i.e. periodic binary sequences in which any $n$ -tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine $n$ consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Dai et al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences. [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]

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]

We formulate and study the problem of ON-OFF privacy. ON-OFF privacy algorithms enable a user to continuously switch his privacy between ON and OFF. An obvious example is the incognito mode in internet browsers. But beyond internet browsing, ON-OFF privacy can be a desired feature in most online applications. The challenge is that the statistical correlation over time of a user’s online behavior can lead to leakage of information. We consider the setting in which a user is interested in retrieving the latest message generated by one of $N$ sources. The user’s privacy status can change between ON and OFF over time. When privacy is ON the user wants to hide his request. Moreover, since the user’s requests depend on personal attributes such as age, gender, and political views, they are typically correlated over time. As a consequence, the user cannot simply ignore privacy when privacy is OFF. We model the correlation between user’s requests by an $N$ state Markov chain. The goal is to design query schemes with optimal download rate, that preserve privacy in an ON-OFF privacy setting. In this paper, we present inner and outer bounds on the achievable download rate for $N$ sources. We also devise an efficient algorithm to construct an ON-OFF privacy scheme achieving the inner bound and prove its optimality in the case $N=2$ sources. For $N > 2$ , finding tighter outer bounds and efficient constructions of ON-OFF privacy schemes that would achieve them remains an open question. [ABSTRACT FROM AUTHOR]