29 votes
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 ...
user avatar
21 votes
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 ...
user avatar
  • 7,246
17 votes

Simulation based proofs: Simple examples

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.
user avatar
17 votes
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 ...
user avatar
  • 37.7k
16 votes
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). ...
user avatar
  • 37.7k
13 votes

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 ...
user avatar
12 votes
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 ...
user avatar
12 votes
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 ...
user avatar
  • 132k
11 votes

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, ...
user avatar
10 votes
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 ...
user avatar
10 votes
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 ...
user avatar
  • 356
10 votes

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 ...
user avatar
10 votes

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 ...
user avatar
10 votes
Accepted

Examples of protocols that are insecure when run concurrently

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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$-...
user avatar
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 ...
user avatar
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 $$[...
user avatar
  • 1,699
7 votes

Is it possible to find the product of two numbers without knowing the two numbers?

In the way you setup the problem the answer is No. As Charlie can perform $C(A(1),B(b))$.
user avatar
  • 10.5k

Only top scored, non community-wiki answers of a minimum length are eligible