On some generalizations of Shamir’s secret sharing scheme

Schematem Lai-Dinga współdzielenia sekretu (oznaczenie: Sigma^{LD}_q(c, i)) dla parametrów c = (c_0, ..., c_{k-1}), i, q nazywamy modyfikację k-progowego schematu Shamira, w której udziałem uczestnika x w F_q jest wartość wielomianu P(x) = \sum_{j = 0}^{k-1} a_j x^{c_j}, przy czym współczynniki a_j są tajne, zaś wykładniki c_j jawne, zaś wartością sekretu jest współczynnik a_i. Kontynuując wcześniejsze badania Spieża, Urbanowicza i in., badamy struktury dostępu realizowane przez takie schematy, a także zachowanie tzw. zbiorów progowych, gdzie zbiór uczestników nazywamy progowym, jeśli schemat po obcięciu do niego staje się k-progowy.Jednym z naszych ważniejszych celów jest podanie asymptotycznych oszacowań liczby zbiorów progowych (bądź nie-progowych) o danej wielkości n w schemacie Lai-Dinga Sigma^{LD}_q(\mathbf{c}, i), przy czym w oszacowaniach tych rolę zmiennej pełni q, zaś c, i, n są parametrami (mogącymi wpływać na stałe w notacji asymptotycznej). Uogólniając wcześniejsze wyniki dla c = (0, 1, ..., k-1, wykazujemy w ogólności, że liczba zbiorów progowych wynosi Theta(q^n). Odnośnie zbiorów nie-progowych, wykazujemy, że dla ustalonych c oraz i liczba takich zbiorów o wielkości k - 1 może wynosić 0 dla wszystkich q, Theta(q^{k-2}) dla wszystkich q, lub w sposób okresowy przełączać się pomiędzy tymi dwoma wzorcami. Ponadto dla wielu przypadków podajemy rozsądne z obliczeniowego punktu widzenia ograniczenia dolne na q (a także na charakterystykę ciała F_q), powyżej których takie zbiory muszą istnieć. Ma to miejsce w szczególności gdy ciąg c jest arytmetyczny, lub gdy w ciągu \hat{c}_i (powstającym z c przez usunięcie c_i) każde dwa kolejne przyrosty są względnie pierwsze.W ramach powyższego rozumowania (na potrzeby wykorzystywanego w nim twierdzenia Weila) badamy absolutną nierozkładalność klasycznych wielomianów Schura nad ciałami skończonymi. Wykorzystując rozumowania Mongego i Rajana i przenosząc (częściowo) metody Rajana z C nad ciała skończone, otrzymujemy nowy wynik dotyczący nierozkładalności dużej klasy wielomianów Schura. Co więcej, wykorzystując inną, nową metodę, opartą na wielościanach Newtona, uogólniamy powyższe kryterium nierozkładalności na szeroką klasę zaburzeń wielomianów Schura.W ostatnim rozdziale pracy gromadzimy kilka spostrzeżeń dotyczących struktur dostępu w schematach Lai-Dinga. Najpierw wykazujemy, że są one niemal równie ogólne jak w schematach Brickella, choć nasza konstrukcja odpowiedniego schematu Lai-Dinga ma znaczny stopień złożoności. Następnie analizujemy przypadki, gdy ciąg c lub \hat{c}_i jest arytmetyczny. O ile pierwszy z nich zasadniczo sprowadza się do schematów typu Shamira, o tyle w drugim można znaleźć nowe przykłady struktur dostępowych, w tym niektóre struktury grafowe; podajemy charakteryzację grafów uzyskiwalnych w powyższy sposób.