2019/01/01 by Vipin Singh Sehrawat, Yvo Desmedt
Computer Science · Mathematics · #Algorithm #Arithmetic #Ciphertext #Coding theory and cryptography #Combinatorics #Computer network #Computer science #Cryptographic Implementations and Security #Cryptography #Cryptography and Data Security #Discrete mathematics #Encryption #Homomorphic encryption #Homomorphism #Key (lock) #Lattice (music) #Learning with errors #Mathematics #Operating system #Physics #Pseudorandom function family #Pseudorandom number generator #cs.CR
paper · pdf · doi:10.1007/978-3-030-31578-8_1
published as Cryptology and Network Security 2019, LNCS, Springer, Volume 11829, pp. 3-23 · This is the full version of the paper that appears in Cryptology and Network Security 2019, LNCS, Springer, Volume 11829, pp. 3-23
openalex publication_date 2019/01/01 · openalex created_date 2019/10/18 · arxiv created 2020/08/21 · arxiv updated 2020/08/24 · openalex updated_date 2026/08/05
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(k1, x1) and F(k2, x2), there is an efficient algorithm to compute F(k1 ⊕ k2, x1 \ominus x2), where ⊕ and \ominus are (binary) group operations. The homomorphism on the input is restricted to a fixed subset of the input bits, i.e., \ominus operates on some pre-decided m-out-of-n bits, where |x1| = |x2| = n, and the remaining n-m bits are identical in both inputs. In addition, the output length, ℓ, of the operator \ominus is not fixed and is defined as n ≤ ℓ ≤ 2n, hence leading to Homomorphically induced Variable input Length (HVL) as n ≤ |x1 \ominus x2| ≤ 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). An updatable encryption scheme allows rotations of the encryption key, i.e., moving existing ciphertexts from old to new key. These updates are carried out via update tokens, which can be used by an untrusted party since the update procedure does not involve decryption of the ciphertext. 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 update tokens can be used to perform ciphertext updates but they cannot be used to undo already completed updates. Our PRF family also leads to the first left/right key homomorphic constrained-PRF family with HVL.