Patent ID: 8675867

Claim:
An information processing apparatus, comprising: a processor, which comprises, a first inverse transformation unit that transforms an element y of a finite ring K n containing elements constituted of n numbers into an element y′ of the finite ring K n by an inverse transformation T −1 of a first secret polynomial T; an element computation unit that considers the element y′ of the finite ring K n obtained by the first inverse transformation unit as an element Y of an n-order extension A of a finite ring K and computes an element Xε{ZεA|f(Z)=Y} of an inverse image of mapping f(f: A→A) represented by a predetermined multivariable polynomial by using the element Y; an element selection unit that selects one element X of the inverse image computed by the element computation unit with a probability p proportional to a number of elements α of the inverse image and outputs an exception value with a probability (1-p); and a second inverse transformation unit that considers the element X selected by the element selection unit as an element x′ of the finite ring K n and transforms the element x′ of the finite ring K n into an element x of the finite ring K n by an inverse transformation S −1 of a second secret polynomial S.