Cryptology ePrint Archive: Report 2020/719

Hypercube and Cascading-based Algorithms for Secret Sharing Schemes

Shion Samadder Chaudhury and Sabyasachi Dutta and Kouichi Sakurai

Abstract: Secret sharing is a very useful way to maintain secrecy of private data when stored in a distributed way among several nodes. Two signifi cant questions in this area are 1. how to accommodate new nodes and assign shares to the new nodes, the problem becomes harder if the number of joining nodes or the access structure is not known in advance and can be (potentially) unbounded and 2. to reduce the computational complexity of secret sharing schemes. In this paper we propose two new constructions of such secret sharing schemes based on different combinatorial structures. The fi rst construction is based on generalized paths joining the opposite vertices of a hypercube which has been divided into smaller hypercubes. The second construction is a forest- based construction utilizing a dynamic data structure technique known as fractional cascading. The generalized path we call a pavement is new to this paper. Both our constructions use a new secret redistribution scheme to assign and re-assign shares to nodes. Towards the second question we show that allowing certain trade-offs, the constructions are implementable by $AC^0$ circuits which is the lowest complexity class in which secret sharing and reconstruction is possible. To the best of the knowledge of the authors, none of the similar existing schemes (evolving or dynamic) are $AC^0$ computable and this paper for the fi rst time combines the idea of hypercubes and dynamic data structures with secret sharing for preserving long-term confi dentiality of secret data.

Category / Keywords: cryptographic protocols / Hypercube, Forest, Secret Sharing, Error-Correcting Codes, AC0 Circuits

Date: received 15 Jun 2020

Contact author: chaudhury shion at gmail com,saby math@gmail com,sakurai@inf kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20200616:065752 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]