Fast systematic encoding of multiplicity codes
This work addresses a bottleneck in implementing private information retrieval protocols for secure data access, though it is incremental as it builds on existing interpolation methods.
The authors tackled the problem of slow systematic encoding for multiplicity codes by developing quasi-linear time algorithms, which remove a practical obstruction for applying a private information retrieval protocol.
We present quasi-linear time systematic encoding algorithms for multiplicity codes. The algorithms have their origins in the fast multivariate interpolation and evaluation algorithms of van der Hoeven and Schost (2013), which we generalise to address certain Hermite-type interpolation and evaluation problems. By providing fast encoding algorithms for multiplicity codes, we remove an obstruction on the road to the practical application of the private information retrieval protocol of Augot, Levy-dit-Vehel and Shikfa (2014).