A Chinese Remainder Theorem Based Perfect Secret Sharing Scheme with Enhanced Secret Range Values Using Tensor Based Operations

摘要

Protecting sensitive information is an increasingly difficult task due to the advances in hardware. Brute force attacks (BFA) have been successful in accessing protected data. As BFA is a trial and error process, and a natural solution against it consists of enhancing the range of possible secret values. One of the most used cryptographic techniques to protect sensitive data is the Secret Sharing Scheme (SSS), by means of which one can protect the secret by mathematically and individually distributing it into shares over n participants. Only when a minimal quantity of t participants combine their shares the secret is revealed to all of them. Among the several applications of the Chinese Remainder Theorem (CRT), it is also used as a SSS. Although the state-of-the-art Asmuth-Bloom’s SSS is perfect in terms of secrecy, the candidate values for the secret are quite small, therefore enhancing the probability of a successful BFA, as less values are to be tested by the attacker. In this paper, we propose a new and perfect CRT based SSS based on sparse matrices. The secret is an integer that, by means of the Lehmer Code, has a bijective relationship with the permutations of the values in a vector constructed with the shares. In the proposed CRT based SSS, the secret can assume a set of values that largely outperforms the range of values obtained with the Asmuth-Bloom’s SSS. Furthermore, it is mathematically proven to be potentially unlimited. Considering for instance a set of 6 co-prime numbers under 100, the gain in secret range compared with the Asmuth-Bloom’s SSS per bits used is 10¹⁰³ higher.