Private information retrieval (PIR) allows to privately read a chosen bit from an N-bit database x with o(N) bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing x into an encoded database x, it suffices to access only polylog(N) bits of x per query. This requires |x|≥ N· polylog(N), and even larger server circuit size.

Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix-vector product (EMVP). Let ⅇ be a finite field. In an offline phase, a client uploads an encryption of a matrix M∈ ⅇmxℓ to a server, keeping only a short secret key. The server stores the encrypted matrix M. In the online phase, the client may repeatedly send encryptions qi of query vectors qi∈ ⅇℓ, which enables the client and the server to locally compute compact shares of the matrix-vector product M qi. The server learns nothing about M or qi. The shared output can either be revealed to the client or processed by another protocol.

Tree codes (Schulman, STOC 93’, IEEE Transactions on Information Theory 96’) are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the i-th codeword symbol depends only on the first i message symbols. Codewords should have good tree distance meaning that for any two codewords, starting at the first point of divergence, they should have large Hamming distance.