YuS: A FHE-Friendly Stream Cipher Based on New Quadratic Permutations
Yongqiang Li, Fangzhen Wang, Xingwei Ren, Fen Liu, Xichao Hu, Lin Jiao, Ya Han · IEEE Transactions on Information Theory · 2025
Permutations with low multiplication depth over prime fields are highly valuable in the design of symmetric ciphers that are compatible with fully homomorphic encryption (FHE). Quadratic permutations, which have the lowest depth, have been widely used in prior designs. In this paper, we propose a construction method that can give new quadratic permutations over Fpm, and cryptographic properties such as differential uniformity and Walsh spectrum of these permutations are also characterized. We give sufficient conditions for permutations over Fpnto attain a differential uniformity ofpn−1forn≥ 3. Furthermore, it is proven that for these permutations, the maximal 2-norm of Walsh coefficients remains bounded bypn−1, provided either the lastn− 1 entries of the input mask or the lastn− 1 entries of the output mask form a nonzero vector. As an application, we design a new FHE-friendly stream cipher named YuS based on a new quadratic permutation over Fp3and a fixed linear mapping. According to our implementation, achieves YuS faster evaluation times and higher throughput compared to Masta, Pasta, Pastav2and HERA in almost all instances for both BGV and BFV schemes at 80-bit and 128-bit security levels.