Paper 2021/146
Securely Computing Piecewise Constant Codes
Abstract
Piecewise constant codes form an expressive and well-understood class of codes. In this work, we show that many piecewise constant codes admit exact coverings by polynomial-cardinality collections of hyperplanes. We prove that any boolean function whose "on-set" has been covered in just this manner can be evaluated by two parties with malicious security. This represents an interesting connection between covering codes, affine-linear algebra over prime fields, and secure computation. We observe that many natural boolean functions' on-sets admit expressions as piecewise constant codes (and hence can be computed securely). Our protocol supports secure computation on committed inputs; we describe applications in blockchains and credentials. We finally present an efficient implementation of our protocol.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- applications boolean functions combinatorial cryptography number theory
- Contact author(s)
- benediamond @ gmail com
- History
- 2022-09-07: last of 4 revisions
- 2021-02-12: received
- See all versions
- Short URL
- https://ia.cr/2021/146
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/146,
author = {Benjamin E. Diamond},
title = {Securely Computing Piecewise Constant Codes},
howpublished = {Cryptology ePrint Archive, Paper 2021/146},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/146}},
url = {https://eprint.iacr.org/2021/146}
}
