On the lossiness of 2k-th power and the instantiability of Rabin-OAEP

• Main Authors: XUE, Haiyang, LI, Bao, LU, Xianhui, WANG, Kunpeng, LIU, Yamin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Rabin; OAEP; Lossy trapdoor function; Φ-hiding; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/9198; https://ink.library.smu.edu.sg/context/sis_research/article/10203/viewcontent/on_the_lossiness.pdf
• Institution: Singapore Management University

Seurin PKC 2014 proposed the 2-ï /4-hiding assumption which asserts the indistinguishability of Blum Numbers from pseudo Blum Numbers. In this paper, we investigate the lossiness of 2 k -th power based on the 2 k -ï /4-hiding assumption, which is an extension of the 2-ï /4-hiding assumption. And we prove that 2 k -th power function is a lossy trapdoor permutation over Quadratic Residuosity group. This new lossy trapdoor function has 2 k -bits lossiness for k -bits exponent, while the RSA lossy trapdoor function given by Kiltz et al. Crypto 2010 has k -bits lossiness for k -bits exponent under ï -hiding assumption in lossy mode. We modify the square function in Rabin-OAEP by 2 k -th power and show the instantiability of this Modified Rabin-OAEP by the technique of Kiltz et al. Crypto 2010. The Modified Rabin-OAEP is more efficient than the RSA-OAEP scheme for the same secure bits. With the secure parameter being 80 bits and the modulus being 2048 bits, Modified Rabin-OAEP can encrypt roughly 454 bits of message, while RSA-OAEP can roughly encrypt 274 bits.