Top

Journal of Cryptology

Published in:

30-09-2015

Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

Authors: Ivan Damgård, Sebastian Faust, Pratyay Mukherjee, Daniele Venturi

Published in: Journal of Cryptology | Issue 1/2017

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

search-config

AI-assisted search

Off

Abstract

Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the number of tampering queries the adversary is allowed to ask for. The latter restriction is necessary in case of arbitrary key relations, as otherwise a generic attack of Gennaro et al. (TCC 2004) shows how to recover the key of almost any cryptographic primitive. We describe our contributions in more detail below. (1) We show that standard ID and signature schemes constructed from a large class of \(\Sigma \)-protocols (including the Okamoto scheme, for instance) are secure even if the adversary can arbitrarily tamper with the prover’s state a bounded number of times and obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters. (2) We show a bounded tamper and leakage resilient CCA-secure public key cryptosystem based on the DDH assumption. We first define a weaker CCA-like security notion that we can instantiate based on DDH, and then we give a general compiler that yields CCA security with tamper and leakage resilience. This requires a public tamper-proof common reference string. (3) Finally, we explain how to boost bounded tampering and leakage resilience [as in (1) and (2) above] to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal hardware token (containing leak- and tamper-free information) which can be used to refresh the secret key. We believe that bounded tampering is a meaningful and interesting alternative to avoid known impossibility results and can provide important insights into the security of existing standard cryptographic schemes.

previous article A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

next article Non-malleable Coding Against Bit-Wise and Split-State Tampering

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

The impossibility result of [46] leaves certain loopholes, which, however, seem very hard to exploit.

We notice that the self-destruct has to be permanent as otherwise the attack of [46] may still apply.

Notice that “floppy” is just terminology and we use it for consistency with earlier works.

Note that \({\tilde{y}} = 0\hbox { mod }{{\tilde{p}}}\) implies that for at least one of the generators \(g_i\)’s we get \({\tilde{g}}_i = 0\hbox { mod }{{\tilde{p}}}\), so that \(a = \prod _{i=1}^\ell {\tilde{g}}_i^{r_i} =0\hbox { mod }{{\tilde{p}}}\).

Recall that for \(t=0\) no decryption query is allowed, and thus restricted IND-CCA \((\lambda ',0)\)-BLT security collapses to the notion of semantic security against \(\lambda '\)–key-leakage attacks from [57].

We note that in the schemes of [6] making the content of the floppy public does not constitute a total breach of security; however the security proof completely breaks down, leaving no security guarantee for the schemes at hand.

Alternatively \(\mathsf {P}\) can send \(( pk ,\mathsf {help})\) together with the first message of the identification scheme, in order to keep the same round complexity as in \(\mathcal {ID}\).

We stress that in the PKE case we cannot apply the same trick as for the compiler of Fig. 4, since that would require to make the scheme interactive.

Here is how \(\mathsf {B}\) simulates the transcript with more details. Without loss of generality, assume that a basic interaction \(\mathsf {P}\rightleftarrows \mathsf {V}\) consists of \(\mu \) messages for odd \(\mu \in \mathbb {N}\); recall that the interaction \(\mathsf {P}'\rightleftarrows \mathsf {V}'\) also consists of \(\mu \) messages, where the pair \((\overline{ pk },\overline{\mathsf {help}})\) is appended to the first message sent by \(\mathsf {P}\). Thus, the ith message of the interaction \({\tilde{\mathsf {P}}}'_j\rightleftarrows \mathsf {V}'\), for \(i\in [\mu ]\) can be simulated by a leakage query hard-wiring a description of \({\tilde{\mathsf {P}}}'_j\) together with \((m_{1},\ldots ,m_{i-1}, pp ,\overline{ pk },\overline{\mathsf {help}})\), where \((m_{1},\ldots ,m_{i-1})\) is the current partial transcript.

D. Aggarwal, Y. Dodis, T. Kazana, M. Obremski, Non-malleable reductions and applications, in STOC (2015)

D. Aggarwal, Y. Dodis, S. Lovett, Non-malleable codes from additive combinatorics, in STOC, (2014), pp. 774–783

D. Aggarwal, S. Dziembowski, T. Kazana, M. Obremski, Leakage-resilient non-malleable codes, in TCC, (2015), pp. 398–426

S. Agrawal, D. Gupta, H.K. Maji, O. Pandey, M. Prabhakaran, Explicit non-malleable codes against bit-wise tampering and permutations, in CRYPTO, (2015), pp 538–557.

S. Agrawal, D. Gupta, H.K. Maji, O. Pandey, M. Prabhakaran, A rate-optimizing compiler for non-malleable codes against bit-wise tampering and permutations, in TCC, (2015), pp. 375–397

S. Agrawal, Y. Dodis, V. Vaikuntanathan, D. Wichs, On continual leakage of discrete log representations, in ASIACRYPT, (2013), pp. 401–420

J. Alwen, Y. Dodis, D. Wichs, Leakage-resilient public-key cryptography in the bounded-retrieval model, in CRYPTO, (2009), pp. 36–54

R. Anderson, M. Kuhn, Tamper resistance: a cautionary note, in WOEC’96: Proceedings of the 2nd conference on Proceedings of the Second USENIX Workshop on Electronic Commerce, (USENIX Association, Berkeley, 1996), p. 1

B. Applebaum, D. Harnik, Y. Ishai, Semantic security under related-key attacks and applications, in ICS, (2011), pp. 45–60

10.

M. Bellare, D. Cash, Pseudorandom functions and permutations provably secure against related-key attacks, in CRYPTO, (2010), pp. 666–684

11.

M. Bellare, D. Cash, R. Miller, Cryptography secure against related-key attacks and tampering. In ASIACRYPT, (2011), pp. 486–503

12.

M. Bellare, T. Kohno, A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications, in EUROCRYPT, (2003), pp. 491–506

13.

M. Bellare, K.G. Paterson, S. Thomson. RKA security beyond the linear barrier: IBE, encryption and signatures, in ASIACRYPT, (2012), pp. 331–348

14.

R. Bhattacharyya, A. Roy, Secure message authentication against related key attack, in FSE (2013)

15.

D. Boneh, R.A. DeMillo, R.J. Lipton, On the importance of eliminating errors in cryptographic computations. J. Cryptol., 14(2):101–119 (2001)

16.

D. Boneh, S. Halevi, M. Hamburg, R. Ostrovsky, Circular-secure encryption from decision diffie-hellman, in CRYPTO, (2008), pp. 108–125

17.

J. Camenisch, N. Chandran, V. Shoup, A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks, in EUROCRYPT, (2009), pp. 351–368

18.

E. Chattopadhyay, D. Zuckerman. Non-malleable codes against constant split-state tampering, in FOCS, (2014), pp. 306–315

19.

M. Cheraghchi, V. Guruswami, Capacity of non-malleable codes, in Innovations in Theoretical Computer Science, ITCS, (2014), pp. 155–168

20.

M. Cheraghchi, V. Guruswami, Non-malleable coding against bit-wise and split-state tampering, in TCC, (2014), pp. 440–464

21.

S.G. Choi, A. Kiayias, T. Malkin, BiTR: Built-in tamper resilience, in ASIACRYPT, (2011), pp. 740–758

22.

S. Coretti, Y. Dodis, B. Tackmann, D. Venturi, Non-malleable encryption: simpler, shorter, stronger. IACR Cryptol. ePrint Archive, 772 (2015)

23.

S. Coretti, U. Maurer, B. Tackmann, D. Venturi, From single-bit to multi-bit public-key encryption via non-malleable codes, in TCC, (2015), pp. 532–560

24.

R. Cramer, Modular Design of Secure yet Practical Cryptographic Protocols. PhD thesis, University of Amsterdam, (1996)

25.

G. Di Crescenzo, R.J. Lipton, S. Walfish, Perfectly secure password protocols in the bounded retrieval model, in TCC, (2006), pp. 225–244

26.

D. Dachman-Soled, Y.T. Kalai, Securing circuits against constant-rate tampering, in CRYPTO, (2012), pp. 533–551

27.

D. Dachman-Soled, Y.T. Kalai, Securing circuits and protocols against 1/poly(k) tampering rate, in TCC, (2014), pp. 540–565

28.

D. Dachman-Soled, F.-H. Liu, E. Shi, H.-S. Zhou, Locally decodable and updatable non-malleable codes and their applications, in TCC, (2015), pp. 427–450

29.

I. Damgård, S. Faust, P. Mukherjee, D. Venturi, Bounded tamper resilience: How to go beyond the algebraic barrier, in ASIACRYPT, (2013), pp. 140–160

30.

I. Damgård, S. Faust, P. Mukherjee, D. Venturi, The chaining lemma and its application, in ICITS, (2015), pp. 181–196

31.

Y. Dodis, K. Haralambiev, A. López-Alt, D. Wichs, Cryptography against continuous memory attacks, in FOCS, (2010), pp. 511–520

32.

Y. Dodis, K. Haralambiev, A. López-Alt, D. Wichs, Efficient public-key cryptography in the presence of key leakage, in ASIACRYPT, (2010), pp. 613–631

33.

Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)

34.

S. Dziembowski, Intrusion-resilience via the bounded-storage model, in TCC, (2006), pp. 207–224

35.

S. Dziembowski, T. Kazana, M. Obremski, Non-malleable codes from two-source extractors, in CRYPTO, (2013), pp. 239–257

36.

S. Dziembowski, T. Kazana, D. Wichs, One-time computable self-erasing functions, in TCC, (2011), pp. 125–143

37.

S. Dziembowski, K. Pietrzak, D. Wichs, Non-malleable codes, in ICS, (2010), pp. 434–452

38.

S. Faust, M. Kohlweiss, G.A. Marson, D. Venturi, On the non-malleability of the fiat-shamir transform, in INDOCRYPT, (2012), pp. 60–79

39.

S. Faust, P. Mukherjee, J.B. Nielsen, D. Venturi, Continuous non-malleable codes, in TCC (2014)

40.

S. Faust, P. Mukherjee, J.B. Nielsen, D. Venturi, A tamper and leakage resilient von Neumann architecture, in PKC, (2015), pp. 579–603

41.

S. Faust, P. Mukherjee, D. Venturi, D. Wichs, Efficient non-malleable codes and key-derivation for poly-size tampering circuits, in EUROCRYPT, (2014), pp. 111–128

42.

S. Faust, K. Pietrzak, D. Venturi, Tamper-proof circuits: How to trade leakage for tamper-resilience. In ICALP (1), (2011), pp. 391–402

43.

A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in CRYPTO, (1986), pp. 186–194

44.

M. Fischlin, R. Fischlin, The representation problem based on factoring, in CT-RSA, (2002), pp. 96–113

45.

D. Genkin, Y. Ishai, M. Prabhakaran, A. Sahai, E. Tromer, Circuits resilient to additive attacks with applications to secure computation, in STOC, (2014), pp. 495–504

46.

R. Gennaro, A. Lysyanskaya, T. Malkin, S. Micali, T. Rabin, Algorithmic tamper-proof (ATP) security: theoretical foundations for security against hardware tampering, in TCC, (2004), pp. 258–277

47.

V. Goyal, A. O’Neill, V. Rao, Correlated-input secure hash functions, in TCC, (2011), pp. 182–200

48.

J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in ASIACRYPT, (2006), pp. 444–459

49.

L.C. Guillou, J.-J. Quisquater, A “paradoxical” identity-based signature scheme resulting from zero-knowledge, in CRYPTO, (1988), pp. 216–231

50.

Y. Ishai, M. Prabhakaran, A. Sahai, D. Wagner, Private circuits II: keeping secrets in tamperable circuits, in EUROCRYPT, (2006), pp. 308–327

51.

Z. Jafargholi, D. Wichs, Tamper detection and continuous non-malleable codes, in TCC, (2015), pp. 451–480,

52.

Y.T. Kalai, B. Kanukurthi, A. Sahai, Cryptography with tamperable and leaky memory, in CRYPTO, (2011), pp. 373–390

53.

J. Katz, V. Vaikuntanathan, Signature schemes with bounded leakage resilience, In ASIACRYPT, (2009), pp. 703–720

54.

A. Kiayias, Y. Tselekounis, Tamper resilient circuits: the adversary at the gates, in ASIACRYPT, (2013), pp. 161–180

55.

F.-H. Liu, A. Lysyanskaya, Tamper and leakage resilience in the split-state model, in CRYPTO, (2012), pp. 517–532

56.

S. Lucks, Ciphers secure against related-key attacks, in FSE, (2004), pp. 359–370

57.

M. Naor, G. Segev, Public-key cryptosystems resilient to key leakage, in CRYPTO, (2009), pp. 18–35

58.

T. Okamoto, Provably secure and practical identification schemes and corresponding signature schemes, in CRYPTO, (1992), pp. 31–53

59.

K. Pietrzak, Subspace LWE, in TCC, (2012), pp. 548–563

60.

S. Pohlig, M. Hellman, An improved algorithm for computing logarithms over and its cryptographic significance. IEEE Trans. Inform. Theory, 24(1), 106–110 (1978)

61.

B. Qin, S. Liu, T.H. Yuen, R.H. Deng, K. Chen, Continuous non-malleable key derivation and its application to related-key security, in PKC, (2015), pp. 557–578

62.

H. Wee, Public key encryption against related key attacks, in PKC, (2012), pp. 262–279

Title: Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier
Authors: Ivan Damgård
Sebastian Faust
Pratyay Mukherjee
Daniele Venturi
Publication date: 30-09-2015
Publisher: Springer US
Published in: Journal of Cryptology / Issue 1/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9218-0

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"

Other articles of this Issue 1/2017

Dynamic Proofs of Retrievability Via Oblivious RAM

Obfuscating Conjunctions

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

An Algebraic Framework for Diffie–Hellman Assumptions

Efficient One-Sided Adaptively Secure Computation

Weak Locking Capacity of Quantum Channels Can be Much Larger Than Private Capacity

Premium Partner