Secret sharing schemes with hidden sets and a new secret sharing scheme based on linear feedback shift register sequences

Abstract

O esquema de segredo compartilhado de Shamir é bem conhecido, estabelecido e o mais utilizado. A sua principal característica é o uso de dois parâmetros: t e n, tal que 2 = t = n, onde n represents o número total de participantes em um determinado grupo e t representa o número mínimo de participantes desse determinado grupo para recuperar o segredo. A suposição principal do esquema de Shamir é que nenhum conhecimento sobre o segredo pode ser obtido por um subconjunto menor do que t participantes. Entretanto, existem diferentes modelos de ameaça onde o esquema de Shamir não consegue garantir a segurança do segredo. Um exemplo é o caso onde a entidade chamada distribuidor (distribuidor das partes do segredo) é maliciosa e distribui partes do segredo incorretas para os participantes. Portanto, diferentes grupos de participantes irão reconstruir diferentes segredos sem saber qual é o correto. Para garantir a segurança contra esse modelo de ameaça foram propostos os trabalhos chamados Esquemas de Segredo Compartilhado Verificáveis. Entretanto, existe um outro modelo de ameaça onde o distribuidor pode criar um esquema em que permite a reconstrução do segredo com menos partes do que o limiar determinado inicialmente no esquema. Neste trabalho vamos mostrar que existem subconjuntos menores do que t participantes onde é possível recuperar o segredo. Nós chamamos tais subgrupos de Conjuntos Escondidos. Este trabalho define o modelo de ameaça tradicional e o extende para poder explicar o uso dos conjuntos escondidos. Foram feitas definições e exemplos no trabalho sobre esses conjuntos. Neste trabalho também foram propostos métodos para detectar e inserir tais conjuntos escondidos. O esquema de segredo compartilhado de Shamir é o mais tradicional e utiliza o conceito de limiar para gerenciar as partes do segredo. Ito, Saito e Nishizeki propuseram um novo esquema baseado em estruturas de acesso gerais. Tais estruturas não possuem um limiar, mas permitem que qualquer grupo qualificado de participantes possam recuperar o segredo, independentemente de sua cardinalidade. Beimel afirma em um survey que um dos principais problemas nesses esquemas de segredo compartilhado com estruturas de acesso gerais é que o tamanho dos shares é proporcionalmente exponencial ao número de participantes. Portanto, torna-se impraticável. Neste trabalho nós propomos um estudo inicial de um novo esquema de segredo compartilhado com estruturas de acesso gerais que é perfeito e ideal. É baseado na construção de matrizes ortogonais utilizando matrizes de registradores de deslocamento linear.

Abstract: Shamir?s Secret Sharing Scheme is well established and widely used. Its main characteristic is the use of two parameters, t and n, such that 2 = t = n, where n represents the total number of participants and t represents the minimum number of participants to reconstruct a secret. The underlying assumption of Shamir scheme is that no knowledge of the secret can be acquired by a group of less than t participants. However, there are different threat models that can compromise the secret?s security using Shamir secret sharing scheme. One example is the case where the entity called the dealer (share?s distributor) is malicious and distributes wrong shares to participants. Therefore, different groups of participants could reconstruct different secrets without knowing which one is correct. To guarantee security with these threat models, verifiable secret sharing schemes (VSS) may be used. However, there exists another threat where the dealer could create a scheme that allows secret reconstruction with fewer shares than the threshold. In this work, we show there may be subsets of less than t participants that can recover the secret. We call such subsets as Hidden Sets. This work defines the traditional threat model and extends it to the situations where it is possible to insert hidden sets. Definitions and examples are given about these hidden set members. We also propose methods to detect and insert these privileged sets. Shamir secret sharing scheme is the most traditional, and it uses the threshold concept to manage shares. Later, Ito, Saito, and Nishizeki proposed a scheme based on general access structures. Such structures do not have a threshold, but allow any qualified set of participants to reconstruct the secret, regardless of their cardinality. Beimel affirms in a survey that one of the significant problems in these general access structure schemes is that the shares? size is exponential in the number of participants. Hence, it becomes impractical. In this work, we propose an initial study of a general access structure scheme that is perfect and ideal. It is based on the construction of orthogonal arrays using linear feedback shift registers matrices.