DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2026.7

Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography

Authors: Yuval Ishai, Hugo Krawczyk, and Tal Rabin

Published in: LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026)

Abstract

We revisit the question of securely compressing multiparty correlations using only symmetric cryptography. A linear correlation C, defined by a linear subspace C ⊆ 𝔽ⁿ, samples a secret random 𝐜 ∈ C and assigns to each party a fixed subset of the entries of 𝐜. Gilboa and Ishai (Crypto 1999) and Cramer, Damgård and Ishai (TCC 2005) provide a general technique for securely compressing many independent samples from C by replicating independent keys of a pseudorandom function (PRF) among the parties. This implies a pseudorandom correlation function (PCF) for C from any PRF, where the PCF key size scales with the number of minimal-support codewords in C. We observe that the above generalizes to other types of useful target correlations C_T by using a secret replication pattern obtained via a random secret assignment of parties in C to parties in C_T. We present several corollaries of this general blueprint. These include a re-derivation of two-party PCF constructions for VOLE and subfield-VOLE over small domains (Roy, Crypto 2022) as well as new multiparty PCFs for small-domain VOLE-style correlations, including scalar-vector multiplication triples and their authenticated variants. Finally, we discuss applications to secure computation.

Cite as

Yuval Ishai, Hugo Krawczyk, and Tal Rabin. Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography. In 7th Conference on Information-Theoretic Cryptography (ITC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 385, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.ITC.2026.7,
  author =	{Ishai, Yuval and Krawczyk, Hugo and Rabin, Tal},
  title =	{{Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography}},
  booktitle =	{7th Conference on Information-Theoretic Cryptography (ITC 2026)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-426-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{385},
  editor =	{Dodis, Yevgeniy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.7},
  URN =		{urn:nbn:de:0030-drops-271001},
  doi =		{10.4230/LIPIcs.ITC.2026.7},
  annote =	{Keywords: Pseudorandom correlation functions, correlated randomness, secure computation, symmetric cryptography}
}

Document

DOI: 10.4230/DagRep.6.9.46

Public-Key Cryptography (Dagstuhl Seminar 16371)

Authors: Marc Fischlin, Alexander May, David Pointcheval, and Tal Rabin

Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)

Abstract

This report documents the program and results of Dagstuhl seminar 16731 “Public-Key Cryptography” which took place September 11th -16th, 2016. The goal of the seminar was to bring together different sub areas from public-key cryptography and to promote research among these areas.

Cite as

Marc Fischlin, Alexander May, David Pointcheval, and Tal Rabin. Public-Key Cryptography (Dagstuhl Seminar 16371). In Dagstuhl Reports, Volume 6, Issue 9, pp. 46-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{fischlin_et_al:DagRep.6.9.46,
  author =	{Fischlin, Marc and May, Alexander and Pointcheval, David and Rabin, Tal},
  title =	{{Public-Key Cryptography (Dagstuhl Seminar 16371)}},
  pages =	{46--58},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{9},
  editor =	{Fischlin, Marc and May, Alexander and Pointcheval, David and Rabin, Tal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.46},
  URN =		{urn:nbn:de:0030-drops-69147},
  doi =		{10.4230/DagRep.6.9.46},
  annote =	{Keywords: cryptanalysis, encryption, homomorphic encryption, key exchange, obfuscation, signatures}
}

Search Results

Documents authored by Rabin, Tal

Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography

Abstract

Cite as

Public-Key Cryptography (Dagstuhl Seminar 16371)

Abstract

Cite as

Thanks for your feedback!

Could not send message