# Tag Info

Accepted

### Why can't the commitment schemes have both information theoretic hiding and binding properties?

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an ...
• 5,609
Accepted

### Constructing Garbled Circuits

In order to answer this, you need to be sure to understand how garbled circuits actually work. I'll try to explain this from top to bottom: The protocol Let Alice and Bob be willing to compute ...
• 7,246

### Simulation based proofs: Simple examples

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.
• 26.9k
Accepted

### Salary Negotiation Problem

Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else. So ...
• 37.7k
Accepted

### What does "circuits" mean in Cryptography?

Circuits can be expressed using very simple operations. For example, a boolean circuit consists of only two types of gates, addition and multiplication (where the input values are each 1 bit). ...
• 37.7k

### What are the roles of the simulator in simulation based proofs

In general, the role of the simulator in simulation-based proofs is to show that the real protocol behaves like some idealized one. Actually, simulation goes back to the original definition of ...
• 26.9k
Accepted

### The main differences between Sketch of Proof and Full proof

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and ...
• 26.9k
Accepted

### Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key ...
• 132k

### What are the ways to generate Beaver triples for multiplication gate?

Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, ...
• 16.7k
Accepted

### Simulation Based Proof: What Can / Can not Simulator Do?

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can ...
• 26.9k
Accepted

### Efficiency of oblivious algorithms vs non-oblivious algorithms?

Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to ...
• 356

### How to securely compute AES where the key is splitted across different servers?

If you only use secret sharing, then upon reconstruction the key could be stolen. Therefore, secure multiparty computation can be used. There are many different methods, depending on your setting. If ...
• 26.9k

### Why can't the commitment schemes have both information theoretic hiding and binding properties?

Another way to look at it informally is this; If it is perfectly hiding, then you cannot tell what made the final value. It could equally be any combination. If it is perfectly binding, then there ...
• 1,243
Accepted

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table: $$\begin{array}{c|cc} f & L & R \\ \hline U & 0 & 0 \\ D ... • 10.6k 9 votes ### garbled circuit vs fully homomorphic encryption Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later ... • 91 9 votes ### Real world use cases of Multi-Party Computation As I mentioned in a comment, a relatively new application of multi-party computation is its use as a countermeasure against (mainly hardware) side-channel attacks. In particular, there is a method ... • 1,786 9 votes Accepted ### Why can't garbled circuits be reused? One of the security guarantees of garbled circuits is that the evaluator doesn't learn anything about the circuit beyond the output on the given input. Executing more than one input string will break ... • 1,245 9 votes Accepted ### Beavers Triple Vs BGW Multiplication on MPC Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other ... • 10.6k 9 votes Accepted ### Difference between secure function evaluation and private function evaluation? You will find similar terminology interchanged a lot in this field. So, secure multiparty computation can take the acronym MPC, SFE, SMC and so on. In general, you should look at each paper closely to ... • 26.9k 8 votes Accepted ### What is an example of a secure sigma proof? Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform ... • 26.9k 8 votes Accepted ### 2 party AND computation under passive perfect security The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. ... • 26.9k 8 votes Accepted ### Paillier encryption: Many private keys for a public key No, that doesn't work. If one party chooses primes p,q and sets n = pq, then other parties would also have to know p and q, because it is the only way to get the same n. But you just left ... • 12.3k 8 votes ### Why can't the commitment schemes have both information theoretic hiding and binding properties? To be a little more formal, consider the notation provided by Iftach. Assume a commitment scheme (S,R) is statistically hiding. This means that a computationally unbounded R is unable to get any ... 7 votes Accepted ### Optimal threshold for passive and perfect security The way to extend the proof to arbitrary t,n and this threshold is as follows. Assume that there exists a protocol for any n parties that withstands a threshold of t=n/2 corrupted parties, for ... • 26.9k 7 votes Accepted ### Importance of round complexity in determining the efficiency of an MPC protocol First note that all polynomial-time functions can be securely computed with a constant number of rounds (Yao and BMR families) and all can be securely computed with protocols that have rounds ... • 26.9k 7 votes Accepted ### SPDZ for the 2-party case Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation ... • 2,857 7 votes ### Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box? Here's one more way in which a dishonest participant can mess with Shamir's secret sharing: Let's briefly review how secret reconstruction in Shamir's (k,n) secret sharing works. Given the x-... • 44.4k 7 votes Accepted ### Secure function evaluation for Boolean formulae For log-depth circuits, it is possible to use an information-theoretic version of Yao's garbled circuits. Note that in a garbled gate, each key is used to encrypt twice. Thus, if the keys on the input ... • 26.9k 7 votes Accepted ### Paillier Homomorphic encryption to calculate the means The Paillier encryption of an integer x_i is given by c_i = (1+x_iN)r_i^N \bmod N^2 for some random 0<r_i<N. Given the encryption of x_1, \dots, x_k, the encrypted mean is defined as$$[...
• 1,699
In the way you setup the problem the answer is No. As Charlie can perform $C(A(1),B(b))$.