Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption

Thomas HolensteinContact Information and Renato RennerContact Information

(1)  Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland
Abstract
Secret-key agreement between two parties Alice and Bob, connected by an insecure channel, can be realized in an information-theoretic sense if the parties share many independent pairs of correlated and partially secure bits. We study the special case where only one-way communication from Alice to Bob is allowed and where, for each of the bit pairs, with a certain probability, the adversary has no information on Alice’s bit. We give an expression which, for this situation, exactly characterizes the rate at which Alice and Bob can generate secret key bits.
This result can be used to analyze a slightly restricted variant of the problem of polarizing circuits, introduced by Sahai and Vadhan in the context of statistical zero-knowledge, which we show to be equivalent to secret-key agreement as described above. This provides us both with new constructions to polarize circuits, but also proves that the known constructions work for parameters which are tight.
As a further application of our results on secret-key agreement, we show how to immunize single-bit public-key encryption schemes from decryption errors and insecurities of the encryption, a question posed and partially answered by Dwork, Naor, and Reingold. Our construction works for stronger parameters than the known constructions.
Supported by the Swiss National Science Foundation, project no. 200020-103847/1.

Contact Information Thomas Holenstein
Email: thomahol@inf.ethz.ch

Contact Information Renato Renner
Email: renner@inf.ethz.ch
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)