Performance Evaluation of Interpolation Techniques in Shamir Secret Sharing Scheme

This work evaluates the performance of several polynomial interpolation techniques applied to the Shamir Secret Sharing (SSS) scheme, considering seven methods: Lagrange, Newton, Neville, Aitken, Lagrange Barycentric, Vandermonde, and the Fast Fourier Transform (FFT), also referred to in finite fields as the Number Theoretic Transform (NTT). All methods were adapted to finite fields and implemented in Python. The analysis identifies the NTT as the most efficient technique for large-scale secret reconstruction, especially when combined with pre-computations, achieving runtime reductions of up to 92%. The results not only confirm the theoretical superiority of NTT but also quantify gains, enable method-to-method comparisons, and offer practical guidelines for selecting appropriate techniques according to share number threshold, memory size and performance requirements. The methods with better asymptotic complexity achieved superior performance in all experiments, without crossover point. Regarding memory usage, the methods exhibited non-monotonic behavior due to various architectural factors, such as cache effects.