International Association for Cryptologic Research

International Association
for Cryptologic Research


Dmitry Kogan


Private Information Retrieval with Sublinear Online Time 📺
Henry Corrigan-Gibbs Dmitry Kogan
We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client’s query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Our protocols can provide statistical security in the two-server setting and computational security in the single-server setting. Finally, we prove that, in this model, our protocols are optimal in terms of the trade-off they achieve between communication and running time.
The Function-Inversion Problem: Barriers and Opportunities
Henry Corrigan-Gibbs Dmitry Kogan
The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function $$f{:}\,[N] \rightarrow [N]$$ in time $$T = \widetilde{O}(N^{2/3})$$ given only $$S = \widetilde{O}(N^{2/3})$$ bits of precomputed advice about f. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin 2003), which achieves the same asymptotic cost and is widely used in practical cryptanalysis.Is Hellman’s method the best possible algorithm for inverting functions with preprocessed advice? The best known lower bound, due to Yao (1990), shows that $$ST = \widetilde{\Omega }(N)$$, which still admits the possibility of an $$S = T = \widetilde{O}(N^{1/2})$$ attack. There remains a long-standing and vexing gap between Hellman’s $$N^{2/3}$$ upper bound and Yao’s $$N^{1/2}$$ lower bound. Understanding the feasibility of an $$S = T = N^{1/2}$$ algorithm is cryptanalytically relevant since such an algorithm could perform a key-recovery attack on AES-128 in time $$2^{64}$$ using a precomputed table of size $$2^{64}$$.For the past 29 years, there has been no progress either in improving Hellman’s algorithm or in strengthening Yao’s lower bound. In this work, we connect function inversion to problems in other areas of theory to (1) explain why progress may be difficult and (2) explore possible ways forward.Our results are as follows:We show that any improvement on Yao’s lower bound on function-inversion algorithms will imply new lower bounds on depth-two circuits with arbitrary gates. Further, we show that proving strong lower bounds on non-adaptive function-inversion algorithms would imply breakthrough circuit lower bounds on linear-size log-depth circuits.We take first steps towards the study of the injective function-inversion problem, which has manifold cryptographic applications. In particular, we show that improved algorithms for breaking PRGs with preprocessing would give improved algorithms for inverting injective functions with preprocessing.Finally, we show that function inversion is closely related to well-studied problems in communication complexity and data structures. Through these connections we immediately obtain the best known algorithms for problems in these domains.


Henry Corrigan-Gibbs (3)