Patent Description:
A cryptographic system that can remove duplicate encrypted data is able to determine whether encrypted plaintexts match or not in their encrypted data without decrypting the encrypted data (Patent Literature <NUM> and Non-Patent Literature <NUM>, for instance).

A core idea of common encryption that allows deduplication, like Patent Literature <NUM> and Non-Patent Literature <NUM>, is to convert plaintext into a bit string of a fixed length via a hash function, make it an encryption key, and perform encryption with the encryption key. Thus, if plaintexts are the same, encryption keys generated from the same plaintexts will be the same keys, and when deterministic encryption like AES (Advanced Encryption Standard) is used, the same plaintexts are turned into ciphertexts of the same value.

On the other hand, if plaintexts are different even in one bit, completely different keys are generated and the values of the generated ciphertexts are also different. With such a system, a user can utilize encryption that can remove duplication of ciphertexts without having a key.

For such encryption that allows deduplication, it is known that ciphertext does not have de facto standard security in cryptography called indistinguishability.

In addition, since per-user keys are not present and ciphertexts for individual users cannot be distinguished from each other, encryption like the conventional art is subject to the risk of leakage of plaintext information for one user's ciphertext from other users, in combination with the absence of indistinguishability mentioned above.

Non-Patent Literature <NUM> discloses a deduplicated convergent encryption method using a SHA256 hash function and a CTR[AES128] encryption scheme.

Non-Patent Literature <NUM> discloses an architecture that provides deduplicated storage, wherein clients encrypt under message-based keys obtained from a key-server via an oblivious PRF protocol.

Non-Patent Literature <NUM> discloses a deduplication scheme that features scalable key management based on pairing-based cryptography and supports dynamic ownership management.

Non-Patent Literature <NUM> discloses a storage solution which allows a storage provider to attest to its customers the deduplication patterns of the encrypted data that it is storing.

Non-Patent Literature <NUM> discloses a key management scheme for convergent encryption wherein convergent key shares are distributed across multiple servers.

Non-Patent Literature <NUM> discloses a cryptographic primitive wherein the key under which encryption and decryption are performed is itself derived from the message.

Patent Literature <NUM> discloses a method for performing data duplication on data that was previously consolidated (e.g., deduplicated or merged), the method comprising: receiving, by a processing device, a request to modify a storage block comprising data encrypted using a location dependent cryptographic input; causing the data of the storage block to be encrypted using a location independent cryptographic input corresponding to a first storage location; copying the data encrypted using the location independent cryptographic input from the first storage location to a second storage location; causing data at the second storage location to be encrypted using a location dependent cryptographic input corresponding to the second storage location; and updating a reference of the storage block from the first storage location to the second storage location.

Patent Literature <NUM> discloses an apparatus comprising at least one processing core and at least one memory including computer program code, the at least one memory and the computer program code being configured to, with the at least one processing core, cause the apparatus at least to receive, from a first user, a ciphertext, a first hash value and a first ciphered encryption key, receive, from a second user, a second hash value, responsive to a determination the first hash value is the same as the second hash value, obtain a re-encryption key, and apply the re-encryption key to the first ciphered encryption key to obtain a re-encrypted encryption key, the re-encrypted encryption key being decryptable with a secret key of the second user.

Patent Literature <NUM> discloses a key change direction control system, wherein key change information that defines whether or not information can be shared between users and the relationship between directions, and decryption in which one user's encrypted data is held by the other user.

This invention aims to provide a cryptographic system in which (<NUM>), (<NUM>), and (<NUM>) below are possible.

A cryptographic system according to the present invention includes:.

The cryptographic system of this invention can provide a cryptographic system in which (<NUM>), (<NUM>), and (<NUM>) below are possible.

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.

A deduplication system <NUM> in Embodiment <NUM> is described. The deduplication system <NUM> is a cryptographic system that removes ciphertexts for which ciphertexts are duplicate.

<FIG> shows a system configuration of the deduplication system <NUM>.

As shown in <FIG>, the deduplication system <NUM> includes a common parameter generation apparatus <NUM>, multiple user key generation apparatuses <NUM>, multiple encryption apparatuses <NUM>, a conversion key generation apparatus <NUM>, a tag conversion apparatus <NUM>, and a match determination apparatus <NUM>. The tag conversion apparatus <NUM> converts 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 apparatus <NUM> corresponds to an encryption unit, the conversion key generation apparatus <NUM> corresponds to a third key generation unit, the tag conversion apparatus <NUM> corresponds to an encrypted data conversion unit, and the match determination apparatus <NUM> corresponds to a match determination unit.

The common parameter generation apparatus <NUM>, the multiple user key generation apparatuses <NUM>, the multiple encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> are computers.

In the deduplication system <NUM>, the common parameter generation apparatus <NUM>, the multiple user key generation apparatuses <NUM>, the multiple encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> are connected to a network <NUM>. The network <NUM> may be the Internet or a LAN (Local·Area·Network) installed in a corporation.

The network <NUM> is a communication channel connecting the common parameter generation apparatus <NUM>, the multiple user key generation apparatuses <NUM>, the multiple encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> with each other.

The common parameter generation apparatus <NUM> creates a common parameter for use in the deduplication system <NUM> and transmits the common parameter to the multiple user key generation apparatuses <NUM>, the multiple encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, and the tag conversion apparatus <NUM> over the network <NUM>. The common parameter may instead be sent directly to parties of the deduplication system <NUM> such as by postal mail without going through the network <NUM>.

Each user key generation apparatus <NUM> generates a user key and transmits the user key to the encryption apparatus <NUM> and the conversion key generation apparatus <NUM>. Each encryption apparatus <NUM> generates an encryption tag ETag with plaintext M and the user key transmitted from the user key generation apparatus <NUM> as input and transmits the ETag to the tag conversion apparatus <NUM>. The conversion key generation apparatus <NUM> receives the user key from the user key generation apparatus <NUM> and generates a conversion key ck from the user key. The tag conversion apparatus <NUM> receives the conversion key ck from the conversion key generation apparatus <NUM> and receives the encryption tag ETag from the encryption apparatus <NUM>. The tag conversion apparatus <NUM> converts 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 apparatus <NUM> transmits the encryption tag T to the match determination apparatus <NUM>. The match determination apparatus <NUM> receives multiple encryption tags T from the tag conversion apparatus <NUM>, 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 apparatuses <NUM>, the encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, and the tag conversion apparatus <NUM>.

<FIG> is a block diagram showing a configuration of the common parameter generation apparatus <NUM>. The common parameter generation apparatus <NUM> includes an input unit <NUM>, a common parameter generation unit <NUM>, and a transmission unit <NUM>. Although not shown, the common parameter generation apparatus <NUM> includes a recording medium for storing data used in the components of the common parameter generation apparatus <NUM>. To the input unit <NUM>, a bit length k of the key used in the deduplication system <NUM> is input. The common parameter generation unit <NUM> generates a common parameter to be a basis of computations executed in the deduplication system <NUM>. Although not shown, the common parameter generation unit <NUM> may have random number generation functionality in order to generate common parameters. The transmission unit <NUM> transmits the common parameter generated by the common parameter generation unit <NUM> to the multiple user key generation apparatuses <NUM>.

<FIG> is a block diagram showing a configuration of the user key generation apparatus <NUM>. The user key generation apparatus <NUM> includes a parameter reception unit <NUM>, a key generation unit <NUM>, and a key transmission unit <NUM>. Although not shown, the user key generation apparatus <NUM> includes a recording medium for storing data used in the components of the user key generation apparatus <NUM>. The parameter reception unit <NUM> receives the common parameter. The key generation unit <NUM> generates an encryption key ek and a conversion key generation key tk. Although not shown, the key generation unit <NUM> may have random number generation functionality in order to generate these keys. The key transmission unit <NUM> transmits the encryption key ek to the encryption apparatus <NUM> and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus <NUM>.

<FIG> is a block diagram showing a configuration of the encryption apparatus <NUM>. As shown in <FIG>, the encryption apparatus <NUM> includes an input unit <NUM>, a reception unit <NUM>, a tag generation unit <NUM>, and a tag transmission unit <NUM>. Although not shown, the encryption apparatus <NUM> includes a recording medium for storing data used in the components of the encryption apparatus <NUM>. To the input unit <NUM>, the plaintext M is input. The reception unit <NUM> receives the encryption key ek. The tag generation unit <NUM> generates the encryption tag ETag. Although not shown, the tag generation unit <NUM> may have random number generation functionality in order to generate the encryption tag ETag. The tag transmission unit <NUM> transmits the encryption tag ETag generated by the tag generation unit <NUM> to the tag conversion apparatus <NUM>.

<FIG> is a block diagram showing a configuration of the conversion key generation apparatus <NUM>. The conversion key generation apparatus <NUM> includes a key reception unit <NUM>, a conversion key generation unit <NUM>, and a transmission unit <NUM>. Although not shown, the conversion key generation apparatus <NUM> includes a recording medium for storing data used in the components of the conversion key generation apparatus <NUM>. The key reception unit <NUM> receives the encryption key ek and the conversion key generation key tk. The conversion key generation unit <NUM> generates a conversion key ck from the encryption key ek and the conversion key generation key tk. Although not shown, the conversion key generation unit <NUM> may have random number generation functionality in order to generate the conversion key ck. The transmission unit <NUM> transmits the conversion key ck to the tag conversion apparatus <NUM>.

<FIG> is a block diagram showing a configuration of the tag conversion apparatus <NUM>. The tag conversion apparatus <NUM> is an encrypted data conversion apparatus.

The tag conversion apparatus <NUM> includes a reception unit <NUM>, an input unit <NUM>, a key saving unit <NUM>, a conversion unit <NUM>, and a transmission unit <NUM>. Although not shown, the tag conversion apparatus <NUM> includes a recording medium for storing data used in the components of the tag conversion apparatus <NUM>.

The reception unit <NUM> receives the conversion key ck. The input unit <NUM> receives the encryption tag ETag. The key saving unit <NUM> saves the conversion key ck. The conversion unit <NUM> converts the encryption tag ETag input at the input unit <NUM> into an encryption tag T that can be deduplicated, using the conversion key ck saved in the key saving unit <NUM>. Although not shown, the conversion unit <NUM> may have random number generation functionality in order to convert the encryption tag ETag to the encryption tag T. The transmission unit <NUM> transmits the encryption tag T, which is encrypted data that can be deduplicated, to the match determination apparatus <NUM>.

<FIG> is a block diagram showing a configuration of the match determination apparatus <NUM>. The match determination apparatus <NUM> includes a tag input unit <NUM>, a determination unit <NUM>, and a result transmission unit <NUM>. Although not shown, the match determination apparatus <NUM> includes a recording medium for storing data used in the components of the match determination apparatus <NUM>. To the tag input unit <NUM>, an encrypted encryption tag T1, which can be deduplicated, and an encrypted encryption tag T2, which can be deduplicated, are input. The determination unit <NUM> determines whether the values of the encryption tag T1 and the encryption tag T2 match. The result transmission unit <NUM> outputs a determination result on whether they match.

Operations of the individual apparatuses in the deduplication system <NUM> are now described.

<FIG> is a flowchart illustrating the operation of the common parameter generation apparatus <NUM>.

<FIG> is a flowchart illustrating the operation of the user key generation apparatus <NUM>.

<FIG> is a flowchart illustrating the operation of the encryption apparatus <NUM>. The encryption apparatus <NUM> generates an encryption tag ETag which is an encryption of the plaintext M, using the encryption key ek and the plaintext M.

<FIG> is a flowchart illustrating the operation of the conversion key generation apparatus <NUM>. The conversion key generation apparatus <NUM> generates a conversion key ck using the encryption key ek and the conversion key generation key tk.

<FIG> is a flowchart illustrating the operation of the tag conversion apparatus <NUM>. By applying the conversion key ck to the encryption tags ETag, the tag conversion apparatus <NUM> converts 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> is a flowchart illustrating the operation of the match determination apparatus <NUM>. The match determination apparatus <NUM> determines whether the values of two pieces of second encrypted data T match.

<FIG> is a diagram showing the flowcharts of <FIG> as a sequence.

Referring to <FIG>, the operations of the individual apparatuses of the deduplication system <NUM> will be described.

A general operation of the deduplication system <NUM> shown in <FIG> is as follows. The encryption apparatus <NUM> calculates an exclusive OR of the encryption key ek and the plaintext M as the encryption tag ETag. The conversion key generation apparatus <NUM> calculates 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 apparatus <NUM> converts 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.

At step S201, the bit length k is input to the input unit <NUM>.

At step S202, the common parameter generation unit <NUM> generates a k-bit random value sk as a common parameter.

At step S203, the transmission unit <NUM> transmits the bit length k and the common parameter sk to the user key generation apparatus <NUM>.

At step S301, the parameter reception unit <NUM> receives the bit length k and the common parameter sk from the common parameter generation apparatus <NUM>.

At step S302, the key generation unit <NUM> generates a k-bit random value skA as the encryption key ek. The key generation unit <NUM> also sets the conversion key generation key tk as the encryption key sk.

At step S303, the key transmission unit <NUM> transmits the encryption key ek to the encryption apparatuses <NUM> and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus <NUM>.

At step S401, the plaintext M is input to the input unit <NUM>.

At step S402, the reception unit <NUM> receives the encryption key ek from the user key generation apparatus <NUM>.

At step S403, the tag generation unit <NUM> calculates: <MAT> Here, Hash indicates a cryptographic hash function and can be SHA256, for example. <XOR> represents exclusive OR.

At step S404, the tag transmission unit <NUM> transmits the encryption tag ETag to the tag conversion apparatus <NUM>.

At step S501, the key reception unit <NUM> receives the encryption key ek and the conversion key generation key tk from the user key generation apparatus <NUM>.

At step S502, the conversion key generation unit <NUM> calculates: <MAT>.

At step S503, the transmission unit <NUM> transmits the conversion key ck to the tag conversion apparatus <NUM>.

At step S601, the reception unit <NUM> as 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 unit <NUM> as 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 unit <NUM> converts 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 system <NUM> of Embodiment <NUM>, 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 (<NUM>) 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. <MAT> is calculated.

At step S604, the transmission unit <NUM> as a transmission control unit transmits the encryption tags T to the match determination apparatus <NUM>, which determines whether the values of two encryption tags T match.

At step S701, two encryption tags T1 and T2 are input to the tag input unit <NUM>.

At step S702, the determination unit <NUM> verifies whether bit strings of the encryption tag T1 and the encryption tag T2 are equal. If the bit strings of the encryption tag T1 and the encryption tag T2 are determined to be equal by the determination unit <NUM>, the result transmission unit <NUM> outputs <NUM> at step S703, and if the bit strings of the encryption tag T1 and the encryption tag T2 are determined to be different, the result transmission unit <NUM> outputs <NUM> at step S704.

In Embodiment <NUM>, 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 <NUM>, a cryptographic system having high security can be provided without losing the convenience of deduplication.

Referring to <FIG>, the deduplication system <NUM> in Embodiment <NUM> is described. In Embodiment <NUM>, 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 <NUM>, the encryption tag ETag is generated by means of pairing computation.

The configuration of the deduplication system <NUM> is the same as <FIG> of Embodiment <NUM>. The configurations of the common parameter generation apparatus <NUM>, the user key generation apparatuses <NUM>, the encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> are also the same as <FIG> of Embodiment <NUM>.

<FIG> is a flowchart illustrating the operation of the encryption apparatus <NUM>.

<FIG> is a flowchart illustrating the operation of the conversion key generation apparatus <NUM>.

<FIG> is a flowchart illustrating the operation of the tag conversion apparatus <NUM>.

<FIG> is a flowchart illustrating the operation of the match determination apparatus <NUM>.

At step S801, the bit length k is input to the input unit <NUM>.

At step S802, based on the bit length k, the common parameter generation unit <NUM> generates an element available for pairing computation: <MAT>.

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 <MAT> holds for all g ∈ G, and a, b ∈ Zp. Computation using this e is called pairing computation.

At step S803, the transmission unit <NUM> transmits the bit length k, g, and the element BG to the user key generation apparatus <NUM>.

At step S901, the parameter reception unit <NUM> receives the bit length k, g, and BG from the common parameter generation apparatus <NUM>.

At step S902, the key generation unit <NUM> randomly selects x ∈ Zp and calculates:<MAT>.

The key generation unit <NUM> also selects Y ∈ G.

The key generation unit <NUM> sets: <MAT> and <MAT>.

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 unit <NUM> transmits the encryption key ek to the encryption apparatus <NUM> and transmits the encryption key ek and the conversion key generation key tk to the conversion key generation apparatus <NUM>.

At step S1001, the plaintext M is input to the input unit <NUM>.

At step S1002, the reception unit <NUM> receives the encryption key ek from the user key generation apparatus <NUM>.

At step S1003, the tag generation unit <NUM> calculates: <MAT> and sets: <MAT> and the encryption tag ETag.

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

At step S1004, the tag transmission unit <NUM> transmits the encryption tag ETag to the tag conversion apparatus <NUM>.

As shown in expression <NUM>, the encryption apparatus <NUM> as the encryption unit encrypts the plaintext M using the first element g and the second element y. The encryption apparatus <NUM> generates, as the ETag, data which is an encryption of the plaintext M.

At step S1101, the key reception unit <NUM> receives:.

At step S1102, the conversion key generation unit <NUM> calculates: <MAT>.

At step S1103, the transmission unit <NUM> transmits:
the conversion key ck = (ck', ek)
to the tag conversion apparatus <NUM>.

As in expression <NUM> and the expression of the conversion key ck shown above, the conversion key generation apparatus <NUM> as 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.

At step S1201, the reception unit <NUM> receives: <MAT> from the conversion key generation apparatus <NUM>.

At step S <NUM>, to the input unit <NUM>, the encryption tag: <MAT> is input.

At step S1203, the conversion unit <NUM> converts 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 system <NUM> of Embodiment <NUM>, the same values are set for different users as the g selected at step S802 and the Y selected at step S902. Thus, according to expression (<NUM>) 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 unit <NUM> calculates: <MAT> e represents a pairing computation.

At step S1204, the transmission unit <NUM> transmits the encryption tag T converted from the encryption tag ETag to the match determination apparatus <NUM>.

At step S1301, two encryption tags T1 and T2 are input to the tag input unit <NUM>.

At step S1302, the determination unit <NUM> verifies whether bit strings of the encryption tag T1 and the encryption tag T2 are equal.

At step S1302, if the bit strings of the encryption tag T1 and the encryption tag T2 are determined to be equal by the determination unit <NUM>, the result transmission unit <NUM> outputs <NUM> at step S1303, and if the bit strings of the encryption tag T1 and the encryption tag T2 are determined to be different, the result transmission unit <NUM> outputs <NUM> at step S1304.

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

<FIG> is a diagram showing a hardware configuration of the common parameter generation apparatus <NUM>, the multiple user key generation apparatuses <NUM>, the encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> in Embodiments <NUM> and <NUM>.

The common parameter generation apparatus <NUM>, the multiple user key generation apparatuses <NUM>, the encryption apparatuses <NUM>, the conversion key generation apparatus <NUM>, the tag conversion apparatus <NUM>, and the match determination apparatus <NUM> are computers. <FIG> is a hardware configuration of the common parameter generation apparatus <NUM> through the match determination apparatus <NUM>, which are computers.

As the common parameter generation apparatus <NUM> through the match determination apparatus <NUM> have the same hardware configuration, the encryption apparatus <NUM> will be described as a representative.

In <FIG>, the encryption apparatus <NUM> includes a CPU <NUM> (Central Processing Unit).

The CPU <NUM> is connected with hardware devices such as a ROM <NUM>, a RAM <NUM>, a communication board <NUM>, a display <NUM>, a keyboard <NUM>, a mouse <NUM>, a drive <NUM>, and a magnetic disk device <NUM> via a bus <NUM> and controls these hardware devices.

The drive <NUM> is 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 ROM <NUM>, the RAM <NUM>, the magnetic disk device <NUM>, and the drive <NUM> are examples of storage devices.

The keyboard <NUM>, the mouse <NUM>, and the communication board <NUM> are examples of input devices. The display <NUM> and the communication board <NUM> are examples of output devices.

The communication board <NUM> is connected with a communication network such as a LAN, the Internet, and a telephone line by wire or wirelessly.

The magnetic disk device <NUM> stores an operating system <NUM>, programs <NUM>, and files <NUM>.

In <FIG>, the operating system <NUM> is denoted as OS <NUM>.

The programs <NUM> include programs for executing those functions that are described as ". units" in Embodiments <NUM> and <NUM>.

The programs are read and executed by the CPU <NUM>.

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

The files <NUM> include 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 <NUM> and <NUM>.

The arrows included in configuration diagrams and flowcharts in Embodiments <NUM> and <NUM> mostly indicate input and output of data and signals.

Processing in Embodiments <NUM> and <NUM> described with respect to a flowchart and the like is executed using hardware such as the CPU <NUM>, a storage device, an input device, and an output device.

Those that are described as ". units" in Embodiments <NUM> and <NUM> may be ". circuits", ". devices", or ". apparatus" and may also be ". procedure", or ". That is, those that are described as ". units" may be implemented in any of firmware, software, hardware, or a combination thereof.

In the hardware configuration shown in <FIG>, the functions of the individual apparatuses are implemented in software. However, the functions of the apparatuses may also be implemented in hardware.

As with <FIG>, this will be described with the encryption apparatus <NUM> as a representative.

<FIG> shows a configuration in which the functions of the encryption apparatus <NUM> are implemented by hardware. An electronic circuit <NUM> of <FIG> is a dedicated electronic circuit for implementing the functions of the input unit <NUM>, the reception unit <NUM>, the tag generation unit <NUM>, and the tag transmission unit <NUM> of the encryption apparatus <NUM>. The electronic circuit <NUM> is connected to a signal line <NUM>. The electronic circuit <NUM> is 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 apparatus <NUM> may 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 apparatus <NUM> may be implemented by an electronic circuit and the remaining functions may be implemented by software.

Each of the CPU <NUM> and the electronic circuit <NUM> is also called processing circuitry. In the encryption apparatus <NUM>, the functions of the input unit <NUM>, the reception unit <NUM>, the tag generation unit <NUM>, and the tag transmission unit <NUM> may be implemented by processing circuitry. Alternatively, the functions of the ". units" shown in <FIG> may be implemented by processing circuitry.

Claim 1:
A cryptographic system (<NUM>) comprising:
an encryption unit (<NUM>) to generate first encrypted data (ETag) by calculating an exclusive OR using any first key (ek) of a plurality of first keys and a hash value of a plaintext (M), so that the first encrypted data (ETag) is data which is an encryption of the plaintext (M) and is data that has a different value even with the same plaintext (M) when a value of the first key (ek) used in encryption is different;
a third key generation unit (<NUM>) to generate a third key (ck) by calculating an exclusive OR of the first key (ek) used in the encryption of the plaintext (M) and a second key (tk) which is a k-bit random value; and
an encrypted data conversion unit (<NUM>) to convert the first encrypted data (ETag) for which the same plaintext (M) has been used into second encrypted data (T);
characterized in that
the encrypted data conversion unit (<NUM>) is configured to convert the first encrypted data (ETag) into the second encrypted data (T) by calculating an exclusive OR using the third key (ck) and the first encrypted data (ETag) so that the second encrypted data (T) takes the same value regardless of the value of the first key (ek) used in the encryption of the first encrypted data (ETag)
and in that the cryptographic system (<NUM>) includes a match determination unit (<NUM>) to determine whether values of two pieces of the second encrypted data (T), which can be deduplicated, match.