Top

Published in:

2025 | OriginalPaper | Chapter

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

Authors : Daniele Micciancio, Mark Schultz-Wu

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

We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions, and facilitating their use. Specific contributions of this paper include: (1) identifying the optimal adversaries achieving the highest possible MW advantage, showing that they are deterministic and have a very simple threshold structure; (2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and (3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments and probability replacement theorems. On the technical side, our results are obtained by introducing a new notion of “fuzzy” distinguisher (which we prove equivalent to the “aborting” distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam metric, a standard quantity used in statistics.

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 Bit-Security Preserving Hardness Amplification

next chapter Low-Degree Security of the Planted Random Subgraph Problem

Various measures of cost have been considered, and the reader is referred to [2, Appendix B] for a discussion. For simplicity, in this paper we identify the cost of an attack with its running time.

This is justified by the fact that one can repeat the attack \(O(1/\epsilon )\) times to make the success probability arbitrarily close to 1.

This is at least for search (key recovery) and decision problems. The work [10] also proposes a more general definition based on information theory that interpolates between search and decision problems (e.g., encompassing password recovery problems with a polynomially large set of secrets,) but the corresponding notion of bit security for intermediate cases is largely unexplored. In this paper, we focus on the special case of decision problems which is the most relevant to cryptography. For search problems, the general bit-security definition of [10] reduces to \(\log _2 T_A/\epsilon _A\), which is standard, and is adopted in this paper too.

We believe that this is the case because we tend to give convexity for granted.

Here and elsewhere we use MW and WY as a shorthand for the number of bits of security as computed according to the respective definitions.

By co-domain we mean the set of possible outputs of the adversary, i.e., \(|\{0,1\}|=2\) for traditional distinguishers and \(|\{0,1,\bot \}|\) for aborting adversaries.

Specifically, the estimates are twice as high as the optimal, correct value. Recall that bit security (roughly) measures the exponent of the running time of the adversary. So, a multiplicative factor in bit security estimation is quite large.

This is most obvious when \(\Game \) is a game where A may issue an arbitrary number of calls to the game oracles.

This is syntactically different, but perfectly equivalent to the definition given in [10], which defines the advantage as \(\alpha _A\cdot (2\beta _A^* - 1)^2\), where \(\beta _A^* = \beta _A / \alpha _A\).

A transformation is simply a game \(\varGamma (\Game _b)\) with oracle access to \(\Game _b\). Applying \(\varGamma \) to a game \(\Game \) defines a new game \((\varGamma (\Game _0),\varGamma (\Game _1))\).

We recall that for a search problem, the output of \(A(\Game )\) is determined by the game \(\Game \).

When \(\sigma =0\), the confidence \(|\sigma |=0\) is zero, and the decision \(\textsf{sign}(\sigma )\) is irrelevant. For concreteness, we define \(\textsf{sign}(0) = 0\).

More precisely, \({\textsf{N}}[A]\) is the aborting adversary that runs the fuzzy attack \(a \leftarrow A(\Game _b) \in [-1,1]\), and then outputs \((1-\textsf{sign}(a))/2\) with probability \(\left| a\right| \) and \(\bot \) with probability \(1 - \left| a\right| \). Note that the output of \({\textsf{N}}[A]\) is always in \(\{0,1,\bot \}\), i.e., \({\textsf{N}}[A] \in \mathcal {A}_\bot \) is a valid aborting adversary.

Naturally, one could approximate these probabilities in a relatively efficient manner by repeatedly running \(A(x;r_i)\) on a given input x and many independent random \(r_i\). However, this would result in a randomized algorithm.

Note that turning \(\textsf{F}[A]\) into an aborting adversary \({\textsf{N}}[\textsf{F}[A]]\) using Lemma 10 does not work, because the result of \({\textsf{N}}\) is generally a randomized algorithm.

Similarly to the MW advantage \((\beta _A - \bar{\beta }_A)^2/(\beta _A + \bar{\beta }_A)\) and statistical distance \((\beta _A - \bar{\beta }_A)\), we define this function as a simple combination of \(\beta _A\) and \(\bar{\beta }_A\). We included the \((\beta _A - \bar{\beta }_A)\) factor so that the advantage measure retains the appealing feature that “trivial adversaries” (with \(\beta _A = \bar{\beta }_A\)) have advantage 0. Our definition is otherwise rather arbitrary.

The choice that \(A(x)=0\) when \(\left| \ell _\mathcal {X}(x)\right| =\tau \) is somehow arbitrary. We will use a threshold \(\tau \) such that \(\left| \ell _\mathcal {X}(x)\right| =\tau \) with probability 0.

Recall that the co-domain of A is the set of all possible outputs of A, e.g., \(\{0,1\}\) or \(\{0,1,\bot \}\).

This is a doubling of the number of security bits k, so it corresponds to overestimating the cost of the attack by an exponential factor \(2^k\).

This is indeed the optimal MW distinguisher when \(\epsilon \le 1/8\). When \(\epsilon \ge 1/8\), then \(A_{\textsf{SD}}^{\mathcal {X}}\) becomes optimal.

One can recover the exact same loss (\(\log _2 (2k^2) = 2 \log _2(\sqrt{2}k)\)) by giving a variant of Lemma 15 with constant factor 2 rather than 3. This can be done by comparing \(\textsf{adv}_{\mathcal {X}}^{\textsf{MW}}(A)\) to \(\varDelta _{\textsf{LC}}^2(X_0', X_1')\), where \(X_b'\in [0,1]^2\) is the first two coordinates of \(A(X_b)\in [0,1]^3\). This is to say that one can exactly generalize [10, Theorem 7] by working with \((X_0', X_1')\) that are positive measures of total mass \(\le 1\) rather than probability measures of total mass \(=1\). We avoid doing this as the quantitative improvement is small, at the cost of a large amount of conceptual overhead.

Recall from Definition 1 that \(T_\Game \) is the relative running time of \(\Game \). So, \(T_\Game = O(1)\) is quite common, e.g., when oracle calls can be answered in linear time.

Abla, P., Liu, F., Wang, H., Wang, Z.: Ring-based identity based encryption - asymptotically shorter MPK and tighter security. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part III. Lecture Notes in Computer Science, vol. 13044, pp. 157–187. Springer (2021). https://doi.org/10.1007/978-3-030-90456-2_6

Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: The power of free precomputation. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II. Lecture Notes in Computer Science, vol. 8270, pp. 321–340. Springer (2013). https://doi.org/10.1007/978-3-642-42045-0_17

De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and PRGs. In: Rabin, T. (ed.) Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6223, pp. 649–665. Springer (2010). https://doi.org/10.1007/978-3-642-14623-7_35

Grigoryan, N., Harutyunyan, A., Voloshynovskiy, S., Koval, O.: On multiple hypothesis testing with rejection option. In: 2011 IEEE Information Theory Workshop, pp. 75–79. IEEE (2011)

Lalitha, A., Javidi, T.: On error exponents of almost-fixed-length channel codes and hypothesis tests. arXiv preprint arXiv:2012.00077 (2020)

Lee, K.: Bit security as cost to observe advantage: Towards the definition from the book. Communications in Cryptology (2024). https://doi.org/10.62056/an5txol7

Levin, L.A.: Randomness and non-determinism. J. Symb. Log. 58, 1102–1103 (1993)

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, Part I. Lecture Notes in Computer Science, vol. 13507, pp. 560–589. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 15–18, 2022). https://doi.org/10.1007/978-3-031-15802-5_20

Micciancio, D., Walter, M.: Gaussian sampling over the integers: efficient, generic, constant-time. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 455–485. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_16CrossRef

10.

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

11.

Pensia, A., Jog, V., Loh, P.L.: Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities. IEEE Transactions on Information Theory (2023)

12.

Polyanskiy, Y., Wu, Y.: Information theory: From coding to learning. Book draft (2022)

13.

Suresh, A.T.: Robust hypothesis testing and distribution estimation in Hellinger distance. In: International Conference on Artificial Intelligence and Statistics, pp. 2962–2970. PMLR (2021)

14.

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, Part III. Lecture Notes in Computer Science, vol. 13092, pp. 161–188. Springer, Heidelberg, Germany, Singapore (Dec 6–10, 2021). https://doi.org/10.1007/978-3-030-92078-4_6

15.

Watanabe, S., Yasunaga, K.: Unified view for notions of bit security. In: Guo, J., Steinfeld, R. (eds.) Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part VI. Lecture Notes in Computer Science, vol. 14443, pp. 361–389. Springer (2023). https://doi.org/10.1007/978-981-99-8736-8_12

16.

Yasunaga, K.: Replacing probability distributions in security games via Hellinger distance. In: Tessaro, S. (ed.) 2nd Conference on Information-Theoretic Cryptography, ITC 2021, July 23-26, 2021, Virtual Conference. LIPIcs, vol. 199, pp. 17:1–17:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPICS.ITC.2021.17

Title: Bit Security: Optimal Adversaries, Equivalence Results, and a Toolbox for Computational-Statistical Security Analysis
Authors: Daniele Micciancio
Mark Schultz-Wu
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_8

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"