Paper 2021/624
Group Structure in Correlations and its Applications in Cryptography
Guru-Vamsi Policharla, Manoj Prabhakaran, Rajeev Raghunath, and Parjanya Vyas
Abstract
Correlated random variables are a key tool in cryptographic applications like secure multi-party computation. We investigate the power of a class of correlations that we term group correlations: A group correlation is a uniform distribution over pairs $(x,y) \in G^2$ such that $x+y\in S$, where $G$ is a (possibly non-abelian) group and $S$ is a subset of $G$. We also introduce bi-affine correlations and show how they relate to group correlations. We present several structural results, new protocols, and applications of these correlations. The new applications include a completeness result for black-box group computation, perfectly secure protocols for evaluating a broad class of black box ``mixed-groups'' circuits with bi-affine homomorphism, and new information-theoretic results. Finally, we uncover a striking structure underlying OLE: In particular, we show that OLE over $\mathrm{GF}(2^n)$, is isomorphic to a group correlation over $\mathbb{Z}_4^n$.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ITC 2021
- Keywords
- group correlationsbi-affine correlationssecure computation
- Contact author(s)
-
guruvamsi policharla @ gmail com
mp @ cse iitb ac in
rajeev mrug08 @ gmail com
vyas parjanya @ gmail com - History
- 2021-05-17: received
- Short URL
- https://ia.cr/2021/624
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/624,
author = {Guru-Vamsi Policharla and Manoj Prabhakaran and Rajeev Raghunath and Parjanya Vyas},
title = {Group Structure in Correlations and its Applications in Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/624},
year = {2021},
url = {https://eprint.iacr.org/2021/624}
}