The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed
in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and
access to the full text.
On the second hand, it deals with Ph.D. subjects
currently under investigation. This way, we provide a timely
map of contemporary research in cryptology.
All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.
Constantin Catalin Dragan (#981)
Constantin Catalin Dragan
Topic of his/her doctorate.
Security of CRT-based Secret Sharing Schemes
Secret Sharing Schemes, Chinese Remainder Theorem, (Shannon) Entropy, (Asymptotic) Perfectness, (Asymptotic) Idealness, Perfect Zero-Knowledge
Year of completion
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.
In 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 and perfect zero-knowledge, no matter the sequences of co-primes used. The information rate of the Mignotte scheme asymptotically goes to 0.
We also consider the construction of a CRT-based scheme, called
distributive weighted threshold secret sharing scheme, that satisfy the asymptotic perfectness and perfect zero-knowledge properties. As the scheme allows for the share spaces to be arbitrarily large compared to the secret space, the scheme can not be asymptotically ideal.
constantin.dragan (at) info.uaic.ro