International Association
for Cryptologic Research

Name: Constantin Catalin Dragan
Topic: Security of CRT-based Secret Sharing Schemes
Category: (no category)

Description:

The Chinese Remainder Theorem (CRT) is a very useful tool in many areas of theoretical and practical cryptography. One of these areas is the theory of threshold secret sharing schemes. A (t+1,n)-threshold secret sharing scheme is a method of partitioning a secret among n users by providing each user with a share of the secret such that any t+1 users can uniquely reconstruct the secret by pulling together their shares. Several threshold schemes based on CRT are known. These schemes use sequences of pairwise co-prime positive integers with special properties. The shares are obtained by dividing the secret or a secret-dependent quantity by the numbers in the sequence and collecting the remainders. The secret can be reconstructed by some sufficient number of shares by using CRT. It is well-known that the CRT-based threshold secret sharing schemes are not perfect (and, therefore, not ideal) but some of them are asymptotically perfect and asymptotically ideal and perfect zero-knowledge if sequences of consecutive primes are used for defining them.

\r\n\r\n

\r\nIn this thesis we introduce (k-)compact sequences of co-primes and their applications to the security of CRT-based threshold secret sharing schemes is thorough investigated. Compact sequences of co-primes may be significantly denser than sequences of consecutive primes of the same length, and their use in the construction of CRT-based threshold secret sharing schemes may lead to better security properties. Concerning the asymptotic idealness property for CRT-based threshold schemes, we have shown there exists a necessary and sufficient condition for the Goldreich-Ron-Sudan (GRS) scheme and Asmuth-Bloom scheme if and only if (1-)compact sequences of co-primes are used. Moreover, the GRS and Asmuth-Bloom schemes based on k-compact sequences of co-primes are asymptotically perfect and perfect zero-knowledge. The Mignotte scheme is far from being asymptotically perfect [...]