We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.
We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.
We consider interactive computation of randomized functions between two users with the following privacy requirement: the interaction should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings. We also study perfectly secure non-interactive computation when only one of the users computes a randomized function based on a single transmission from the other user. We characterize randomized functions which can be perfectly securely computed in this model and obtain tight bounds on the optimal message lengths in all the privacy settings.
Two user secure computation of randomized functions is considered, where only one user computes the output. Both the users are semi-honest; and computation is such that no user learns any additional information about the other user's input and output other than what cannot be inferred from its own input and output. First we consider a scenario, where privacy conditions are against both the users. In perfect security setting, Kilian gave a characterization of securely computable randomized functions in [1], and we provide rate-optimal protocols for such functions. We prove that the same characterization holds in asymptotic security setting as well and give a rate-optimal protocol. In another scenario, where privacy condition is only against the user who is not computing the function, we provide rate-optimal protocols. For perfect security in both the scenarios, our results are in terms of chromatic entropies of different graphs. In asymptotic security setting, we get single-letter expressions of rates in both the scenarios.
We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.
We consider interactive computation of randomized functions between two users with the following privacy requirement: the interactive communication should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings.
In information theoretically secure multiparty computation, several mutually distrusting users want to jointly compute a function of their private data such that users do not learn any additional information about other users' data other than what they can infer from their own data and the function value they compute. In this work we consider asymptotically secure computation - where vanishing probability of error and vanishing information leakage are allowed as block lengths become large - in a three user setting, where two users have inputs and third user securely computes the output of a function on these two inputs. We provide generic lower bounds on the amount of communication required among users and the total amount of private randomness needed to compute any function in this three-user model. We also consider some examples where our bounds are tight. Our lower bounds are derived for the honest-but-curious security model and hence also apply for the malicious model.
Consider two parties, Alice and Bob, who hold private inputs x and y, and wish to compute a function f (x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f (x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f (x, y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties' inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and errorresilience are contradictory goals. In particular, we show that for every constant c > 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.