5

A protocol (and in general, a cryptographic construction) satisfies information-theoretic security if no adversary can break the system, no matter how powerful the adversary is. The term "information-theoretic" is rooted in the idea that the leakage from the interaction can be studied from the perspective of information theory, and it can be ...


5

[...][Most] of the MPC protocol is built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$($p$ is a big prime), why? The relevant protocols for $\mathbb{Z}_{2^\ell}$ most likely use boolean sharing / boolean garbled circuits (representing each individual bit as a shared value) whereas the ones for $\mathbb{Z}_p$ use ...


4

So the gist of my question here is about the usage of my field size, that I use for modulo. Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in Wikipedia if you're interested), however addition and multiplication modulo a composite (...


3

Lindell's "How to Simulate It" tutorial uses what is known as the standalone security model. See Section 10.1 for a discussion. The standalone model analyzes the security of a protocol instance, in isolation. The UC model analyzes security in the presence of arbitrary "other things going on in the world" concurrent with the protocol ...


3

If Alice is the only person to speak, but Bob can learn output, then the protocol must leak more than just $f(x,y)$. See: Halevi, Lindell, Pinkas: Secure Computation on the Web: Computing without Simultaneous Interaction Essentially, Bob can choose many different $y_i$ values and re-run the protocol to learn many different $f(x,y_i)$ outputs. Since Bob ...


3

Bolt labs uses Garbled circuits (from emp-toolkit) for channel management between the merchant and the customer. More on their blog post In general, I don't think Garbled circuits is one of the most efficient MPC protocol out there for most tasks. So you're not likely to find many practical applications.


3

It depends if you want many instances (like 1 million) of OT, or just a few. For a small number of OTs, I would recommend looking at our very recent paper: McQuoid, Rosulek, Roy: Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions, CCS 2020. We're not aware of other protocols whose communication is independent of $N$. For a ...


3

A secret-sharing scheme allows you to distribute a secret message among multiple parties. However, a fundamental question is how this message is represented. In many SS schemes, this message is an integer between $0$ and some maximum value $M-1$ (for unsigned values), and whenever you add secret-shared values, the addition happens modulo $M$. Addition modulo ...


2

However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer. Of course you can do that. In fact there are examples in the very repository you linked to, e.g. wire 3488 of the AES-128 implementation is used twice.


2

It is more likely to find applications of secret-sharing based multiparty computation instead of garbled circuit-based. In fact, of the former type several applications can be found such as the sugar beet in Denmark or the analysis of gender income inequality in Boston (sorry, I’m on mobile and it’s hard to provide references). MPC based on garbled circuits ...


2

There is a model, typically called proactive security (and sometimes also called a mobile adversary), that considers the case that parties can be corrupted and later uncorrupted. Time is divided into epochs and security holds as long as the appropriate threshold of parties is honest in each epoch. In the dishonest majority case, this means that unless all of ...


2

As discussed in @SEJPM's answer, traditionally, MPC over $\mathbb{Z}_{2^l}$ usually adopt boolean sharing while MPC over $\mathbb{Z}_p$ adopt arithmetic sharing and they mainly differ in the "primitve" set of operations they provide. However, a few recent works (refer CDE+18,GRW18,KPPS20 and the works they cite) focus on efficient MPC for small ...


2

It is not true that RLWE guarantees that $h_i$ is computationally indistinguishable from uniform for any fixed $p_1$: just consider the case of $p_1 = 0$. At the opposite end, if $p_1$ is invertible is $R_q$ (which is the generic case), then each $h_i$ is exactly uniformly distributed in $R_q$, and they are all independent, so the joint distribution is just ...


2

In interactive protocols (like MPC) you will often see a combination of computational and statistical security parameters used together. Computational security parameter: tunes the hardness of some attack that depends on the adversary's running time. For example, a protocol uses a pseudorandom function, and breaking that pseudorandom function will break ...


2

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets. A simple application of arithmetic secret-sharing based secure multi-party computation ("arithmetic GMW") can do that. The protocol ...


1

This really depends on which garbling scheme is used. Using the state-of-the-art half-gate scheme (here), your question has been the subject of a paper by Dupin, Pointcheval, and Bidan, which can be found here. The bottom line is: any such attack amounts to adding or removing NOT gates arbitrarily in the original circuit. Whether this can be used to leak the ...


1

I'll focus on semi-honest security in this response. You can divide the relevant PSI protocols into two categories: In Diffie-Hellman-based protocols (originating in Huberman-Franklin-Hogg), the parties must calculate a few exponentiations for each item in their sets. In Oblivious-transfer-based protocols (the leading ones in this case would be KKRT and ...


1

In most FHE schemes, the ciphertexts contain noise which grows after performing operations. Its growth for additions is usually negligible compared to multiplications. In addition, the cost of operations is different. Therefore, one wants to minimize the multiplicative depth but also the number of multiplications as they are more costly. For example, in the ...


1

In general, AND gates are no big deal. In practice however, many zero-knowledge systems are based on rank-1-constraint systems (R1CS, often "arithmetic circuits" in folklore), and the concern that LowMC tries to address is linked to this practicality. Note that I'm talking from the perspective of ZK, although the principles probably carry over to ...


1

I don't think there are some guidelines as such. However, different approaches have been considered. A common consideration across several implementations that aim at making these things more accessible in practice (e.g. TF-Encrypted, or PySyft) is to consider a third trusted party that distributes the necessary preprocessing material before the computation ...


1

Yes it does. Here is a brief summary from https://eprint.iacr.org/2009/214.pdf: When a majority of the parties are honest, efficient and completely fair coin-flipping protocols are known as a special case of secure multiparty computation with an honest majority (assuming a broadcast channel) as in M. Ben-Or, S. Goldwasser, and A. Wigderson Completeness ...


1

The multiplication is indeed correct without adding the randomness, but it is no longer private (i.e., it leaks information). By adding the correlated randomness, it ensures that what any single party sees during the computation is just uniformly distributed and reveals nothing.


1

The protocol is only designed to work when $a$ is in the range $\{-2^{k-1},\dots,2^{k-1}-1\}$. This ensures that $c$ doesn't overflow mod $p$, as long as $p$ is sufficiently large. In the paper they ensure this by choosing $p > 2^{k+\kappa+\log n}$, where $\kappa$ is a statistical security parameter and $n$ is the number of parties. See the discussions on ...


1

Lets first state the definitions. Consider a two party computation, where $i\in(1,2)$ Definition 1 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a probabilistic polynomial time algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that ...


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