Multi-party computation (MPC) allows a set of parties, each with a private input, to securely and jointly perform any computation over their inputs.
1
vote
0answers
36 views
Testing whether a secret value is zero without security bits (in SPDZ)
To test whether a secret value $[x]$ is zero, where $x \in [0,2^{k−1}]$, SPDZ uses the a based on the method of Catrina and de Hoogh [1].
This method requires to working on a field with modulus $p>...
0
votes
0answers
28 views
Using SPDZ over smaller field
While trying to implement SPDZ of a function (using the fresco framework[1]),
it enforce me to work on a larger field than the one that I need.
This occur because I'm trying to use functions such as "...
0
votes
0answers
15 views
Fiat-Shamir identification protocol how work with prpoabilty for following case study?
Consider a Fiat-Shamir identification protocol run between a prover and a verifier. To start,
the prover selects a secret s(1 ≤ s ≤ n) co-prime to a RSA like modulus n, and computes
v = s^2 mod n and ...
0
votes
2answers
86 views
How to compute secure sum using secure multparty computation?
Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X
$, $Y$ and $Z$ respectively (with 2 bits ...
0
votes
0answers
26 views
Adding new participants to a multiparty signature scheme
I'm looking for a signature scheme that allows a group of N parties, without the help of a trusted dealer, to:
Jointly create a group public key $P$
Produce a valid signatures for an arbitrary ...
5
votes
1answer
67 views
How to determine the layers of a circuit?
In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically ...
0
votes
1answer
32 views
In Multi-party communication, how can I find that one encrypted value is negative or not?
I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob.
Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key ...
2
votes
1answer
51 views
computing INV in boolean circuit for MPC
Is it feasible to generate an efficient MPC function that compute $a^{-1}$ for $a \in \mathbb{F_q}$, with Boolean circuit?
The naive way seems impossible since the depth of the computation might ...
2
votes
1answer
39 views
What is shared-input for Multi Party Computation?
I heard shared input.
For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$.
Each share is ...
2
votes
0answers
44 views
Multi-Party Offline Key Exchange Using Public and Private Keys
I hope the title already explains the problem I have in mind; but let me lay out some more details.
Given public-private key pairs $P_A, P_B, P_C, ... P_Z$, (first $3$ of which are owned by our usual ...
2
votes
0answers
25 views
complete functionality for fair multiparty computation
I found a statement in a paper "We reduce the fairness problem in MPC to the problem of fair decryption. Fair decryption was shown to be a complete functionality for fair MPC (shown by Dov Gordon in ...
1
vote
1answer
60 views
Check if $a<b$ in a trustless scenario
Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need ...
1
vote
0answers
25 views
Threshold Bitcoin signature scheme
Any advice would be appreciated:
It seems to me that using an uncomplicated combination of a shamir scheme and schnorr it's fairly trivial to have a threshold signature scheme.
I think it's also ...
3
votes
2answers
136 views
How to use Homomorphic encryption for secure computing Arctan() function?
In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their ...
4
votes
2answers
115 views
Atomic multi-party commitments
Alice and Bob publicly choose the messages $M_A$ and $M_B$ and independently sign them (Alice privately signs $M_A$, Bob signs $M_B$).
Now Alice and Bob are looking for a protocol that allows them to:...
3
votes
3answers
67 views
communication efficient private lookup
I have a scenario where a client has a private set and the server has a large public set, we would like an estimate of the intersection size or more specifically the percent of the private set covered ...
1
vote
1answer
113 views
AES encryption using MPC SPDZ protocol
I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT).
However I'm thinking about practical application of SPDZ for AES ...
3
votes
1answer
82 views
Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?
I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
2
votes
1answer
75 views
How can Alice enable Bob to look-up values in a private map
I think this problem is similar to private set intersection, yet distinct in a way where:
Alice has an extensive Mapping of say id to name
id1 -> John Doe
id2 -> Jane Doe
id3 -> Edgar ...
4
votes
1answer
89 views
Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security
A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal ...
2
votes
2answers
77 views
Multiparty secret generation protocol
The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their ...
1
vote
1answer
47 views
Difference in the Powers of Simulator and Environment in Universal Composability
I know that in UC model, environment controls the real world adversaries but there is still a simulator wrapped around these real-world adversaries in the ideal world (which we sometimes collectively ...
5
votes
1answer
102 views
Extractability for Simulator in Malicious Model
It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of ...
0
votes
1answer
32 views
Private set supporting adding elements and proving elements exist
Is it possible to construct such a set that parties can
Add elements to the set without revealing the elements or knowing the elements presently in the set.
Proving to other parties that a certain ...
0
votes
1answer
58 views
Enforcing Randomness in Malicious Setting
I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the ...
0
votes
0answers
28 views
Anti-collusion cryptography/schemes for multi party authentication
Due to the fact that 95+%, if I remember correctly, of security breaches are done by insiders (due to malicious intent or incompetence), I made a (experimental) server that uses Shamir Secret Sharing ...
6
votes
1answer
130 views
In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end?
To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]:
Alice sends Bob the commitment $c = commit(x)$
Bob sends Alice ...
0
votes
0answers
23 views
How to assert that n distinct users have generate an aggregate signature?
If We have n users, each one generate message m1 and signs it to generate (σ1).
then by using aggregate signature scheme, we get the aggregate signature of all messages m from n users.
Is there a ...
2
votes
1answer
84 views
About DDH over cyclic group Z*p^2
To construct a secure multiparty computation function, we need to use the cyclic group G = Z*p^2 with p is a large prime. However, we are uncertain that DDH holds over this group.
Can you show that ...
2
votes
0answers
54 views
Necessity of Randomness when Privately Computing a Sum
I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
1
vote
0answers
73 views
Optimized Random-OT Security in Standard Model
I was going through the paper - " Efficient Oblivious Transfer and
Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
2
votes
0answers
20 views
Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?
Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost ...
5
votes
1answer
73 views
Can Secure Multi-party Computation be used to reconstruct secret shares?
When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share?
When searching I have found results ...
3
votes
1answer
38 views
Is it possible to carry out multiplication of BGW protocol without communication?
I read the following famous two papers related to multiparty computation and I have a question like title.
[AL17] Gilad Asharov, and Yehuda Lindell. "A full proof of the BGW
protocol for perfectly ...
1
vote
0answers
25 views
Secure multiparty computation connectivity bound
I read some papers which studied the relation between the fault tolerance in secure multiparty computation and the connectivity of the underlying communication graph. Here I consider information-...
0
votes
0answers
51 views
How to perform homomorphic multiplication using Shamirs secret sharing
Shamir's secret sharing (SSS) support additive homomorphism. The problem with it while dealing with multiplication is it will increase the polynomial degree and as a result number of shares required ...
1
vote
1answer
39 views
Discussion about the importance of communication complexity for MPC?
Communication complexity is generally discussed among many papers on secure multi-party computation (MPC).
However, I do not still understand the importance of it.
What communication complexity ...
0
votes
0answers
53 views
Practical MPC scheme for Elliptic curve multiplication and hash functions
Is there exist a better technique to compute a Multiparty Computation protocol to compute ECC multiplication over shared key between k-players, better than the general purpose Yao's garbled circuits?
...
1
vote
1answer
32 views
Does semi-honest adversary eavesdrop honest parties communication?
Assume we have a multi-party computation protocol and the protocol definition, where both of them consider a semi-honest adversary, without explicitly assuming the type of channel the parties want to ...
1
vote
0answers
45 views
Rewinding techniques with some examples
I'm aware of these posts:
What is a "rewinding argument"?
Random oracle model proofs and programmability
But I think, some concrete examples are missing.
I need to know how exactly ...
1
vote
0answers
79 views
Homomorphic encryption - addition for more than two parties
I have just found out about the homomorphic encryption and I was wondering how is it possible to perform an addition for more than two parties?
More concretely, I want to have several parties $P_i$, ...
2
votes
1answer
68 views
Explanation of correlated randomness for garbled circuits
While studying Yao's garbled circuits I was mentioned that correlated randomness played some part in MPC. I looked for online documentation but everything I've found is far too complicated for me to ...
1
vote
1answer
50 views
Which party have to be online during garbled circuit-based MPC protocol?
Suppose that Alice, Bob and Charlie want to compute some functions without revealing each input to the function one another.
We can construct the protocols using garbled circuits by multiple ...
9
votes
1answer
104 views
BGW Theorem 2- Does this proof work?
I was reading the original BGW paper. Great paper. I'm confused about Theorem 2, though.
The Theorem states, "There are functions for which there are no n/2-private protocols."
The proof is simply ...
1
vote
0answers
49 views
What SMPC protocols make use only of additive secret sharing?
In Appendix G of the Hawk paper, where it talks about financially fair SFE, it mentions that it's possible to run a SMPC protocol where, at the end, each party has a share of their own output y, and a ...
5
votes
1answer
71 views
How to know when decryption fails in Yao's Garbled Circuits
I'm reading A Gentle Introduction to Yao's Garbled Circuits, and I came across this passage:
Note that in order for this to work, Evan needs to know when
decryption succeeds, and when it doesn’t. ...
0
votes
1answer
72 views
Commit and prove as a general trick for malicious security
After reading through Lindell's excellent tutorial (https://eprint.iacr.org/2016/046.pdf), I wonder about the following.
To make a protocol secure against fully-malicious security, it seems that ...
0
votes
1answer
43 views
Multikeyed Hash: known algorithms?
A MAC (or HMAC) can be represented by the general formula:
MAC = H(key, message)
I am calling "Multikeyed Hash" the operation (probably there exists already a ...
0
votes
0answers
36 views
Efficiency of Multi party computation
I want to know about the efficiency of Multi party computation. When compared with FHE its computation cost is less but communication cost is high.
2
votes
1answer
58 views
Computing power function with BGW scheme
Is it possible to use BGW scheme, to compute (private value) power of some other private input?
I believe that it's not possible, because this scheme allow only multiplication and addition. Where ...
