Secret Sharing and Algorithmic Information Theory

Our work deals with secret sharing in the theoretical points of view of Shannon's Information Theory and Kolmogorov's Algorithmic Information Theory. We are going to explain how these three subjects are naturally deeply intertwined. Information inequalities play a central role in this text. They are the inequalities for Shannon entropy, but also they are in exact correspondence with the inequalities for Kolmogorov complexity. Algorithmic Information theory, as introduced by Kolmogorov, formalizes the idea of randomness for strings. These two reasons alone justify to consider the notion of secret sharing in the Algorithmic framework (if one can share a random secret one can share anything). Originally, secret sharing was first studied under the combinatorial lens, only later was it more generally formalized using information-theoretic measures. This step allowed the use of information inequalities which revealed to be very important to understand the existence of secret-sharing schemes with respect to efficiency. The investigation of information inequalities is at its debut. We contribute to the subject by introducing the notion of essentially conditional inequalities, which shows once again that information inequalities are yet not fully understood.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00763117
Author Kaced, Tarik
Maintainer CCSD
Last Updated June 1, 2026, 02:50 (UTC)
Created June 1, 2026, 02:50 (UTC)
Identifier tel-00763117
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Systèmes complexes, automates et pavages (ESCAPE) ; Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) ; Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
creator Kaced, Tarik
date 2012-12-04T00:00:00
harvest_object_id ad0194cb-337d-4fec-80ed-ef388f701a11
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-13T00:00:00
set_spec type:THESE