Research Topics
A New Shift-Add Secret Sharing Scheme for Partial Data Protection with Parallel Zigzag Decoding
Background - Security in Distributed Storage
We target at the scenario of distributed storage, protecting the confidentiality of partial data in the presence of storage node failures. It is required that not only the original data can be reconstructed from the remaining surviving nodes, but also the data lost by a failed node can be repaired from as few nodes as possible.Â
Inspired by the zigzag-decodable secret sharing scheme, we propose a new shift-add secret sharing scheme based on the XOR and bitwise-shift operations, in which confidential data is protected by using random keys generated from non-confidential data. In contrast to conventional zigzag-decodable codes, the special structure of our proposed scheme allows the design of fast parallel algorithms for modern devices with multi-core processors, which have a linear speedup in decoding time compared with various versions of serial zigzag decoding.
Zigzag code - What and Why
Zigzag code, also known as Zigzag-decodable code, belongs to a category of codes that have the MDS property and function on a binary field using the XOR operator. It demonstrates significant promise in distributed storage and security systems due to its low decoding/encoding complexity. Additionally, it facilitates the restoration of source blocks, a beneficial feature in distributed storage applications.
A classic example of Zigzag code construction is presented here. It operates on binary fields using solely the XOR operator.
When described as a systematic code, it comprises both source message blocks and coded blocks. The coded blocks are generated by shifting and XORing the source blocks.
Integration of Parallel Computing - New Code Structure and Decoding Algorithm
The core of traditional decoding algorithms is the nested for loop. However, strong data dependencies make it infeasible to decompose the nested loop for parallel execution. The excessive synchronizations required prolong the decoding time beyond that of the original algorithm.
To address this issue, we introduced a novel zigzag code structure accompanied by serial and parallel decoding algorithms. These algorithms achieve a substantial acceleration over existing benchmarks. Notably, the parallel algorithm demonstrates a linear speedup relative to different versions of the serial zigzag decoding algorithms.
*Paper:
J. Chen, Y. Shen and C. Wan Sung, "A New Shift-Add Secret Sharing Scheme for Partial Data Protection With Parallel Zigzag Decoding," in IEEE Transactions on Information Forensics and Security, vol. 19, pp. 10221-10232, 2024, doi: 10.1109/TIFS.2024.3488498.