Paper 2021/624

Group Structure in Correlations and its Applications in Cryptography

Guru-Vamsi Policharla, Manoj Prabhakaran, Rajeev Raghunath, and Parjanya Vyas


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$.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ITC 2021
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
2021-05-17: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.