We’re rewarding the question askers & reputations are being recalculated! Read more.
18

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 unbounded committer), so the scheme is not perfectly binding.


17

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 Alice and Bob just run the protocol with their respective inputs A and B.


15

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 securely a function $f(x,y)$ (in your example, it would be $f(x,y)=\min(x,y)$) while keeping their respective inputs $x$ and $y$ secret. In order to do so, they ...


14

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


13

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). Furthermore, (boolean) circuits can describe any computation. This is very nice when it comes to fully-homomorphic encryption. All we have to do is provide a way to ...


12

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 semantic security for encryption and is also the way zero knowledge is defined. In these settings, the aim of the simulator is to show that nothing is revealed (in ...


12

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 shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process ...


10

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share ...


10

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 also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ...


10

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 design an ORAM matching the lower bound. No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell ...


10

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 not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow ...


10

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 you are interested in two-party computation with semi-honest adversaries then simple Yao works (e.g., http://eprint.iacr.org/2015/751.pdf); if you are ...


10

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 & 1 & 2 \end{array} $$ Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row). A ...


8

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 this property. For instance, if you allow him to evaluate two inputs, $0^n$ and $1^n$, then he can "mix and match" bits on each gate to determine what kind of ...


8

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 suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more ...


8

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. Likewise, in the opposite direction. Thus, the set of possible transcripts when P1 has 1 and P2 has 0 equals the set of possible transcripts when both have 0, and ...


8

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 see what they mean in their definition. However, pretty much secure function evaluation is just another term for secure computation. In contrast private ...


7

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 you may ask the evaluation of the function on a single input not fixed in advance). Indeed this is the approach to Verifiable Computation proposed in a paper ...


7

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 computing $f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1}$. (If it withstands $t>n/2$ then it also withstands $t=n/2$, so that's fine.) I will now construct a two-...


7

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 advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold: ...


7

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 out a part of the public key, which is $g$. This results in a different question: If you have a trusted party set up $n$ and assign different $g$ values to each ...


7

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 protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ ...


7

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$-coordinates of $k$ participants $(x_1, x_2, \dots, x_k)$, one way to reconstruct the secret is to compute the Lagrange basis polynomials: $$\ell_j(x) = \prod_{1 \...


7

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 wires are double the length of the keys on the output wires, then one-time pad encryption can be used and the result is information theoretically secure. See ...


6

There is the Might Be Evil framework and FairplayMP. The hcrypt project also has a secure function evaluation library. UPDATE: Also, VIFF and SCAPI (though as of writing this, the SCAPI framework is not fully released). March 2016: I just came across FRESCO.


6

There are roughly two common techniques for multi-party computation, garbled circuits and secret sharing. Either may work for your situation, so I've detailed some info and recommendations about each below. Garbled Circuits GC is most often applied to the 2 party case. It can be made to be secure against malicious adversaries and can be fairly efficient (a ...


6

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 called "threshold implementations" which is based on a form of secret sharing. A relevant reference would be the paper Secure Hardware Implementations of ...


6

Suppose Alice has $x$ and Bob has $y$ in your scenario, and let $\pi =(\pi_A, \pi_B)$ be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice. Define the following algorithms / random variables: ${\sf Real}(\pi, y,\mathcal{A},1^k)$: Internally simulate an instance of ...


6

You've got the relationship a bit muddled. A scheme for fully homomorphic encryption can be used to perform secure multi-party computation (MPC). However, it's not a special case of MPC. The connection is a standard elementary result, which I will summarize here. If you want to do secure multi-party computation, you can express the computation as a ...


6

Check out Pedersen's scheme for threshold ElGamal (link). Also, check out (this) for an application to electronic voting. Basically, the scheme works like this. There are $n$ parties, out of which at least $t$ must be reliable or else the scheme collapses. They choose a prime $p = 2q + 1$ where $q$ is also prime, i.e.: $p$ is a safe prime. Additionally, ...


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