Paper 2019/594
Computing Primitive Idempotents in Finite Commutative Rings and Applications
Abstract
In this paper, we compute an algebraic decomposition of blackbox rings in the generic ring model. More precisely, we explicitly decompose a black-box ring as a direct product of a nilpotent black-box ring and local Artinian black-box rings, by computing all its primitive idempotents. The algorithm presented in this paper uses quantum subroutines for the computation of the p-power parts of a black-box ring and then classical algorithms for the computation of the corresponding primitive idempotents. As a by-product, we get that the reduction of a black-box ring is also a black-box ring. The first application of this decomposition is an extension of the work of Maurer and Raub [26] on representation problem in black-box finite fields to the case of reduced p-power black-box rings. Another important application is an IND-CCA1 attack for any ring homomorphic encryption scheme in the generic ring model. Moreover, when the plaintext space is a nite reduced black-box ring, we present a plaintext-recovery attack based on representation problem in black-box prime fields. In particular, if the ciphertext space has smooth characteristic, the plaintext-recovery attack is effectively computable in the generic ring model.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- homomorphic encryption schemes quantum computing plaintext-recovery attack black-box rings
- Contact author(s)
-
mugurel barcau @ imar ro
vicentiu pasol @ imar ro - History
- 2022-08-25: last of 2 revisions
- 2019-06-02: received
- See all versions
- Short URL
- https://ia.cr/2019/594
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/594,
author = {Mugurel Barcau and Vicentiu Pasol},
title = {Computing Primitive Idempotents in Finite Commutative Rings and Applications},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/594},
year = {2019},
url = {https://eprint.iacr.org/2019/594}
}
