Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Randomness versus Fault-Tolerance.

Ran Canetti, Eyal Kushilevitz Z, Rafail Ostrovsky, Adi Rosén

Published Jan 1, 1998• 0 citations
OpenAlex

Abstract

We investigate the relations between two major properties of multiparty protocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of colluding faulty parties, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness is measured in terms of the total number of random bits needed by the parties in order to execute the protocol. Previously, the upper bound on the amount of randomness required by general constructions for securely computing any non-trivial function f was polynomial both in n, the total number of parties, and the circuit-size C(f). This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one faulty party). In this paper, we show that for any linear-size circuit, and for any number t ! n=3 of faulty parties, O(poly(t) \\Delta log n) randomness is sufficient. More generally, we show that for...

Related papers

Randomness vs. fault-tolerance

Ran Canetti, Eyal Kushilevitz Z, Rafail Ostrovsky +1 more

We investigate the relations between the fault tolemnce (or resilience) and the mndornnea requirements of multiparty protocols.Fault-tolerance is measured in terms of the maximum number of colluding faulty players, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honeat players).Randomness is measured in terms of the total number of random bits needed by the players in order to execute the protocol.Previously, the upper bound on the amount of randomncm needed for securely computing any non-trivial function ~was polynomial both in n, the total number of parties, and the circuit-size C(f).This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one malicious player).In this paper, we show that for any linear-size circuit, and for any value t < n/2, O(poly(t) .log n) randomness is srtflicient.More generally, we show that for any function j with circuit-size C(~), we need only O (poiy(t) .log n + polg(t) .~) randomness in order to withstrmd any coalition of size at most t.Moreover, in our prot~ CO1 only t + 1 players flip coins and the rest of the players are deterministic.Our results generalize to the case of adaptive adversaries as well.

ACM Symposium on Principles of Distributed Computing (PODC)•Jan 1, 1997•12 citations

High Entropy Random Selection Protocols

Nikolay Vereshchagin, Harry Buhrman, Cristandl, Matthias +3 more

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Dagstuhl Seminar Proceedings•Jan 1, 2008•0 citations

Efficient secure computation and randomness

Rafail Ostrovsky, Joshua Baron

The question of how to construct optimally efficient secure protocols is a central question in cryptography and in the computer security world at large. We focus in this work on several facets of this question, with a particular view towards the role of randomness in secure computation. The use of random inputs is ubiquitous in cryptographic primitives. However, the ability to consistently draw from large random sources may be a barrier in practice. We examine the existence of optimally strong pseudorandom sources with particularly efficient implementations; namely, we construct exponentially hard pseudorandom generators that can be computed by circuits that have size linear in the generator output. Conversely, we also examine efficient protocols that rely only minimally on their random inputs. In the resettable security model, parties may be forced to use the same random input across polynomially many interactions with other parties. We examine this security model in the case of zero knowledge proofs, which are a primitive frequently required in secure computation protocols when one party must prove that they have executed the protocol correctly to another party without revealing secret inputs and compromising security. Finally, we examine the secure and efficient implementation of a specific functionality, including its various required cryptographic primitives (such as zero knowledge arguments of knowledge). In particular, we construct a protocol that securely realizes pattern matching, including single character wildcards and substring matching.

•Jan 1, 2012•0 citations

On Randomness Complexity of 1-Private Protocols

Samuel Dittmer, Rafail Ostrovsky

In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of 1-private computation of n-party AND, the exact complexity is unknown. We study two settings. First, we consider the model of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that two random bits always suffice to compute an arbitrary Boolean circuit C 1-privately: a single designated inputless helper flips the two bits and privately distributes the derived one-time bits to the other helper parties and the input parties as they are needed. We give an explicit construction using seven helper parties per AND gate and three helper parties per XOR gate (plus the single global randomness dealer). Moreover, two random bits are necessary already for the AND functionality (by a reduction to the standard no-helper model together with the lower bound of Kushilevitz, Ostrovsky, Prouff, Rosén, Thillard and Vergnaud (TCC '19), and therefore the worst-case helper-party randomness complexity is exactly 2 bits. Second, in the setting without helper parties, we improve the upper bound from Couteau and Rosén (Asiacrypt '22) on the (asymptotic) randomness complexity of n-party AND from 6 to 5 bits. That is, we give a 1-private protocol for computing the AND of n parties' inputs requiring 5 bits of randomness, for all n ≥ 6. Our construction, like that of Couteau and Rosén, uses a single party to flip the 5 bits and distribute the required derived values during the execution. Our approach to both problems is built around a more systematic exploration of techniques for recycling randomness across sub-computations. As part of resolving the second problem, we isolate an exact local-independence combinatorial object called a Sliding-Window Independence Generator, or a SWIG. A (k,m)-SWIG is a linear generator from a k-bit seed to m ≥ k output bits, where every cyclic length-k sliding window chosen from m output bits is perfectly uniform. We give an explicit (k,m)-SWIG for every k ≥ 1 and every m ≥ k and use a (5,n-1)-SWIG in our no-helper AND protocol.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

Secure Multiparty Computation with Partial Fairness

Amos Beimel, Eran Omri, Ilan Orlov

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.

arXiv:1011.5567•Nov 25, 2010•0 citations

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation.

Ran Cohen, Yehuda Lindell

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.

•Jan 1, 2014•0 citations
We investigate the relations between two major properties of multiparty protocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of colluding faulty parties, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness is measured in terms of the total number of random bits needed by the parties in order to execute the protocol. Previously, the upper bound on the amount of randomness required by general constructions for securely computing any non-trivial function f was polynomial both in n, the total number of parties, and the circuit-size C(f). This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one faulty party). In this paper, we show that for any linear-size circuit, and for any number t ! n=3 of faulty parties, O(poly(t) \Delta log n) randomness is sufficient. More generally, we show that for...
We investigate the relations between the fault tolemnce (or resilience) and the mndornnea requirements of multiparty protocols.Fault-tolerance is measured in terms of the maximum number of colluding faulty players, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honeat players).Randomness is measured in terms of the total number of random bits needed by the players in order to execute the protocol.Previously, the upper bound on the amount of randomncm needed for securely computing any non-trivial function ~was polynomial both in n, the total number of parties, and the circuit-size C(f).This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one malicious player).In this paper, we show that for any linear-size circuit, and for any value t < n/2, O(poly(t) .log n) randomness is srtflicient.More generally, we show that for any function j with circuit-size C(~), we need only O (poiy(t) .log n + polg(t) .~) randomness in order to withstrmd any coalition of size at most t.Moreover, in our prot~ CO1 only t + 1 players flip coins and the rest of the players are deterministic.Our results generalize to the case of adaptive adversaries as well.
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.
The question of how to construct optimally efficient secure protocols is a central question in cryptography and in the computer security world at large. We focus in this work on several facets of this question, with a particular view towards the role of randomness in secure computation. The use of random inputs is ubiquitous in cryptographic primitives. However, the ability to consistently draw from large random sources may be a barrier in practice. We examine the existence of optimally strong pseudorandom sources with particularly efficient implementations; namely, we construct exponentially hard pseudorandom generators that can be computed by circuits that have size linear in the generator output. Conversely, we also examine efficient protocols that rely only minimally on their random inputs. In the resettable security model, parties may be forced to use the same random input across polynomially many interactions with other parties. We examine this security model in the case of zero knowledge proofs, which are a primitive frequently required in secure computation protocols when one party must prove that they have executed the protocol correctly to another party without revealing secret inputs and compromising security. Finally, we examine the secure and efficient implementation of a specific functionality, including its various required cryptographic primitives (such as zero knowledge arguments of knowledge). In particular, we construct a protocol that securely realizes pattern matching, including single character wildcards and substring matching.
In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of 1-private computation of n-party AND, the exact complexity is unknown. We study two settings. First, we consider the model of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that two random bits always suffice to compute an arbitrary Boolean circuit C 1-privately: a single designated inputless helper flips the two bits and privately distributes the derived one-time bits to the other helper parties and the input parties as they are needed. We give an explicit construction using seven helper parties per AND gate and three helper parties per XOR gate (plus the single global randomness dealer). Moreover, two random bits are necessary already for the AND functionality (by a reduction to the standard no-helper model together with the lower bound of Kushilevitz, Ostrovsky, Prouff, Rosén, Thillard and Vergnaud (TCC '19), and therefore the worst-case helper-party randomness complexity is exactly 2 bits. Second, in the setting without helper parties, we improve the upper bound from Couteau and Rosén (Asiacrypt '22) on the (asymptotic) randomness complexity of n-party AND from 6 to 5 bits. That is, we give a 1-private protocol for computing the AND of n parties' inputs requiring 5 bits of randomness, for all n ≥ 6. Our construction, like that of Couteau and Rosén, uses a single party to flip the 5 bits and distribute the required derived values during the execution. Our approach to both problems is built around a more systematic exploration of techniques for recycling randomness across sub-computations. As part of resolving the second problem, we isolate an exact local-independence combinatorial object called a Sliding-Window Independence Generator, or a SWIG. A (k,m)-SWIG is a linear generator from a k-bit seed to m ≥ k output bits, where every cyclic length-k sliding window chosen from m output bits is perfectly uniform. We give an explicit (k,m)-SWIG for every k ≥ 1 and every m ≥ k and use a (5,n-1)-SWIG in our no-helper AND protocol.
A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.