Pseudorandom Correlation Functions for Garbled Circuits

This chapter delves into the innovative use of pseudorandom correlation functions (PCFs) and pseudorandom correlation generators (PCGs) to enhance the efficiency and security of cryptographic protocols, particularly those involving garbled circuits. The text begins by addressing the limitations of traditional methods for distributing correlated randomness, such as oblivious transfer extension and somewhat homomorphic encryption, which often incur large communication overheads. It then introduces PCGs and PCFs as solutions that allow parties to generate large amounts of correlated pseudorandomness from short seeds without any interaction. The chapter explores the application of these primitives in improving the distributed generation of garbled circuits, which are crucial for secure computation protocols with minimal interaction. The authors introduce new definitions for garbling pseudorandom correlation generators (GPCGs) and garbling pseudorandom correlation functions (GPCFs), which enable parties to locally generate pseudorandom garbled circuits and labels. The text provides detailed constructions of GPCGs and GPCFs, highlighting their efficiency and practicality. It also discusses the applications of these constructions in various areas, including efficient secure computation, threshold cryptography, private set intersection, and zero-knowledge proofs. The chapter concludes with a technical overview of the results, including a strawman approach and its limitations, as well as the challenges and solutions in generating secret-shared garbled circuits. The text emphasizes the potential of these constructions to revolutionize secure computation and other cryptographic applications.