Traceability Codes and Their Generalizations
- PDF / 385,306 Bytes
- 12 Pages / 612 x 792 pts (letter) Page_size
- 61 Downloads / 260 Views
DING THEORY
Traceability Codes and Their Generalizations G. A. Kabatiansky Skolkovo Institute of Science and Technology, Moscow, Russia e-mail : [email protected] Received April 8, 2019; revised April 8, 2019; accepted June 18, 2019 Abstract—Codes with the identifiable “parent” property appeared as one of solutions for the broadcast encryption problem. We propose a new, more general model of such codes, give an overview of known results, and formulate some unsolved problems. Key words: broadcast encryption, secret sharing schemes, IPP schemes, separating codes. DOI: 10.1134/S0032946019030074
1. INTRODUCTION Consider the following problem: distributor D uses a broadcast channel to deliver a stream of files to M authorized users. Each of the authorized users has his personal device, a decoder, allowing him to read (play back) the files transmitted by the distributor. A possible attack on such a system by malicious users is a coalition attack when a group of malicious users (in what follows, a coalition) constructs a counterfeit decoder for further illegal distribution of the files. The goal of a coalition is to construct a counterfeit decoder such that all members of the coalition remain unknown even if D gets this counterfeit in his disposal. In turn, the distributor wants to construct a set of decoders distributed among authorized users such that in the case of a coalition attack, given a counterfeit decoder, he could correctly identify at least one member of the coalition. This problem has the following primitive but at the same time optimal solution if there are no restrictions on the coalitions (for instance, on their size). The distributor D broadcasts all files in an encrypted form, i.e., instead of a file x he transmits a file y = F (x, s0 ) obtained with the use of an encryption map F (· , ·) and a secret key s0 ∈ S0 . In general, the key s0 is changed when transmitting another file. Also, D generates M different encrypted copies g1 , . . . , gM of the key s0 using another encryption map G(· , ·), where gi = G(s0 , ki ) and ki is a personal key of the ith user, which he gets from D before the transmission starts. These M encrypted copies are appended to y, so that the transmitted sequence is y, g1 , . . . , gM . Having received this sequence, the ith user decrypts gi using his personal key ki , thus finds a secret key s0 , uses it to decrypt y, and obtains the desired file x. In order to construct a decoder capable of reading/playing back the files transmitted by D, any coalition has to put at the decoder’s disposal at least one of the personal keys of the coalition members, and therefore D can reveal at least one member of the coalition. An obvious drawback of this solution is large redundancy, since together with y (as a rule, encryption does not increase the file size) D must also transmit M encrypted copies g1 , . . . , gM of the key s0 . In [1], the following solution was proposed, which allows to reduce the redundancy to ct log M given that the coalition size is at most t. The solution is based on perfect s
Data Loading...
