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.