# US 2017/0250819 A1 · Digital signature method and apparatus

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

- Number: US 2017/0250819 A1
- Document ID: US20170250819A1
- Status: Published application
- Kind: A1
- Application number: 15/530,762
- Filed: 2017-02-24
- Published: 2017-08-31
- Earliest claimed: 2016-02-25
- Assignees: Security Innovation Inc.
- Applicants: Security Innovation Inc.
- Inventors: Jeffrey Hoffstein; Jill Pipher; Joseph H. Silverman; William J. Whyte; Zhenfei Zhang
- Web page: https://patentgrep.com/patent/US20170250819A1

## CPC

- H04L 9/3247: {involving digital signatures}
- H04L 9/3026: {details relating to polynomials generation, e.g. generation of irreducible polynomials}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for signing and subsequently verifying a digital message, including the following steps: generating an irreducible monic polynomial f(x) of degree n in a ring Fq[x]; generating an irreducible monic polynomial F(y) of degree n in a ring Fq[y]; producing first and second finite fields as Fq[x]/(f(x)) and Fq[y]/(F(y)), respectively; producing a secret isomorphism from the first finite field to the second finite field; producing and publishing a public key that depends on F(y); producing a private key that depends on the secret isomorphism; producing a message digest by applying a hash function to the digital message and the public key; producing a digital signature using the message digest and the private key; and performing a verification procedure utilizing the digital signature and the public key.

## Claims

### Claim 1

A method for signing and subsequently verifying a digital message, comprising the following steps implemented using at least one processor-based subsystem:
generating an irreducible monic polynomial f(x) of degree n in a ring Fq[x];
generating an irreducible monic polynomial F(y) of degree n in a ring Fq[y];
producing first and second finite fields as Fq[x]/(f(x)) and Fq[y]/(F(y)), respectively;
producing a secret isomorphism from the first finite field to the second finite field;
producing and publishing a public key that depends on F(y);
producing a private key that depends on said secret isomorphism;
producing a message digest by applying a hash function to the digital message and the public key;
producing a digital signature using the message digest and the private key; and
performing a verification procedure utilizing the digital signature and the public key to determine whether the signature is valid.

### Claim 2 (depends on 1)

The method as defined by claim 1, wherein said first and second finite fields are designated, respectively, as x-space and y-space, and further comprising generating a specified lattice in x-space and using said isomorphism to generate a corresponding lattice in y-space, and wherein said step of producing said digital signature includes initially producing a signature in the x-space lattice and then producing the digital signature in the corresponding y-space lattice.

### Claim 3 (depends on 1)

The method as defined by claim 1, wherein said secret isomorphism comprises a polynomial.

### Claim 4 (depends on 1)

The method as defined by claim 1, further comprising transmitting the digital signature, and wherein said step of performing a verification procedure includes receiving the transmitted digital signature and performing the verification procedure on the received digital signature.

### Claim 5 (depends on 2)

The method as defined by claim 2, further comprising transmitting the digital signature, and wherein said step of performing a verification procedure includes receiving the transmitted digital signature and performing the verification procedure on the received digital signature.

### Claim 6 (depends on 1)

The method as defined by claim 1, wherein said digital message comprises a challenge communication from a verifier entity, and wherein said digital signature is transmitted to said verifier entity.

### Claim 7 (depends on 2)

The method as defined by claim 2, wherein said digital message comprises a challenge communication from a verifier entity, and wherein said digital signature is transmitted to said verifier entity.

### Claim 8

A method for signing and sending a digital message, comprising the following steps implemented using at least one processor-based subsystem:
generating an irreducible monic polynomial f(x) of degree n in a ring Fq[x];
generating an irreducible monic polynomial F(y) of degree n in a ring Fq[y];
producing first and second finite fields as Fq[x]/(f(x)) and Fq[y]/(F(y)), respectively;
producing a secret isomorphism from the first finite field to the second finite field;
producing and publishing a public key that depends on F(y);
producing a private key that depends on said secret isomorphism;
producing a message digest by applying a hash function to the digital message and the public key;
producing a digital signature using the message digest and the private key; and
transmitting the digital signature.

### Claim 9 (depends on 8)

The method as defined by claim 8, wherein said first and second finite fields are designated, respectively, as x-space and y-space, and further comprising generating a specified lattice in x-space and using said isomorphism to generate a corresponding lattice in y-space, and wherein said step of producing said digital signature includes initially producing a signature in the x-space lattice and then producing the digital signature in the corresponding y-space lattice.

### Claim 10 (depends on 8)

The method as defined by claim 8, wherein said secret isomorphism comprises a polynomial.

### Claim 11 (depends on 8)

The method as defined by claim 8, further comprising receiving the digital signature, and employing a further process-based subsystem for performing a verification procedure on the received digital signature.

### Claim 12 (depends on 9)

The method as defined by claim 9, further comprising receiving the digital signature, and employing a further process-based subsystem for performing a verification procedure on the received digital signature.

### Claim 13

A system for signing and subsequently verifying a digital message, comprising:
at least one processor-based subsystem that is programmed with instructions that cause the at least one processor subsystem to implement the following steps:
generating an irreducible monic polynomial f(x) of degree n in a ring Fq[x];
generating an irreducible monic polynomial F(y) of degree n in a ring Fq[y];
producing first and second finite fields as Fq[x]/(f(x)) and Fq[y]/(F(y)), respectively;
producing a secret isomorphism from the first finite field to the second finite field;
producing and publishing a public key that depends on F(y);
producing a private key that depends on said secret isomorphism;
producing a message digest by applying a hash function to the digital message and the public key;
producing a digital signature using the message digest and the private key; and
performing a verification procedure utilizing the digital signature and the public key to determine whether the signature is valid.

### Claim 14 (depends on 13)

The system as defined by claim 13, wherein said encoded digital signature is transmitted to a further processor-based subsystem, and said further processor-based system is programmed with instructions that cause the further processor-based system to implement said step of performing said verification procedure utilizing the encoded digital signature and the public key to determine whether the signature is valid.

### Claim 15 (depends on 13)

The system as defined by claim 13, wherein said first and second finite fields are designated, respectively, as x-space and y-space, and further comprising said at least one processor-based subsystem being programmed with instructions to implement: generating a specified lattice in x-space and using said isomorphism to generate a corresponding lattice in y-space, and wherein said step of producing said digital signature includes initially producing a signature in the x-space lattice and then producing the digital signature in the corresponding y-space lattice.

### Claim 16 (depends on 14)

The system as defined by claim 14, wherein said first and second finite fields are designated, respectively, as x-space and y-space, and further comprising said at least one processor-based subsystem being programmed with instructions to implement: generating a specified lattice in x-space and using said isomorphism to generate a corresponding lattice in y-space, and wherein said step of producing said digital signature includes initially producing a signature in the x-space lattice and then producing the digital signature in the corresponding y-space lattice.
