Fast systematic encoding of multiplicity codes. (September 2019)

• Record Type: Journal Article
• Authors: Coxon, Nicholas
• Is Part Of: Journal of symbolic computation. Volume 94(2019)
• Page Start: 234
• Page End: 254
• Publication Date: 2019-09
• Subjects: Reed–Muller codes -- Multiplicity codes -- Systematic encoding -- Hermite interpolation -- Hermite evaluation; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2018.08.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present quasi-linear time systematic encoding algorithms for multiplicity codes. The algorithms have their origins in the fast multivariate interpolation and evaluation algorithms ofvan 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 ofAugot et al. (2014) .