Shoni Gilboa, Ron Peled
A Chebyshev-type quadrature for a given weight function is a quadrature formula with equal weights. In this work we show that a method presented by Kane may be used to produce tight bounds for the minimal number of nodes required in Chebyshev-type quadratures for doubling weight functions. This extends a long line of research on Chebyshev-type quadratures starting with the 1937 work of Bernstein.
Shoni Gilboa, Shay Gueron
Constructing a Pseudo Random Function (PRF) is a fundamental problem in cryptology. Such a construction, implemented by truncating the last $m$ bits of permutations of $\{0, 1\}^{n}$ was suggested by Hall et al. (1998). They conjectured that the distinguishing advantage of an adversary with $q$ queries, ${\bf Adv}_{n, m} (q)$, is small if $q = o (2^{(n+m)/2})$, established an upper bound on ${\bf Adv}_{n, m} (q)$ that confirms the conjecture for $m < n/7$, and also declared a general lower bound ${\bf Adv}_{n,m}(q)=Ω(q^2/2^{n+m})$. The conjecture was essentially confirmed by Bellare and Impagliazzo (1999). Nevertheless, the problem of {\em estimating} ${\bf Adv}_{n, m} (q)$ remained open. Combining the trivial bound $1$, the birthday bound, and a result of Stam (1978) leads to the upper bound \begin{equation*} {\bf Adv}_{n,m}(q) = O\left(\min\left\{\frac{q(q-1)}{2^n},\,\frac{q}{2^{\frac{n+m}{2}}},\,1\right\}\right). \end{equation*} In this paper we show that this upper bound is tight for every $0\leq m<n$ and any $q$. This, in turn, verifies that the converse to the conjecture of Hall et al. is also correct, i.e., that ${\bf Adv}_{n, m} (q)$ is negligible only for $q = o (2^{(n+m)/2})$.
Shoni Gilboa, Shay Gueron, Ben Morris
An oracle chooses a function $f$ from the set of $n$ bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an $n$-bit string $w$, the oracle computes $f(w)$, truncates the $m$ last bits, and returns only the first $n-m$ bits of $f(w)$. How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from the (truncated) function? In 1998, Hall et al. showed an algorithm for determining (with high probability) whether or not $f$ is a permutation, using $O(2^{\frac{m+n}{2}})$ queries. They also showed that if $m < n/7$, a smaller number of queries will not suffice. For $m > n/7$, their method gives a weaker bound. In this note, we first show how a modification of the approximation method used by Hall et al. can solve the problem completely. It extends the result to practically any $m$, showing that $Ω(2^{\frac{m+n}{2}})$ queries are needed to get a non-negligible distinguishing advantage. However, more surprisingly, a better bound for the distinguishing advantage can be obtained from a result of Stam published, in a different context, already in 1978. We also show that, at least in some cases, Stam's bound is tight.
Shoni Gilboa, Shay Gueron, Mridul Nandi
The $r$-rounds Even-Mansour block cipher is a generalization of the well known Even-Mansour block cipher to $r$ iterations. Attacks on this construction were described by Nikolić et al. and Dinur et al., for $r = 2, 3$. These attacks are only marginally better than brute force, but are based on an interesting observation (due to Nikolić et al.): for a "typical" permutation $P$, the distribution of $P(x) \oplus x$ is not uniform. This naturally raises the following question. Call permutations for which the distribution of $P(x) \oplus x$ is uniform "balanced." Is there a sufficiently large family of balanced permutations, and what is the security of the resulting Even-Mansour block cipher? We show how to generate families of balanced permutations from the Luby-Rackoff construction, and use them to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. We prove that this cipher is indistinguishable from a random permutation of $\{0, 1\}^{2n}$, for any adversary who has oracle access to the public permutations and to an encryption/decryption oracle, as long as the number of queries is $o (2^{n/2})$. As a practical example, we discuss the properties and the performance of a $256$-bit block cipher that is based on our construction, and uses AES as the public permutation.