Hot answers tagged

10

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation). The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic ...


9

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 ...


7

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 ...


7

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 ...


7

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 ...


7

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 ...


7

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 ...


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 ...


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

the securty of 1-n OT is a function of the security of a 1-2 OT. So in analysis it is easy to use 1-2 OT for security proofs. A 1-n OT is essentially a multiple run of a 1-2 OT. (somewhat like a byte is made of 8 bits) So IMO the question is like asking why use bits when you can use bytes for communication. [it depends on the application]


6

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


6

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: ...


5

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation. However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write: To compute some arbitrary ...


5

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, ...


5

It's not possible because if $B$ knows $b$ and $g^{ab}$, then she can compute $\left(g^{ab}\right)^{b^{-1} \bmod N} = g^a$ (where $N$ is the order of $g$, which is normally prime so that $b^{-1} \bmod N$ exists). EDIT: As noted by poncho in the comments, this assumes we are in a typical discrete logarithm setting, where the order of the group is prime to ...


5

As the previous answer says, they are certainly NOT the same. However, there is certainly a connection between them. Specifically, the covert model just says that there is a deterrent parameter $\epsilon$ and the guarantee is that if the adversary tries to cheat then it will be caught with probability at least $\epsilon$. The question that arises is how ...


5

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 ...


5

In the vast majority of cases, the simulator sets the random tape of the adversary simply because it has to (by the definition). So, the simulator sets it in the beginning to be uniform, and this is then ignored from then on. There is one cases that I know of that this is actually really important, and this is non-black-box zero knowledge. Specifically, in ...


5

You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ ...


4

The one I'm most familiar with is the SPDZ protocol. The authors have implementing AES via SPDZ with up to 10 parties.


4

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 ...


4

I guess you are talking about Figure 5.3? It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting. To see why a cheating verifier is a problem in Figure 5.3 think ...


4

Ok, here we are speaking of non-interactive zero-knowledge proof systems for some language $L\in NP$. We there have a pair $\sf (P,V)$ of probabilistic polynomial time algorithms (called the prover and the verifier) where both have input $x\in L$ and $\sf P$ additionally holds a secret witness $w$ for membership of $x$ in $L$ and wants to convince a ...


4

There might be better ways to do this, but I wanted to do it with only primitives found in VIFF (why? because it is the MPC framework I am most familiar with). There could be specialized protocols which are better. In VIFF, we have access a primitive >= which returns 0 or 1 (false or true). We can do the comparison you seek using that plus some simple ...


4

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 ...


4

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same). If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input. Consider a concrete example, the ...


4

Here is a concrete example of how the receiver could extract information about the senders input: Assume the circuit to be evaluated is the simple circuit computing $(x \oplus (y \wedge z)) = w$, where $x, y$ is the input of the sender and $z$ the input of the receiver. Note, that $w$ and $z$ alone does not reveal the value of $y$ (you can write down the ...


4

In short, A cryptography scheme is a homomorphic encryption scheme if it is somehow equivalent to manipulate its plaintexts and its ciphertexts. Secure multi-party computation and secure circuit evaluation are protocols to calculate functions in a distributed way without disclosing the data owned by each party and blind computation is any technique for ...


4

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 ...


4

This is very strange, and somewhat suspect. The abort here is one that prevents the client from getting output. However, the real-world adversary may behave in a way that the client does get output. I suggest writing to the authors to ask and/or going through this very carefully. Without having gone through the details at all, my initial guess is that this ...



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