Top

Published in:

2016 | OriginalPaper | Chapter

Simultaneous Secrecy and Reliability Amplification for a General Channel Model

Authors : Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro

Published in: Theory of Cryptography

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a general notion of channel for cryptographic purposes, which can model either a (classical) physical channel or the consequences of a cryptographic protocol, or any hybrid. We consider simultaneous secrecy and reliability amplification for such channels. We show that simultaneous secrecy and reliability amplification is not possible for the most general model of channel, but, at least for some values of the parameters, it is possible for a restricted class of channels that still includes both standard information-theoretic channels and keyless cryptographic protocols.

Even in the restricted model, we require that for the original channel, the failure chance for the attacker must be a factor c more than that for the intended receiver. We show that for any \(c > 4 \), there is a one-way protocol (where the sender sends information to the receiver only) which achieves simultaneous secrecy and reliability. From results of Holenstein and Renner (CRYPTO’05), there are no such one-way protocols for \(c < 2\). On the other hand, we also show that for \(c > 1.5\), there are two-way protocols that achieve simultaneous secrecy and reliability.

We propose using similar models to address other questions in the theory of cryptography, such as using noisy channels for secret agreement, trade-offs between reliability and secrecy, and the equivalence of various notions of oblivious channels and secure computation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Oblivious Transfer from Any Non-trivial Elastic Noisy Channel via Secret Key Agreement

next chapter Proof of Space from Stacked Expanders

If a channel is such that the state description rapidly grows (say, squares) after each use, then after very few uses, the adversary that is allowed polynomial time in the size of the state will get to use exponential-time computation for her attacks. A standard cryptographic channel will unlikely be secure in this case. However, it is up to the designer of the channel to ensure that it remains secure, with respect to polynomial-time adversaries (which will probably force the designer to make sure that the state description does not grow too fast with respect to k).

Note that Eve can guess the bit with probability 1 / 2 when she receives \(\bot \). So the probability of her knowing the bit b is \(1 - 2 \alpha + (1/2) \cdot (2 \alpha ) = 1-\alpha \).

In contrast, consider a 2-way protocol where Bob, after receiving his n bits over the channel, sends Alice a message in the clear stating whether all his received bits are the same. Then fixing the value of Bob’s message to Alice will change the distribution of \(Y_i\) as a function of \(X_i\). So the argument in the present theorem does not apply to this 2-way protocol. (In fact, we use such a 2-way protocol in Sect. 5 in order to overcome the “factor-2 barrier” for one-way protocols given by the present theorem).

Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1997, pp. 374–383 (1997)

Bellare, M., Tessaro, S., Vardy, A.: Semantic security for the wiretap channel. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 294–311. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_18 CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, 14–17 October 2001, pp. 136–145. IEEE Computer Society (2001)

Chung, K.-M., Liu, F.-H.: Parallel repetition theorems for interactive arguments. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 19–36. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11799-2_2 CrossRef

Chung, K.-M., Pass, R.: Tight parallel repetition theorems for public-coin arguments using KL-divergence. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 229–246. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46497-7_9 CrossRef

Crépeau, C.: Efficient cryptographic protocols based on noisy channels. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 306–317. Springer, Heidelberg (1997). doi:10.1007/3-540-69053-0_21 CrossRef

Crépeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions. In: 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 42–52, October 1988

Crépeau, C., Morozov, K., Wolf, S.: Efficient unconditional oblivious transfer from almost any noisy channel. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 47–59. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30598-9_4 CrossRef

Csiszar, I., Körner, J.: Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24(3), 339–348 (1978)MathSciNetCrossRefMATH

10.

Dodis, Y.: Shannon impossibility, revisited. In: Smith, A. (ed.) ICITS 2012. LNCS, vol. 7412, pp. 100–110. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32284-6_6 CrossRef

11.

Dwork, C., Naor, M., Reingold, O.: Immunizing encryption schemes from decryption errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 342–360. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24676-3_21 CrossRef

12.

Garg, S., Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with one-way communication. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 191–208. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_10 CrossRef

13.

Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 25–32 (1989)

14.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRefMATH

15.

Haitner, I.: A parallel repetition theorem for any interactive argument. In: Proceedings of the 50th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2009, pp. 241–250 (2009)

16.

Halevi, S., Rabin, T.: Degradation and amplification of computational hardness. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 626–643. Springer, Heidelberg (2008). doi:10.1007/978-3-540-78524-8_34 CrossRef

17.

Håstad, J., Pass, R., Wikström, D., Pietrzak, K.: An efficient parallel repetition theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 1–18. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11799-2_1 CrossRef

18.

Holenstein, T.: Key agreement from weak bit agreement. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 664–673 (2005)

19.

Holenstein, T., Renner, R.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478–493. Springer, Heidelberg (2005). doi:10.1007/11535218_29 CrossRef

20.

Holenstein, T., Schoenebeck, G.: General hardness amplification of predicates and puzzles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 19–36. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19571-6_2 CrossRef

21.

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A., Wullschleger, J.: Constant-rate oblivious transfer from noisy channels. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 667–684. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22792-9_38 CrossRef

22.

Iwamoto, M., Ohta, K.: Security notions for information theoretically secure encryptions. In: 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1777–1781, July 2011

23.

Iwamoto, M., Ohta, K., Shikata, J.: Security formalizations and their relationships for encryption and key agreement in information-theoretic cryptography. CoRR, abs/1410.1120 (2014)

24.

Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)MathSciNetCrossRefMATH

25.

Liang, Y., Poor, H.V., Shamai (Shitz), S.: Information theoretic security. Found. Trends Commun. Inf. Theory 5(45), 355–580 (2008)MATH

26.

Lin, H., Tessaro, S.: Amplification of chosen-ciphertext security. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 503–519. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38348-9_30 CrossRef

27.

Maurer, U.: Constructive cryptography – a new paradigm for security definitions and proofs. In: Mödersheim, S., Palamidessi, C. (eds.) TOSCA 2011. LNCS, vol. 6993, pp. 33–56. Springer, Heidelberg (2012). doi:10.1007/978-3-642-27375-9_3 CrossRef

28.

Maurer, U., Renner, R.: Abstract cryptography. In: ICS, pp. 1–21. Tsinghua University Press (2011)

29.

Maurer, U.M.: Perfect cryptographic security from partially independent channels. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 561–571. ACM, New York (1991)

30.

Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993)MathSciNetCrossRefMATH

31.

Ueli, M.: Information-theoretic cryptography. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 47–65. Springer, Berlin Heidelberg (1999). doi:10.1007/3-540-48405-1_4 CrossRef

32.

Pass, R., Venkitasubramaniam, M.: An efficient parallel repetition theorem for Arthur-Merlin games. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 420–429 (2007)

33.

Pietrzak, K., Wikström, D.: Parallel repetition of computationally sound protocols revisited. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 86–102. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70936-7_5 CrossRef

34.

Sahai, A., Vadhan, S.P.: A complete promise problem for statistical zero-knowledge. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19–22 October 1997, pp. 448–457. IEEE Computer Society (1997)

35.

Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656–715 (1949)MathSciNetCrossRefMATH

36.

Shikata, J.: Formalization of information-theoretic security for key agreement, revisited. In: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 2720–2724, July 2013

37.

Wullschleger, J.: Oblivious-transfer amplification. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 555–572. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72540-4_32 CrossRef

38.

Wullschleger, J.: Oblivious transfer from weak noisy channels. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 332–349. Springer, Heidelberg (2009). doi:10.1007/978-3-642-00457-5_20 CrossRef

39.

Wyner, A.D.: The wire-tap channel. Bell Syst. Tech. J. 54, 1355–1387 (1975)MathSciNetCrossRefMATH

Title: Simultaneous Secrecy and Reliability Amplification for a General Channel Model
Authors: Russell Impagliazzo
Ragesh Jaiswal
Valentine Kabanets
Bruce M. Kapron
Valerie King
Stefano Tessaro
Publisher: Springer Berlin Heidelberg
Book: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner