KR101967521B1 - Broadcast encryption and decryption method based on subset difference - Google Patents

Abstract

A subset difference based broadcast encryption and decryption method is disclosed. The broadcast encryption method includes generating a public key and a secret key for each of a plurality of second devices, generating a subset difference based encryption key using the public key, and generating the subset difference based. And encrypting and broadcasting a message using an encryption key, wherein the subset difference-based encryption key includes a public key corresponding to an identifier of a device group included in a message transmission target among a plurality of second devices, and a device included in the message. A public key corresponding to an identifier of a device group to be excluded from the group is generated.

Description

Broadcast encryption and decryption method based on subset difference}

The present invention relates to a subset difference based broadcast encryption and decryption method.

Broadcast encryption is an encryption method for securely transmitting a message to a group of recipients, and only certain users can decrypt the received message. Application examples include pay TV and digital rights management (DRM).

Numerous broadcast encryption methods with different features have been introduced. Broadcast encryption methods include a symmetric key setting method and a public key setting method.

The public key based broadcast encryption method allows anyone to broadcast a message to a changing set of authorized users using the public key. On the other hand, in the secret key broadcast encryption method, only a specific center that knows the secret key can broadcast the message. The broadcast encryption method may be stateful or stateless based. Stateful broadcast encryption methods can sometimes update a user's private key, while stateless broadcast encryption methods allow a user's private key to remain the same for the life of the system. Security can be defined against enemies who conspire in whole or in part. Broadcast encryption methods can be aggregated into revocation and traitor-tracing algorithms. This algorithm may support an identity based public key scheme and / or forward security.

In the broadcast encryption method, the message format is generally represented by (S, Hdr, C _M ). Where S represents a group of users, Hdr is a header, and C _M is the ciphertext of the original message. The sender generates the ciphertext C _M of the message M with the session key K _s , calculates Hdr with S and K _s , and sends (S, Hdr, C _M ). For decryption, a particular user decrypts the cipher text by calculating K _s from the secret key and the header. However, excluded users cannot deduce K _s from their personal information. Moreover, K _s cannot be calculated even if all excluded users collude.

In the broadcast encryption method, header length, secret key / public key size, and encryption / decryption time are important factors. These elements are ideal as small as possible, but in most broadcast encryption methods, reducing one element increases the other. In broadcast encryption, where a message is sent to a large number of recipients, it is important to minimize the header length along with the actual computation cost and storage medium size.

In this regard, as a prior document, "Revocation and tracing schemes for stateless receivers, Dalit Naor, Moni Naor, and Jeffery Lotspiech." (Hereinafter referred to as Document 1), "Public Key Broadcast Encryption for Stateless Receivers, Y. Dodis and N. Fazio. " (Hereinafter referred to as Prior Art 2), "Hierarchical identity based encryption with constant size ciphertext, Dan Boneh, Xavier Boyen, and Eu-Jin Goh." (Hereinafter referred to as Priority 3), "Collusion resistant broadcast encryption with short ciphertexts and private keys, Dan Boneh, Craig Gentry, and Brent Waters." (Hereinafter referred to as Document 4) and "Public-Key Revocation and Tracing Schemes with Subset Difference Methods Revisited, Kwangsu Lee, Woo Kwon Koo, Dong Hoon Lee, Jong Hwan Park." (Hereinafter referred to as Prior Document 5) is disclosed.

Assuming that there are a total of N devices and r devices are excluded from broadcast decryption, Prior Art 1 is a symmetric key-based broadcast encryption scheme, where the shared keys are O (1), and the private keys stored in the devices O ((log N) ² ). The decryption time is O (log N) and the ciphertext is O (r).

The combination of Prior Art 2 and Prior Art 3 becomes a public key based broadcast encryption technique. In this technique, the size of the public key is O (log N) and the size of the secret key is O ((log N) ³ ). The decryption time is O (log N) and the ciphertext is O (r).

Prior Art 4 discloses a public key-based broadcast encryption scheme in which the size of the public key is O (N) and the size of the secret key is O ((log N) ² ). The decryption time is O (1) and the ciphertext is O (r).

Prior art 5 has a public key size of O (1) and a private key size of O ((log N) ² ). The decryption time is O (1) and the ciphertext is O (r).

Compared with the conventional broadcast encryption method, there is a need for a broadcast encryption method that reduces the size of a cipher text, the size of a secret key / public key, or an encryption / decryption time while increasing the other elements.

The present invention relates to a subset difference-based broadcast encryption and decryption method that can reduce the size of a secret key to O (log N), while maintaining the size of the ciphertext as O (r) as before.

According to an aspect of the present invention, a broadcast encryption method is disclosed in which a first device performs to transmit a message to at least one specific device of a plurality of second devices.

In a broadcast encryption method according to an embodiment of the present invention, generating a public key and a secret key for each of the plurality of second devices, and generating a subset difference based encryption key using the public key. And encrypting and broadcasting a message using the generated subset difference-based encryption key, wherein the subset difference-based encryption key is a device included in a message transmission target among the plurality of second devices. A public key corresponding to an identifier of a group and a public key corresponding to an identifier of a device group excluded from the included device group are generated.

The identifier is represented using a Boolean representation.

The private key includes an included public key corresponding to the identifier of the second device and a excluded public key, and multiplies the included public key by a random value R selected for the corresponding device, and the excluded public key. It is generated by multiplying the inverse of the random value (R ^-1 ).

The device group composed of the specific device is represented by an identifier pair including a first bit value and a second bit value, wherein the first bit value is an identifier of the included device group, and the second bit value is excluded. Identifier of the device group.

According to another aspect of the present invention, there is disclosed a broadcast decryption method performed by a second device receiving an encrypted message broadcasted by a first device to transmit a message to at least one specific device of a plurality of second devices. do.

In the broadcast decryption method according to an embodiment of the present invention, storing the secret key and the public key generated by the first device, using the received encryption message and the stored secret and public key, the first device Generating a second subset difference based encryption key that is identical to the first subset difference based encryption key generated by the user; and decrypting the encrypted message using the generated second subset difference based encryption key; The second subset difference based encryption key is generated by calculating a public key constituting the first subset difference based encryption key from the stored secret key and the public key.

The first subset difference-based encryption key corresponds to a first public key corresponding to an identifier of a device group included in a message transmission target among the plurality of second devices and an identifier of a device group excluded from the included device group. It consists of a second public key.

The private key includes an included public key corresponding to the identifier of the second device and a excluded public key, and multiplies the included public key by a random value R selected for the corresponding device, and the excluded public key. It is generated by multiplying the inverse of the random value (R ^-1 ).

The generating of the second subset difference-based encryption key may include multiplying the random value R by the included public key and the excluded public key by the inverse of the random value R ⁻¹ . The first public key and the second public key are calculated from the secret key by multiplying and erasing the random value R and the inverse R- ¹ of the random value.

The subset difference-based broadcast encryption and decryption method according to an embodiment of the present invention can reduce the size of the secret key to O (log N) smaller than before while maintaining the size of the ciphertext as O (r). have.

1 is a diagram schematically illustrating a configuration of a broadcast system according to an embodiment of the present invention.
2 is a flowchart illustrating a subset difference based broadcast encryption method according to an embodiment of the present invention.
3 is a flowchart illustrating a subset difference based broadcast decoding method according to an embodiment of the present invention.

As used herein, the singular forms "a", "an" and "the" include plural forms unless the context clearly indicates otherwise. In this specification, terms such as “consisting of” or “comprising” should not be construed as necessarily including all of the various components or steps described in the specification, and some of the components or some steps It should be construed that it may not be included or may further include additional components or steps. In addition, the terms "... unit", "module", etc. described in the specification mean a unit for processing at least one function or operation, which may be implemented in hardware or software or a combination of hardware and software. .

Hereinafter, various embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a diagram schematically illustrating a configuration of a broadcast system according to an embodiment of the present invention.

Referring to FIG. 1, the broadcast system 100 according to an exemplary embodiment of the present invention may receive a first device 110 transmitting a message through broadcasting and a plurality of broadcast messages received from the first device 110. The second device 120.

That is, since the broadcast system 100 according to the embodiment of the present invention uses a public encryption-based broadcast encryption and decryption technique, all devices constituting the broadcast system 100 transmit and receive messages in a broadcast manner. can do. However, for convenience of understanding and explanation, as described above, a device operating as a transmitting node will be referred to as a first device 110 and a device operating as a receiving node as a second device 120.

Referring back to FIG. 1, the first device 110 transmits a message to a specific device 130 among a plurality of second devices 120, according to a subset difference-based broadcast encryption method according to an embodiment of the present invention. To broadcast the encrypted message.

In addition, the specific device 130 that receives the encrypted message broadcast by the first device 110 may decrypt the encrypted message by performing a subset difference based broadcast decryption method according to an embodiment of the present invention. .

A broadcast encryption method performed by the first device 110 and a broadcast decryption method performed by the second device 120 will be described below with reference to FIGS. 2 and 3.

2 is a flowchart illustrating a subset difference based broadcast encryption method according to an embodiment of the present invention.

In operation S210, the first device 110 generates a public key PK and a secret key SK _ID for each of the plurality of second devices 120.

가 생성된다. 여기서,

는 비트 사이즈 θ(λ)의 프라임 오더(prime order) p에 대한 바이리니어 그룹이다. 그리고, 랜덤 엘리먼트(random element) g ∈

가 선택되고, 랜덤 지수(random exponent)

(

는 랜덤값인 p에 대한 잉여계)가 선택된다. 그리고, O(l)개의 랜덤 그룹 엘리먼트(random group elements) h_1,0, h_1,1, …, h_l,0, h_l,1, k_1,0, k_1,1, …, k_l,0, k_l,1 ∈

가 선택된다. 그래서, 마스터키 MK = g^α와 하기 수학식 1의 공개키가 산출된다.First, a bilinear group

Is generated. here,

Is a bilinear group for the prime order p of the bit size θ (λ). And random element g ∈

Is selected and a random exponent

(

Is a surplus system for p, which is a random value. And O (l) random group elements h _1,0 , h ₁ , _{1 ,.} , h _{l, 0} , h _{l, 1} , k _1,0 , k _1,1 ,... , k _{l, 0} , k _{l, 1} ∈

Is selected. Thus, the master key MK = g ^α and the public key of the following equation (1) are calculated.

가 선택되고, 비밀키(SK_ID)가 하기 수학식 2와 같이 산출된다.The secret key is generated using an identifier (ID), a master key (MK) and a public key (PK). That is, the random indices α _ω and r ∈

Is selected, and the secret key SK _ID is calculated as shown in Equation 2 below.

이다.here,

to be.

For example, the first device 110 may generate a public key PK defined as in Equation 3 below.

Where d represents the number of public keys. Assuming that the number of the plurality of second devices 120 is N, the number of public keys d = log N.

The secret key SK _ID is generated using a public key corresponding to the identifier ID of each of the second devices 120.

Here, each identifier ID may be represented using a Boolean representation. That is, the identifier may be represented by a bit value including d bits, such as ID = (b ₁ ... b _d ).

For example, assuming eight second devices 120, the number of public keys d is three. In this case, identifiers of the eight second devices 120 may be 000, 001, 010, 011, 100, 101, 110, and 111.

Hereinafter, for convenience of understanding and explanation of the present invention, it will be described on the assumption that the number of the plurality of second devices 120 is eight.

When the number of the plurality of second devices 120 is 8, the public key may be represented by Equation 4 below.

The public key corresponding to the identifier ID may be represented by Equation 5 below.

The secret key (SK _ID ) is composed of an included public key corresponding to the identifier (ID) and the excluded public key, multiplying the public key included by the random value (R) selected for the device, and excluded public key Is generated by multiplying the inverse of the random value (R ^-1 ) by.

For example, the secret key SK ₀₀₁ of the second device 120 having an identifier of ID = 001 among the eight second devices 120 may be represented by Equation 6 below.

In operation S220, the first device 110 generates a subset difference based encryption key using the public key PK.

For example, the subset difference-based encryption key corresponds to a public key corresponding to an identifier of a device group included in a message transmission target among the plurality of second devices 120 and an identifier of a device group excluded from the included device group. Can be generated with a public key.

The device group composed of the specific device 130 is represented by an identifier pair, and the identifier pair may include a first bit value and a second bit value. Here, the first bit value is a bit value representing an identifier of some devices of the second device 120, and the second bit value is a bit value representing an identifier of a device excluded from some devices represented by the first bit value. Can be.

In more detail, each of the first bit value and the second bit value includes d bits similar to the bit value corresponding to the identifier of the second device 120, and each of the d bits constituting the bit value is 0, It can have one of 1 and *. At this time, * may be a value including both 0 and 1.

For example, if the identifier of each of the eight second devices 120 is expressed as a bit value including three bits, 000 (node 1), 001 (node 2), 010 (node 3), and 011 ( Nodes 4), 100 (node 5), 101 (node 6), 110 (node 7), and 111 (node 8), where a particular device 130 is capable of receiving and decrypting the broadcast encrypted message. , Assume node 4 and node 6. In this case, the device group composed of the specific device 130 may be represented by the identifier pair (** 1, 111). Here, ** 1 represents an identifier of a device group included as a first bit value, and 111 represents an identifier of a device group to be excluded as a second bit value. That is, ** 1 represents 001 (node 2), 011 (node 4), 101 (node 6), and 111 (node 8), except for ** 1 to 111 (node 8), the specific device 130 The device group may consist of 001 (node 2), 011 (node 4), and 101 (node 6).

The device group constituted of the specific device 130 has a public key corresponding to the identifier pair (** 1, 111), which is the public key included (h _1,0 h _1,1 h _2,0 h _2,1 h _3,1 ) and the excluded public key (k _1,1 k _2,1 k _3,1 ).

Accordingly, the subset difference-based encryption key corresponds to the identifier of the included device group, which is a public key corresponding to the identifier pair (** 1, 111) consisting of the identifier of the included device group and the identifier of the excluded device group. The public key (k _1,1 k _2,1 k _3,1) corresponding to the public key (h _1,0 h _1,1 h _2,0 h _2,1 h _3,1 ) Can be generated). That is, the subset difference-based encryption key may be composed of a public key corresponding to the identifier of the included device group and a public key corresponding to the identifier of the excluded device group.

In operation S230, the first device 110 encrypts and broadcasts a message using the generated subset difference-based encryption key.

_T) 및 공개키(PK)를 이용하여 수행된다. 랜덤 지수 t ∈

가 선택되고, 암시적으로 (GL, ML)이 포함된 암호문(ciphertext)이 하기 수학식 7과 같이 산출된다.That is, message encryption using a subset difference-based encryption key includes labels (GL, ML) and messages (M ∈).

_T ) and public key (PK). Random exponent t ∈

Is selected, and a ciphertext implicitly including (GL, ML) is calculated as in Equation 7 below.

이다.here,

to be.

3 is a flowchart illustrating a subset difference based broadcast decoding method according to an embodiment of the present invention.

In operation S310, the plurality of second devices 120 receives an encryption message broadcast by the first device 110.

In operation S320, the plurality of second devices 120 generates a subset difference-based encryption key by using the received encryption message, a previously stored secret key, and a public key as the encryption message is received. As described above, the secret key and the public key are generated by the first device 110, and each of the plurality of second devices 120 may receive the public key and the private key from the first device 110 and store them in advance. have.

That is, the plurality of second devices 120 calculates a public key constituting the subset difference-based encryption key used for encrypting the encrypted message, so that the plurality of second devices 120 share the subset difference-based encryption key generated by the first device 110. Can be generated.

Of course, only a specific device 130 among the plurality of second devices 120 may generate the same subset-based encryption key generated by the first device 110.

For example, the subset difference-based encryption key generated by the first device 110 is the public key corresponding to the identifier of the device group to be included, which is the public key corresponding to the identifier pair (** 1, 111). Suppose it was created with a public key (k _1,1 k _2,1 k _3,1 ) corresponding to _1,0 h _1,1 h _2,0 h _2,1 h _3,1 ) and an identifier of the device group to be excluded. In this case, the second device 120 having an identifier of ID = 001 among the eight second devices 120 becomes the specific device 130. The specific device 130 having the identifier of ID = 001 has a secret key as shown in Equation (4). The specific device 130 having an identifier of ID = 001 uses the secret key and the public key of Equation 4 to equalize the subset difference-based encryption key generated by the first device 110 as shown in Equation 5 below. Can be generated.

That is, the specific device 130 having an identifier of ID = 001 may perform a multiplication operation on the random value R multiplied by the included public key and the inverse R ⁻¹ of the random value multiplied by the excluded public key. By erasing, the public key corresponding to the identifier of the device group constituting the subset difference-based encryption key generated by the first device 110 and the public key corresponding to the identifier of the excluded device group can be calculated from its private key. Can be.

On the other hand, the second device 120 rather than the specific device 130 having an identifier of ID = 111 has a secret key as shown in Equation 6 below.

The second device 120 having an identifier of ID = 111 erases a random value R multiplied by the included public key and an inverse R ^-1 of the random value multiplied by the excluded public key by a multiplication operation. In order to do so, at least one of the excluded public keys k _1,1 k _2,1 k _3,1 of the subset difference-based encryption key generated by the first device 110 must be provided as a secret key. However, as shown in Equation 6 representing the secret key of the second device 120 having the identifier of ID = 111, the second device 120 having the identifier of ID = 111 has R ⁻¹ · k _{1, 1} ,. _{^{R -1 · k 2,1, R -1}} · k 3, does not have at least one secret key of the _first. Accordingly, the second device 120, not the specific device 130, erases the inverse R- ¹ of the random value multiplied by the excluded public key and the random value R multiplied by the included public key. Since the public key constituting the subset difference-based encryption key generated by the first device 110 cannot be calculated from its secret key, the subset difference-based encryption key generated by the first device 110 cannot be generated. .

In operation S230, the first device 110 decrypts the encrypted message using the generated subset difference based encryption key.

과

이 계산되고, 복화화된 메시지는 하기 수학식 10과 같이 산출된다.That is, decryption of the encrypted message is performed using a ciphertext (CT _{(GL, ML)} ), a secret key (SK _ID ), and a public key (PK). Assume d is the number of bits in an ID different from ML. If d> 0,

and

The calculated and complexed message is calculated as shown in Equation 10 below.

The accuracy can be verified by the following equation (11).

이고,here,

ego,

이고,

ego,

이다.

to be.

On the other hand, the components of the above-described embodiment can be easily identified from a process point of view. That is, each component can be identified as a respective process. In addition, the process of the above-described embodiment can be easily understood in terms of the components of the apparatus.

In addition, the technical contents described above may be embodied in the form of program instructions that may be executed by various computer means and may be recorded in a computer readable medium. The computer readable medium may include program instructions, data files, data structures, etc. alone or in combination. Program instructions recorded on the media may be those specially designed and constructed for the purposes of the embodiments, or they may be of the kind well-known and available to those having skill in the computer software arts. Examples of computer-readable recording media include magnetic media such as hard disks, floppy disks, and magnetic tape, optical media such as CD-ROMs, DVDs, and magnetic disks, such as floppy disks. Magneto-optical media, and hardware devices specifically configured to store and execute program instructions, such as ROM, RAM, flash memory, and the like. Examples of program instructions include not only machine code generated by a compiler, but also high-level language code that can be executed by a computer using an interpreter or the like. The hardware device may be configured to operate as one or more software modules to perform the operations of the embodiments, and vice versa.

The embodiments of the present invention described above are disclosed for purposes of illustration, and those skilled in the art having ordinary knowledge of the present invention may make various modifications, changes, and additions within the spirit and scope of the present invention. Should be considered to be within the scope of the following claims.

100: broadcast system
110: first device
120: second device
130: specific device

Claims (9)

A broadcast encryption method performed by a first device to transmit a message to at least one specific second device of a plurality of second devices, the method comprising:
Generating a plurality of public keys corresponding to identifiers of the second devices and a private key for each of the plurality of second devices;
Generating a subset difference based encryption key using the public keys; And
Encrypting and broadcasting a message using the generated subset difference-based encryption key,
The specific second device belongs to a device group,
The subset difference-based encryption key is a public key corresponding to an identifier of the specific second device belonging to a device group included in a message transmission target among the plurality of second devices and a second device excluded from the included device group. And a public key corresponding to the identifier of the broadcast encryption method.
The method of claim 1,
And the identifier is represented using a Boolean representation.
The method of claim 1,
The secret key is generated by using a public key corresponding to an identifier of the specific second device belonging to the device group and a public key corresponding to an identifier of the second device excluded from the device group, and corresponding second device Is generated by multiplying the included public key by the selected random value (R) and multiplying the excluded public key by the inverse (R ^-1 ) of the random value.
The method of claim 1,
The device group composed of the specific second device is represented by an identifier pair including a first bit value and a second bit value.
The first bit value is a bit value representing an identifier of a part of the specific second device, and the second bit value is a bit value representing an identifier of the remaining second device of the specific second device. Cast encryption method.
A broadcast decryption method performed by a specific second device that receives an encrypted message broadcast by a first device to transmit a message to at least one specific second device of a plurality of second devices.
Storing a plurality of public keys corresponding to identifiers of the second devices generated by the first device and secret keys for each of the plurality of second devices;
Generating a second subset difference-based encryption key that is identical to a first subset difference-based encryption key generated by the first device using the received encryption message and the stored secret keys and public keys; And
Decrypting the encrypted message using the generated second subset difference-based encryption key,
And the second subset difference-based encryption key is generated by calculating a public key constituting the first subset difference-based encryption key from the stored secret keys and the public keys.
The device of claim 5, wherein the specific second device belongs to a device group.
The first subset difference-based encryption key is excluded from the first public key and the included device group corresponding to an identifier of the specific second device belonging to a device group included in a message transmission target among the plurality of second devices. And a second public key corresponding to the identifier of the second device.
The method of claim 6,
The secret key is generated by using a first public key corresponding to the identifier of the specific second device belonging to the device group and a second public key corresponding to the identifier of the second device excluded from the device group, And a random value (R) selected for the corresponding second device by multiplying the first public key and multiplying the inverse (R ^-1 ) of the random value by the second public key.
The method of claim 7, wherein
Generating the second subset difference based encryption key,
The random value R is multiplied by the first public key and the second public key is multiplied by the inverse of the random value R- ¹ to multiply and calculate the inverse of the random value R and the random value. And erasing (R ^-1 ), thereby calculating the first public key and the second public key from the secret key.
A computer readable recording medium having recorded thereon a program for performing the method of any one of claims 1 to 8.

Images