Paper 2014/949
Simplification/complication of the basis of prime Boolean ideal
Alexander Rostovtsev and Anna Shustrova
Abstract
Prime Boolean ideal has the basis of the form (x1 + e1, ..., xn + en) that consists of linear binomials. Its variety consists of the point (e1, ..., en). Complication of the basis is changing the simple linear binomials by non-linear polynomials in such a way, that the variety of ideal stays fixed. Simplification of the basis is obtaining the basis that consists of linear binomials from the complicated one that keeps its variety. Since any ideal is a module over the ring of Boolean polynomials, the change of the basis is uniquely determined by invertible matrix over the ring. Algorithms for invertible simplifying and complicating the basis of Boolean ideal that fixes the size of basis are proposed. Algorithm of simplification optimizes the choose of pairs of polynomials during the Groebner basis computation, and eliminates variables without using resultants.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- block ciphersBoolean functionscryptanalysischaracteristic setGroebner basishash functionsvarieties
- Contact author(s)
- alexander rostovtsev @ ibks ftk spbstu ru
- History
- 2014-11-19: received
- Short URL
- https://ia.cr/2014/949
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/949,
author = {Alexander Rostovtsev and Anna Shustrova},
title = {Simplification/complication of the basis of prime Boolean ideal},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/949},
year = {2014},
url = {https://eprint.iacr.org/2014/949}
}
