BASS: Boolean Automorphisms Signature Scheme

We offer a digital signature scheme using Boolean automorphisms of a multivariate polynomial algebra over integers. Verification part of this scheme is based on the approximation of the number of zeros of a multivariate Boolean function.

Authors and Affiliations

1. CNRS, Mathématiques, Université de Lille, 59655, Villeneuve d’Ascq, France

   Dima Grigoriev

2. Department of Computer Science, CUNY Graduate Center, 365 5th Avenue, New York, NY, 10016, USA

   Ilia Ilmer

3. Department of Mathematics, Queens College, City University of New York, Queens, NY, 11367, USA

   Alexey Ovchinnikov

4. Department of Mathematics, The City College of New York, New York, NY, 10031, USA

   Vladimir Shpilrain

Corresponding author

Correspondence to Vladimir Shpilrain .

Editors and Affiliations

1. Universität der Bundeswehr München, Munich, Germany

   Mark Manulis

2. Technology Innovation Institute, Abu Dhabi, United Arab Emirates

   Diana Maimuţ

3. Advanced Technologies Institute, Bucharest, Romania

   George Teşeleanu

Appendix

Here we give a proof of Proposition 1.

Proposition 1. Let \(h=h(x_1,\ldots , x_n)\) be a polynomial from the set \(\mathbb {G}\). Suppose h does not depend on \(x_k\). Let \(\alpha \) be the map that takes \(x_k\) to \(x_k + h - 2x_k \cdot h\) and fixes all other variables. Then:

(a):

\(\alpha \) defines an automorphism of B(K), the factor algebra of the algebra \(\mathbb {Z}[x_1, \ldots , x_n]\) by the ideal generated by all polynomials of the form \((x_i^2-x_i)\), \(i=1, \ldots , n\). Denote this automorphism also by \(\alpha \).

(b):

The group of automorphisms of B(K) is generated by all automorphisms as in part (a) and is isomorphic to the group of permutations of the vertices of the n-dimensional Boolean cube.

(c):

For any polynomial P from \(\mathbb {Z}[x_1, \ldots , x_n]\), the number of positive values of P on Boolean tuples \((x_1, \ldots , x_{n})\) equals that of \(\alpha (P)\).

Proof

(a) Let \(B^n\) denote the Boolean n-cube, i.e., the n-dimensional cube whose vertices are Boolean n-tuples. The map \(\alpha \) leaves the set of vertices of \(B^n\) invariant. Indeed, \(\alpha \) fixes all \(x_i\) except \(x_k\), and it is straightforward to see that if \(x_k=0\), then \(\alpha (x_k) = h(x_1,\ldots , x_n)\), and if \(x_k=1\), then \(\alpha (x_k) = 1 - h(x_1,\ldots , x_n)\). Since on any Boolean n-tuple \((x_1, \ldots , x_n)\), one has \(h(x_1, \ldots , x_n)=\) 0 or 1 (see Sect. 3.2), we see that \(\alpha \) is a bijection of the set of vertices of \(B^n\) onto itself.

Next, observe that for any polynomial h from the set \(\mathbb {G}\), one has \(h^2=h\) modulo the ideal generated by all polynomials of the form \((x_i^2-x_i)\); this easily follows from the inductive procedure of constructing polynomials h, see Sect. 3.2. Therefore, \(\alpha \) leaves the ideal generated by all \((x_i^2-x_i)\) invariant since \(\alpha \) takes \(x_i\) to \(x_i + h - 2x_i \cdot h\), and then \(\alpha (x_i^2-x_i) = (x_i + h - 2x_i \cdot h)^2 - (x_i + h - 2x_i \cdot h) = (x_i^2-x_i) + (h^2-h) + 2x_ih -4x_i^2h -4x_ih^2 + 4x_i^2h^2 +2x_ih = (x_i^2-x_i) + (h^2-h) + 4h(x_i-x_i^2) + 4h^2(x_i^2-x_i)\).

(b) Consider the automorphism \(\alpha \) again. Fix a particular Boolean n-tuple \((x_1,\ldots , x_n)\). Suppose that \(h(x_1,\ldots , x_n)=1\). Suppose \(x_k=0\) in this tuple. Then \(\alpha \) takes this tuple to the tuple where all \(x_i\), except \(x_k\), are the same as before, and \(x_k=1\), i.e., just one of the coordinates in the tuple was flipped. Therefore, an appropriate composition of different \(\alpha \) (with different \(x_k\)) can map any given Boolean n-tuple to any other Boolean n-tuple.

(c) This follows immediately from the argument in the proof of part (a). More specifically, since the set of vertices of \(B^n\) is invariant under \(\alpha \), there is a bijection between the sets of values of P and \(\alpha (P)\) on Boolean n-tuples.

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics