34
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 ...
- 5,773
22
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 ...
- 7,629
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 ...
- 38.5k
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.
- 27.6k
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 ...
- 1,303
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 ...
- 27.6k
12
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. ...
- 121
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 ...
- 145k
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, ...
- 19.1k
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 ...
- 12k
10
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 ...
- 12k
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 ...
- 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 ...
- 27.6k
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,836
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 ...
- 27.6k
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 ...
- 27.6k
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. ...
- 27.6k
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.6k
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))$.
- 11.7k
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 $...
- 138k
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 ...
- 19.1k
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 ...
- 27.6k
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 ...
- 27.6k
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,867
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$-...
- 45.9k
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 ...
- 27.6k
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,759
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 ...
- 4,148
7
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 "...
- 3,922
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 ...
- 27.6k
Only top scored, non community-wiki answers of a minimum length are eligible