Patent ID: 8532289
Filing Date: 2013-09-10
Classification: H04L,Y04S

Abstract:
1. A method for computing, as part of a homomorphic encryption scheme, a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f n (x), comprising: receiving at a computing system the first polynomial v(x) modulo the second polynomial f computing by the computing system lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field, where computing the lowest two coefficients of the third polynomial g(z) comprises computing a fourth polynomial h(z), where h(z)=g(z)mod z 2 , and where computing the fourth polynomial comprises computing pairs of polynomials U j (x) and V j (x) for j=0, 1, . . . , log n, such that for all j it holds that g(z) is congruent modulo z 2 to a fifth polynomial G j (z), where outputting by the computing system the lowest coefficient of g(z) as the resultant; outputting by the computing system the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f using by the computing system the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme.