# US 2014/0153717 A1 · Information processing apparatus, information processing method, program, and recording medium

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

- Number: US 2014/0153717 A1
- Document ID: US20140153717A1
- Status: Published application
- Kind: A1
- Application number: 14/235,240
- Filed: 2012-06-25
- Published: 2014-06-05
- Earliest claimed: 2011-08-12
- Assignees: Sony Corporation
- Inventors: Koichi Sakumoto
- Web page: https://patentgrep.com/patent/US20140153717A1

## CPC

- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 9/3247: {involving digital signatures}
- H04L 9/3271: {using challenge-response}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided an information processing apparatus including a message generation unit that generates a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn, a message supply unit that supplies the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), an intermediate information generation unit that generates third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message, an intermediate information supply unit that supplies the third information to the verifier, and a response supply unit that supplies the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns.

## Claims

### Claim 1

An information processing apparatus comprising:
a message generation unit that generates a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn;
a message supply unit that supplies the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation unit that generates third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply unit that supplies the third information to the verifier; and
a response supply unit that supplies 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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q (z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### 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;
wherein the intermediate information generation unit generates the third information of the N times based on the first information selected by the verifier for 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 pattern selected by the verifier for the messages of the N times, with interactivity of one time.

### Claim 3 (depends on 2)

The information processing apparatus according to claim 2,
wherein the message generation unit generates the messages of the N times (where N≧2) and generates one hash value from the messages of the N times,
wherein the message supply unit supplies the hash value to the verifier,
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 pattern selected by the verifier for each of the messages of the N times and some of messages not obtained even in execution of the calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information, with interactivity of one time.

### Claim 4

An information processing apparatus comprising:
an information storage unit that stores a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a message acquisition unit that acquires a message generated based on the pair of multi-order multivariate polynomials F and a vector s which is an element of a set Kn;
an information supply unit that supplies randomly selected first information to a prover that supplies the message;
an intermediate information acquisition unit that acquires third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
a pattern information supply unit that supplies the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a response acquisition unit that acquires response information corresponding to the selected verification pattern from the prover; and
a verification unit that verifies whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 5 (depends on 4)

The information processing apparatus according to claim 4,
wherein the message acquisition unit acquires the messages of N (where N≧2) times 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 supplies 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 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 verification succeeds for all of the messages of the N times.

### Claim 6 (depends on 5)

The information processing apparatus according to claim 5,
wherein the message acquisition unit acquires one hash value generated from the messages of the N times (where N≧2),
wherein the information supply unit randomly selects the first information for each of the messages of the N times and supplies with 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, from the prover, the response information corresponding to the selected verification pattern and some of the messages not obtained even in execution of the 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 the verification unit verifies whether or not the prover stores the vector s based on the hash value, some of the messages, the public keys, and the response information and determines that the prover stores the vector s, when the verification succeeds for all of the messages of the N times.

### Claim 7

An information processing method comprising:
generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn;
supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
supplying the third information to the verifier; and
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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 8

An information processing method comprising: by an information processing apparatus storing a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)),
acquiring a message generated based on the pair of multi-order multivariate polynomials F and a vector s which is an element of a set Kn;
supplying randomly selected first information to a prover that supplies the message;
acquiring third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
supplying the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns; and
acquiring response information corresponding to the selected verification pattern from the prover;
verifying whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 9

A program causing a computer to realize:
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation function of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply function of supplying the third information to the verifier; and
a response supply function 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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 10

A program causing a computer to realize:
an information storage function of storing a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a message acquisition function of acquiring a message generated based on the pair of multi-order multivariate polynomials F and a vector s which is an element of a set Kn;
an information supply function of supplying randomly selected first information to a prover that supplies the message;
an intermediate information acquisition function of acquiring third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
a pattern information supply function of supplying the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns; and
a response acquisition unit of acquiring response information corresponding to the selected verification pattern from the prover;
a verification function that verifies whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , f1n defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 11

A computer-readable recording medium having a program recorded thereon, the program causing a computer to realize:
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation function of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply function of supplying the third information to the verifier; and
a response supply function 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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

### Claim 12

A computer-readable recording medium having a program recorded thereon, the program causing a computer to realize:
an information storage function of storing a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a message acquisition function of acquiring a message generated based on the pair of multi-order multivariate polynomials F and a vector s that is an element of a set Kn;
an information supply function of supplying randomly selected first information to a prover that supplies the message;
an intermediate information acquisition function of acquiring third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
a pattern information supply function of supplying the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
a response acquisition unit of acquiring response information corresponding to the selected verification pattern from the prover; and
a verification function of verifying whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
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 the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).
