On the weightwise nonlinearity of weightwise perfectly balanced functions

in Discrete Applied Mathematics (2022), 322

In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this ... [more ▼]

In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this criterion can take over WPB functions, deriving theoretic bounds, and exhibiting the first values. We emphasize the link between this minimum and weightwise affine functions, and we prove that for n≥8 no n-variable WPB function can have this property. Then, we focus on the distribution and the maximum of this criterion over the set of WPB functions. We provide theoretic bounds on the latter and algorithms to either compute or estimate the former, together with the results of our experimental studies for n up to 8. Finally, we present two new constructions of WPB functions obtained by modifying the support of linear functions for each set of fixed Hamming weight. This provides a large corpus of WPB function with proven weightwise nonlinearity, and we compare the weightwise nonlinearity of these constructions to the average value, and to the parameters of former constructions in 8 and 16 variables. [less ▲]

Provably Solving the Hidden Subset Sum Problem via Statistical Learning

in Mathematical Cryptology (2022, March), 1

At Crypto ’99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. As an ... [more ▼]

At Crypto ’99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. As an application, they showed how to break the Boyko et al. fast generator of random pairs (x, g x(mod p)). The Nguyen-Stern algorithm works quite well in practice for moderate values of n, but its complexity is exponential in n. A polynomial-time variant was recently described at Crypto 2020, based on a multivariate technique, but the approach is heuristic only. In this paper, we describe a proven polynomial-time algorithm for solving the hidden subset-sum problem, based on statistical learning. In addition, we show that the statistical approach is also quite efficient in practice: using the FastICA algorithm, we can reach n = 250 in reasonable time. [less ▲]

Weightwise perfectly balanced functions and nonlinearity

E-print/Working paper (2022)

Supersingular Isogeny-Based Designated Verifier Blind Signature

E-print/Working paper (2019)