International Association
for Cryptologic Research

The study of fine-grained cryptography has proliferated in recent years due to its allure of potentially relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in $\mathbf{P}$ such as $k$-SUM or Zero-$k$-Clique. The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if $\mathbf{P} = \mathbf{NP}$ or if we live in Pessiland where one-way functions do not exist. In our work, we consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. As our main result, we show that many popular fine-grained complexity problems are easy to solve in the average-case when one-way functions do not exist. In other words, many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland. As an example, we prove that the average-case $k$-SUM or Zero-$k$-Clique conjectures are false for sufficiently large constant $k$ when no one-way functions exist. The average-case Zero-$k$-Clique assumption was used to build fine-grained key-exchange by Lavigne {\em et al.} [CRYPTO'19]. One can also view the contrapositive of our result as providing an explicit construction of one-way functions assuming $n^{\omega_k(1)}$ average-case hardness of $\ksum$ or $\zkc$ for all constant $k$. We also show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography. First, we show that finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between $k$-SUM and $k$-CYC (an extension of $k$-SUM to cyclic groups). In particular, finding such a reduction from $k$-CYC to $k$-SUM could potentially lead to breakthrough algorithms for the discrete logarithm, factoring, RSA and quadratic residuosity problems. Finally, we show that discrete logarithms with preprocessing may be reduced to the $k$-CYC-Index problem, and we present faster algorithms for average-case $k$-SUM-Index and $k$-CYC-Index.

In predicate encryption for a function f, an authority can create ciphertexts and secret keys which are associated with ‘attributes’. A user with decryption key $$K_y$$ corresponding to attribute y can decrypt a ciphertext $$CT_x$$ corresponding to a message m and attribute x if and only if $$f(x,y)=0$$. Furthermore, the attribute x remains hidden to the user if $$f(x,y) \ne 0$$.We construct predicate encryption from assumptions on bilinear maps for a large class of new functions, including sparse set disjointness, Hamming distance at most k, inner product mod 2, and any function with an efficient Arthur-Merlin communication protocol. Our construction uses a new probabilistic representation of Boolean functions we call ‘one-sided probabilistic rank,’ and combines it with known constructions of inner product encryption in a novel way.