Abstract
Sum-preserving encryption, introduced by Tajik, Gunasekaran, Dutta, Ellia, Bobba, Rosulek, Wright, and Feng (NDSS 2019), allows the encryption of a vector of integers into another vector with the same sum. Tajik et al. proposed a construction resembling a shuffling algorithm and used it to build a type of image encryption called thumbnail-preserving encryption. Later work by Miracle and Yilek (Asiacrypt 2022) introduced additional applications, provided mixing time bounds on the Tajik et al. scheme, and proposed rankings that could be used in the rank-encipher-unrank technique from format-preserving encryption. We build on previous work and improve on their results specifically for the encryption of long vectors with thousands of elements or more. First, we provide an improved analysis of the Tajik et al. construction that relies on a more complex coupling argument than the analysis of Miracle and Yilek. In one of our target applications, this new analysis reduces the number of rounds from about 160,000 to just under 2,600. Our second result is the first analysis of a generalization of the Tajik et al. construction that we call a grouping-based scheme. This solves an open problem given by Miracle and Yilek and provides schemes with improved performance that should scale better as vector size increases.