aqora

On Lower Bounds and Size Reduction for Correlated Randomness in Secure Two-party Computation

Keitaro Hiwatashi

Mar 21, 20240 citations

Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose

Yan Huang, Jonathan I. Katz, David Evans

Lecture notes in computer scienceJan 1, 2013119 citations

Towards Characterizing Securely Computable Two-Party Randomized Functions

Deepesh Data, Manoj Prabhakaran

Lecture notes in computer scienceJan 1, 20187 citations

Correlated Randomness Reduction in Domain-Restricted Secure Two-Party Computation

Keitaro Hiwatashi, Koji Nuida

Secure two-party computation is a cryptographic tool that enables two parties to compute a function jointly without revealing their inputs. It is known that any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. Sometimes we can construct more efficient secure two-party protocol for a function g than that for a function f, where g is a restriction of f. However, it is not known in which case we can construct more efficient protocol for domain-restricted function. In this paper, we focus on the size of CR. We prove that we can construct more efficient protocol for a domain-restricted function when there is a “good” structure in CR space of a protocol for the original function, and show a unified way to construct a more efficient protocol in such case. In addition, we show two applications of the above result: The first application shows that some known techniques of reducing CR size for domain-restricted function can be derived in a unified way, and the second application shows that we can construct more efficient protocol than an existing one using our result.Secure two-party computation is a cryptographic tool that enables two parties to compute a function jointly without revealing their inputs. It is known that any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. Sometimes we can construct more efficient secure two-party protocol for a function g than that for a function f, where g is a restriction of f. However, it is not known in which case we can construct more efficient protocol for domain-restricted function. In this paper, we focus on the size of CR. We prove that we can construct more efficient protocol for a domain-restricted function when there is a “good” structure in CR space of a protocol for the original function, and show a unified way to construct a more efficient protocol in such case. In addition, we show two applications of the above result: The first application shows that some known techniques of reducing CR size for domain-restricted function can be derived in a unified way, and the second application shows that we can construct more efficient protocol than an existing one using our result.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesOct 3, 20230 citations

Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography

Yuval Ishai, Hugo Krawczyk, Tal Rabin

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

Leibniz international proceedings in informaticsJan 1, 20260 citations

On the Power of Correlated Randomness in Secure Computation

Yuval Ishai, Eyal Kushilevitz Z, Sigurd Meldgaard +2 more

Lecture notes in computer scienceJan 1, 2013111 citations

On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness

Related papers

On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness

Related papers