Cryptology ePrint Archive: Report 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$.

Category / Keywords: cryptographic protocols / group correlations, bi-affine correlations, secure computation

Original Publication (with major differences): ITC 2021

Date: received 12 May 2021

Contact author: guruvamsi policharla at gmail com, mp at cse iitb ac in, rajeev mrug08 at gmail com, vyas parjanya at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210517:062918 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]