1. Computing primitive idempotents in finite commutative rings and applications.
- Author
-
Barcau, Mugurel and Paşol, Vicenţiu
- Subjects
- *
FINITE rings , *LOCAL rings (Algebra) , *FINITE fields , *QUANTUM computing , *HOMOMORPHISMS - Abstract
In this paper, we compute an algebraic decomposition of black-box 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 unital local 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 (2007) on representation problem in black-box finite fields to the case of reduced p -power black-box rings. Another important application is an IND-CCA 1 attack for any ring homomorphic encryption scheme in the generic ring model. Moreover, when the plaintext space is a finite 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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF