2026-07-23T19:43:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14320 2024-03-06T10:53:46Z ddc:004 open_access

Group Structure in Correlations and Its Applications in Cryptography Policharla, Guru-Vamsi Prabhakaran, Manoj Raghunath, Rajeev Vyas, Parjanya Group correlations bi-affine correlations secure computation 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) ∈ G² such that x+y ∈ S, where G is a (possibly non-abelian) group and S is a subset of G. We also introduce bi-affine correlation{s}, 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 homomorphisms, and new information-theoretic results. Finally, we uncover a striking structure underlying OLE: In particular, we show that OLE over 𝔽_{2ⁿ}, is isomorphic to a group correlation over ℤ_4^n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guru-Vamsi Policharla and Manoj Prabhakaran and Rajeev Raghunath and Parjanya Vyas 2021 Is Part Of LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2021.1 urn:nbn:de:0030-drops-143208 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.1 eng https://creativecommons.org/licenses/by/4.0/legalcode