# Tag Info

9

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

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

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

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

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem. Typically MPC works by translating your function into a ...

3

You can solve this using mixnets. Sample protocol: The parties jointly choose a public/private keypair, such that the random key is shared among all $n$ parties. (This is threshold crypto, and there are standard protocols for this.) Each party $P_i$ encrypts his/her value $v_i$ under the public key chosen in step 1. He/she broadcasts this ciphertext ...

3

I must confess to not fully understanding your question but hopefully this will assist. To generate a public key in Elgamal, you need a group (e.g., subgroup $\mathbb{G}_q$ of $\mathbb{Z}_p$ for large primes $p,q$) and a generator ($g$ where $\mathrm{order}(g)=q$). A secret key is chosen from $x \in_r \mathbb{Z}_q$ and the public key is computed as ...

3

Really the connection is intrinsic. There is at least one other paper I know of that mentions it specifically, however. That is the SPDZ paper. The relevant quotes are below for your convenience. Recently, another approach has become possible with the advent of Fully Homomorphic Encryption (FHE) by Gentry. In this approach all parties first encrypt their ...

3

Aaron Roth on theoretical CS was kind enough to answer with the following answer for anyone out there who is interested. What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of ...

3

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

3

First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references). So we could simply do something like this: while k >= m: k = k-m $m$ could be public or secret ...

3

Your simple approach is not bad, but you might consider these modifications: First, you don't need a PRF, any form of hashed key or a simple hash over the concatenation of a key and the element should be enough. Basically any one-way function over elements and some sort of key should do the trick, and you can optimize for speed. The key is not chosen by ...

2

This question makes no sense to me. You probably will need to edit it. It makes no sense to ask for the users to "agree" on anything, since the other $n$ parties have absolutely no information about $D$ other than what is provided by $u$. So, your requirements don't make any sense to me. If the output of the protocol depends only upon $D$, and if one ...

2

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

2

Yes and no. A threshold cryptosystem means the decryption key can be split into $n$ shares such that only $t\leq n$ are required to recover it. That property in isolation is not useful for multiparty computation. However when you combine a threshold cryptosystem with one that is at least partially homomorphic (meaning you can do some operation, like ...

2

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

2

You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$. What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by ...

2

I think your first question is answered by K.G., so I'll tackle the other two Why not the inputs? The paper talks about a "secret state". Is the secret state different from input/output? Often the inputs of the corrupted parties assumed to be known, but not those of the honest parties. As far as the secret state, a quote from the abstract might help: ...

2

Suppose you have a black box with some buttons and some lights. When you push the buttons, the lights go on and off. You wonder what's inside, but you cannot open the box. The only way to figure out what's inside is by pushing buttons and observing the lights. Now suppose you have two black boxes. You wonder if they are the same on the inside. Again, you ...

2

The term you are looking for is homomorphic encryption. This allows you to evaluate a general circuit (so no branches) on encrypted data without knowing the decryption key. It works in theory, but to my knowledge no practical applications have been developed yet. They are either incomplete (only allowing addition, XOR, or some other operation) or ...

2

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

2

There is no source code to simulate this. It is a theoretic construct used in security proofs. Cryptography is often about the very limits of what could be calculated. This is quite far from actual programming source code. For example, quite often something is called "efficient" in cryptography, if the algorithm runs in polynomial time (for some parameter). ...

1

It is easy to observe that any secure protocol must touch every bit of both parties' inputs -- otherwise it's not secure. However recent work has shown that you can amortize the protocol complexity over several runs, with state stored between the runs, so that not every execution will touch every bit. See here for the paper. It doesn't address set ...

1

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

1

Basically, there a many real-world problems where one might want to compute something on sensitive data several times. Indeed, later in the paper you cite, the authors give several example, e.g.: "Medical Data: One may envision a huge database which contains the medical data of every patient in the US. To compute any global statistic on this data, one ...

1

I believe the basic idea is the following: Choose $m$ so that $\: \sum p_i \:$ can be efficiently recovered from $\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \:\:$. Each party $i$ chooses $\:n\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ elements $\:q_{i,\hspace{.03 in}j}\:$ of \$\:\{0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 ...

1

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

1

As @nightcracker explains, fully homomorphic encryption (FHE) is one possible solution (though not practical). There are others, some of which are practical. Multiparty computation is another possible solution. The tradeoff here is that MPC typically requires more communication than FHE, but the result is that it can be practical for many situations. The ...

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