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

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


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

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


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]


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

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


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

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


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


4

Realizes vs Implements Given the context of the cited papers, they mean the same thing. That said, I would prefer realizes. Implements has a connotation of a source code implementation. There could be implementation flaws (buffer overflow, etc) that impact security. The protocol design is secure, but the implementation is not. That, to me, is the primary ...


4

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


3

Concerning some trade-offs between GC and FHE, some of these are described in the introductory chapter of Gentry’s PhD thesis available here http://crypto.stanford.edu/craig/. In essence, for a private information retrieval type of scenario where an encrypted data set is stored in the cloud, the communication complexity of a private query is potentially high ...


3

It depends on what you mean by interaction. Some protocols for secure multiparty computation, e.g. those based on Shamir secret sharings and the GMW protocol, require the servers to communicate a lot during the computation. In other protocols, such as those based on Yao's garbled circuits (e.g. Fairplay MP), the interaction between servers is reduced in ...


3

I believe what you are describing is somewhat orthogonal to typical MPC adversary models. Typically in MPC we let the adversary know all information that corrupt parties know (so if a corrupt party learns the output, the adversary is allowed to learn the output). What we care about in MPC protocols is that the adversary is not able to learn any additional ...


3

there are some special constructions that could be used. for example see this paper of florain kerschbaum (freely available version). also, you can use some secure DFA evaluation protocols, as any regex can be represented as a DFA. what you have proposed is not secure and the servers can learn lots of information.



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