# US 2020/0401706 A1 · Data comparison device, data comparison system, and data comparison method

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

- Number: US 2020/0401706 A1
- Document ID: US20200401706A1
- Status: Published application
- Kind: A1
- Application number: 16/890,046
- Filed: 2020-06-02
- Published: 2020-12-24
- Earliest claimed: 2019-06-18
- Assignees: Hitachi, Ltd.
- Applicants: Hitachi, Ltd.
- Inventors: Masayuki YOSHINO; Ken NAGANUMA; Hisayoshi SATO
- Web page: https://patentgrep.com/patent/US20200401706A1

## CPC

- G06F 21/602: {Providing cryptographic facilities or services}
- H04L 9/065: {Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3}
- G06F 7/02: Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence)
- H04L 9/0869: {involving random numbers or seeds}
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- H04L 9/3242: {involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC}
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A data comparison device holds first and second encrypted data of first and second plaintext, respectively. The first plaintext is divided into a plurality of blocks and the first encrypted data is generated by executing encryption of each of the plurality of blocks and shuffling of the plurality of blocks. The second plaintext is divided into a plurality of blocks and the second encrypted data is generated by executing encryption of each of the plurality of blocks. In at least one of the first encrypted data and the second encrypted data, a plaintext value is embedded as a value indicating a magnitude comparison result, and the data comparison device compares blocks at the same position before shuffling of the first encrypted data and the second encrypted data based on the embedded value and determines a magnitude relationship between the first plaintext and the second plaintext.

## Claims

### Claim 1

A data comparison device comprising:
a processor and a memory, wherein
the memory holds first encrypted data in which a first plaintext is encrypted and second encrypted data in which a second plaintext is encrypted,
for the first plaintext divided into a plurality of blocks, the first encrypted data is data generated by executing processing including encryption of each of the plurality of blocks and shuffling of the plurality of blocks,
for the second plaintext divided into the plurality of blocks, the second encrypted data is data generated by executing processing including encryption of each of the plurality of blocks,
in at least one of the first encrypted data and the second encrypted data, a value of the at least one plaintext is embedded as a value indicating a magnitude comparison result, and
the processor compares blocks at the same position before shuffling of the first encrypted data and the second encrypted data based on the embedded value of the at least one plaintext and determines a magnitude relationship between the first plaintext and the second plaintext.

### Claim 2 (depends on 1)

The data comparison device according to claim 1, wherein
in the encryption of each of the plurality of blocks in at least one of the first encrypted data and the second encrypted data, a value of each block of the one plaintext is converted to a different value.

### Claim 3 (depends on 2)

A data comparison system that is the data comparison device according to claim 2, wherein
the first plaintext and the second plaintext are bit strings,
for the first plaintext divided for each bit, the first encrypted data is data generated by executing processing including encryption in which for each bit value, a value of the bit, a value of a bit higher than the bit, and a value of a secret key input to a first function are obtained, and the value of the bit in the first plaintext is embedded in a value obtained by inputting the obtained values and a random number to a second function, and shuffling of the first plaintext in 1-bit units,
the first encrypted data includes the random number, and
for the second plaintext divided for each bit, the second encrypted data is data generated by executing processing including encryption in which for each bit value, a value obtained by inverting the bit, a value of a bit higher than the bit, and the secret key are input to the first function.

### Claim 4 (depends on 3)

The data comparison device according to claim 3, wherein
the processor
obtains the random number from the first encrypted data,
calculates an exclusive OR of a value obtained by inputting the bit and the random number to the second function and a bit at the same position before shuffling of the first encrypted data, for the bits of the second encrypted data, and
determines a magnitude relationship between the first plaintext and the second plaintext based on the calculated exclusive OR.

### Claim 5 (depends on 4)

A data comparison system that is the data comparison device according to claim 4, wherein
the processor
determines that a first plaintext is larger than a second plaintext if the calculated exclusive OR is 1,
determines that a first plaintext is smaller than a second plaintext if the calculated exclusive OR is 0, and
determines that the first plaintext is equal to the second plaintext if the calculated exclusive OR is a random number.

### Claim 6 (depends on 2)

The data comparison device according to claim 2, wherein
the first plaintext and the second plaintext are base-p numeric strings,
p is an integer of 3 or more,
for the first plaintext divided every predetermined number of digits, the first encrypted data is data generated by executing processing including encryption in which for each digit value, a value of the digit, a value of a digit higher than the digit, and a value of the secret key input to a first function are obtained, and the obtained values and a first random number are input to a second function, and shuffling of the first plaintext in units of the predetermined number of digits,
the first encrypted data includes the first random number, and
for the second plaintext divided every predetermined number of digits, the second encrypted data is data generated by executing processing including encryption in which for each digit value, a value of the digit, a value of a digit higher than the digit, and the secret key are input to the first function or a newly generated random number is set as the value of the digit.

### Claim 7 (depends on 6)

The data comparison device according to claim 6, wherein
the processor
obtains the first random number from the first encrypted data,
calculates an exclusive OR of a value obtained by inputting the bit and the random number to the second function and the same digit before shuffling of the first encrypted data, for the bits of the second encrypted data, and
determines a magnitude relationship between the first plaintext and the second plaintext based on the calculated exclusive OR.

### Claim 8

A data comparison system comprising:
a data comparison device;
a first encrypted data generation device that encrypts a first plaintext; and
a second encrypted data generation device that encrypts a second plaintext, wherein
the first encrypted data generation device
divides the first plaintext into a plurality of blocks, and
generates a first encrypted data by executing processing including encryption of the first plaintext for each of the plurality of blocks and shuffling of the plurality of blocks,
the second encrypted data generation device
divides the second plaintext into the plurality of blocks,
generates a second encrypted data by executing processing including encryption of the second plaintext for each of the plurality of blocks,
when at least one of processing of embedding a value of the first plaintext as a value indicating a magnitude comparison result in the generation of the first encrypted data by the first encrypted data generation device and processing of embedding a value of the second plaintext as a value indicating a magnitude comparison result in the generation of the second encrypted data by the second encrypted data generation device is executed,
the first encrypted data generation device transmits the first encrypted data to the data comparison device and
the second encrypted data generation device transmits the second encrypted data to the data comparison device, and
the data comparison device compares blocks at the same position before shuffling of the first encrypted data and the second encrypted data based on the embedded value of the at least one plaintext and determines a magnitude relationship between the first plaintext and the second plaintext based on a value indicating the magnitude comparison result.

### Claim 9

A data comparison method executed by a data comparison device, wherein
the data comparison device includes a processor and a memory,
the memory holds first encrypted data in which a first plaintext is encrypted and second encrypted data in which a second plaintext is encrypted,
for the first plaintext divided into a plurality of blocks, the first encrypted data is data generated by executing processing including encryption of each of the plurality of blocks and shuffling of the plurality of blocks,
for the second plaintext divided into the plurality of blocks, the second encrypted data is data generated by executing processing including encryption of each of the plurality of blocks,
in at least one of the first encrypted data and the second encrypted data, a value of the at least one plaintext is embedded as a value indicating a magnitude comparison result, and
the processor compares blocks at the same position before shuffling of the first encrypted data and the second encrypted data based on the embedded value of the at least one plaintext and determines a magnitude relationship between the first plaintext and the second plaintext.