International Association
for Cryptologic Research

In key-and-message homomorphic encryption (KMHE), the key space is a subset of the message space, allowing encryption of secret keys such that the same homomorphism can be applied to both the key and the message of a given ciphertext. KMHE with suitable security properties is the main building block for constructing rerandomizable garbling schemes (RGS, Gentry et al., CRYPTO 2010), which enable advanced cryptographic applications like multi-hop homomorphic encryption, the YOSO-like MPC protocol SCALES (Acharya et al., TCC 2022 and CRYPTO 2024), and more. The BHHO scheme (Boneh et al., CRYPTO 2008) is currently the only known KMHE scheme suitable for constructing RGS. An encryption of a secret key consists of O(λ^2) group elements. We present a new, more efficient KMHE scheme with linear-size ciphertexts. Despite using heavier cryptographic tools (pairings instead of plain DDH-hard groups), the concrete ciphertext size and computational costs are very significantly reduced. We are able to shrink the ciphertext by 95.66 % (from 8.33 MB to 360 kB) and reduce the estimated computations for encryption by 98.01 % (from 7.65 seconds to 0.15) in comparison to BHHO. Additionally, we introduce gate KMHE as a new tool to build more efficient RGS. Our RGS construction shrinks the size of a garbled gate by 97.97 % (from 66.65 MB to 1.35 MB) and decreases the estimated cost of garbling by 99 % (from 61 seconds to 610 milliseconds per gate) in comparison to Acharya et al. In summary, our work shows for the first time that RGS and the SCALES protocol (and hence YOSO-like MPC) are practically feasible for simple circuits.