Bi-Homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption
share
We define a pseudorandom function (PRF) F: K×X→Y to be bi-homomorphic when it is fully Key homomorphic and partially Input Homomorphic (KIH), i.e., given F(k_1, x_1) and F(k_2, x_2), there is an efficient algorithm to compute F(k_1 ⊕ k_2, x_1 x_2), where ⊕ and are (binary) group operations. The homomorphism on the input is restricted to a fixed subset of the input bits, i.e., operates on some pre-decided m-out-of-n bits, where |x_1| = |x_2| = n, m < n, and the remaining n-m bits are identical in both inputs. In addition, the output length, ℓ, of the operator is not fixed and is defined as n ≤ℓ≤ 2n, hence leading to Homomorphically induced Variable input Length (HVL) as n ≤ |x_1 x_2| ≤ 2n. We present a learning with errors (LWE) based construction for a HVL-KIH-PRF family. Our construction is inspired by the key homomorphic PRF construction due to Banerjee and Peikert (Crypto 2014). We use our novel PRF family to construct an updatable encryption scheme, named QPC-UE-UU, which is quantum-safe, post-compromise secure and supports unidirectional ciphertext updates, i.e., the tokens can be used to perform ciphertext updates, but they cannot be used to undo completed updates. Our PRF family also leads to the first left/right key homomorphic constrained-PRF family with HVL.
READ FULL TEXT