Paper 2026/701
Boolean Arithmetic over $\mathbb{F}_2$ from Group Commutators
, ZamaAbstract
This paper studies efficient realizations of arithmetic over the binary field $\mathbb{F}_2$ in nonabelian groups using only intrinsic group operations, namely multiplication and inversion. The constructions rely on commutators to implement Boolean computation within the group structure. Two complementary approaches are presented: a realization of a universal Boolean gate (NAND) and direct realizations of the field operations XOR and AND. These approaches apply to finite nonabelian simple groups and can be implemented using a small number of group operations. Explicit realizations are provided in the alternating groups $A_5$ and $A_6$. For the smallest nonabelian simple group $A_5$, these constructions achieve state-of-the-art efficiency in the number of group operations.
Note: Added an appendix with hand-optimized realizations of standard Boolean gates over $A_5$ and $S_5$.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Minor revision. WAIFI 2026
- DOI
- 10.1007/978-3-032-27574-5_15
- Keywords
- Arithmetic over F_2Boolean computationCommutatorsGroup-based computationFully homomorphic encodings
- Contact author(s)
- marc @ zama ai
- History
- 2026-07-15: last of 4 revisions
- 2026-04-09: received
- See all versions
- Short URL
- https://ia.cr/2026/701
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/701,
author = {Marc Joye},
title = {Boolean Arithmetic over $\mathbb{F}_2$ from Group Commutators},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/701},
year = {2026},
doi = {10.1007/978-3-032-27574-5_15},
url = {https://eprint.iacr.org/2026/701}
}
