I'm trying to implement a cryptographic scheme that leverages constant-sized polynomial commitments by Kate et al [1].

I'm looking for a library that can interpolate a polynomial fast via FFT in a finite field, but from values at arbitrary points (i.e., not roots of unity). A technique for doing this in O(n log^2(n)) time for n points is described in "Fast evaluation and interpolation," by H. T. Kung.

I'm aware of:

...but AFAICT none of them seem to support interpolation from values at arbitrary points.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.