RE: BigNum API Proposal

Let me add a use case I needed last year: Shamir's secret sharing algorithm implementation in JS. I ended up implementing it over SJCL's BN (BigNumber). 

Furthermore, the performance of my general-purpose secret-sharing implementation over BN was expectedly bad (several seconds for 192 bits), so I ended up crafting special-case optimized algorithms for acceptable performance. Having a performance BigInt in JS would help a lot.

- Tolga

> -----Original Message-----
> From: Anthony Nadalin [mailto:tonynad@microsoft.com]
> Sent: Tuesday, March 05, 2013 11:26 AM
> To: Harry Halpin; Ryan Sleevi
> Cc: Richard Barnes; public-webcrypto@w3.org
> Subject: RE: BigNum API Proposal
> 
> First this is not a general purpose bignum proposal. It is specialized for crypto,
> fields, rings, elliptic curves. These are the primitives upon which more
> advanced crypto can be built, which would free folks from the standard
> primitives when they needed to step outside those primitives, for example
> blind signatures (U-Prove and IDEMIX). Since it is crypto-specialized is make
> sense to consider it as part of WebCrypto.
> 
> Second of all, even general purpose bignum has low probability of getting
> into js.There are simply some performance optimizations that are best done
> in the context of specialized crypto math api. For example field multiplication
> x*y mod p, can be done using a generic bignum api, but is best done using
> montgomery multiplication with reduction built in. A non-crypto bignum
> library might do this naively as separate operations (which would be terrible),
> or (much better) as a specialized ModMul() routine. In the latter case certain
> constants that are used in the computation which depend on the modulus
> must be computed every time the routine is called. The integer group
> abstraction encapsulates this, allowing the constants to be computed once
> and reused as long as the field is in use. Additionally, crypto operands are
> typically all the same size (e.g. 16 bytes) because they are all random field
> elements. Therefore the extra checks on array sizes that are required for a
> general purpose bignum library are not useful and will slow things down.
> Consider also that certain bit lengths may allow for highly optimized native
> implementations. For example 256bit multiplies can be made very fast, using
> registers, on x64 platform. General purpose bignum simply cannot be made
> to take advantage of these facts.
> 
> 1. So the motivation is the blind signature work along with other country
> specific crypto algorithms. So our motivation for putting this in Web crypto is
> stared above 2. See above
> 
> -----Original Message-----
> From: Harry Halpin [mailto:hhalpin@w3.org]
> Sent: Tuesday, March 5, 2013 2:49 AM
> To: Ryan Sleevi
> Cc: Richard Barnes; Anthony Nadalin; public-webcrypto@w3.org
> Subject: Re: BigNum API Proposal
> 
> On 03/04/2013 07:32 PM, Ryan Sleevi wrote:
> > On Mon, Mar 4, 2013 at 10:23 AM, Richard Barnes <rbarnes@bbn.com>
> wrote:
> >> Could you clarify why this needs to be done as a web API instead of in JS?
> >>
> >> To answer the obvious question: The WebCrypto API needs to provide
> crypto primitives so that the keying material can remain hidden from the JS in
> most circumstances.  Not clear to me that that applies to general BigNum
> stuff.
> > Huge +1. I think this has absolutely no place as a DOM API - which is
> > what we're talking about.
> Tony,
> 
> Thanks for the very concrete suggestions!
> 
> 1) I think one thing that would help would be a use-case for the ZKP work I
> assume is motivating this API.
> 
> 2) What kinds of primitives can not be built on top of the low-level API and
> BigInt [1]?
> 
> I think if the use-case is convincing and certain BigInt operations require
> client-side performance, I would not rule things out of scope just because it
> should be "in the language" rather than "in the DOM."
> For example, one could argue that real random number generation should
> be in the language, not the DOM equally, but we need it for the Crypto use-
> cases, so thus its part of this API. However, the key should be to minimize
> the number of features to be implemented.
> 
> [1] http://www.w3.org/TR/WebCryptoAPI/#big-integer
> 
> 
> >
> >
> >>
> >> On Mar 4, 2013, at 12:41 PM, Anthony Nadalin <tonynad@microsoft.com>
> wrote:
> >>
> >>> With all the discussion about blind signatures and support for BigNum,
> here is a draft API that Microsoft is submitting to the WG as a basis for the
> API. The BigNum API is common function in other JS libraries and a needed
> basic function for nonstandard algorithms. We would like to further discuss
> this at the up and coming F2F thus a heads up and a chance to read prior and
> looking forward to comments and discussions.
> >>> <CryptoAPI.j_>
> >>
> 
> 
> 
>

Received on Tuesday, 5 March 2013 20:10:00 UTC