TY - GEN
T1 - Randomness Recoverable Secret Sharing Schemes
AU - Hajiabadi, Mohammad
AU - Khazaei, Shahram
AU - Vahdani, Behzad
N1 - Funding Information:
We would like to thank Sorush Bahariyan for bringing Fact 1 to our attention and Motahareh Gharahi for fruitful discussions on the proof of Theorem 20.
Publisher Copyright:
© Mohammad Hajiabadi, Shahram Khazaei, and Behzad Vahdani; licensed under Creative Commons License CC-BY 4.0 4th Conference on Information-Theoretic Cryptography (ITC 2023)
PY - 2023/7
Y1 - 2023/7
N2 - It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone AC0) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone AC0 implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.
AB - It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone AC0) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone AC0 implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.
UR - http://www.scopus.com/inward/record.url?scp=85169047955&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85169047955&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITC.2023.12
DO - 10.4230/LIPIcs.ITC.2023.12
M3 - Conference contribution
AN - SCOPUS:85169047955
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 4th Conference on Information-Theoretic Cryptography, ITC 2023
A2 - Chung, Kai-Min
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 4th Conference on Information-Theoretic Cryptography, ITC 2023
Y2 - 6 June 2023 through 8 June 2023
ER -