US 2012/0233704 A1 · INFORMATION PROCESSING APPARATUS, KEY GENERATION APPARATUS, SIGNATURE VERIFICATION APPARATUS, INFORMATION PROCESSING METHOD, SIGNATURE GENERATION METHOD, AND PROGRAM · patentgrep

Loading patent…

Abstract

Provided is an information processing apparatus for realizing an electronic signature system of the MPKC signature method capable of safety certification with respect to chosen-message attack. An information processing apparatus including a first inverse transformation unit that transforms an element y of a finite ring Kn containing elements constituted of n numbers into an element y′ of the finite ring Kn 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 Kn obtained here as an element Y of an n-order extension A of a finite ring K and computes an element Xε{Z|f(Z)=Y} of an inverse image of mapping 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 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 here as an element x′ of the finite ring Kn and transforms the element x′ of the finite ring Kn into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S is provided.

Claims18

Dependent claims

An information processing apparatus, comprising:

a first inverse transformation unit that transforms an element y of a finite ring Kn containing elements constituted of n numbers into an element y′ of the finite ring Kn 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 Kn 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 Kn and transforms the element x′ of the finite ring Kn into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S.

3 more elements

An information processing apparatus, comprising:

a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers;
a first inverse transformation unit that transforms an element y of a finite ring Km containing elements constituted of m elements into an element y′ of the finite ring Km 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 Km obtained by the first inverse transformation unit as an element Y of an m-order extension A of a finite ring K and computes an element Xε{ZεB|f(Z,vx)=Y} of an inverse image of mapping f(f:
A×Kv→B, B is an o-order extension of the finite ring K) represented by a predetermined multivariable polynomial by using the element Y and the element vx selected by the partial element selection unit;
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 ox of a finite ring Ko and transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S.

4 more elements

An information processing apparatus, comprising:

a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers;
a number generation unit that generates a number r;
a data generation unit that generates an element y of a finite ring Km containing elements constituted of m numbers by using the number r generated by the number generation unit and electronic data M;
a first inverse transformation unit that transforms the element y of the finite ring Km generated by the data generation unit into an element y′ of the finite ring Km by an inverse transformation T−1 of a first secret polynomial T;
an element computation unit that computes an element oxε{ZεKo|f(Z,vx)=y′} of mapping f(f:
Kn→Ko, n=o+v) represented by a predetermined multivariable polynomial by using the element y′ of the finite ring Km obtained by the first inverse transformation unit and the element vx selected by the partial element selection unit;
an element selection unit that selects the element ox of the inverse image computed by the element computation unit if the element of the inverse image exists and causes the number generation unit to generate the different number r and selects the element ox of the inverse image computed by processing of the data generation unit, the first inverse transformation unit, and the element computation unit by using the different number r if the element of the inverse image does not exist;
a second inverse transformation unit that transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) containing the element ox selected by the element selection unit into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S;
and
a signature generation unit that generates an electronic signature σ containing the element x of the finite ring Kn obtained by the second inverse transformation unit.

7 more elements

An information processing apparatus, comprising:

a data generation unit that generates an element y of a finite ring Km containing elements constituted of m numbers by using electronic data M;
a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers;
a first inverse transformation unit that transforms the element y of the finite ring Km generated by the data generation unit into an element y′ of the finite ring Km by an inverse transformation T−1 of a first secret polynomial T;
an element computation unit that computes an element oxε{ZεKo|f(Z,vx)=y′} of mapping f (f:Kn→Ko, n=o+v) represented by a predetermined multivariable polynomial by using the element y′ of the finite ring Km obtained by the first inverse transformation unit and the element vx selected by the partial element selection unit;
an element selection unit that selects the element ox of the inverse image computed by the element computation unit if the element of the inverse image exists and causes the partial element selection unit to select the different number vx and selects the element ox of the inverse image computed by processing of the first inverse transformation unit and the element computation unit by using the different number vx if the element of the inverse image does not exist;
a second inverse transformation unit that transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) containing the element ox selected by the element selection unit into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S;
and
a signature generation unit that generates an electronic signature σ containing the element x of the finite ring Kn obtained by the second inverse transformation unit, wherein the m satisfies a n≧m+β condition and the β satisfies a q−β<<1 condition for a number of elements q of the finite ring K.

5 more elements

An information processing apparatus, comprising:

a data generation unit that generates an element y of a finite ring Km containing elements constituted of m numbers by using electronic data M;
a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers;
a first inverse transformation unit that transforms the element y of the finite ring Km generated by the data generation unit into an element y′ of the finite ring Km by an inverse transformation T−1 of a first secret polynomial T;
an element computation unit that computes an element oxε{ZεKo|f(Z,vx)=y′} of mapping f(f:
Kn→Ko, n=o+v) represented by a predetermined multivariable polynomial by using the element y′ of the finite ring Km obtained by the first inverse transformation unit and the element vx selected by the partial element selection unit;
an element selection unit that selects the element ox of the inverse image computed by the element computation unit if the element of the inverse image exists and causes the partial element selection unit to select the different number vx and selects the element ox of the inverse image computed by processing of the first inverse transformation unit and the element computation unit by using the different number vx if the element of the inverse image does not exist;
a second inverse transformation unit that transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) containing the element ox selected by the element selection unit into an element x of the finite ring Kn by an inverse transformation S−1of a second secret polynomial S;
and
a signature generation unit that generates an electronic signature σ containing the element x of the finite ring Kn obtained by the second inverse transformation unit, wherein the mapping f is represented for ox=(ox1, . . . , oxo) and vx=(vx1, . . . , vxv) as f(ox1, . . . , oxo, vx1, . . . , vxv)=L(vx1, . . . , vxv)(ox1, . . . , oxo)T+g(vx1, . . . , vxv), the L is represented as L(vx1, . . . , vxv)=L1 L2(vx1, . . . , vxv) L3 where the L1 and L3 are non-singular matrices, and the L2 is an upper or lower triangular matrix having a function 1ij(vx1, . . . , vxv) of vx1, . . . , vxv as an i-th row j-th column element and 1 as a diagonal component.

6 more elements

A key generation apparatus, comprising:

a secret key generation unit that generates a secret key used by a computational algorithm having a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers, a number generation unit that generates a number r;
a data generation unit that generates an element y of a finite ring Km containing elements constituted of m numbers by using the number r generated by the number generation unit and electronic data M, a first inverse transformation unit that transforms the element y of the finite ring Km generated by the data generation unit into an element y′ of the finite ring Km by an inverse transformation T−1 of a first secret polynomial T, an element computation unit that computes an element oxε{ZεKo|f(Z,vx)=y′} of mapping f (f:
Kn→Ko, n=o+v) represented by a predetermined multivariable polynomial by using the element y′ of the finite ring Km obtained by the first inverse transformation unit and the element vx selected by the partial element selection unit, an element selection unit that selects the element ox of the inverse image computed by the element computation unit if the element of the inverse image exists and causes the number generation unit to generate the different number r and selects the element ox of the inverse image computed by processing of the data generation unit, the first inverse transformation unit, and the element computation unit by using the different number r if the element of the inverse image does not exist, a second inverse transformation unit that transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) containing the element ox selected by the element selection unit into an element x of the finite ring Kn by an inverse transformation S−1 of a second secret polynomial S, and a signature generation unit that generates an electronic signature σ containing the element x of the finite ring Kn obtained by the second inverse transformation unit and containing information about the first secret polynomial T, the second secret polynomial S, and the predetermined multivariable polynomial;
and
a public key generation unit that generates a public key containing information about composite mapping F constituted of the first secret polynomial T, the mapping f, and the second secret polynomial S.

2 more elements

A signature verification apparatus, comprising;

an acquisition unit that acquires information about composite mapping F constituted of a first secret polynomial T, mapping f, and a second secret polynomial S, an electronic signature σ, and electronic data M from a signature generation apparatus having a partial element selection unit that selects an element vx of a finite ring Kv containing elements constituted of v numbers, a number generation unit that generates a number r;
a first data generation unit that generates an element y of a finite ring Km containing elements constituted of m numbers by using the number r generated by the number generation unit and the electronic data M, a first inverse transformation unit that transforms the element y of the finite ring Km generated by the first data generation unit into an element y′ of the finite ring Km by an inverse transformation T−1 of the first secret polynomial T, an element computation unit that computes an element oxε{ZεKo|f(Z,vx)=y′} of the mapping f(f:
Kn→Ko, n=o+v) represented by a predetermined multivariable polynomial by using the element y′ of the finite ring Km obtained by the first inverse transformation unit and the element vx selected by the partial element selection unit, an element selection unit that selects the element ox of the inverse image computed by the element computation unit if the element of the inverse image exists and causes the number generation unit to generate the different number r and selects the element ox of the inverse image computed by processing of the first data generation unit, the first inverse transformation unit, and the element computation unit by using the different number r if the element of the inverse image does not exist, a second inverse transformation unit that transforms an element x′=(ox,vx) of the finite ring Kn(n=o+v) containing the element ox selected by the element selection unit into an element x of the finite ring Kn by an inverse transformation S−1 of the second secret polynomial S, and a signature generation unit that generates the electronic signature σ containing the element x of the finite ring Kn obtained by the second inverse transformation unit and the number r generated by the number generation unit;
a second data generation unit that generates an element y1 of the finite ring Km by using the number r contained in the electronic signature σ and the electronic data M;
a third data generation unit that generates an element y2 of the finite ring Km by applying the element x of the finite ring Kn contained in the electronic signature σto the composite mapping F;
and
a verification unit that verifies whether the element y1 of the finite ring Km generated by the second data generation unit and the element y2 of the finite ring Km generated by the third data generation unit match.

4 more elements

Dependencies are inferred from the claim text.