Narrow Results

We study the learnability of representation classes in Angluin's exact learning model. In particular, we consider the following three query types: equivalence queries, equivalence and membership queries, and membership queries only. We show in all three cases that polynomial query complexity implies already polynomial-time learnability, provided that the learner additionally has access to an oracle in . It follows that boolean circuits are polynomial-time learnable with equivalence queries and the help of an oracle in .^a

Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH${}^{\ast }$, which was shown to be $\mathrm{\Delta }$-universal by Halevi and Krawczyk in 1997, is a well-known universal hash function family. We introduce a variant of MMH${}^{\ast }$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $x=〈x_1,\dots ,x_k〉\in {\mathbb{Z}}_n^k$ satisfy the conditions $gcd(x_i,n)=t_i$ ($1\le i\le k$), where $t_1,\dots ,t_k$ are given positive divisors of $n$. Then via connecting the universal hashing problem to the number of solutions of restricted linear congruences, we prove that the family GRDH is an $𝜀$-almost-$\mathrm{\Delta }$-universal family of hash functions for some $𝜀<1$ if and only if $n$ is odd and $gcd(x_i,n)=t_i=1$$(1\le i\le k)$. Furthermore, if these conditions are satisfied then GRDH is $\frac{1}{p-1}$-almost-$\mathrm{\Delta }$-universal, where $p$ is the smallest prime divisor of $n$. Finally, as an application of our results, we propose an authentication code with secrecy scheme which strongly generalizes the scheme studied by Alomair et al. [J. Math. Cryptol.4 (2010) 121–148], and [J.UCS15 (2009) 2937–2956].

Traditional data authentication systems are sensitive to single bit changes and so are unsuitable for message spaces that are naturally "fuzzy" where "similar" messages are considered "the same" or indistinguishable. In this paper, we study unconditionally secure approximate authentication. We generalize traditional universal hashing to fuzzy universal hashing and use it to construct secure approximate authentication for multiple messages.