Patent ID: 12261951

DESCRIPTION OF EMBODIMENTS

Embodiments are described below with the drawings. In the drawings, the same or equivalent portions are denoted with the same reference characters. In the description of the embodiments, description will be omitted or simplified as appropriate for the same or equivalent portions.

Embodiment 1

A deduplication system100in Embodiment 1 is described. The deduplication system100is a cryptographic system that removes ciphertexts for which ciphertexts are duplicate.

FIG.1shows a system configuration of the deduplication system100.

As shown inFIG.1, the deduplication system100includes a common parameter generation apparatus200, multiple user key generation apparatuses300, multiple encryption apparatuses400, a conversion key generation apparatus500, a tag conversion apparatus600, and a match determination apparatus700. The tag conversion apparatus600converts an encryption tag ETag into an encryption tag T. The encryption tag ETag is first encrypted data and the encryption tag T is second encrypted data. The encryption apparatus400corresponds to an encryption unit, the conversion key generation apparatus500corresponds to a third key generation unit, the tag conversion apparatus600corresponds to an encrypted data conversion unit, and the match determination apparatus700corresponds to a match determination unit.

The common parameter generation apparatus200, the multiple user key generation apparatuses300, the multiple encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700are computers.

In the deduplication system100, the common parameter generation apparatus200, the multiple user key generation apparatuses300, the multiple encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700are connected to a network101. The network101may be the Internet or a LAN (Local⋅Area⋅Network) installed in a corporation.

The network101is a communication channel connecting the common parameter generation apparatus200, the multiple user key generation apparatuses300, the multiple encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700with each other.

The common parameter generation apparatus200creates a common parameter for use in the deduplication system100and transmits the common parameter to the multiple user key generation apparatuses300, the multiple encryption apparatuses400, the conversion key generation apparatus500, and the tag conversion apparatus600over the network101. The common parameter may instead be sent directly to parties of the deduplication system100such as by postal mail without going through the network101.

Each user key generation apparatus300generates a user key and transmits the user key to the encryption apparatus400and the conversion key generation apparatus500. Each encryption apparatus400generates an encryption tag ETag with plaintext M and the user key transmitted from the user key generation apparatus300as input and transmits the ETag to the tag conversion apparatus600. The conversion key generation apparatus500receives the user key from the user key generation apparatus300and generates a conversion key ck from the user key. The tag conversion apparatus600receives the conversion key ck from the conversion key generation apparatus500and receives the encryption tag ETag from the encryption apparatus400. The tag conversion apparatus600converts the encryption tag ETag as the first encrypted data into an encryption tag T as the second encrypted data that can be deduplicated, using the conversion key ck. The tag conversion apparatus600transmits the encryption tag T to the match determination apparatus700. The match determination apparatus700receives multiple encryption tags T from the tag conversion apparatus600, determines whether the encryption tags T match, and outputs a determination result.

A single computer may implement any two, any three, or four of the user key generation apparatuses300, the encryption apparatuses400, the conversion key generation apparatus500, and the tag conversion apparatus600.

FIG.2is a block diagram showing a configuration of the common parameter generation apparatus200. The common parameter generation apparatus200includes an input unit201, a common parameter generation unit202, and a transmission unit203. Although not shown, the common parameter generation apparatus200includes a recording medium for storing data used in the components of the common parameter generation apparatus200. To the input unit201, a bit length k of the key used in the deduplication system100is input. The common parameter generation unit202generates a common parameter to be a basis of computations executed in the deduplication system100. Although not shown, the common parameter generation unit202may have random number generation functionality in order to generate common parameters. The transmission unit203transmits the common parameter generated by the common parameter generation unit202to the multiple user key generation apparatuses300.

FIG.3is a block diagram showing a configuration of the user key generation apparatus300. The user key generation apparatus300includes a parameter reception unit301, a key generation unit302, and a key transmission unit303. Although not shown, the user key generation apparatus300includes a recording medium for storing data used in the components of the user key generation apparatus300. The parameter reception unit301receives the common parameter. The key generation unit302generates an encryption key ek and a conversion key generation key tk. Although not shown, the key generation unit302may have random number generation functionality in order to generate these keys. The key transmission unit303transmits the encryption key ek to the encryption apparatus400and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus500.

FIG.4is a block diagram showing a configuration of the encryption apparatus400. As shown inFIG.4, the encryption apparatus400includes an input unit401, a reception unit402, a tag generation unit403, and a tag transmission unit404. Although not shown, the encryption apparatus400includes a recording medium for storing data used in the components of the encryption apparatus400. To the input unit401, the plaintext M is input. The reception unit402receives the encryption key ek. The tag generation unit403generates the encryption tag ETag. Although not shown, the tag generation unit403may have random number generation functionality in order to generate the encryption tag ETag. The tag transmission unit404transmits the encryption tag ETag generated by the tag generation unit403to the tag conversion apparatus600.

FIG.5is a block diagram showing a configuration of the conversion key generation apparatus500. The conversion key generation apparatus500includes a key reception unit501, a conversion key generation unit502, and a transmission unit503. Although not shown, the conversion key generation apparatus500includes a recording medium for storing data used in the components of the conversion key generation apparatus500. The key reception unit501receives the encryption key ek and the conversion key generation key tk. The conversion key generation unit502generates a conversion key ck from the encryption key ek and the conversion key generation key tk. Although not shown, the conversion key generation unit502may have random number generation functionality in order to generate the conversion key ck. The transmission unit503transmits the conversion key ck to the tag conversion apparatus600.

FIG.6is a block diagram showing a configuration of the tag conversion apparatus600. The tag conversion apparatus600is an encrypted data conversion apparatus.

The tag conversion apparatus600includes a reception unit601, an input unit602, a key saving unit603, a conversion unit604, and a transmission unit605. Although not shown, the tag conversion apparatus600includes a recording medium for storing data used in the components of the tag conversion apparatus600.

The reception unit601receives the conversion key ck. The input unit602receives the encryption tag ETag. The key saving unit603saves the conversion key ck. The conversion unit604converts the encryption tag ETag input at the input unit602into an encryption tag T that can be deduplicated, using the conversion key ck saved in the key saving unit603. Although not shown, the conversion unit604may have random number generation functionality in order to convert the encryption tag ETag to the encryption tag T. The transmission unit605transmits the encryption tag T, which is encrypted data that can be deduplicated, to the match determination apparatus700.

FIG.7is a block diagram showing a configuration of the match determination apparatus700. The match determination apparatus700includes a tag input unit701, a determination unit702, and a result transmission unit703. Although not shown, the match determination apparatus700includes a recording medium for storing data used in the components of the match determination apparatus700. To the tag input unit701, an encrypted encryption tag T1, which can be deduplicated, and an encrypted encryption tag T2, which can be deduplicated, are input. The determination unit702determines whether the values of the encryption tag T1and the encryption tag T2match. The result transmission unit703outputs a determination result on whether they match.

Operations of the individual apparatuses in the deduplication system100are now described.

FIG.8is a flowchart illustrating the operation of the common parameter generation apparatus200.

FIG.9is a flowchart illustrating the operation of the user key generation apparatus300.

FIG.10is a flowchart illustrating the operation of the encryption apparatus400. The encryption apparatus400generates an encryption tag ETag which is an encryption of the plaintext M, using the encryption key ek and the plaintext M.

FIG.11is a flowchart illustrating the operation of the conversion key generation apparatus500. The conversion key generation apparatus500generates a conversion key ck using the encryption key ek and the conversion key generation key tk.

FIG.12is a flowchart illustrating the operation of the tag conversion apparatus600. By applying the conversion key ck to the encryption tags ETag, the tag conversion apparatus600converts an encryption tag ETag for which the same plaintext M has been used into an encryption tag T that takes the same value regardless of the value of the encryption key ek used for the encryption tag ETag.

FIG.13is a flowchart illustrating the operation of the match determination apparatus700. The match determination apparatus700determines whether the values of two pieces of second encrypted data T match.

FIG.14is a diagram showing the flowcharts ofFIGS.8to13as a sequence.

Referring toFIG.14, the operations of the individual apparatuses of the deduplication system100will be described.

A general operation of the deduplication system100shown inFIG.14is as follows. The encryption apparatus400calculates an exclusive OR of the encryption key ek and the plaintext M as the encryption tag ETag. The conversion key generation apparatus500calculates an exclusive OR of the encryption key ek and the conversion key generation key tk, and generates a calculation result thereof as the conversion key ck. The tag conversion apparatus600converts the encryption tag ETag into the encryption tag T, which is the second encrypted data, by applying the conversion key ck to the encryption tag ETag, which is the first encrypted data.

<Common Parameter Generation Apparatus200>

At step S201, the bit length k is input to the input unit201.

At step S202, the common parameter generation unit202generates a k-bit random value sk as a common parameter.

At step S203, the transmission unit203transmits the bit length k and the common parameter sk to the user key generation apparatus300.

<User Key Generation Apparatus300>

At step S301, the parameter reception unit301receives the bit length k and the common parameter sk from the common parameter generation apparatus200.

At step S302, the key generation unit302generates a k-bit random value skA as the encryption key ek. The key generation unit302also sets the conversion key generation key tk as the encryption key sk.

At step S303, the key transmission unit303transmits the encryption key ek to the encryption apparatuses400and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus500.

<Encryption Apparatus400>

At step S401, the plaintext M is input to the input unit401.

At step S402, the reception unit402receives the encryption key ek from the user key generation apparatus300.

At step S403, the tag generation unit403calculates:
ETag=Hash(M)<XOR>skA(1)
Here, Hash indicates a cryptographic hash function and can be SHA256, for example. <XOR> represents exclusive OR.

At step S404, the tag transmission unit404transmits the encryption tag ETag to the tag conversion apparatus600.

<Conversion Key Generation Apparatus500>

At step S501, the key reception unit501receives the encryption key ek and the conversion key generation key tk from the user key generation apparatus300.

At step S502, the conversion key generation unit502calculates:
ck=ek<XOR>tk=skA<XOR>sk(2)

At step S503, the transmission unit503transmits the conversion key ck to the tag conversion apparatus600.

<Tag Conversion Apparatus600>

At step S601, the reception unit601as a third key acquisition unit acquires the conversion key ck, which is a third key generated using the encryption key ek and the conversion key generation key tk, which is a second key.

At step S602, the input unit602as an acquisition unit acquires an encryption tag ETag, which is the first encrypted data and is an encryption of the plaintext M generated using the encryption key ek as the first key and the plaintext M.

At step S603, the conversion unit604converts an encryption tag ETag for which the same plaintext M has been used into an encryption tag T as the second encrypted data that takes the same value regardless of the value of the encryption key ek used for the encryption tag ETag. Specifically, it is done as follows.

In the deduplication system100of Embodiment 1, the same key is set for different users as the conversion key generation key tk=Sk that is set at step S302. Thus, according to expression (3) below, an encryption tag ETag for which the same plaintext M has been used is converted to an encryption tag T that takes the same value regardless of the value of the encryption key ek used for the encryption tag ETag.

T=ck⁢〈XOR〉⁢ETag={ek⁢〈XOR〉⁢tk}⁢〈XOR〉⁢{Hash(M)⁢〈XOR〉⁢ek}=tk⁢〈XOR〉⁢Hash(M)(3)
is calculated.

At step S604, the transmission unit605as a transmission control unit transmits the encryption tags T to the match determination apparatus700, which determines whether the values of two encryption tags T match.

At step S701, two encryption tags T1and T2are input to the tag input unit701.

At step S702, the determination unit702verifies whether bit strings of the encryption tag T1and the encryption tag T2are equal. If the bit strings of the encryption tag T1and the encryption tag T2are determined to be equal by the determination unit702, the result transmission unit703outputs 1 at step S703, and if the bit strings of the encryption tag T1and the encryption tag T2are determined to be different, the result transmission unit703outputs 0 at step S704.

Effect of Embodiment 1

In Embodiment 1, an encryption tag ETag generated with the encryption key ek which is different from person to person can be converted to the encryption tag T by using the conversion key ck.

Although the encryption tag ETag cannot be deduplicated, it has the de facto standard security of encryption. In addition, an encryption tag T converted from the encryption tag ETag can be deduplicated. Thus, according to Embodiment 1, a cryptographic system having high security can be provided without losing the convenience of deduplication.

Embodiment 2

Referring toFIGS.15to23, the deduplication system100in Embodiment 2 is described. In Embodiment 1, the encryption tag ETag was generated with the exclusive OR of a hash value of plaintext M and the encryption key ek at step S403. In Embodiment 2, the encryption tag ETag is generated by means of pairing computation.

The configuration of the deduplication system100is the same asFIG.1of Embodiment 1. The configurations of the common parameter generation apparatus200, the user key generation apparatuses300, the encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700are also the same asFIGS.2to7of Embodiment 1.

FIG.15is a flowchart illustrating the operation of the common parameter generation apparatus200.

FIG.16is a flowchart illustrating the operation of the user key generation apparatus300.

FIG.17is a flowchart illustrating the operation of the encryption apparatus400.

FIG.18is a flowchart illustrating the operation of the conversion key generation apparatus500.

FIG.19is a flowchart illustrating the operation of the tag conversion apparatus600.

FIG.20is a flowchart illustrating the operation of the match determination apparatus700.

FIG.21is a diagram showing the flowcharts ofFIGS.15to20as a sequence.

Referring toFIG.21, the operations of the individual apparatuses of the deduplication system100will be described.

<Common Parameter Generation Apparatus200>

At step S801, the bit length k is input to the input unit201.

At step S802, based on the bit length k, the common parameter generation unit202generates an element available for pairing computation:
BG=(p,G,GT,e)  (4)

Here, p represents the order of group G and group GT.

e is a bilinear mapping with a mapping of G×G→GT.

A bilinear mapping is a mapping such that
e(ga,gb)=e(g,g)ab∈GT(5)
holds for all g∈G, and a, b∈Zp. Computation using this e is called pairing computation.

Zpis a set of integers with mod=p.

g∈G is randomly selected.

At step S803, the transmission unit203transmits the bit length k, g, and the element BG to the user key generation apparatus300.

<User Key Generation Apparatus300>

At step S901, the parameter reception unit301receives the bit length k, g, and BG from the common parameter generation apparatus200.

At step S902, the key generation unit302randomly selects x∈Zpand calculates:
y=gx.

The key generation unit302also selects Y∈G.

The key generation unit302sets:
encryption keyek=(g,y,Y)  (6), and
conversion key generation keytk=x(7)

The encryption key ek as the first key includes a first element, a second element, and a third element. In the encryption key ek, g is the first element, y is the second element, and Y is the third element.

At step S903, the key transmission unit303transmits the encryption key ek to the encryption apparatus400and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus500.

<Encryption Apparatus400>

At step S1001, the plaintext M is input to the input unit401.

At step S1002, the reception unit402receives the encryption key ek from the user key generation apparatus300.

At step S1003, the tag generation unit403calculates:
C1=gr,C2=yr+Hash(g,M)(8)
and sets:
ETag=(C1,C2)=(gr,yx{r+Hash(g,M)})  (9)
and the encryption tag ETag.

Here, Hash indicates a cryptographic hash function and can be SHA256, for example.

At step S1004, the tag transmission unit404transmits the encryption tag ETag to the tag conversion apparatus600.

As shown in expression 9, the encryption apparatus400as the encryption unit encrypts the plaintext M using the first element g and the second element y. The encryption apparatus400generates, as the ETag, data which is an encryption of the plaintext M

<Conversion Key Generation Apparatus500>

At step S1101, the key reception unit501receives:
encryption keyek=(g,y,Y)=(g,gx,Y), and
conversion key generation keytk=xfrom the user key generation apparatus 300.

At step S1102, the conversion key generation unit502calculates:
ck′=Y1/x(10)

At step S1103, the transmission unit503transmits:
the conversion keyck=(ck′,ek)
to the tag conversion apparatus600.

As in expression 10 and the expression of the conversion key ck shown above, the conversion key generation apparatus500as the third key generation unit applies the conversion key generation key tk, which is the second key, to the third element Y and generates, as a conversion key ck, which is the third key, a pair of a value ck′ resulting from applying the conversion key generation key tk to the third element Y and the encryption key ek, which is the first key.

<Tag Conversion Apparatus600>

At step S1201, the reception unit601receives:
conversion keyck=(ck′,ek)=(Y1/x,g,gx,Y)
from the conversion key generation apparatus500.

At step S1202, to the input unit602, the encryption tag:
ETag=(C1,C2)=(gr,gx{r+Hash(g,M)})
is input.

At step S1203, the conversion unit604converts an encryption tag ETag for which the same plaintext M has been used into an encryption tag T as the second encrypted data that takes the same value regardless of the value of the encryption key ek used for the encryption tag ETag. Specifically, it is done as follows.

In the deduplication system100of Embodiment 2, the same values are set for different users as the g selected at step S802and the Y selected at step S902. Thus, according to expression (11) below, an encryption tag ETag for which the same plaintext M has been used is converted to an encryption tag T that takes the same value regardless of the value of the encryption key ek used for the encryption tag ETag.

The conversion unit604calculates:

T=e⁡(C2,ck′)/e⁡(C1,Y)=e⁡(gx⁢{r+Hash⁡(g,M)},Y1/x)/e⁡(gr,Y)=e⁡(g,Y)x⁢{r+Hash(g,M}*1/x/e⁡(g,Y)r=e⁡(g,Y){r+Hash⁡(g,M)}/e⁡(g,Y)r=e⁡(g,Y)Hash⁡(g,M)(11)

e represents a pairing computation.

At step S1204, the transmission unit605transmits the encryption tag T converted from the encryption tag ETag to the match determination apparatus700.

<Match Determination Apparatus700>

At step S1301, two encryption tags T1and T2are input to the tag input unit701.

At step S1302, the determination unit702verifies whether bit strings of the encryption tag T1and the encryption tag T2are equal.

At step S1302, if the bit strings of the encryption tag T1and the encryption tag T2are determined to be equal by the determination unit702, the result transmission unit703outputs 1 at step S1303, and if the bit strings of the encryption tag T1and the encryption tag T2are determined to be different, the result transmission unit703outputs 0 at step S1304.

Effect of Embodiment 2

According to Embodiment 2, a cryptographic system of a public key approach can be made a cryptographic system having high security without losing the convenience of deduplication.

FIG.22is a diagram showing a hardware configuration of the common parameter generation apparatus200, the multiple user key generation apparatuses300, the encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700in Embodiments 1 and 2.

The common parameter generation apparatus200, the multiple user key generation apparatuses300, the encryption apparatuses400, the conversion key generation apparatus500, the tag conversion apparatus600, and the match determination apparatus700are computers.FIG.22is a hardware configuration of the common parameter generation apparatus200through the match determination apparatus700, which are computers.

As the common parameter generation apparatus200through the match determination apparatus700have the same hardware configuration, the encryption apparatus400will be described as a representative.

InFIG.22, the encryption apparatus400includes a CPU1101(Central Processing Unit).

The CPU1101is connected with hardware devices such as a ROM1103, a RAM1104, a communication board1105, a display1111, a keyboard1112, a mouse1113, a drive1114, and a magnetic disk device1120via a bus1102and controls these hardware devices.

The drive1114is a device to read and write storage media such as an FD (Flexible Disk Drive), a CD (Compact Disc), and a DVD (Digital Versatile Disc).

The ROM1103, the RAM1104, the magnetic disk device1120, and the drive1114are examples of storage devices.

The keyboard1112, the mouse1113, and the communication board1105are examples of input devices. The display1111and the communication board1105are examples of output devices.

The communication board1105is connected with a communication network such as a LAN, the Internet, and a telephone line by wire or wirelessly.

The magnetic disk device1120stores an operating system1121, programs1122, and files1123.

InFIG.22, the operating system1121is denoted as OS1121.

The programs1122include programs for executing those functions that are described as “ . . . units” in Embodiments 1 and 2.

The programs are read and executed by the CPU1101.

That is, the programs cause computers to function as “ . . . units” and cause computers to execute the procedure or methods of the “ . . . units”.

The files1123include various kinds of data such as input data, output data, determination results, calculation results, and processing results that are used in the “ . . . units” described in Embodiments 1 and 2.

The arrows included in configuration diagrams and flowcharts in Embodiments 1 and 2 mostly indicate input and output of data and signals.

Processing in Embodiments 1 and 2 described with respect to a flowchart and the like is executed using hardware such as the CPU1101, a storage device, an input device, and an output device.

Those that are described as “ . . . units” in Embodiments 1 and 2 may be “ . . . circuits”, “ . . . devices”, or “ . . . apparatus” and may also be “ . . . steps”, “ . . . procedure”, or “ . . . process”. That is, those that are described as “ . . . units” may be implemented in any of firmware, software, hardware, or a combination thereof

<Supplementary Note on Hardware Configuration>

In the hardware configuration shown inFIG.22, the functions of the individual apparatuses are implemented in software. However, the functions of the apparatuses may also be implemented in hardware.

As withFIG.22, this will be described with the encryption apparatus400as a representative.

FIG.23shows a configuration in which the functions of the encryption apparatus400are implemented by hardware. An electronic circuit910ofFIG.23is a dedicated electronic circuit for implementing the functions of the input unit401, the reception unit402, the tag generation unit403, and the tag transmission unit404of the encryption apparatus400. The electronic circuit910is connected to a signal line911. The electronic circuit910is specifically a single circuit, a composite circuit, a programmed processor, a parallel programmed processor, a logic IC, a GA, an ASIC, or an FPGA. GA is an abbreviation for Gate Array. ASIC is an abbreviation for Application Specific Integrated Circuit. FPGA is an abbreviation for Field-Programmable Gate Array. The functions of the components of the encryption apparatus400may be implemented in one electronic circuit or implemented as being distributed across multiple electronic circuits. Also, some of the functions of the components of the encryption apparatus400may be implemented by an electronic circuit and the remaining functions may be implemented by software.

Each of the CPU1101and the electronic circuit910is also called processing circuitry. In the encryption apparatus400, the functions of the input unit401, the reception unit402, the tag generation unit403, and the tag transmission unit404may be implemented by processing circuitry. Alternatively, the functions of the “ . . . units” shown inFIGS.2to7may be implemented by processing circuitry.

REFERENCE SIGNS LIST

ck: conversion key; ETag: encryption tag; T: encryption tag; ek: encryption key; M: plaintext; tk: conversion key generation key;100: deduplication system;101: network;200: common parameter generation apparatus;201: input unit;202: common parameter generation unit;203: transmission unit;300: user key generation apparatus;301: parameter reception unit;302: key generation unit;303: key transmission unit;400: encryption apparatus;401: input unit;402: reception unit;403: tag generation unit;404: tag transmission unit;500: conversion key generation apparatus;501: key reception unit;502: conversion key generation unit;503: transmission unit;600: tag conversion apparatus;601: reception unit;602: input unit;603: key saving unit;604: conversion unit;605: transmission unit;700: match determination apparatus;701: tag input unit;702: determination unit;703: result transmission unit;910: electronic circuit;911: signal line.