Top

Published in:

2025 | OriginalPaper | Chapter

Bit-Security Preserving Hardness Amplification

Authors : Shun Watanabe, Kenji Yasunaga

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

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

search-config

AI-assisted search

Off

Abstract

Hardness amplification is one of the important reduction techniques in cryptography, and it has been extensively studied in the literature. The standard XOR lemma known in the literature evaluates the hardness in terms of the probability of correct prediction; the hardness is amplified from mildly hard (close to 1) to very hard $1/2 + \varepsilon $ by inducing $\varepsilon ^2$ multiplicative decrease of the circuit size. Translating such a statement in terms of the bit-security framework introduced by Micciancio-Walter (EUROCRYPT 2018) and Watanabe-Yasunaga (ASIACRYPT 2021), it may cause a bit-security loss of $\log (1/\varepsilon )$. To resolve this issue, we derive a new variant of the XOR lemma in terms of the Rényi advantage, which directly characterizes the bit security. In the course of proving this result, we prove a new variant of the hardcore lemma in terms of the conditional squared advantage; our proof uses a boosting algorithm that may output the $\bot $ symbol in addition to 0 and 1, which may be of independent interest.

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 Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World

next chapter Bit Security: Optimal Adversaries, Equivalence Results, and a Toolbox for Computational-Statistical Security Analysis

Available only for authorised users

Generally, the CS advantage is bounded above by the Rényi advantage. While the CS advantage may take a much smaller value in some cases, the CS advantage can be increased to the level of the Rényi advantage by modifying adversaries appropriately.

The symbol $\bot $ indicates that the adversary gives up the prediction.

More precisely, this statement assumes that the cost of a weighted majority gate can be ignored. Indeed, if $s = \omega (\log (1/\delta )/\varepsilon ^2)$, the cost is negligible; See Remark 1 for discussion.

Note that since there is a renormalization procedure, the updated probabilities of those symbols may be changed.

The latter was attributed to Nisan.

More precisely, the CS advantage in (5) is for a predictor; on the other hand, when we define the bit security, we consider the CS advantage for a distinguisher (cf. (27)). The CS advantage for a predictor was first introduced in the context of the Goldreich-Levin algorithm [17].

By the Taylor approximation, we have

$$\begin{aligned} e^{-\theta } \le 1 - \theta + \sup _{-1 \le \tau \le 1} \frac{e^{-\tau }}{2} \theta ^2 \le 1 - \theta + \frac{e}{2} \theta ^2 \le 1 - \theta + 2 \theta ^2 \end{aligned}$$

Such a naive implementation of the weighted majority has been studied in the circuit complexity [9].

It comes from the fact that the majority can be realized by a circuit of linear size of inputs [41].

In [32], the authors first introduced an advantage using the Shannon entropy and the mutual information; then, in order to justify the definition (28), they discussed that that advantage is approximated by the CS advantage.

In this paper, we focus on the circuit size.

Here, the support is the set of realizations that occur with positive probability.

Aslam, J.A.: Improving algorithms for boosting. In: Proceedings of the 13th Annual Conference on Computational Learning Theory, pp. 200–207 (2000)

Bader, C., Jager, T., Li, Y., Schäge, S.: On the impossibility of tight cryptographic reductions. In: Fischlin, M., Coron, J. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science, vol. 9666, pp. 273–304. Springer (2016). https://doi.org/10.1007/978-3-662-49896-5_10

Barak, B., Hardt, M., Kale, S.: The uniform hardcore lemma via approximate Bregman projections. In: Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1193–1200 (2009)

Bellare, M., Ristenpart, T.: Simulation without the artificial abort: Simplified proof and improved concrete security for Water’s IBE scheme. In: Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Lecture Notes in Computer Science, vol. 5479, pp. 407–424. Springer (2009). https://doi.org/10.1007/978-3-642-01001-9_24

Csiszár, I., Shields, P.C.: Information theory and statistics: a tutorial. Found. Trends Commun. Inf. Theory 1(4) (2004). https://doi.org/10.1561/0100000004

Diemert, D., Jager, T.: On the tight security of TLS 1.3: Theoretically sound cryptographic parameters for real-world deployments. J. Cryptol. 34(3), 30 (2021). https://doi.org/10.1007/s00145-021-09388-x

Dodis, Y., Impagliazzo, R., Jaiswal, R., Kabanets, V.: Security amplification for interactive cryptographic primitives. In: Reingold, O. (ed.) Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5444, pp. 128–145. Springer (2009). https://doi.org/10.1007/978-3-642-00457-5_9

van Erven, T., Harremoës, P.: Rényi divergence and Kullback-Leibler divergence. IEEE Trans. Inform. Theory 60(7), 3797–3820 (2014)MathSciNetCrossRef

Goldmann, M., Håstad, J., Razborov, A.: Majority gates vs. general weighted threshold gates. Comput. Complex. 2, 277–300 (1992)

10.

Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR lemma. Electronic Colloquium on Computational Complexity (March 1995)

11.

Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press (2001). https://doi.org/10.1017/CBO9780511546891, http://www.wisdom.weizmann.ac.il/%7Eoded/foc-vol1.html

12.

Goldreich, O.: On security preserving reductions - revised terminology. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Lecture Notes in Computer Science, vol. 6650, pp. 540–546. Springer (2011)

13.

Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security preserving amplification of hardness. In: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pp. 318–326. IEEE Computer Society (1990). https://doi.org/10.1109/FSCS.1990.89550

14.

Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR-lemma. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Lecture Notes in Computer Science, vol. 6650, pp. 273–301. Springer (2011). https://doi.org/10.1007/978-3-642-22670-0_23

15.

Götze, F., Sambale, H., Sinulis, A.: Higher order concentration for functions of weakly dependent random variables. Electron. J. Probab. 24(85), 1–19 (2019)MathSciNet

16.

Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput. 42(3), 1405–1430 (2013). https://doi.org/10.1137/100814421

17.

Hast, G.: Nearly one-sided tests and the Goldreich-Levin predicate. J. Cryptol. 17, 209–229 (2004)MathSciNetCrossRef

18.

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999). https://doi.org/10.1137/S0097539793244708

19.

Hatano, K., Warmuth, M.K.: Boosting versus covering. In: Advances in Neural Information Processing Systems. vol. 16 (2003)

20.

Hatano, K., Watanabe, O.: Learning $r$-of-$k$ functions by boosting. In: Proceedings of the 15th International Conference on Algorithmic Learning Theory, pp. 114–126 (2004)

21.

Herzberg, A., Luby, M.: Pubic randomness in cryptography. In: Brickell, E.F. (ed.) Advances in Cryptology - CRYPTO ’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings. Lecture Notes in Computer Science, vol. 740, pp. 421–432. Springer (1992). https://doi.org/10.1007/3-540-48071-4_29

22.

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

23.

Impagliazzo, R.: Hard-core distribution for somewhat hard problems. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’95), pp. 538–545 (1995)

24.

Kale, S.: Boosting and hard-core set constructions: a simplified approach (2007), electronic Colloquium on Computational Complexity (ECCC), Report No. 131

25.

Klivans, A.R., Servedio, R.A.: Boosting and hard-core set construction. Mach. Learn. 51, 217–238 (2003)CrossRef

26.

Lanzenberger, D., Maurer, U.: Direct product hardness amplification. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II. Lecture Notes in Computer Science, vol. 13043, pp. 605–625. Springer (2021)

27.

Lee, K.: Bit security as cost to demonstrate advantage. IACR Commun. Cryptol. 1(1) (2024). https://doi.org/10.62056/an5txol7

28.

Li, B., Micciancio, D., Schultz, M., Sorrell, J.: Securing approximate homomorphic encryption using differential privacy. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2022. Lecture Notes in Computer Science, vol. 13507, pp. 560–589. Springer (2022). https://doi.org/10.1007/978-3-031-15802-5_20

29.

Luby, M.: Pseudorandomness and cryptographic applications. Princeton University Press, Princeton computer science notes (1996)CrossRef

30.

Maurer, U., Tessaro, S.: A hardcore lemma for computational indistinguishability: Security amplification for arbitrary weak PRGs with optimal stretch. In: TCC 2010. Lecture Notes in Computer Science, vol. 5078, pp. 237–254. Springer (2010)

31.

Maurer, U.M., Tessaro, S.: Computational indistinguishability amplification: Tight product theorems for system composition. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5677, pp. 355–373. Springer (2009). https://doi.org/10.1007/978-3-642-03356-8_21

32.

Micciancio, D., Walter, M.: On the bit security of cryptographic primitives. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018. Lecture Notes in Computer Science, vol. 10820, pp. 3–28. Springer (2018). https://doi.org/10.1007/978-3-319-78381-9_1

33.

Morgan, A., Pass, R.: On the security loss of unique signatures. In: Theory of Cryptography. Theory of Cryptography, vol. 11239, pp. 507–536. Springer (2018). https://doi.org/10.1007/978-3-030-03807-6_19

34.

Myers, S.A.: Efficient amplification of the security of weak pseudo-random function generators. J. Cryptol. 16(1), 1–24 (2003). https://doi.org/10.1007/s00145-002-0007-1

35.

Schapire, R.E., Freund, Y.: Boosting: Foundations and Algorithms. MIT Press (2012)

36.

Schapire, R.E., Singer, Y.: Improved boosting algorithm using confidence-rated predictions. Mach. Learn. 37(3), 297–336 (1999)CrossRef

37.

Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Advances in Cryptography–CRYPTO ’13. Lecture Notes in Computer Science, vol. 8042, pp. 93–110. Springer (2013)

38.

Vadhan, S., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. STOC ’12, Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2213977.2214051

39.

Watanabe, S., Yasunaga, K.: Bit security as computational cost for winning games with high probability. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2021. Lecture Notes in Computer Science, vol. 13092, pp. 161–188. Springer (2021)

40.

Watanabe, S., Yasunaga, K.: Unified view for notions of bit security. In: Guo, J., Steinfeld, R. (eds.) Advances in Cryptology - ASIACRYPT 2023. Lecture Notes in Computer Science, vol. 14443, pp. 361–389. Springer (2023)

41.

Wegener, I.: The Complexity of Boolean Functions. Wiley (1991)

Title: Bit-Security Preserving Hardness Amplification
Authors: Shun Watanabe
Kenji Yasunaga
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_7

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"