Tag Info

Hot answers tagged

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

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

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

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

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

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

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

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


3

In here, it is 1-2 oblivious transfer meaning that for each $i$, the receiver gets $A'_{i1}$ or $A'_{i2}$ but the sender does not know which. The length of the elements $A'_{ij}$ is not important as long as you choose a correct oblivious transfer protocol.


3

The simplest way to do this would be to have the sender randomly shuffle the elements. The receiver chooses a random element to request. That way the receiver has no idea which of the original (before the shuffle) elements he got.


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

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

MPC implementated on largest scale for danish farmers sugar beet auctions using http://viff.dk/ another framework http://sharemind.cyber.ee/


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

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

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

Your protocol is good (assuming an honest-but-curious adversary model). As DrLecter pointed out, each party will need to publish their sum of shares. To recover the answer, each party then simply xors all published values.


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

I think they are saying assuming leak free is necessary to prove security for their protocol, but it would be really cool (thus an open problem) to design a protocol that can tolerate leaks in any stage.


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

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


2

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



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