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:
Compact Attribute-Based Encryption and Signcryption for General Circuits from Multilinear Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Non-malleable Extractors with Shorter Seeds and Their Applications

Authors : Yanqing Yao, Zhoujun Li

Published in: Progress in Cryptology -- INDOCRYPT 2015

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs (STOC’09) introduced the notion of a non-malleable extractor. A non-malleable extractor \(\textsf {nmExt}: \{0, 1\}^n \times \{0, 1\}^d \rightarrow \{0, 1\}^m\) takes two inputs, a weakly-random W and a uniformly random seed S, and outputs a string which is nearly uniform, given S as well as \(\textsf {nmExt}(W, \mathcal {A}(S))\), for an arbitrary function \(\mathcal {A}\) with \(\mathcal {A}(S) \ne S\).
In this paper, by developing the combination and permutation techniques, we improve the error estimation of the extractor of Raz (STOC’05), which plays an extremely important role in the constraints of the non-malleable extractor parameters including seed length. Then we present improved explicit construction of non-malleable extractors. Though our construction is the same as that given by Cohen, Raz and Segev (CCC’12), the parameters are improved. More precisely, we construct an explicit \((1016, \frac{1}{2})\)-non-malleable extractor \(\textsf {nmExt}: \{0, 1\}^{n} \times \{0, 1\}^d \rightarrow \{0, 1\}\) with \(n=2^{10}\) and seed length \(d=19\), while Cohen et al. showed that the seed length is no less than \(\frac{46}{63} + 66\). Therefore, our method beats the condition “\(2.01 \cdot \log n \le d \le n\)” proposed by Cohen et al., since d is just \(1.9 \cdot \log n\) in our construction. We also improve the parameters of the general explicit construction given by Cohen et al. Finally, we give their applications to privacy amplification.

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 A Key to Success
next chapter Efficiently Simulating High Min-entropy Sources in the Presence of Side Information
Appendix
Available only for authorised users
Footnotes
1
When we say a source in this paper, we mean a random variable.
 
2
The concept of the error of seeded extractor can be seen in Definition 1.
 
3
The concept of the error of non-malleable extractor can be seen in Definition 3.
 
4
In other papers (e.g., [9, 11, 14, 24]), X is \(\epsilon \)-close to Y if \(\frac{1}{2} \Vert X-Y\Vert _1 = \frac{1}{2} \sum _{s} |\Pr [X =s]- \Pr [Y =s]| \le \epsilon \). To keep consistency, Definition 1 holds throughout this paper.
 
5
In this paper, two elements \(s_i\) and \(s_j\) in the sequence \( s_1, \ldots , s_k\), where \(i\ne j\), might represent the same string.
 
Literature
1.
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289–304 (1992)MATHCrossRef
2.
3.
Cheraghchi, M., Guruswami, V.: Non-malleable coding against bit-wise and split-state tampering. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 440–464. Springer, Heidelberg (2014) CrossRef
4.
Chandran, N., Kanukurthi, B., Ostrovsky, R., Reyzin, L.: Privacy amplification with asymptotically optimal entropy loss. In: STOC 2010, pp. 785–794 (2010)
5.
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230–261 (1988)MATHMathSciNetCrossRef
6.
Cohen, G., Raz, R., Segev, G.: Non-malleable extractors with short seeds and applications to privacy amplification. In: CCC 2012, pp. 298–308 (2012)
7.
Dodis, Y., Katz, J., Reyzin, L., Smith, A.: Robust fuzzy extractors and authenticated key agreement from close secrets. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 232–250. Springer, Heidelberg (2006) CrossRef
8.
Dodis, Y., Li, X., Wooley, T.D., Zuckerman, D.: Privacy amplification and non-malleable extractors via character sums. In: FOCS 2011, pp. 668–677 (2011)
9.
Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: STOC 2009, pp. 601–610 (2009)
10.
Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Proceedings of Innovations in Computer Science (ICS 2010), pp. 434–452 (2010)
11.
Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1–22. Springer, Heidelberg (2013) CrossRef
12.
Fortnow, L., Shaltiel, R.: Recent developments in explicit constructions of extractors, 2002. Bull. EATCS 77, 67–95 (2002)
13.
Kanukurthi, B., Reyzin, L.: Key agreement from close secrets over unsecured channels. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 206–223. Springer, Heidelberg (2009) CrossRef
14.
Li, X.: Non-malleable extractors, two-source extractors and privacy amplification. In: FOCS 2012, pp. 688–697 (2012)
15.
Maurer, U.M., Wolf, S.: Privacy amplification secure against active adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 307–321. Springer, Heidelberg (1997) CrossRef
16.
Maurer, U.M., Wolf, S.: Secret-key agreement over unauthenticated public channels III: privacy amplification. IEEE Trans. Inf. Theory 49(4), 839–851 (2003)MATHMathSciNetCrossRef
17.
Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)MATHMathSciNetCrossRef
18.
19.
20.
Raz, R.: Extractors with weak random seeds. In: STOC 2005, pp. 11–20 (2005)
21.
Renner, R.S., Wolf, S.: Unconditional authenticity and privacy from an arbitrarily weak secret. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 78–95. Springer, Heidelberg (2003) CrossRef
22.
Vadhan, S.: Randomness extractors and their many guises: invited tutorial. In: FOCS 2002, p. 9 (2002)
23.
Wolf, S.: Strong security against active attacks in information-theoretic secret-key agreement. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 405–419. Springer, Heidelberg (1998)
24.
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Theory of Computing 2007, pp. 103–128 (2007)
Metadata
Title
Non-malleable Extractors with Shorter Seeds and Their Applications
Authors
Yanqing Yao
Zhoujun Li
Copyright Year
2015
Book
Progress in Cryptology -- INDOCRYPT 2015

Print ISBN: 978-3-319-26616-9

Electronic ISBN: 978-3-319-26617-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26617-6_16

Premium Partner

    Image Credits