Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Be Adaptive, Avoid Overcommitting

Authors : Zahra Jafargholi, Chethan Kamath, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, Daniel Wichs

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future.
Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to \(2^n\). However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of \(m \ll n\) bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only \(2^m \ll 2^n\).
In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.

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 Memory-Tight Reductions
next chapter The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling Revisited
Footnotes
1
In many previous works – including [8, 9, 16], and by the authors of this paper – this random guessing was referred to as “complexity leveraging”, but this seems to be an abuse of the term. Instead, complexity leveraging [7] refers to the use of two different schemes, \(S_1,S_2\), where the two schemes are chosen with different values of the security parameter, \(k_1\) and \(k_2\), where \(k_1 < k_2\) and such that an adversary against \(S_2\) (or perhaps even the honest user of \(S_2\)) can break the security of \(S_1\).
 
2
In the access structure for directed connectivity, the parties correspond to an edge in the complete directed graph and the “qualified” subsets are those edges that connect two distinguished nodes s and t.
 
3
For access structures in \(\mathsf {NP}\), a qualified set of parties needs to know an \(\mathsf {NP}\) witness that they are qualified.
 
4
Witness encryption for a language \(L \in \mathsf {NP}\) allows to encrypt a message relative to a statement \(x\in L\) such that anyone holding a witness to the statement can decrypt the message, but if \(x\notin L\), then the message is computationally hidden.
 
5
One can relax the additional assumption of one-way functions to an average-case hardness assumption in \(\mathsf {NP}\) [20].
 
6
This is a knowledge assumption that says that if an adversary can decrypt a witness encryption ciphertext, then it must know a witness which can be extracted from it.
 
7
In the actual game the adversary can also make standard CPA encryption queries \(\mathsf{{Enc}}(k_i,m)\) for chosen m, i. As this doesn’t meaningfully change the security proof we ignore this here.
 
8
The presentation in [16] follows the above outline fairly closely and the reader can easily match it with our general framework. The one conceptual difference is that we think of all the hybrids \(\mathsf{H}_i\) as existing in the selective setting where the adversary commits to the entire input but then we analyze indistinguishability of neighboring hybrids in a partially selective setting. The work of [16] thought of the hybrids \(\mathsf{H}_i\) as already being partially selective, which made it difficult to compare neighboring hybrids, since the adversary was expected to commit to different information in each one. We view our new framework as being conceptually simpler.
 
9
To be precise, we only need the encryption scheme to be secure in a weaker model where encryptions of two random messages \(m_0,m_1\in \mathcal{K}\) under a random key \(k\in \mathcal{K}\) are \((s,\delta )\)-indistinguishable, with the adversary having access to ciphertexts on random messages from \(\mathcal{K}\).
 
10
Even though \(\mathsf{R}_I\) does not know the key \(k_{\sigma (I)}\), the query \(({\mathtt {encrypt}},v_{\sigma (I-1)},v_{\sigma (I)})\) does not cause a problem as its response is \(\mathsf{{Enc}}(k_{\sigma (I)},r_{\sigma (I-1)})\).
 
11
In the full version, one can see that the sequence \(\mathcal {P}_0,\ldots ,\mathcal {P}_{3^{\log {n}}}\) corresponds to an “edge-pebbling” of the path graph.
 
12
To be more precise, the scheme that Vinod et al. presented and analyzed is slightly different. Specifically, they considered AND and OR gates with fan-out 1 and showed how to separately handle FAN-OUT gates (gates that have fan-in 1 and fan-out 2). Their analysis can be modified to handle our scheme.
 
Literature
1.
Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20901-7_​2 CrossRef
2.
Bellare, M., Hoang, V.T., Rogaway, P.: Adaptively secure garbling with applications to one-time programs and secure outsourcing. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 134–153. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34961-4_​10 CrossRef
3.
4.
Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of AFIPS 1979 National Computer Conference, vol. 48, pp. 313–317 (1979)
5.
6.
7.
Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge (extended abstract). In: 32nd ACM STOC, pp. 235–244. ACM Press, May 2000
8.
Fuchsbauer, G., Jafargholi, Z., Pietrzak, K.: A quasipolynomial reduction for generalized selective decryption on trees. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 601–620. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​29 CrossRef
9.
Fuchsbauer, G., Konstantinov, M., Pietrzak, K., Rao, V.: Adaptive security of constrained PRFs. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 82–101. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​5
10.
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 467–476. ACM Press, June 2013
11.
Goldreich, O., Goldwasser, S., Micali, S.: On the cryptographic applications of random functions (extended abstract). In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 276–288. Springer, Heidelberg (1985). doi:10.​1007/​3-540-39568-7_​22 CrossRef
12.
Hemenway, B., Jafargholi, Z., Ostrovsky, R., Scafuro, A., Wichs, D.: Adaptively secure garbled circuits from one-way functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 149–178. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53015-3_​6 CrossRef
13.
Hohenberger, S., Sahai, A., Waters, B.: Replacing a random oracle: full domain hash from indistinguishability obfuscation. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 201–220. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​12 CrossRef
14.
Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proceedings of IEEE Global Telecommunication Conference (Globecom 1987), pp. 99–102 (1987)
15.
16.
17.
Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: 20th ACM STOC, pp. 539–550. ACM Press, May 1988
18.
Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of Structures in Complexity Theory, pp. 102–111 (1993)
19.
Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A.R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 669–684. ACM Press, November 2013
20.
Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: 55th FOCS, pp. 374–383. IEEE Computer Society Press, October 2014
21.
22.
23.
24.
Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: 57th FOCS, pp. 406–415. IEEE Computer Society Press (2016)
25.
Rogaway, P., Bellare, M.: Robust computational secret sharing and a unified account of classical secret-sharing goals. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM CCS 2007, pp. 172–184. ACM Press, October 2007
26.
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) 46th ACM STOC, pp. 475–484. ACM Press, May/Jun 2014
27.
28.
Vinod, V., Narayanan, A., Srinathan, K., Rangan, C.P., Kim, K.: On the power of computational secret sharing. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 162–176. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-24582-7_​12 CrossRef
29.
Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160–164. IEEE Computer Society Press, November 1982
30.
Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986
Metadata
Title
Be Adaptive, Avoid Overcommitting
Authors
Zahra Jafargholi
Chethan Kamath
Karen Klein
Ilan Komargodski
Krzysztof Pietrzak
Daniel Wichs
Copyright Year
2017
Book
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_5

Premium Partner

    Image Credits