# US 2014/0208110 A1 · Information processing apparatus, signature generation apparatus, signature verification apparatus, information processing method, signature generation method, and signature verification method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0208110 A1
- Document ID: US20140208110A1
- Status: Published application
- Kind: A1
- Application number: 14/237,460
- Filed: 2012-07-20
- Published: 2014-07-24
- Earliest claimed: 2011-08-29
- Assignees: Sony Corporation
- Inventors: Harunaga Hiwatari; Koichi Sakumoto; Taizo Shirai
- Web page: https://patentgrep.com/patent/US20140208110A1

## CPC

- H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 9/3247: {involving digital signatures}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided is an information processing apparatus including a message generation unit configured to generate a message based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a vector s that is an element of a set Kn, a message supply unit configured to supply the message to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), and a response supply unit configured to supply the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧3) verification patterns.

## Claims

### Claim 1

An information processing apparatus comprising:
a message generation unit configured to generate a message based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, when the message is generated, the message generation unit executes calculation of a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix).

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1,
wherein the message generation unit generates the messages of N times (where N≧2),
wherein the message supply unit supplies the verifier with the messages of the N times with interactivity of one time, and
wherein the response supply unit supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time.

### Claim 3

An information processing apparatus comprising:
an information storage unit configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a message acquisition unit configured to acquire a message generated based on the pair of quadratic multivariate polynomials F and a vector s that is an element of a set Kn;
a pattern information supply unit configured to supply a prover supplying the message with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a response acquisition unit configured to acquire response information corresponding to the selected verification pattern from the prover; and
a verification unit configured to verify whether or not the prover stores the vector s based on the message, the pair of quadratic multivariate polynomials F, the vectors y, and the response information,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, when the message used for the verification is reproduced, the verification unit executes calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) as F(x, y)+F(y) which is calculation between quadratic forms.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3,
wherein the message acquisition unit acquires the messages of N times (where N≧2) with interactivity of one time,
wherein the pattern information supply unit selects the verification pattern for each of the messages of the N times and supplies the prover with the information on the selected verification patterns of the N times with interactivity of one time,
wherein the response acquisition unit acquires the response information of the N times corresponding to the selected verification patterns of the N times from the prover with interactivity of one time, and
wherein the verification unit determines that the prover stores the vector s when the verification succeeds for all of the messages of the N times.

### Claim 5

An information processing apparatus comprising:
a message generation unit configured to generate a message based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(y1, . . . , ym)=(fi(s), . . . , fm(s));
an intermediate information generation unit configured to generate third information using first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply unit configured to supply the third information to the verifier; and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information, and
wherein, when the message is generated, the message generation unit executes calculation of a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix).

### Claim 6 (depends on 5)

The information processing apparatus according to claim 5,
wherein the message generation unit generates the messages of N times (where N≧2),
wherein the message supply unit supplies the verifier with the messages of the N times with interactivity of one time,
wherein the intermediate information generation unit generates the third information of the N times based on the first information selected by the verifier for each of the messages of the N times and the second information of the N times obtained at the time of the generation of the messages,
wherein the intermediate information supply unit supplies the verifier with the third information of the N times with interactivity of one time, and
wherein the response supply unit supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time.

### Claim 7

An information processing apparatus comprising:
an information storage unit configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a message acquisition unit configured to acquire a message generated based on the pair of quadratic multivariate polynomials F and a vector s that is an element of a set Kn;
an information supply unit configured to supply the prover supplying the message with the randomly selected first information;
an intermediate information acquisition unit configured to acquire third information which the prover generates based on the first information and second information obtained at a time of the generation of the message;
a pattern information supply unit configured to supply the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a response acquisition unit configured to acquire response information corresponding to the selected verification pattern from the prover; and
a verification unit configured to verify whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of quadratic multivariate polynomials F, and the response information,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message is information obtained by executing calculation prepared in advance for a verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, when the message used for the verification is reproduced, the verification unit executes calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) as F(x, y)+F(y) which is calculation between quadratic forms.

### Claim 8 (depends on 7)

The information processing apparatus according to claim 7,
wherein the message acquisition unit acquires the messages of N times (where N≧2) with interactivity of one time,
wherein the information supply unit randomly selects the first information for each of the messages of the N times and provides the prover with the selected first information of the N times with interactivity of one time,
wherein the intermediate information acquisition unit acquires the third information of the N times generated by the prover based on the first information of the N times and the second information of the N times obtained at the time of the generation of the messages of the N times,
wherein the pattern information supply unit selects the verification pattern for each of the messages of the N times and supplies the prover with the information on the selected verification patterns of the N times with interactivity of one time,
wherein the response acquisition unit acquires the response information of the N times corresponding to the selected verification patterns of the N times from the prover with interactivity of one time, and
wherein the verification unit determines that the prover stores the vector s when the verification succeeds for all of the messages of the N times.

### Claim 9

A signature generation apparatus comprising:
a signature generation unit configured to generate a digital signature for a document M based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a signature key s that is an element of a set Kn; and
a signature supply unit configured to supply the digital signature to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(f1(s), . . . , fm(s)),
wherein the signature generation unit executes calculation of a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) executed during the generation of the digital signature based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix).

### Claim 10

A signature verification apparatus comprising:
an information storage unit configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(f1(s), . . . , fm(s)); and
a signature verification unit configured to verify legitimacy of a document M based on a digital signature generated using the quadratic multivariate polynomials F and a signature key s that is an element of a set Kn with respect to the document M,
wherein the signature verification unit executes calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) as F(x, y)+F(y) executed during the verification of the digital signature, as calculation between quadratic forms.

### Claim 11

An information processing method comprising:
a step of generating a message based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a step of supplying the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, in the step of generating the message, calculation of a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) is executed based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix) when the message is generated.

### Claim 12

An information processing method executed by an information processing apparatus configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), the information processing method comprising:
a step of acquiring a message generated based on the pair of quadratic multivariate polynomials F and a vector s that is an element of a set Kn;
a step of supplying a prover supplying the message with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a step of acquiring response information corresponding to the selected verification pattern from the prover; and
a step of verifying whether or not the prover stores the vector s based on the message, the pair of quadratic multivariate polynomials F, the vectors y, and the response information,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, in the step of verifying whether or not the prover stores the vector s, calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) is executed as F(x, y)+F(y) which is calculation between quadratic forms when the message used for the verification is reproduced.

### Claim 13

An information processing method comprising:
a step of generating a message based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(y1, . . . , ym) (f1(s), . . . , fm(s));
a step of generating third information using first information randomly selected by the verifier and second information obtained at a time of generation of the message;
a step of supplying the third information to the verifier; and
a step of supplying the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information, and
wherein, in the step of generating the message, calculation of a function G=g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) is executed based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix) when the message is generated.

### Claim 14

An information processing method executed by an information processing apparatus configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), the information processing method comprising:
a step of acquiring a message generated based on the pair of quadratic multivariate polynomials F and a vector s that is an element of a set Kn;
a step of supplying the prover supplying the message with the randomly selected first information;
a step of acquiring third information which the prover generates based on the first information and second information obtained at a time of the generation of the message;
a step of supplying the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a step of acquiring response information corresponding to the selected verification pattern from the prover; and
a step of verifying whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of quadratic multivariate polynomials F, and the response information,
wherein the vector s is a secret key,
wherein the pair of quadratic multivariate polynomials F and the vectors y are public keys,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message is information obtained by executing calculation prepared in advance for a verification pattern corresponding to the response information based on the public keys and the response information, and
wherein, in the step of verifying whether or not the prover stores the vector s, calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) is executed as F(x, y)+F(y) which is calculation between quadratic forms when the message used for the verification is reproduced.

### Claim 15

A signature generation method comprising:
a step of generating a digital signature for a document M based on a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and a signature key s that is an element of a set Kn; and
a step of supplying the digital signature to a verifier storing the pair of quadratic multivariate polynomials F and vectors y=(f1(s), . . . , fm(s)),
wherein, in the step of generating the digital signature, calculation of a function G=gm), which is defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2), executed during the generation of the digital signature is executed based on a formula g1(x1, x2)=x1TA1x2+x2TA1x1 (where 1=1 to m and A1 is an n×n coefficient matrix).

### Claim 16

A signature verification method executed by an information processing apparatus configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(f1(s), . . . , fm(s)), the signature verification method comprising:
a step of verifying legitimacy of a document M based on a digital signature generated using the quadratic multivariate polynomials F and a signature key s that is an element of a set Kn with respect to the document M,
wherein, in the step of verifying the legitimacy, calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) executed during the verification of the digital signature is executed as F(x, y)+F(y) which is calculation between quadratic forms.
