# US 2020/0287722 A1 · Electronic device capable of data communication through electronic signatures based on syndrome and operating method thereof

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

- Number: US 2020/0287722 A1
- Document ID: US20200287722A1
- Status: Published application
- Kind: A1
- Application number: 16/699,097
- Filed: 2019-11-28
- Published: 2020-09-10
- Earliest claimed: 2019-03-08
- Assignees: Seoul National University R&Db Foundation; Industry-Academic Cooperation Foundation, Chosun University
- Applicants: Seoul National University R&DB Foundation; Industry-Academic Cooperation Foundation, Chosun University
- Inventors: Jong Seon NO; Young Sik KIM; Yong Woo LEE; Wi Jik LEE
- Web page: https://patentgrep.com/patent/US20200287722A1

## CPC

- H04L 9/3247: {involving digital signatures}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/304: {based on error correction codes, e.g. McEliece}
- H04L 2209/34: Encoding or coding, e.g. Huffman coding or error correction
- H04L 2209/56: Financial cryptography, e.g. electronic payment or e-cash
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided is an electronic signature technique depending on a diametrically different algorithm from the existing asymmetric key infrastructure electronic signature technique which generates predetermined syndrome data based on a message to be transmitted a data receiving device and then detects an error vector for an electronic signature from the syndrome data by using a parity check matrix and then generates an electronic signature value based on an error vector for the electronic signature and transmits the generated electronic signature value to the data receiving device.

## Claims

### Claim 1

An electronic device capable of data communication through electronic signatures based on syndrome, the electronic device comprising:
a private key storing unit storing a parity check matrix H for a linear code having a size of (n−k)×n, in which n and k are natural numbers and n is larger than k, configured by a Reed-Muller (RM) code, an invertible matrix S having a size of (n−k)×(n−k) including code values of ‘1’ and ‘0’ as components, and a permutation matrix Q having a size of n×n including the code values of ‘1’ and ‘0’ as the components as a private key for the electronic signature;
a syndrome data generating unit generating syndrome data si to be used as the syndrome based on the plain text message m to be transmitted to a data receiving device and the invertible matrix S;
an error vector generating unit generating a signature error vector esT by performing the syndrome decoding for error detection with respect to the syndrome data si based on the parity check matrix H;
an electronic signature unit computing Q−1esT by multiplying a left term of the signature error vector esT by Q−1 which is an inverse matrix of the permutation matrix Q to generate the computed Q−1esT as the electronic signature value for the plain text message m; and
an electronic signature transmitting unit transmitting the plain text message m and the electronic signature value Q−1esT to the data receiving device.

### Claim 2 (depends on 1)

The electronic device of claim 1, wherein the parity check matrix H is a parity check matrix corresponding to Gm which is a generation matrix made by randomly permuting components which are present in p (p is a natural number) rows included in at least one partial matrix among a plurality of partial matrixes configured by another RM code configured when n columns constituting the generation matrix G are distinguished for each of n/4 in the generation matrix G having the size of k×n configured by the RM code.

### Claim 3 (depends on 1)

The electronic device of claim 1, wherein the syndrome data generating unit includes:
a first hash value computing unit computing a first hash value h(m) by applying the plain text message m to a predetermined hash function h(x) as an input, in which the hash function h(x) is a unidirectional function to convert an input value into an output value having an (n−k) bit size; and
a syndrome generating unit generating the syndrome data si in which si=S−1h(h(m)|i)T by computing h(h(m)|i) which is a second hash value by applying a result value h(m)|i acquired by concatenating a bit value for a variable i to the first hash value h(m) while randomly selecting the variable i in which the variable i is an integer which is equal to or more than ‘0’ to the hash function h(x) as the input and multiplying the left term of h(h(m)| which is the transposed matrix of the h(h(m)|i) which is the second hash value by S−1 which is the inverse matrix of the invertible matrix S, when computing the first hash value h(m) is completed.

### Claim 4 (depends on 3)

The electronic device of claim 3, wherein the error vector generating unit computes eT satisfying HeT=si in which eT as the transposed matrix of vector e having a size of n has a size of n×1 by performing complete decoding for the error detection based on the parity check matrix H with respect to the syndrome data si of each variable i whenever while the variable i is randomly selected, the syndrome data si is generated and then selects the variable i at the time when the Hamming weight of eT is computed to be equal to or less w which is the predetermined Hamming weight as a signature variable is and selects eT computed to correspond to the signature variable is as the signature error vector esT, and
the electronic signature transmitting unit transmits the plain text message m, and the electronic signature value Q−1esT and the signature variable is to the data receiving device.

### Claim 5 (depends on 4)

The electronic device of claim 4, wherein the data receiving device stores, in the memory, Kpub, in which Kpub=SHQ, having a size of (n−k)×n, which is a matrix multiplied by the invertible matrix S, the parity check matrix H, and the permutation matrix Q as a public key for verifying the electronic signature, and when the data receiving device receives the plain text message m, and the electronic signature value Q−1esT and the signature variable is, the data receiving device checks whether the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight and then when it is verified that the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight, the data receiving device verifies the electronic signature value Q−1esT based on the public key Kpub and the signature variable is.

### Claim 6 (depends on 5)

The electronic device of claim 5, wherein the data receiving device
additionally stores the hash function h(x) in the memory and when the plain text message m, and the electronic signature value Q−1esT and the signature variable is are received, verifies whether the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight and then when it is verified that the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight, computes the first hash value h(m) by applying the plain text message m to the hash function h(x) stored in the memory as the input,
when the first hash value h(m) is computed, computes h(h(m)|is) which is a verification hash value by applying a result value h(m)|is acquired by concatenating the bit value for the signature variable is to the first hash value h(m) to the hash function h(x) as the input, and
compares whether KpubQ−1esT which is a result value acquired by multiplying the public key Kpub by the electronic signature value Q−1esT coincides with h(h(m)|is)T which is the transposed matrix of the verification hash value h(h(m)|is) and when it is determined that the KpubQ−1esT coincides with h(h(m)|is)T which is the transposed matrix of the verification hash value h(h(m)|is), determines that verifying the electronic signature value Q−1esT is successful.

### Claim 7

An operating method of an electronic device capable of data communication through electronic signatures based on syndrome, the operating method comprising:
maintaining a private key storing unit storing a parity check matrix H for a linear code having a size of (n−k)×n, in which n and k are natural numbers and n is larger than k, configured by a Reed-Muller (RM) code, an invertible matrix S having a size of (n−k)×(n−k) including code values of ‘1’ and ‘0’ as components, and a permutation matrix Q having a size of n×n including the code values of ‘1’ and ‘0’ as the components as a private key for the electronic signature;
generating syndrome data si to be used as the syndrome based on the plain text message m to be transmitted to a data receiving device and the invertible matrix S;
generating a signature error vector esT by performing the syndrome decoding for error detection with respect to the syndrome data si based on the parity check matrix H;
computing Q−1esT by multiplying a left term of the signature error vector esT by Q−1 which is an inverse matrix of the permutation matrix Q to generate the computed Q−1esT as the electronic signature value for the plain text message m; and
transmitting the plain text message m and the electronic signature value Q−1esT to the data receiving device.

### Claim 8 (depends on 7)

The operating method of claim 7, wherein the parity check matrix H is a parity check matrix corresponding to Gm which is a generation matrix made by randomly permuting components which are present in p (p is a natural number) rows included in at least one partial matrix among a plurality of partial matrixes configured by another RM code configured when n columns constituting the generation matrix G are distinguished for each of n/4 in the generation matrix G having the size of k×n configured by the RM code.

### Claim 9 (depends on 7)

The operating method of claim 7, wherein the generating of the syndrome data si includes:
computing a first hash value h(m) by applying the plain text message m to a predetermined hash function h(x) as an input, in which the hash function h(x) is a unidirectional function to convert an input value into an output value having an (n−k) bit size; and
generating the syndrome data si in which si=S−1h(h(m)|i)T by computing the second hash value h(h(m)|i) by applying a result value h(m)|i acquired by concatenating a bit value for a variable i to the first hash value h(m) while randomly selecting the variable i (i the variable i is an integer which is equal to or more than ‘0’) to the hash function h(x) as the input and multiplying the left term of h(h(m)|i)T which is the transposed matrix of the h(h(m)|i) which is the second hash value by S−1 which is the inverse matrix of the invertible matrix S, when computing the first hash value h(m) is completed.

### Claim 10 (depends on 9)

The operating method of claim 9, wherein in the generating of the signature error vector esT,
eT satisfying HeT=si in which eT as the transposed matrix of vector e having a size of n has a size of n×1 is computed by performing complete decoding for the error detection based on the parity check matrix H with respect to the syndrome data si of each variable i whenever while the variable i is randomly selected, the syndrome data si is generated and then the variable i is selected at the time when the Hamming weight of eT is computed to be equal to or less than w which is the predetermined Hamming weight as a signature variable is and eT computed to correspond to the signature variable is is selected as the signature error vector esT, and
in the transmitting of the electronic signature value Q−1esT,
the plain text message m, and the electronic signature value Q−1esT and the signature variable is are transmitted to the data receiving device.

### Claim 11 (depends on 10)

The operating method of claim 10, wherein the data receiving device stores, in the memory, Kpub, in which Kpub=SHQ, having a size of (n−k)×n, which is a matrix multiplied by the invertible matrix S, the parity check matrix H, and the permutation matrix Q as a public key for verifying the electronic signature, and when the data receiving device receives the plain text message m, and the electronic signature value Q−1esT and the signature variable is, the data receiving device checks whether the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight and then when it is verified that the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight, the data receiving device verifies the electronic signature value Q−1esT based on the public key Kpub and the signature variable is.

### Claim 12 (depends on 11)

The operating method of claim 11, wherein the data receiving device
additionally stores the hash function h(x) in the memory and when the plain text message m, and the electronic signature value Q−1esT and the signature variable is are received, the data receiving device verifies whether the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight and then when it is verified that the Hamming weight of the electronic signature value Q−1esT is equal to or less than w which is the predetermined Hamming weight, the data receiving device computes the first hash value h(m) by applying the plain text message m to the hash function h(x) stored in the memory as the input,
when the first hash value h(m) is computed, computes h(h(m)|is which is a verification hash value by applying a result value h(m)|is acquired by concatenating the bit value for the signature variable is to the first hash value h(m) to the hash function h(x) as the input, and
compares whether KpubQ−1esT which is a result value acquired by multiplying the public key Kpub by the electronic signature value Q−1esT coincides with h(h(m)|is)T which is the transposed matrix of the verification hash value h(h(m)|is) and when it is determined that the KpubQ−1esT coincides with h(h(m)|is)T which is the transposed matrix of the verification hash value h(h(m)|is), determines that verifying the electronic signature value Q−1esT is successful.

### Claim 13

A non-transitory computer readable recording medium having a program recorded therein for allowing a computer to execute an operating method of an electronic device capable of data communication through electronic signatures based on syndrome, the operating method comprising:
maintaining a private key storing unit storing a parity check matrix H for a linear code having a size of (n−k)×n, in which n and k are natural numbers and n is larger than k, configured by a Reed-Muller (RM) code, an invertible matrix S having a size of (n−k)×(n−k) including code values of ‘1’ and ‘0’ as components, and a permutation matrix Q having a size of n×n including the code values of ‘1’ and ‘0’ as the components as a private key for the electronic signature;
generating syndrome data si to be used as the syndrome based on the plain text message m to be transmitted to a data receiving device and the invertible matrix S;
generating a signature error vector esT by performing the syndrome decoding for error detection with respect to the syndrome data si based on the parity check matrix H;
computing Q−1esT by multiplying a left term of the signature error vector esT by Q−1 which is an inverse matrix of the permutation matrix Q to generate the computed Q−1esT as the electronic signature value for the plain text message m; and
transmitting the plain text message m and the electronic signature value Q−1esT to the data receiving device.
