Zigzag-decodable Codes: Constructions and Applications

Abstract

Zigzag Decodable(ZD) code, which is a new class of erasure codes is proposed. The encoding and decoding process of ZD codes can both be done in linear time, involving only XOR and bit-shift operations. It has the combination property, which implies that the code maps k source blocks into n coded blocks, and any k out of the n coded blocks allow recovery of the original k source blocks. In the thesis, we present two different constructions of ZD codes, each of which has its own characteristics in terms of the extra storage overhead.

ZD codes can be employed in data storage system. At the expense of slight extra storage overhead, the retrieval process will be highly speed up. We evaluate the encoding and decoding performance of ZD codes both analytically and experimentally, and compare it with Cauchy-RS codes, the state-of-the-art general-purpose MDS codes. Analytical results show that ZD codes have a lower time complexity than those of Cauchy-RS codes. Numerical results show that ZD codes outperform Cauchy-RS codes over a wide range of coding parameters.

Also, because of the attractive low coding complexity, ZD codes can be applied to construct secret sharing schemes. Classical secret sharing schemes usually have high computation complexity during the distribution and recovery process. We propose a ramp secret sharing scheme based on ZD codes. The scheme is shown to approach a linear ramp scheme when the secret size grows to infinity. It is conceptually easy to understand, and has low computation cost, since both its encoding and decoding algorithms are based only on the XOR and bitwise-shift operations. Performance evaluation results show that our new scheme outperforms other fast secret sharing schemes in secret recovery time when the secret size is large.

Date of Award	22 Mar 2018
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Wan SUNG (Supervisor)