Separating sources for encryption and secret sharing

Yevgeniy Dodis, Krzysztof Pietrzak, Bartosz Przydatek

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Most cryptographic primitives such as encryption, authentication or secret sharing require randomness. Usually one assumes that perfect randomness is available, but those primitives might also be realized under weaker assumptions. In this work we continue the study of building secure cryptographic primitives from imperfect random sources initiated by Dodis and Spencer (FOCS'02). Their main result shows that there exists a (high-entropy) source of randomness allowing for perfect encryption of a bit, and yet from which one cannot extract even a single weakly random bit, separating encryption from extraction. Our main result separates encryption from 2-out-2 secret sharing (both in the information-theoretic and in the computational settings): any source which can be used to achieve one-bit encryption also can be used for 2-out-2 secret sharing of one bit, but the converse is false, even for high-entropy sources. Therefore, possibility of extraction strictly implies encryption, which in turn strictly implies 2-out-2 secret sharing.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography
Subtitle of host publicationThird Theory of Cryptography Conference, TCC 2006, Proceedings
Number of pages16
StatePublished - 2006
Event3rd Theory of Cryptography Conference, TCC 2006 - New York, NY, United States
Duration: Mar 4 2006Mar 7 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3876 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Theory of Cryptography Conference, TCC 2006
Country/TerritoryUnited States
CityNew York, NY

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Separating sources for encryption and secret sharing'. Together they form a unique fingerprint.

Cite this