new demo - validate points on a single polynomial

[saart]

New demo suggestion: N players. Each player i have a private point (i, y_i) on a polynomial of degree k. They want to know if their points are on the same polynomial without revealing their private point.

[codecov-io]

Codecov Report

Merging #21 (6c09208) into master (6b23ffc) will not change coverage. The diff coverage is n/a.

@@           Coverage Diff           @@
##           master      #21   +/-   ##
=======================================
  Coverage   89.70%   89.70%           
=======================================
  Files          13       13           
  Lines        4302     4302           
=======================================
  Hits         3859     3859           
  Misses        443      443           

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 6b23ffc...6c09208. Read the comment docs.

[lschoe]

Hi, I've tried your program and it works fine indeed. Also, it's clear what the program does, but I'm trying to understand why this would be interesting as a demo?

The program is checking if the MPyC parties each hold a point on a common (secret) polynomial. I can imagine applications in threshold cryptography, like in verifiable secret sharing, where one needs to check if all shares lie on a unique polynomial for consistency. But you are using fixed-point arithmetic for the calculations, to mimic polynomials over the reals apparently, which doesn't fit with applications in cryptography.

Do you have a particular scenario in mind?

[saart]

I had exactly the "key-sharing" scenario in mind. The scenario was to validate that all the parties share shares of the same secret.

Re the field, obviously, you are right. Cryptographic applications assume polynomials over a finite field, while I assume the reals, right? I'll update the demo. Thanks for the review and sorry for the trouble!

[lschoe]

I was thinking a bit more about your problem, also to get good performance for the consistency check.

So, here's a quick and simple way to do the consistency check using the secure finite fields built in MPyC:

    p = 2**31 - 1             # Mersenne prime, cheating probability 1/p approx. 2^-31
    secfld = mpc.SecFld(p)    # secure finite field of order p
    field = secfld.field
    m = len(mpc.parties)
    i = mpc.pid
    k = 3                    # k <= m required
    f_i = 3*i**2 + 2*i + 11  # coefficients of your secret polynomial f(x) of degree k-1
    b = await mpc.output(mpc._randoms(field, m - k))  # jointly random coefficients of polynomial g(x) of degree < m-k
    g_i = sum(b[j] * i**j for j in range(m - k))      # party P_i computes g(i) locally
    v_i = field(math.prod(i - j for j in range(m) if j != i))
    d = mpc.sum(mpc.input(secfld(f_i * g_i / v_i)))  # dot product of Reed-Solomon codewords
    if await mpc.is_zero_public(d):
        print(f'Consistent with one polynomial of degree <= {k-1}')
    else:
        print('Inconsistent')

Each party P_i, 0 <= i < m, holds a point (i, f_i) on a given polynomial f(x) that nobody needs to know. We view this as a codeword in an [m, k] Reed-Solomon (RS) code. If it's indeed an RS codeword, it must be orthogonal to any codeword in the dual code. So we generate a random codeword in the dual RS code, which is of dimension m-k. And then test if the dot product of the two codewords is equal to 0. Cheating probability is then exactly equal to 1/p.

As PRSS is used, generating the m-k random coefficients for the dual codeword is a local operation. The running time is then dominated by opening these m-k values (one call to mpc.output()), and distributing the single value f_i * g_i / v_i computed locally by each party (one call to mpc.input()). All other work is local.

This makes the consistency check pretty efficient, even avoiding the use of any secure multiplications.

[saart]

Hi, Thanks for the reply, and sorry for my late response.

I think that there are a few "problems" in your method:

• choosing a random polynomial g(x) is not always secure. An easy example is g(x) = 0.

Claim 1: If there exists i such that g(i)=0 then party i can lie. Proof: the value of f(i) is ignored during the whole computation. Example: in your code, change b[0]=0 and let party 0 lie.

Claim 2: if the degree of g is m-k-l for l>0, then we will falsely trust l parties. Proof: we're actually considering f*g. Liers increases the degree of f, but as long as f*g will be of degree lower than m-1, the condition will hold. Example: increase the degree of f by 1 (i.e. one of the parties lies), and reduce the degree of g (simulate that the highest coefficient in g is zero).

• taking m to be too high might break the validity. Example: Run the code with m=15. It always returns Inconsistent. I'm guessing that it's because v_i gets too high, right?

Although the above, I still think that this is a great idea, and I'll be happy to think more about it. Do you know of any good way to make sure that g will have no roots in the specific inputs?

[lschoe]

Hi Saar, happy to hear from you again. You're raising some interesting issues!

Maybe first about your second point, about using a larger value for m. For me the program runs fine with 15 parties, reporting "consistent" all the time. And if we mess up the polynomial by inserting, for instance, if mpc.pid == 0: f_i = 0 , then the program detects the inconsistency.

Do you run it with the latest version of MPyC? I haven't tested it with older versions.

For your other point, that touches on how the MPC parties might try to cheat. For MPyC, the adversary is assumed to be semi-honest and we need an honest majority (number of corrupt parties t < m/2). I was considering your problem in this setting, in a scenario where say an external client gives each party a point on the polynomial. This would be a way to provide secret inputs to an MPC protocol from 'outside', hence not provided by any of the MPC parties themselves. Like when you would run an auction protocol or so. In this scenario the client can be considered as an actively corrupt party, trying to send inconsistent input maybe to mesh up the entire protocol. And that would be stopped by the consistency check that you're considering.

You are describing some attacks where the MPyC parties themselves deviate from the protocol. So, that's outside the security model of MPyC. When the parties follow the protocol, polynomial g(x) will be of degree m-k with overwhelming probability (equal to 1 - 2^-31), and nobody will know it. With similarly high probability, each g(i) will be nonzero, for i in [0,m). And that's actually the basis for the security of the program.

If parties deviate from the protocol, by changing their MPyC program, then basically anything can happen. A party could set its (local value) g_i = 0 or so, and force the outcome 'Inconsistent'. And if a party wants consistency it can use the correct f_i in this program but later use a totally different value for f_i.

To stop such attacks, one can resort to actively secure MPC protocols. Protocols withstanding active attacks also use Shamir secret sharing 'under the hood' and make sure that the shares remain consistent, even if parties try to cheat. So, in a way these protocols already do consistency checks all the time.

Another way is to make the MPC protocol publicly verifiable. In this case, the parties would commit to their f_i's and then jointly compute a ZK proof showing that the committed values are consistent. Later computations should refer to these commitments again. We are actually working on such extensions for MPyC in the PRIViLEDGE project.

To do the consistency check with some actively corrupt parties around is a delicate problem. So, assuming an MPC framework with only passive security, and then try to get a consistency check secure against active attacks. Your original approach is also susceptible to some similar problems it seems. Like a party can easily mess up the result to give 'Inconsistency' all the time.

But your MPyC program let's party i use f_i as an input, meaning that all parties gets shares of this value. And that works out like a kind of commitment actually, which may help to stop certain attacks. The program I gave can also be adapted to include this commitment (and then compute e.g. f_i * g_i using a secure multiplication). Maybe this leads to something that works for your case?

[saart]

Thank you, again, for your reply :-)

First, regarding the MPyC versioning - you were right, I wasn't on the latest version. Sorry about that!

Regarding the threat model: In my scenario, there are two different untrusted entities: "the external client" that gives the shares, and at most k parties (out of m) that participate in the MPC. The purpose of this demo was to convince a new party, that got a share from the external client, that his share is ok. Denote this new party with P. For this to happen, P will contact k+1 parties and will privately validate that their shares are on the same polynomial. This means that the adversary tries to convince P that he got a real share, while he can control at most m-2 of the inputs (The adversary does not know the share of P.).

This means that I'm ok with maliciously changing the outcome to "inconsistent". I want to prevent changing it to "consistent". You are right that g will be ok with prob.: (1-2^-31)^(m+1) (m for each of the parties, and +1 for the highest degree). But, it is true as long as the polynomial is uniformly selected. You said that MPyC assumes that there are at most m/2 bad guys, and I'm wondering where is it come from? as far as I know, it is possible to implement PRNG with an m-1 adversaries ("all but one"), right? In either case, the PRIViLEDGE project sounds like a good fit- if P can validate that the other parties randomize g as desired, this is good enough.

I think that we both have an interest in the field of practical applications to cryptography and DLTs. If you are interested, I'll be happy to elaborate on a private channel (mail?) on the idea behind this scenario. It is very cool :-)

[lschoe]

Hi Saar, good morning.

Yeah, right, interesting. Producing a new share for this party P can be viewed as a secure function evaluation problem, where the MPC parties hold the other shares as secret input, and the new share is private output for P.

For MPC relying on honest majority like MPyC we have the t < m/2 bound to allow for secure multiplication, where the parties handle a degree 2t polynomial, using that 2t+1 <= m. That does not exclude that some things can be done tolerating m-1 corrupted parties, however. Like if you only use addition/subtraction and input/output, such a computation will remain private if one uses t=m-1 as threshold.

I'm certainly interested to hear from you about this setting. My email address is listed with my GitHub account.