Tracing traitors

We give cryptographic schemes that help trace the source of leaks when sensitive or proprietary data is made available to a large set of parties. A very relevant application is in the context of pay television, where only paying customers should be able to view certain programs. In this application, the programs are normally encrypted, and then the sensitive data is the decryption keys that are given to paying customers. If a pirate decoder is found, it is desirable to reveal the source of its decryption keys. We describe fully resilient schemes which can be used against any decoder which decrypts with nonnegligible probability. Since there is typically little demand for decoders which decrypt only a small fraction of the transmissions (even if it is nonnegligible), we further introduce threshold tracing schemes which can only be used against decoders which succeed in decryption with probability greater than some threshold. Threshold schemes are considerably more efficient than fully resilient schemes     

一种基于随机序列的公钥叛逆者追踪方案

基于离散对数困难问题,利用随机序列提出一种公钥叛逆者追踪方案。该方案采用多项式与过滤函数来构建,当缴获盗版解码器时,只需通过一次输入输出即可确定叛逆者。若需要撤销或恢复多个叛逆者时,其能在不更新其他合法用户私钥的前提下,实现完全撤销多个叛逆者或完全恢复已撤销用户。性能分析证明,该方案不仅存储、计算和通信开销低,还具有完全抗共谋性、完全撤销性与完全恢复性以及黑盒追踪的特点。     

Dynamic Traitor Tracing

Traitor tracing schemes were introduced to combat the typical piracy scenario whereby pirate decoders (or access control smartcards) are manufactured and sold by pirates to illegal subscribers. Those traitor tracing schemes, however, are ineffective for the currently less common scenario where a pirate publishes the periodical access control keys on the Internet or, alternatively, simply rebroadcasts the content via an independent pirate network. This new piracy scenario may become especially attractive (to pirates) in the context of broadband multicast over the Internet. In this paper we consider the consequences of this type of piracy and offer countermeasures. We introduce the concept of dynamic traitor tracing which is a practical and efficient tool to combat this type of piracy. Received December 1999 and revised November 2000 Online publication 9 April 2001     

Low Bandwidth Dynamic Traitor Tracing Schemes

Dynamic traitor tracing schemes were introduced by Fiat and Tassa in order to combat piracy in active broadcast scenarios. In such settings the data provider supplies access control keys to its legal customers on a periodical basis. A number of users may collude in order to publish those keys via the Internet or any other network. Dynamic traitor tracing schemes rely on the feedback from the pirate network in order to modify their key allocation until they are able either to incriminate and disconnect all traitors or force them to stop their illegal activity. Those schemes are deterministic in the sense that incrimination is always certain. As such deterministic schemes must multiply the critical data by at least p + 1, where p is the number of traitors, they may impose a too large toll on bandwidth. We suggest here probabilistic schemes that enable one to trace all traitors with almost certainty, where the critical data is multiplied by two, regardless of the number of traitors. These techniques are obtained by combining dynamic traitor tracing schemes with binary fingerprinting techniques, such as those proposed by Boneh and Shaw.     

Broadcast encryption schemes based on RSA

Three broadcast schemes for small receiver set using the property of RSA modulus are presented. They can solve the problem of data redundancy when the size of receiver set is small. In the proposed schemes, the center uses one key to encrypt the message and can revoke authorization conveniently. Every authorized user only needs to store one decryption key of a constant size. Among these three schemes, the first one has indistinguishability against adaptive chosen ciphertext attack (IND-CCA2) secure, and any collusion of authorized users cannot produce a new decryption key but the sizes of encryption modulus and ciphertext are linear in the number of receivers. In the second scheme, the size of ciphertext is half of the first one and any two authorized users can produce a new decryption key, but the center can identify them using the traitor tracing algorithm. The third one is the most efficient but the center cannot identify the traitors exactly.     

适应性安全的可追踪叛徒的基于属性加密方案

针对基于属性加密(ABE, attribute-base encryption)机制存在的密钥滥用问题,为每个用户增加唯一的身份标识符,将联合安全编码和叛徒追踪机制引入到ABE方案中,给出适应性安全的可追踪叛徒ABE的定义、安全模型和可追踪模型,提出一种适应性安全的可追踪叛徒的ABTT方案,该方案允许适应性追踪指定策略盗版解码器中的叛徒。基于合数阶群上的子群判定假设和DDH假设,证明所提方案是适应性安全和适应性可追踪的。因此,所提方案不仅可以适应性追查指定策略盗版解码器中的叛徒,而且进一步增强了ABE系统的安全性,具有一定的理论和应用价值。     

可证安全的基于证书广播加密方案

广播加密可使发送者选取任意用户集合进行广播加密,只有授权用户才能够解密密文.但是其安全性依赖广播中心产生和颁布群成员的解密密钥.针对这一问题,本文提出基于证书广播加密的概念,给出了基于证书广播加密的形式化定义和安全模型.结合基于证书公钥加密算法的思想,构造了一个高效的基于证书广播加密方案,并证明了方案的安全性.在方案中,用户私钥由用户自己选取,证书由认证中心产生,解密密钥由用户私钥和证书两部分组成,克服了密钥托管的问题.在方案中,广播加密算法中的双线性对运算可以进行预计算,仅在解密时做一次双线性对运算,提高了计算效率.     

Traitor tracing over YouTube video service—proof of concept

The development explained in this article proves that is possible to trace dishonest users who upload videos with sensitive content to the YouTube service. To achieve tracing these traitor users, fingerprint marks are embedded by a watermarking algorithm into each copy of the video before distributing it. Our experiments show that if the watermarking algorithm is carefully configured and the fingerprints are correctly chosen, the traitor, or a member of a set of traitors who have performed a collusion attack, can be found from a pirate video uploaded to the YouTube service.     

面向多服务的基于大整数分解困难问题的叛逆者追踪方案

该文提出了一种面向多服务的基于大整数分解困难问题的叛逆者追踪方案。该方案的主要思想是基于大整数分解困难问题构造等式,并引进参数传递服务密钥,解密时利用上述等式和服务密钥可获得会话密钥。与现有两种方案相比,新方案具有多服务、黑盒追踪、密文长度是常量、增加用户或撤销用户以及前向安全性和后向安全性等优点,整体性能好于现有两种方案。     

New VLSI architectures for fast soft-decision threshold decoders

New VLSI architectures for fast convolutional threshold decoders that process soft-quantized channel symbols are presented. The new architectures feature pipelining and parallelism and make it possible to fabricate decoders for data rates up to hundreds of Mbits per second. With these architectures, the data rate is shown to be independent of the memory of the code, implying that fast AAPP (approximate a posteriori probability) decoders can be built for long powerful codes. Furthermore, the architectures are convenient to use with low and high coding rates. Using a typical example it is shown that a soft-decision threshold decoder can provide a substantial coding gain while being less costly to implement than the hard-decision threshold decoder     

MPEG Reconfigurable Video Coding: From specification to a reconfigurable implementation

This paper demonstrates that it is possible to produce automatic, reconfigurable, and portable implementations of multimedia decoders onto platforms with the help of the MPEG Reconfigurable Video Coding (RVC) standard. MPEG RVC is a new formalism standardized by the MPEG consortium used to specify multimedia decoders. It produces visual representations of decoder reference software, with the help of graphs that connect several coding tools from MPEG standards. The approach developed in this paper draws on Dataflow Process Networks to produce a Minimal and Canonical Representation (MCR) of MPEG RVC specifications. The MCR makes it possible to form automatic and reconfigurable implementations of decoders which can match any actual platforms. The contribution is demonstrated on one case study where a generic decoder needs to process a multimedia content with the help of the RVC specification of the decoder required to process it. The overall approach is tested on two decoders from MPEG, namely MPEG-4 part 2 Simple Profile and MPEG-4 part 10 Constrained Baseline Profile. The results validate the following benefits on the MCR of decoders: compact representation, low overhead induced by its compilation, reconfiguration and multi-core abilities.     

一种完整的非对称公钥叛逆者追踪方案

利用不经意多项式估值协议,该文提出了一种新的非对称公钥叛逆者追踪方案。当参与共谋的叛逆者数量不超过预先设置的范围时,与现有的非对称公钥追踪方案相比,该方案能够以完全的黑盒子追踪方式准确地确定出全部叛逆者;借助于密钥更新,该方案具有完善的撤销性,能够撤销任意数量的叛逆者。此外,与已有方案相比该方案显著降低了追踪时的计算量并且有着更高的传输效率。     

A 0.18-$muhbox m$CMOS Analog Min-Sum Iterative Decoder for a (32,8) Low-Density Parity-Check (LDPC) Code

Current-mode circuits are presented for implementing analog min-sum (MS) iterative decoders. These decoders are used to efficiently decode the best known error correcting codes such as low-density parity-check (LDPC) codes and turbo codes. The proposed circuits are devised based on current mirrors, and thus, in any fabrication technology that accurate current mirrors can be designed, analog MS decoders can be implemented. The functionality of the proposed circuits is verified by implementing an analog MS decoder for a (32,8) LDPC code in a 0.18-mum CMOS technology. This decoder is the first reported analog MS decoder. For low signal to noise ratios where the circuit imperfections are dominated by the noise of the channel, the measured error correcting performance of this chip in steady-state condition surpasses that of the conventional floating-point discrete-time synchronous MS decoder. When data throughput is 6 Mb/s, loss in the coding gain compared to the conventional MS decoder at BER of 10^-3 is about 0.3 dB and power consumption is about 5 mW. This is the first time that an analog decoder has been successfully tested for an LDPC code, though a short one     

High-speed decoder of Reed-Solomon codes

A high speed decoding algorithm using a modified step-by-step method for t-error-correcting Reed-Solomon codes is introduced. Based on this algorithm, a sequential decoder and a vector decoder are then proposed. These two decoders can be constructed by four basic modules: the syndrome calculation module, the comparison module, the decision module, and the shift-control module. These decoders can be applied for both binary and nonbinary data transmissions working at high data rate. Because of the simplicity in structure and circuit realization, a decoder employing this algorithm can be easily implemented in a monolithic chip by the VLSI technology     

一个高效的基于M序列的叛逆者追踪方案

文中提出一种基于M序列的叛逆追踪方案.在该方案中,当发现盗版的解密盒时,能够以黑盒子的追踪方式至少追踪到一个制造盗版解密盒的用户(称为叛徒).该方案的一个非常重要的特点是:当发现盗版的解密盒时,追踪的次数是与用户个数之间成线性关系的.因此,追踪算法的效率非常高.此外,追踪算法的实现不受共谋用户个数的限制.     

Current polarity switching decoders for Josephson memory arrays

Two new types of Josephson decoder circuits have been devised, designed, fabricated, and tested. The circuits utilize current polarities along address loops as information. This results in simple circuit configurations with about half the number of circuit gates than conventional Josephson decoder circuits. This contributes to improved yield rates and to a decrease in circuit area. One of the two decoder circuitsz described in this paper can be operated with either dc or unipole while the other is unipole only. Using computer simulation, the operating speed for the former 5-32 decoder circuit is about 320 ps which is almost the same as that of conventional decoders, while for the latter circuit it is 115 ps which is almost half of that for the conventional decoders. The decoders are designed with operating margins of over ±35 percent which is sufficient for Josephson circuits. Critical path subsections of these two 5-32 decoder circuits were fabricated by standard lead-alloy technology and quasi-staticaUy operated successfully.     

Modified majority-logic decoders for use in convolutionally encodedhybrid-ARQ systems

A method is demonstrated for modifying majority-logic convolutional decoders fur use in type-1 hybrid-ARQ protocols. Majority-logic decoders generate reliability information in the form of orthogonal sets of parity check sums. The modified decoder uses this information to identify received packets whose decoded data may be unreliable and to request their retransmission     

一种新的非对称公钥叛逆者追踪方案

应用不经意多项式估值协议构造了一种非对称的公钥叛逆者追踪方案。该方案具有无需任何可信方和不泄漏用户敏感信息(如信用卡号码或数字签字密钥)的非对称追踪能力,以及自身强化性、直接不可否认性、防诬陷性等特性。更重要的是,数据供应商能够动态地撤销或恢复某个叛逆者解密密钥的解密权限,而无需更新其他用户的解密密钥。     

Traceable attribute-based encryption scheme with key-delegation abuse resistance

Aiming at the problem that the traceability of a traceable attribute-based encryption (ABE) scheme was not sufficient to address the key abuse completely,a traceable ABE scheme against key-delegation abuse was proposed.A secret parameter was be shared to all user private key components corresponding to attributes,and the decryption was completed by using all these components together,such that only parts of them could not realize the decryption and the real key-delegation abuse resistance ability was be obtained consequently.A short signature technique was employed to prevent the tracing parameter embedded in a user private key from being forged,so as to achieve the traceability of the user who leaked his user private key.Supporting both key-delegation abuse resistance and user tracing enhances the security of the proposed scheme.And compared with related schemes,the proposed scheme has better advantage in terms of the parameters size and the computation cost.     

Low-floor decoders for LDPC codes

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code?s Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.