On the Security of Some Code-Based (F)HE Approaches Using Reed-Muller Codes

Kurzfassung

We analyze the security of the somewhat homomorphic encryption scheme proposed by Armknecht et al. [AAPS11], which can be seen as a fundamental step toward fully homomorphic encryption based on coding theory and Reed-Muller codes in particular. Through our cryptanalysis, we identify critical vulnerabilities that enable partial key recovery and, in many cases, full message recovery. Our analysis also exposes critical weaknesses in two later code-based fully homomor phic encryption schemes by Challa and Gunta, both of which adopt Reed-Muller codes as their underlying structure.