Skip to main content
36 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 ...
Chris Peikert's user avatar
23 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 ...
Lery's user avatar
  • 7,709
18 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 ...
mikeazo's user avatar
  • 38.7k
14 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, ...
Geoffroy Couteau's user avatar
13 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, where $S$ denotes the commitment sender and $R$ denotes the receiver. Assume a commitment scheme $(S,R)$ is statistically hiding. ...
Russell Pekala's user avatar
13 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 ...
WeCanBeFriends's 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 ...
Yehuda Lindell's 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 ...
poncho's user avatar
  • 148k
11 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 ...
Mikero's user avatar
  • 13.5k
11 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 ...
Mikero's user avatar
  • 13.5k
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 ...
redplum's user avatar
  • 376
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 ...
Yehuda Lindell's 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 ...
Aleph's user avatar
  • 1,876
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 ...
Yehuda Lindell's user avatar
9 votes

Statistical security parameter -> information theoretically secure

In interactive protocols (like MPC) you will often see a combination of computational and statistical security parameters used together. Computational security parameter: tunes the hardness of some ...
Mikero's user avatar
  • 13.5k
8 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 ...
Yehuda Lindell's 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 ...
tylo's user avatar
  • 12.7k
8 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))$.
Meir Maor's user avatar
  • 11.8k
8 votes
Accepted

Statistical security parameter -> information theoretically secure

A protocol (and in general, a cryptographic construction) satisfies information-theoretic security if no adversary can break the system, no matter how powerful the adversary is. The term "...
Daniel's user avatar
  • 3,972
8 votes
Accepted

Is there a way to calculate a hash with two people so that no one knows the pre-image but if they get together they do?

One simple option: The preimage consists of 2 segments $M_A$, $M_B$ of 64 bytes each. They are given to or chosen by $A$ and $B$ respectively. $A$ computes the 32-byte $H_A=R(\mathsf{IV},M_A)$ where $...
fgrieu's user avatar
  • 142k
8 votes
Accepted

What is malicious privacy?

Yes to both. I am not sure the name is extremely standard, but it is relatively common to view security as privacy+correctness. Similar notions have appeared in other works under different names (for ...
Geoffroy Couteau's 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 ...
Guut Boy's user avatar
  • 2,877
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$-...
Ilmari Karonen's 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 ...
Yehuda Lindell's 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 $$[...
user94293's user avatar
  • 1,779
7 votes
Accepted

Extractability for Simulator in Malicious Model

Let me try. First, one thing needs to be clear: simulation and real execution are two different things. The simulator can learn something does not mean a verifier in real execution can learn the same ...
Changyu Dong's user avatar
  • 4,188
6 votes
Accepted

SPDZ protocol: how expensive is it to generate the multiplicative triples?

The answer to your question can be found in a SPDZ follow up paper; it is described as contribution (2) in the intro (top of page 2). There is a new version of SPDZ called MASCOT that uses OT instead ...
Yehuda Lindell's user avatar
6 votes
Accepted

Homomorphic $\bmod p$ operation

Is there any protocol, that given $E(m)$ can compute homomorphic $E(m \bmod p)?$ If there were a way to perform that operation (for any $p>1$ relatively prime to $N$) without the Pallier private ...
poncho's user avatar
  • 148k
6 votes
Accepted

Is security against semi honest adversary inheritable?

In general, no, you cannot do that. That is why frameworks like universal composability exist. In the UC framework, you prove a protocol, $\pi_1$ is secure according to some adversary model. You do ...
mikeazo's user avatar
  • 38.7k
6 votes
Accepted

An example of of an information theoretically secure protocol that is not cryptographically secure

In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is ...
Yehuda Lindell's user avatar

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