Title : 
Almost-perfect secret sharing
         
        
        
            Author_Institution : 
Lab. d´´Inf. Fondamentale de Marseille (LIF), Univ. de Provence, Marseille, France
         
        
        
            fDate : 
July 31 2011-Aug. 5 2011
         
        
        
        
            Abstract : 
To split a secret s between several participants, we generate (for each value of s) shares for all participants. The goal: authorized groups of participants should be able to reconstruct the secret but forbidden ones get no information about it. We introduce several notions of non-perfect secret sharing, where some small information leak is permitted. We study its relation to the Kolmogorov complexity version of secret sharing (establishing some connection in both directions) and the effects of changing the secret size (showing that we can decrease the size of the secret and the information leak at the same time).
         
        
            Keywords : 
computational complexity; security of data; Kolmogorov complexity version; almost-perfect secret sharing; information leak; nonperfect secret sharing; Complexity theory; Cryptography; Entropy; Information rates; Information theory; Random variables;
         
        
        
        
            Conference_Titel : 
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
         
        
            Conference_Location : 
St. Petersburg
         
        
        
            Print_ISBN : 
978-1-4577-0596-0
         
        
            Electronic_ISBN : 
2157-8095
         
        
        
            DOI : 
10.1109/ISIT.2011.6033816