Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Scalar zero #102

Open
LachlanGunn opened this issue Jan 29, 2021 · 14 comments
Open

Scalar zero #102

LachlanGunn opened this issue Jan 29, 2021 · 14 comments

Comments

@LachlanGunn
Copy link

LachlanGunn commented Jan 29, 2021

While implementing proactive secret sharing protocols, we have come across an issue in that the secp256k1 curve library is very reluctant to let us have a scalar zero or the identity point. This makes proactive secret sharing protocols a bit tricky to implement.

Is this a fundamental limitation, or is it just needed for safe ECDSA implementation?

@omershlo
Copy link
Contributor

Hi @LachlanGunn ! :)

yes this is by design. Can you give a concrete example where this becomes a limitation ?

@LachlanGunn
Copy link
Author

Thanks @omershlo. As an example, we sometimes need to compute (ci G), i=0…n over some polynomial, where c0 is a secret to be shared. If this secret may be zero, then to use a raw ECPoint type we need to special-case everything so that there are "polynomials with c0 = 0" and "other polynomials".

@omershlo
Copy link
Contributor

@LachlanGunn
Copy link
Author

Yes, so for scalar operations I do the modular arithmetic directly on the equivalent bignum, then convert it back by checking for zero and using the zero method when I can't convert it to a scalar in the normal way. But there isn't an equivalent for the curve points to get the identity, meaning that I can't actually compute xG in that instance, or even (a-a)G.

@omershlo
Copy link
Contributor

Yes but where do you need to do computation with the identity ?

@LachlanGunn
Copy link
Author

In my case it is because I need to compute xG where x might be equal to zero.

@omershlo
Copy link
Contributor

I claim you can do the computation without using a point xG where x is zero .
Can you perhaps elaborate where do you get stuck ?

@LachlanGunn
Copy link
Author

Might you please elaborate on how you might go about doing it? At least for now, such a workaround might be enough.

But as an example of the issue, see the built-in Feldman VSS implementation, which computes:

let G: P = ECPoint::generator();
let commitments = (0..poly.len())
        .map(|i| G.clone() * poly[i].clone())
        .collect::<Vec<P>>();

So, if I try to share zero:

use curv::cryptographic_primitives::secret_sharing::feldman_vss::*;
use curv::elliptic::curves::traits::ECScalar;

pub type Scalar = curv::elliptic::curves::secp256_k1::Secp256k1Scalar;
pub type Point = curv::elliptic::curves::secp256_k1::Secp256k1Point;
fn main() {
    let secret_one = ECScalar::from(&curv::BigInt::from(1u32));
    let secret_zero = ECScalar::zero();
    eprintln!("Sharing one");
    VerifiableSS::<Point>::share(2, 5, &secret_one);
    eprintln!("Sharing zero");
    VerifiableSS::<Point>::share(2, 5, &secret_zero);
}

It panics:

Sharing one
Sharing zero
thread 'main' panicked at 'Assignment expected: InvalidTweak', /home/lachlan/.cargo/git/checkouts/curv-a122740a63e0e0af/e53db73/src/elliptic/curves/secp256_k1.rs:409:14

@omershlo
Copy link
Contributor

Thank you for clarifying @LachlanGunn !
I actually see two issues here:

  1. improper handling of error
  2. inability to secret share zero
    We can fix the second issue easily by treating separately the case of s = 0 , and using a shorter commitment vector for this case.

will this solve your specific problem ? ( I still claim that computing with identity should be avoided)
Let me know if you want to give it a try and make a PR, otherwise I will take it :)

@LachlanGunn
Copy link
Author

This was just an example—I am implementing a different protocol so am not actually using this code at the moment. But I wonder, is this the right place to fix it? It seems that this is creating a special representation for the identity element that would be used whenever this one piece of code recognises that an operation (in this case, scalar multiplication) may yield the identity element. It will have to be reimplemented, potentially dangerously, for every protocol that needs to be able to work with arbitrary scalars/points.

I am probably biased here because I would need to do this reimplementation myself in several places, but since it would need to be in so many places, could it be better for it to be exposed somehow by the API, even if behind a scary sounding RawPoint or RiskyPoint? I don't really understand why the current restrictions are in place, so it's difficult for me to tell whether this is a reasonable solution.

@omershlo
Copy link
Contributor

sent you an email

@durgesh-pandey
Copy link

Hello,
Recently, I also encountered same error of "'Assignment expected: InvalidTweak'" from secp256_k1.rs while doing a VSS of scalar zero (FE::zero()).
I wanted to do this to experiment the "refresh" method (not the re-sharing method as done in tss-lib) via zero secret sharing as mentioned in section 3.2 of this paper 1.
I guess, to experiment above method, we can also try doing VSS of "a chosen random scalar instead of zero" twice with random sampled data, and the result of first VSS will be added and of the second will be subtracted, but that may require more interaction and may not be very efficient.
That's why VSS of FE::zero() is required. Any approach to resolve this issue?

@omershlo
Copy link
Contributor

Hi,

we tried to solve for this specific issue of VSS by extending the VSS API: see this commit:
e95192f#diff-28708fca15925e1a9d0f4eb491dcb8742d943cac84c8d5ae7d1f0b374d9a90fc
please let me know if that helps you (it should)

@durgesh-pandey
Copy link

Hi,
This is exactly what I had in mind. Tested it and it works as expected.
Thanks a lot.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants