Cryptology ePrint Archive: Report 2019/594

Cryptanalysis of Ring Homomorphic Encryption Schemes

Mugurel Barcau and Vicentiu Pasol

Abstract: We analyze the structure of finite commutative rings with respect to its idempotent and nilpotent elements. Based on this analysis we provide a quantum-classical IND-CCA^1 attack for ring homomorphic encryption schemes. Moreover, when the plaintext space is a finite reduced ring, i.e. a product of finite fields, we present a key-recovery attack based on representation problem in black-box finite fields. In particular, if the ciphertext space has smooth characteristic the key-recovery attack is effectively computable. We also extend the work of Maurer and Raub on representation problem in black-box finite fields to the case of a black-box product of finite fields of equal characteristic.

Category / Keywords: public-key cryptography / homomorphic encryption schemes, quantum computing, key-recovery attack, black-box rings

Date: received 29 May 2019

Contact author: mugurel barcau at imar ro, vicentiu pasol@imar ro

Available format(s): PDF | BibTeX Citation

Version: 20190602:112618 (All versions of this report)

Short URL: ia.cr/2019/594