Paper 2021/624
Group Structure in Correlations and its Applications in Cryptography
Guru-Vamsi Policharla and Manoj Prabhakaran and 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)
- 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