Primitive Sets in Number Fields for Absolutely Optimal Black Box Secret Sharing

Abstrakt:

A black box secret sharing scheme (BBSSS) for a threshold access structure is a linear secret sharing scheme that works for any finite abelian group. Introduced by Desmedt and Frankel, the problem has been rigourously analyzed by Cramer and Fehr.

BBSSS can be based on number fields with certain properties. The approach by Desmedt and Frankel relies on number fields with large Lenstra constant, i.e.,number fields over which a "large" invertible Vandermonde matrix exists. The best known choices for these number fields lead to BBSSS with expansion factor O(n), where n is the number if players. The expansion factor corresponds to the length of each share, i.e., the number of group elements received from the dealer by each player. The solution of Cramer and Fehr achieves expansion factor O(log n), which is asymptotically optimal. It relies on low-degree number fields over which a pair of "large" Vandermonde matrices exists whose determinants are co-prime.

We propose a new approach which aims at achieving an absolutely optimal solution. Our approach is based on low-degree number fields containing a "large primitive set." We give some experimental as well as some theoretical results.