Amortizing Randomness in Private Multiparty Computations

DOI10.1137/S089548010135274XMaRDI QIDQ4443108zbMATH OpenOpenAlexFDO

Authors Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

Publication date 8 January 2004

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s089548010135274x

zbMATH Keywords

amortizationcryptographic protocolsprivate distributed computationsrandomnessround-complexity

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

This paper studies the relationship between the number of rounds needed to repeatedly perform a private computation and the overall randomness need for this task. For the XOR-function it is shown that, by re-using the same random bits, one can significantly speed up the round-complexity of each computation compared to what is achieved by the naive strategy of equally partitioning the random bits between the computations. Moreover, optimality of the presented protocols is proven with respect to the amount of required randomness.

Recommendations

• A Randomness-Rounds Tradeoff in Private Computation
• Random sources in private computation
• A randomness-rounds tradeoff in private computation
• Tight bounds on the randomness complexity of secure multiparty computation
• Randomness in Private Computations

Cited in

(6)

• Lower and upper bounds on the randomness complexity of private computations of AND
• A Randomness-Rounds Tradeoff in Private Computation
• A randomness-rounds tradeoff in private computation
• Amplification and Derandomization without Slowdown
• Lower and upper bounds on the randomness complexity of private computations of AND
• Tight bounds on the randomness complexity of secure multiparty computation

This page was built for publication: Amortizing Randomness in Private Multiparty Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4443108)