Cryptanalysis of enhanced more

Damian Vizár, Serge Vaudenay


Fully homomorphic encryption (FHE) has been among the most pop-
ular research topics of the last decade. While the bootstrapping-based, public key
cryptosystems that follow Gentry's original design are getting more and more ef-
cient, their performance is still far from being practical. This lead to several
attempts to construct symmetric FHE schemes that would not be as inecient as
their public key counterparts. Unfortunately, most such schemes were also based on
(randomized) linear transformations, and shown completely insecure. One such bro-
ken scheme was the Matrix Operation for Randomization and Encryption (MORE).
In a recent paper, Hariss, Noura and Samhat propose Enhanced MORE, which is
supposed to improve over MORE's weaknesses. We analyze Enhanced MORE, dis-
cuss why it does not improve over MORE, and show that it is even less secure by
presenting a highly ecient ciphertext-only decryption attack. We implement the
attack and conrm its correctness.

Full Text: