Chris Brzuska
email: chris.brzuska@aalto.fi

Geoffroy Couteau
email: geoffroy.couteau@ens.fr

Pihla Karanko
email: pihla.karanko@aalto.fi

Felix Rohrbach
email: felix.rohrbach@cryptoplexity.de

On Derandomizing Yao's Weak-to-Strong OWF Construction

The celebrated result of Yao (Yao, FOCS'82) shows that concatenating n • p(n) copies of a weak one-way function (OWF) f , which can be inverted with probability 1-1 p(n) , suffices to construct a strong OWF g, showing that weak and strong OWFs are black-box equivalent. This direct product theorem for hardness amplification of OWFs has been very influential. However, the construction of Yao is not security-preserving, i.e., the input to g needs to be much larger than the input to f . Understanding whether a larger input is inherent is a long-standing open question.

In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of a strong OWF g from a weak OWF f , which can be inverted with probability 1 -1 p(n) , the input size of g must grow as Ω(p(n)). By direct product construction, we refer to any construction with the following structure: the construction g executes some arbitrary pre-processing function (independent of f ) on its input, obtaining a vector (y1, • • • , y l ), and outputs f (y1), • • • , f(y l ). Note that Yao's construction is obtained by setting the pre-processing to be the identity. Our result generalizes to functions g with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong OWF hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense of having a very lossy post-processing of the outputs of f ).

On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak OWFs by evaluating the OWF along a random walk on an expander graph-the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak OWF.

Introduction

In this work, we continue the study of constructions of strong one-way functions (OWFs) from weak OWFs. The classical weak-to-strong hardness amplification technique, due to Yao [START_REF] Yao | Theory and applications of trapdoor functions[END_REF], uses direct product amplification which is not security preserving 1 . Our main result shows that the increase in the input size is inherent for direct product constructions. Namely, any direct product black-box construction of a strong OWF from a (1 -1/p(n))-weak OWF must have input length at least Ω(p(n)).

Weak and Strong

OWFs. An α(n)-secure OWF f : {0, 1} n → {0, 1} is an efficiently computable function such that any probabilistic polynomial-time adversaries A can invert f with probability at most α(n). When α is a negligible function, we say that f is a strong OWF; when α(n) = 1-1/p(n) for a polynomial p, we say that f is a weak OWF. The seminal work of Yao [START_REF] Yao | Theory and applications of trapdoor functions[END_REF] shows that weak OWFs imply strong OWFs, via a standard direct product hardness amplification: given a weak OWF f , define g(x 1 , ..., x l ) = f (x 1 )||...||f (x l ). Then, Yao proved that g is a strong OWF for l > |x i | p(|x i |).

Adaptive vs. Non-adaptive Construction. In this paper we study nonadaptive weak-to-strong OWF constructions, that is, constructions where the calls to the weak OWF can be made in parallel. I.e., a strong OWF construction g that makes calls to a weak OWF f is called non-adaptive if g's calls to f only depend on g's input, but not on the output of f on any of these inputs. Yao's construction is a simple, non-adaptive construction where each call to f is an independent chunk of the input. In general, non-adaptive constructions can make correlated calls to f though. g 1 (x) := f (x)||f (x + 1) g 2 (x) := f (f (x))

We say that a construction is adaptive, if the output of (at least) one call to f is used to determine the input to another f call. That is, adaptive constructions cannot compute all calls to f in parallel. For the toy constructions on the right, g 1 is non-adaptive (it does not matter whether g 1 computes f (x) or f (x + 1) first) and g 2 is adaptive (g 2 must make the inner f call first).

On the (in)efficiency of Yao's Construction. The construction of Yao is generic: it turns an arbitrary weak OWF f into a strong OWF g and just depends on the hardness of f . In addition, g has an appealing simple direct-product structure. In turn, g is suboptimal w.r.t. its computational complexity:

1. g makes a large number of calls to the underlying weak OWF, and 2. g is not security preserving, in that the input length of g is polynomially larger than the input length of f .

Many celebrated cryptographic reductions are similarly not security-preserving and have a high number of calls-the HILL construction of pseudorandom generator from any OWF being perhaps one of the most well-known examples [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF].

In beautiful works, a decade ago, Haitner, Reingold, Vadhan and Zheng [START_REF] Haitner | Efficiency improvements in constructing pseudorandom generators from one-way functions[END_REF][START_REF] Vadhan | Characterizing pseudoentropy and simplifying pseudorandom generator constructions[END_REF] developed rich tools for computational entropy, and improved the original n 8 seed length by HILL to O(n 3 ), where n is the input length of the OWF-since further improvements seem extremely hard to obtain, it is natural to ask whether large lower bounds on the input size are inherent. In a seminal result [START_REF] Impagliazzo | Limits on the provable consequences of one-way permutations[END_REF], Impagliazzo and Rudich [START_REF] Impagliazzo | Limits on the provable consequences of one-way permutations[END_REF] formalize the notions of black-box constructions/reductions, and develop methods to establish their limitations. Informally, a (fully) black-box construction of a primitive C from a primitive P treats both P and any adversary A against P in a black-box way. Following this breakthrough result, a long line of work (see [START_REF] Canetti | Amplifying collision resistance: a complexity-theoretic treatment[END_REF]8,[START_REF] Gennaro | Lower bounds on the efficiency of generic cryptographic constructions[END_REF][START_REF] Kim | Limits on the efficiency of one-way permutationbased hash functions[END_REF][START_REF] Lin | On hardness amplification of one-way functions[END_REF][START_REF] Lu | On the complexity of parallel hardness amplification for one-way functions[END_REF][START_REF] Lu | On the security loss in cryptographic reductions[END_REF][START_REF] Wee | One-way permutations, interactive hashing and statistically hiding commitments[END_REF]) has been devoted to proving limitations on the efficiency of black-box reductions. Our work continues this successful line of work.

To our knowledge, three previous works study black-box limitations on the efficiency of Yao's construction. Lin, Trevisan, and Wee [START_REF] Lin | On hardness amplification of one-way functions[END_REF] address the first of the two limitations above: they show that any fully black-box construction of an ε(n)-secure OWF from a (1δ(n))-secure OWF f must make at least q = Ω((1/δ) • log(1/ε)) calls to f . They also show that fully black-box construction cannot be perfectly security-preserving: if f has input size n, the input size of the strong OWF must be at least n + Ω(log 1/ε) -O(log q). The work of [START_REF] Lu | On the complexity of parallel hardness amplification for one-way functions[END_REF] showed that non-adaptive fully black-box construction (i.e., a construction where all the calls to f are made in parallel) cannot amplify security beyond poly(n) if the algorithm implementing the reduction has constant depth, and its size is below 2 poly(n) . Eventually, the work of [START_REF] Lu | On the security loss in cryptographic reductions[END_REF] extended the results of [START_REF] Lin | On hardness amplification of one-way functions[END_REF] to the weakly black-box setting with bounded non-uniformity.

On Security-Preserving Amplification of Weak OWFs

The above result leaves open one of the most intriguing limitations of Yao's construction: the fact that it causes a polynomial blowup in the input size. While [START_REF] Lin | On hardness amplification of one-way functions[END_REF] shows that some blowup in the input size is available, it leaves a huge gap: starting with a (1 -1/p(n))-secure OWF f with input length n, Yao's construction requires an input size n 2 • p(n) to build any strong OWF, while the result of [START_REF] Lin | On hardness amplification of one-way functions[END_REF] only shows that to build an extremely strong OWF, say a 2 -μ•nsecure OWF (for some constant μ), one needs input size at least (1+μ)•n-log p.

In a sense, the proof of [START_REF] Lin | On hardness amplification of one-way functions[END_REF] cannot do much better, because it also applies to the setting of regular one-way functions (where outputs have the same number of preimages), and rules out even adaptive fully black-box reductions. However, in this setting, it is actually known that we can do much better than Yao's construction and obtain an almost security-preserving construction, if we start from a regular weak OWF, and use adaptivity. Indeed, the work of [START_REF] Goldreich | Security preserving amplification of hardness[END_REF] provides precisely such a construction, using random walks on expander graphs. This leaves us in between two extremes: on the one hand, Yao's construction is non-adaptive (hence optimally parallelizable: if one starts with a parallelizable weak OWF, one ends up with a parallelizable strong OWF), extremely simple (it has a straightforward direct product structure) and works for arbitrary OWFs; however, it is not security-preserving. On the other hand, the construction of Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman [START_REF] Goldreich | Security preserving amplification of hardness[END_REF] is almost security-preserving, but is considerably more involved, requires adaptive calls, and works only for regular OWFs. Improving this state of affair is a long-standing and intriguing open problem.

Our Contribution

In this work, we make progress on this problem. Specifically, we show that any relativizing direct product black-box construction of strong OWF from a (1 -1/p(n))-secure OWF cannot be security preserving, in a strong sense: it requires an input length of at least Ω(p(n)). While this still leaves a gap with respect to Yao's construction, which has input length O(n 2 • p(n)), this gap vanishes asymptotically when p grows. By direct product construction, we mean a construction g of strong OWF with the following structure: on input x, g(x) outputs (f (y 1 ), • • • , f(y )), where f is the weak OWF, and (y 1 , • • • , y ) are computed from x arbitrarily, but without calling f (we call the mapping from x to (y 1 , • • • , y ) the pre-processing). This is a natural generalization of Yao-style constructions of strong OWFs (we recover Yao's construction by letting the preprocessing be the identity function). Furthermore, our result generalizes to the setting where some post-processing (independent of f ) is applied to the outputs (f (y 1 ), • • • , f(y )), whenever this post-processing is not too lossy: we prove that whenever each output of the post-processing has at most polynomially many preimages, the same Ω(p(n)) input length bound holds. We summarize the results in the following informal theorem: Theorem 1. Let f be a (1 -1/p(n))-secure OWF (a weak OWF). Let g be any non-adaptive construction, with not-too-compressing post-processing, of input length < cp(n), for certain constant c. Then, it is impossible to prove, in a relativizing fully black-box way, that g is a strong OWF.

Observe that if we could generalize our result to arbitrary (f -independent) post-processing functions, the above would capture all non-adaptive constructions. Hence, in essence, our result says the following: any (fully black-box) construction of strong OWF from a weak OWF must either (1) be very far from security preserving, or (2) use adaptivity, or (3) compute a highly non-injective function of the outputs of the non-adaptive calls (i.e., be very far from a "direct product" structure).

Relation to Correlated-Product and Correlated-Input Security

Usually, parallel concatenation of cryptographic primitives on independent inputs preserves security. For example, if f and g are one-way functions, then so is (x 1 , x 2 ) → (f (x 1 ), g(x 2 )). However, things might potentially change radically when x 1 and x 2 are not sampled independently, but are instead correlated, e.g., sampled jointly from a high min-entropy source. Variants of this problem have been studied on many occasions in cryptography, and have profound connections to the feasibility of cryptography with weak sources of randomness, leakage-resilient cryptography, related-key attacks, or deterministic encryption (to name a few); see e.g. [START_REF] Wichs | Barriers in cryptography with weak, correlated and leaky sources[END_REF] for discussions on cryptography with correlated sources. In addition, security for correlated inputs has proven to be a very useful assumption by itself: one-wayness under correlated product (i.e., one-wayness of f (x 1 ), • • • , f(x k ) for (x 1 , • • • , x k ) sampled from a joint distribution) has been used to build CCA secure cryptosystems [START_REF] Hemenway | Correlated product security from any oneway function[END_REF]30], and correlated-input secure hash functions have found numerous applications such as OT extension [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF], trapdoor hash function [7], constrained pseudorandom functions [START_REF] Attrapadung | Constrained PRFs for NC 1 in traditional groups[END_REF], passwordbased login [START_REF] Goyal | Correlated-input secure hash functions[END_REF], and many more.

A general and natural question to ask is: which type of constructions preserve hardness, when the inputs are jointly sampled from a high min-entropy source, rather than being sampled independently? This is a fundamental question in itself, because this setting occurs in real-life use of standard cryptographic construction (when they are misused, when the source of randomness is imperfect, or when the adversary has access to some leakage on the inputs), but also due to the many applications outlined above.

It is well-known that not all constructions will preserve security under correlated inputs. For example, even though the map x → x e mod n is believed to be one-way when n is a product of two large safe primes (this is the RSA assumption), the extended euclidean algorithm provides an efficient inverter for the map x → (x e1 , x e2 ) mod n whenever gcd(e 1 , e 2 ) = 1 (this example is taken from [START_REF] Hemenway | Correlated product security from any oneway function[END_REF]). Hence, there are specific functions f i (here, f i : x → x ei ) and specific correlations of the inputs (here, the equality correlation: the same input x is used for all functions) such that correlated-product security breaks down. However, this leaves open the possibility that some specific input correlations preserve correlated-product security (for example, this is the case when the correlatedinputs are indistinguishable from random, e.g. when sampled as the output of a PRG), or that some specific functions maintain correlated-product security for general correlations.

Our results can be cast in the context of correlated-product security: we show that even though Yao's construction of OWF, which is a very natural and seminal construction, is provably secure (with a black-box proof) when used with random and independent inputs, it breaks down for any possible correlated source, whenever the entropy of the source is below p(n). This provides a natural example of a construction, from a weak OWF f , where correlatedproduct security cannot be generically shown to hold (in a black-box way) for arbitrary sources, unless they contain enough entropy such that all of the correlated inputs can have independent entropy. In contrast, [30] shows that when f is instantiated as a lossy trapdoor function, then f (x 1 ), • • • , f(x k ) is one-way for correlated inputs (x 1 , • • • , x k ), and [START_REF] Hemenway | Correlated product security from any oneway function[END_REF] shows that assuming OWFs, there exists a correlated-product secure function. Our results provide a partial complementary perspective to this line of work.

Comparison to [START_REF] Wichs | Barriers in cryptography with weak, correlated and leaky sources[END_REF]. Wichs [START_REF] Wichs | Barriers in cryptography with weak, correlated and leaky sources[END_REF] also studies, among other questions, the onewayness of constructions of the form (f (x 1 ),

• • • , f(x k )) for inputs (x 1 , • • • , x k )
sampled from a correlated source. Our results are incomparable: we show that for a generic weak OWF f , and for any fixed distribution over the inputs (x 1 , • • • , x k ) with o(k) bits of entropy, the one-wayness of f (x 1 ), • • • , f(x k ) does not follow from that of f in a black-box way. In contrast, [START_REF] Wichs | Barriers in cryptography with weak, correlated and leaky sources[END_REF] shows that for an arbitrary function f , there is no black-box reduction (to any standard hardness assumption) of one-wayness of (f (x 1 ), • • • , f(x k )) when the x i can come from arbitrarily correlated distributions, even with high per-input entropy. That is, [START_REF] Wichs | Barriers in cryptography with weak, correlated and leaky sources[END_REF] handles a considerably larger class of constructions and reductions to many possible assumptions, but only rules out a much more stringent security notion (where one-wayness must hold even when the input distributions are not fixed a priori and can be correlated arbitrarily).

Related Works

We already pointed out to numerous related works on bounding the efficiency of black-box reductions [START_REF] Canetti | Amplifying collision resistance: a complexity-theoretic treatment[END_REF]8,[START_REF] Gennaro | Lower bounds on the efficiency of generic cryptographic constructions[END_REF][START_REF] Kim | Limits on the efficiency of one-way permutationbased hash functions[END_REF][START_REF] Lin | On hardness amplification of one-way functions[END_REF][START_REF] Lu | On the complexity of parallel hardness amplification for one-way functions[END_REF][START_REF] Lu | On the security loss in cryptographic reductions[END_REF][START_REF] Wee | One-way permutations, interactive hashing and statistically hiding commitments[END_REF], including some specifically targeting hardness amplifications of one-way functions, and related works on correlated-product security. Besides, our black-box separations use some established tools (in addition to key new technical insights, which we cover afterwards) such as the two-oracle technique of [START_REF] Hsiao | Finding collisions on a public road, or do secure hash functions need secret coins?[END_REF][START_REF] Simon | Finding collisions on a one-way street: can secure hash functions be based on general assumptions?[END_REF] where one oracle implements the base primitive and the second oracle breaks all constructions built from this primitive. We use Borel-Cantelli style technique from [START_REF] Mahmoody | A note on black-box separations for indistinguishability obfuscation[END_REF] to extract a single oracle from a distribution of random oracles analogously to the seminal work on black-box separations by Impagliazzo and Rudich [START_REF] Impagliazzo | Limits on the provable consequences of one-way permutations[END_REF].

Hardness amplification of functions, via direct products and related constructions, have a rich and dense history, which goes well beyond one-way functions and is too vast to be covered here. In particular, amplifying the hardness of computing boolean functions (rather than inverting functions) using direct product constructions is at the heart of rich lines of work on worst-case to average-case reductions, constructions of non-cryptographic pseudorandom generators, circuit lower bounds, and many more -see e.g. [START_REF] Babai | Non-deterministic exponential time has twoprover interactive protocols[END_REF][START_REF] Babai | BPP has subexponential time simulations unlessexptime has publishable proofs[END_REF][START_REF] Goldreich | On yao's xor lemma[END_REF][START_REF] Healy | Using nondeterminism to amplify hardness[END_REF]18,[START_REF] Impagliazzo | P = BPP if E requires exponential circuits: derandomizing the XOR lemma[END_REF][START_REF] Lipton | New directions in testing[END_REF][START_REF] Shaltiel | Hardness amplification proofs require majority[END_REF][START_REF] Sudan | Pseudorandom generators without the XOR lemma[END_REF][START_REF] Trevisan | List-decoding using the XOR lemma[END_REF][START_REF] Trevisan | On uniform amplification of hardness in NP[END_REF][START_REF] Viola | The complexity of constructing pseudorandom generators from hard functions[END_REF]] and references therein.

Technical Overview

To prove our black-box separations, we exhibit an oracle relative to which there is a weak one-way function, yet all strong one-way functions with an appropriate structure can be inverted efficiently with constant probability. The standard method to do so is to design oracles relative to which the starting primitive (here, the weak one-way function) clearly exists and is the only possible source of hardness. For example, in the seminal work by Impagliazzo and Rudich (IR) on the separation of key exchange from OWFs [START_REF] Impagliazzo | Limits on the provable consequences of one-way permutations[END_REF], IR introduce a random oracle, which is a strong OWF with high probability, as well as assuming P = NP, thereby ruling out most other (stronger) cryptographic primitives. In our setting, we instantiate this intuition by choosing three oracles:

(1) A PSPACE oracle, which destroys all possible sources of hardness, (2) a random oracle F, which instantiates the weak OWF, and (3) an inverter INV, which inverts F on a (roughly) 1 -1/p fraction of its inputs, effectively turning it into a weak OWF. Note that a random oracle F alone would already be a strong OWF, if we did not weaken it by adding INV. In this oracle world, we consider non-adaptive constructions of strong OWFs g from the weak OWF F. Since we wish to rule out (relativizing) fully black-box reductions (as defined by Reingold, Trevisan and Vadhan [START_REF] Reingold | Notions of reducibility between cryptographic primitives[END_REF]), we do not give g access to INV. In fact, this is inherent in our setting: observe that given access to INV, it is not too hard to build a strong OWF (e.g. the strong OWF can perform a random walk starting from the input x, until it lands on a hard input y -which can be tested using INV -and outputs F(y)). In general, whenever one can efficiently test which inputs are hard, constructing a security-preserving OWF becomes feasible -and it is precisely the lack of any such tester that makes it highly nontrivial to improve over Yao's seminal construction. Since we rule out fully black-box reductions, we do not let g access INV and thus, g does not know where the easy inputs are.

Modeling Non-adaptive Constructions. Nonadaptive construction can be thought of as a circuit which first has a pre-processing layer, followed by a layer of parallel calls to a weak OWFs and then some post-processing, see Fig. 1. When the construction omits the post-processing layer, as in Yao's construction, this corresponds to a direct product construction. The input size n of the construction might be different from the input size m of the weak OWF. As a starting point, we consider what happens when the construction does not use any post-processing, as is the case in Yao's construction. When there is no postprocessing, the additional data d in Fig. 1 only reduces the input domain and does not add any security. Thus, w.l.o.g., we assume that there is no d.

Inverting Direct Product Constructions. Considering the simple case with no post-processing and no d, the first observation is that g must make more than p(m) calls to the weak OWF, since otherwise all the calls will be easy to invert with constant probability. In that case the adversary could simply invert all the weak OWF calls and then use PSPACE to invert the pre-processing layer, thus inverting g with constant probability. Now that g makes at least p(m) calls to the weak OWF, we can make the main observation of the paper: if we can invert a 1 -1/p(m) fraction of the weak OWF calls and n is slightly smaller than p(m), then the remaining entropy of the input s cannot be very high, on the average. This is formalized in Lemma 21. This is because the number of calls to the weak OWF is at least the same order of magnitude as the length of the input to the strong OWF. Hence, there is not enough entropy in the strong OWF input to distribute among all the weak OWF calls, so most of the calls will end up having very little entropy of their own, i.e. entropy that is not shared with other calls. Now the probability that an adversary can indeed invert a 1-1/p(m) fraction of the weak OWF calls is high, since that is the expected fraction of easy calls. Since the entropy of the input s is low, given the easy calls, and the adversary has the PSPACE oracle, the adversary can guess s with high probability. Note that low entropy alone is not enough to guess s, since inverting pre-processing might be inefficient, hence we also need PSPACE.

To summarize, we know that there must be many calls to the underlying weak one-way function-and since we can also show that each of them must have a non-trivial amount of entropy (i.e., information about the input)-we can show that we can invert all non-adaptive constructions without post-processing, unless n is larger than a small constant times p(m), establishing the first lower bound on the randomness efficiency of non-adaptive constructions. Note that Yao's construction consumes n = m 2 p(m) many bits.

On Strong OWFs with Injectiveish Post-processing. We sketched above why constructions without post-processing (direct product constructions) cannot be strongly one-way. It is relatively easy to extend the above argument to constructions with not too lossy post-processing, i.e., constructions where any output of the post-processing has at most polynomially many preimages: the inverter chooses a uniformly random value amongst the (polynomial size) list of all possible preimages of the post-processing, and applies the previous inversion attack on the candidate. It then succeeds with probability 1 poly times the success probability of the previous attack.

Relation to Threshold Secret Sharing

The pre-processing pre in Fig. 1 is conceptually similar to a threshold secret sharing scheme, where the participants' shares correspond to the values x i and the secret together with the dealer's randomness corresponds to the strong OWF input s. On average, we learn the 'shares' of all but a 1 p(m) fraction of the 'participants'. So effectively, we are interested in how long the secret and the dealer's randomness together must be in a (1 -1 p(m) + )-threshold secret sharing scheme. The difference is that we allow a negligible failing probability for the secret sharing scheme and we do not distinguish which part of the input is the secret and which part of the input is the randomness of dealer in the secret sharing scheme.

To make the intuition concrete, our result can be formulated as a result on the threshold achievable by any deterministic threshold secret sharing schemes with short secret. Definition 2 (Deterministic Threshold Secret Sharing Scheme). We say that function S : {0, 1} n → ({0, 1} m ) l (i.e. S outputs l bitstrings of length m) is (l, t)-deterministic threshold secret sharing scheme if for all adversaries A:

Pr π ← $ permutations of (1,...,l),x ← $ {0,1} n x ←$ A(S(x) π(1) , ..., S(x) π(t) ) ≤ negl(n),
where S(x) i denotes the ith share, i.e., the ith length n bitstring of the output of S. The secret length n should be polynomial in the share length m (hence, negligible in n is also negligible in m).

Note that any threshold secret sharing scheme can be made deterministic by considering the randomness as part of the secret -but then the randomness must be counted towards the secret length. The fact that Definition 2 uses probability over permutations of the shares only makes the definition cover a larger class of schemes, in particular, a scheme that is secure for all permutations is also secure by Definition 2.

Also, notice that Definition 2 relies on a very weak hiding notion: no subset of size less than t should be able to fully recover the secret (except with negligible probability). This sets our result apart from most known bounds on secret sharing, which apply to the indistinguishability setting.

In this language, our result states the following: let m be the share length and p be any polynomial. Consider any candidate (l, t)-threshold deterministic secret sharing scheme with t ≥ (1 -1/p(m)) • l, now the scheme must have secret size n > p(m)/c, for a certain constant. For traditional (l, t)-threshold secret sharing schemes, this means that the combined length of the secret and the randomness used by the scheme must be > p(m)/c, if t ≥ (1 -1/p(m)) • l. Naturally, in order to this result being meaningful, the number of shares l should be bigger than the polynomial p(m).

The result follows from our main conceptual Lemma 21, which effectively states that the expected entropy of the remaining shares, when you know (1 -1/p(m)) fraction of the shares, is small. Hence, the remaining shares can be guessed with non-negligible probability.

Our result stays the same even if we change Definition 2 to cover only efficient, i.e. probabilistic polynomial time, adversaries A, provided that the scheme S is such that you can compute the secret in polynomial time, when you know all the shares. That is, we even rule out computational security if t ≥ (1-1/p(m))•l and n < p(m)/c.

More precisely, let us change the Definition 2 to a definition that covers an even larger class of schemes (the difference to Definition 2 is high-lighted in pink) and subsequently state our result in the secret-sharing terminology.

Definition 3 (Computational Deterministic Threshold Secret Sharing Scheme).

A function S : {0, 1} n → ({0, 1} m ) l (i.e. S outputs l bitstrings of length m) is (l, t)-computational deterministic threshold secret sharing scheme if for all probabilistic polynomial time adversaries A:

Pr π ← $ permutations of (1,...,l),x ← $ {0,1} n x ←$ A(S(x) π(1) , ..., S(x) π(t) ) ≤ negl(n),
where S(x) i denotes the ith share, i.e., the ith length n bitstring of the output of S. The secret length n should be polynomial in the share length m. The function S -1 should be computable in polynomial time.

Theorem 4 (Threshold Secret Sharing View). Fix a large enough m and a polynomial p. Consider a computational deterministic threshold secret sharing scheme where -the dealer has an n bits secret; -there are l participants, each getting a share of length m; -the threshold t satisfies t ≥ (1 -1 p(m) )l.

Then the secret must be long: n > 1 c p(m), where c is some constant. Blundo, Santis, Vaccaro [5] discuss the minimum amount of randomness needed by an information theoretically secure secret sharing scheme. They prove that if the secret length is m and there are l participants, then the dealer needs to use l • m bits of randomness (to choose both the secret and the participants' shares). This is the same as the analogous number in Yao's weak to strong OWF construction (when number of weak OWF calls is l > mp(m), we use lm input length) and it is close to the analogous number that we get in this paper (input length to strong OWF needs to be O(p(m)), i.e. there is m 2 gap between our result and Yao's).

It is intuitive that some gap should exist between the information theoretically secure secret sharing scheme and our more relaxed "mostly secure secret sharing scheme", where the adversary is allowed to learn part of the secret as long as they cannot learn the whole input and additionally, the adversary is only allowed to run in polynomial time. However, the two secret sharing schemes are not really comparable (because we do not distinguish between randomness and secret) and a better lower bound, than what we present, might be possible.

Preliminaries

Definition 5 (One-Way Functions). Let f : {0, 1} * → {0, 1} * be a polynomial-time computable function. f is called a (strong) one-way function (OWF), if for every probabilistic polynomial-time algorithm A there exists a negligible function : N → [0, 1] such that for every n,

Pr A,x←{0,1} n A(1 n , f(x)) ∈ f -1 (f (x)) ≤ (n).
Further, f is called a weak one-way function, if there exists a polynomial p(n) such that for every probabilistic polynomial-time algorithm A there exists a N 0 ∈ N such that for all n ≥ N 0 :

Pr A,x←{0,1} n A(1 n , f(x)) ∈ f -1 (f (x)) ≤ 1 - 1 p(n) .
In this case we sometimes say that f is a p-weak OWF.

Definition 6 (Oracle Algorithms).

The complexity of an oracle algorithm (e.g., Turing Machine) is the number of steps it makes, where an oracle query is counted as one step.

In particular, a probabilistic polynomial-time (PPT) oracle algorithm makes at most polynomial queries. Since our oracle algorithms have access to a PSPACE oracles, we usually limit the discussion to the number of oracle calls the algorithm makes.

We use the following Borel-Cantelli style theorem from [28, Lemma 2.9].

Theorem 7 Let (E 1 , E 2 , ...) be a sequence of events such that ∃c ∀m ∈ N :

Pr[E m ] ≥ c
, where c is a constant strictly between 0 and 1. Then,

Pr ∞ k=1 m>k E m ≥ c (1)

Entropy Toolbox

Throughout this paper, the term entropy refers to Shannon entropy which satisfies a chain rule.

Definition 8 (Shannon Entropy). Let X be a random variable and let dom(X) be its domain, then

H(X) := - z∈dom(X) Pr[X = z ] • log 2 (Pr[X = z ]),
is the Shannon entropy of X.

Lemma 9 (Chain Rule for Entropy). Let X 1 , . . . , X n be random variables.

Then the following holds

H(X 1 , . . . , X n ) = H(X 1 ) + H(X 2 |X 1 ) + • • • + H(X n |X 1 , . . . , X n-1 ).
We use also other simple but useful properties of entropy. In particular, Definition 8 implies that entropy is non-negative. Also, the entropy H(X) of a random variable X is always more or equal to the entropy H(f (X)) of the random variable f (X) for any deterministic function f -if f is injective, the entropy is preserved, if f is not injective, it decreases. Finally, for any three random variables X, Y, Z, we have that H(X|Y ) ≥ H(X|Y, Z), i.e., conditioning on additional information maintains or decreases the entropy of a random variable.

Main Results

In this section, we introduce different types of constructions of strong OWF from weak OWF which we study in this paper (Sect. 3.1) and state our main theorems (Sect. 3.2). In particular, we introduce non-adaptive constructions, nonadaptive constructions without post-processing and non-adaptive constructions with injectiveish post-processing.

Black-Box Constructions and Reductions Definition 10 (Non-adaptive).

A construction g = (pre, post) from a weak one-way function F is non-adaptive, if it computes its output as post(F(pre(s))) (see Fig. 1). The number of queries l is induced by pre. (n, m)-NA denotes a non-adaptive construction with input length n based on a weak OWF F whose input length is m. Definition 11 (Non-adaptive, no post-processing construction). We say that a construction g = (pre, post) is a (n, m)-NANPP, if it is (n, m)-NA and the post-processing function is the identity function, i.e., post(y 1 , ..., y l , d) := y 1 ||..||y l ||d.

Definition 12 (Non-adaptive, injectiveish post-processing constr). We say that a construction g = (pre, post) is a (n, m)-NAIPP, if it is (n, m)-NA and the post-processing function is almost injective, that is, every image of post has at most a polynomial (in n) number of preimages.

Note that the identity function is injective and thus, in particular, is injectiveish. Therefore, every NANPP is also a NAIPP, but the converse does not hold. Likewise, both NANPP and NAIPP are NA constructions, but the converse does not hold. Since we are interested in ruling out negative results, whenever we rule out NAIPP, we also rule out NANPP.

We formalized the kind of constructions our negative results capture, and now specify which type of reduction proofs our theorems rule out. Namely, our results concern BBB-style proofs following the notation of [START_REF] Baecher | Notions of black-box reductions, revisited[END_REF] or fully black-box proofs following the notation of [START_REF] Reingold | Notions of reducibility between cryptographic primitives[END_REF]. Since we consider parametrized definitions, we here state a customized version of fully black-box security which precisely captures the quantifiers our negative results capture.

Definition 13 (Fully Black-Box Proof ). We say that a proof that weak OWF implies strong OWF is fully black-box if it establishes a relativizing statement of the following type:

∀poly p, ∃ poly-time computable g, ∀poly q, ∃P P T R ∀p-weak OWF F, A :

if Pr x ← $ {0,1} n g F (A(1 n , g F (x))) = g F (x) > 1 q(n) for inf. many n ∈ N then Pr x ← $ {0,1} n F(R A,F (1 n , F(x))) = F(x) > 1 -1 p (n) for inf. many n ∈ N.
In this case, we also refer to the construction g as fully black-box.

Note that typically, in the definition of fully black-box, the pink parts are omitted. That is, the polynomial p is considered as part of the definition of F and the polynomial q is considered as part of the definition of A (i.e. the adversary's success probability). We allow the construction g to depend on the polynomial p and the reduction R to depend on q, since we seek to cover a larger and meaningful class of proofs. In particular, Yao's original proof building strong OWFs from weak OWFs is fully black-box in the sense of Definition 13, but would not be covered if the construction were now allowed to depend on p or if the reduction were not allowed to depend on q.

Theorems

We now state our main theorems, all of which rely on the two-oracle technique. Namely, we construct a distribution over oracles (O 1 , O 2 ) such that O 1 will be a weak one-way function and O 2 will help to invert the strong one-way function. Since we rule out black-box reductions rather than provide an oracle separation, only the reduction has access to the oracle O 2 while the construction does not (cf. Section 1.5). Note that in Corollary 16, we extract a single oracle from the oracle distribution, using the Borel-Cantelli style argument Theorem 7. However, we prefer to state our theorem in terms of oracle distributions since this more closely matches the technical core arguments of our separation results.

Theorem 14 (NANPP Impossibility). ∃ constant c such that ∀poly p, ∀(n, m)-NANPP g with input length

n ≤ 1 c p(m), ∃ poly-query A, ∃poly q(n) = n c , c ∈ N + , ∀PPT R, ∃ distribution D over pairs of oracles (O 1 , O 2 ): Pr (O1,O2) ← $ D Bad R,A,g m = constant < 1
where Bad R,A,g m is an indicator variable that is 1 iff at least one of the following is true:

1. Weak OWF breaks:

Pr x ← $ {0,1} m ,R R A O 1 ,O 2 ,O1,O2 (1 m , O 1 (x)) ∈ O -1 1 (O 1 (x)) ≥ 1 -1 p(m) . 2. Strong OWF is secure-ish: Pr s ← $ {0,1} n ,A A O1,O2 (1 n , g O1 (s)) ∈ (g O1 ) -1 (g O1 (s)) ≤ 1 q(n) .
We emphasize that in the definition of the bad event, the oracles are fixed and the randomness is taken only over the sampling of x as well as the internal randomness of A and R, respectively.

Theorem 15 (NAIPP Impossibility). ∃ constant c ∀poly p, ∀(n, m)-NAIPP g with input length

n ≤ 1 c p(m), ∃ poly-query A, ∃poly q(n) = n c , c ∈ N + , ∀PPT R, ∃ distribution D over pairs of oracles (O 1 , O 2 ): Pr (O1,O2) ← $ D Bad R,A,g m = constant < 1
where Bad R,A,g m is the same indicator variable as in Theorem 14.

We use the same oracle distribution for Theorem 15 and Theorem 14, see Sect. 4. Theorem 15 implies Theorem 14, so it would suffice to prove Theorem 15. However, we found the presentation to be easier to follow when presenting the proof of the weaker Theorem 14 first (Sect. 5.2) and then discussing the generalization to the proof of Theorem 15 (Sect. 6). For both theorems, we prove that relative to O 1 , O 2 , oracle O 1 is a weak OWF. Before proving the theorems for oracle distributions, we now use the strengthened Borel-Cantelli lemma by Mahmoody, Mohammed, Nematihaji, Pass and Shelat [START_REF] Mahmoody | A note on black-box separations for indistinguishability obfuscation[END_REF] to extract a single oracle from the distribution where the bad event happens with constant probability, as opposed to less than 1/m 2 required by standard Borel-Cantelli.

Corollary 16 (Main). There is no fully black-box (n, m)-NAIPP construction of a OWF from a p(m)-weak OWF with n ≤ 1

c p(m), where c is some constant. Proof. Recall that a black-box proof means the following: ∀poly p, ∃ poly-time computable g, ∀poly q, ∃PPT R ∀p-weak OWF F, A :

(A inverts g) ⇒ (R A inverts F) Formally: Pr x ← $ {0,1} n g F (A(1 n , g F (x))) = g F (x) > 1 q(n) for inf. many n ∈ N ⇒ Pr x ← $ {0,1} n F(R A,F (1 n , F(x))) = F(x) > 1 -1 p (n) for inf. many n ∈ N
In order to rule out a black-box proof, we thus define an oracle O 1 (and an oracle O 2 helping the adversary) such that the following holds:

∀poly p, ∀ poly-time g O1 , ∃poly q, ∀PPT R O1,O2 ∃A O1,O2 , ∃O 1 , O 2 : A breaks g O 1 , but R does not p-invert O 1 . Formally: Pr x ← $ {0,1} n g O1 (A O1,O2 (1 n , g O1 (x))) = g O1 (x) > 1 q(n) for inf. many n ∈ N. Pr x ← $ {0,1} n O 1 (R A,O1,O2 (1 n , O 1 (x))) = O 1 (x) < 1 -1 p (n) for all but finitely many n ∈ N.
In order to rule out a fully black-box reduction, we would only need to show that statement with the pink universal quantifier being replaced by existential quantifier. However, proving the statement for all polynomials p is stronger without making the proof more complicated. Now, let us fix a polynomial p, a candidate NAIPP g, a polynomial q (s.t. it satisfies Theorem 15) and a candidate reduction R and show the existence of an adversary and a p-weak OWF F.

By Theorem 15, there is an oracle distribution over pairs (O 1 , O 2 ), and an adversary A such that the probability of the bad event Bad R,A,g m is constant in m. We show that there exists a fixed oracle pair (O 1 , O 2 ) for which the bad event Bad R,A,g m in Theorem 15 happens only for finitely many m. From that it follows that there is a fixed oracle pair for which A O1,O2 breaks the candidate strong OWF g O1 infinitely many often, but the reduction R A O 1 ,O 2 inverts the weak OWF O 1 well enough at most on finitely many m. Thus, it suffices to show via Theorem 7, that Theorem 15 implies that there is an oracle relative to which Bad R,A,g m happens only for finitely many m. By Theorem 15, we have

Pr (O1,O2) ← $ D Bad R,A,g m = constant < 1.
Hence, the constant probability version of Borel-Cantelli (Theorem 7) yields

Pr (O1,O2) ← $ D ∞ m=1 m>k Bad R,A,g m = constant < 1,
which means that, with constant probability, there is a k for which no m > k satisfies Bad R,A,g m . Taking such an oracle pair (O 1 , O 2 ) concludes the proof of Corollary 16.

Oracle Distributions

In this section, we define the oracle (distribution)s we rely on. Firstly, a PSPACE creates a world where no one-way functions exist. Then, we add an oracle (distribution) F in order to create a world where weak one-way functions exist, and finally, we add an oracle (distribution) O 2 which breaks NANPP and NAIPP constructions. The adversary will have access to O 2 , PSPACE and F while the candidate strong OWF construction only has access to PSPACE and F, but not to O 2 . We recall from Sect. 1.5 that it is necessary to not give the construction access to the information which parts of F are easy and which parts are hard, and not giving the construction access to O 2 is related to this necessary restriction, since the adversary (modeled by O 2 ) uses the information of which parts are easy. On a technical-conceptual level, it is meaningful to not give the construction access to the adversary (modeled by O 2 ), since the adversary is inefficient, while the construction is efficient (in this (oracle) world where all algorithms have access to PSPACE and F). We consider an inefficient adversary since we rule out black-box reduction which work for any black-box adversary that breaks the strong OWF, including inefficient ones.

As mentioned before, we denote our adversary by O 2 . We encode the pair of oracles PSPACE and F into a single oracle O 1 so that we are aligned with the terminology of a two-oracle separation result (and this is also convenient notation in the proof).

F(x) m ← |x| y ← Πm(x) return y INV(y) m ← |y| if y ∈ EASY m out return F -1 (y) else return ⊥
Here, we use EASY m out := Π m (EASY m in ).

Remark. Throughout this paper we treat (1-1/p(m))2 m as an integer, omitting the ceil function since the difference is negligible and does not affect our proofs.

Proof of Theorem 14

We split the proof of Theorem 14 into two parts. We first show that the probability of Case 1 (weak OWF breaks) of the bad event introduced in Theorem 14 is smaller than any constant (Sect. 5.1), and then we show that the probability of Case 2 (strong OWF is secure-ish) of the bad event introduced in Theorem 14 is a small constant (Sect. 5.2). Recall that both probabilities are (only) over the sampling of the oracles O 1 and O 2 .

R A is Not a Successful Weak OWF Inverter

In this section, we show that the probability (over the oracle distributions) that F is not a 2cp(m)-weak OWF is small.

Theorem 18 (F is Weak OWF). For all constants c, for all polynomials p, for all poly-query A F,PSPACE,INV , for all adversaries R making polynomially many (in m) queries to the oracles F, PSPACE, INV, A F,PSPACE,INV ,

Pr F,PSPACE,INV ← $ Dp SuccInv F,PSPACE,INV A,R ≥ 1 - 1 2cp(m) ≤ 1/c where SuccInv F,PSPACE,INV A,R
is defined as

Pr x ← $ {0,1} m ,R R F,PSPACE,INV,A F,PSPACE,INV (1 m , F(x)) ∈ F -1 (F(x)) .
When we define p(m) := 1 2c p(m), the above is equivalent to We prove Theorem 18 in Appendix B.

Pr (O1,O2) ← $ D Case 1 of Bad R,A,g m ≤ 1/c,

A is a Successful Strong OWF Inverter

We prove that an adversary with access to the oracles F, INV and PSPACE (cf. Sect. 4), can break all short input NANPP constructions which have access to F and PSPACE only.

Theorem 19 (Inverting OWF Candidate). ∀ poly p, ∀(n, m)-NANPP g with input length

n ≤ 1 4 p(m), ∃ poly-query A F,INV,PSPACE , ∃constant c > 0 s. t. Pr (F,INV) ← $ Dp Pr s, coins of A A F,INV,PSPACE inverts g(s) ≤ c = constant < 1

This implies that

Pr (O1,O2) ← $ D Case 2 of Bad R,A,g m = constant < 1 where D := D p , O 1 := F, PSPACE, O 2 := INV and Bad R,A,g m is defined as in Theorem 14.
For the proof of Theorem 19, let p(m) be a fixed polynomial. We start by showing that Theorem 19 holds for constructions which make few queries. More precisely, we show that no matter what the input length to g is, g must make at least l > cp(m) calls to F, otherwise all the F calls are easy with constant probability, which makes inverting g trivial.

Proposition 20 (Easy inversion if few F-Calls). Consider a NANPP g = (pre, post) (where we recall that post(y 1 , .., y l , d) = y 1 ||..||y l ||d). For all constants c, if pre(s) = (x 1 , .., x l , d) induces at most l ≤ cp(m) (parallel) calls to F, then all y i := F(x i ) are in EASY m out with constant probability, more precisely

Pr F ← $ Dp [Pr s [∀y i ∈ g(s) : y i ∈ EASY m out ] > constant > 0] > constant > 0 (2)
In particular, with constant probability over the choice of the oracle F, g can be inverted with non-negligible (constant) probability by a poly-query adversary.

Proof. Suppose there are l ≤ cp(m) parallel calls to F. Denote by y 1 , ..., y l the outputs of the parallel calls to F. Now, when considering the randomness of choosing EASY m in , we have

Pr F ← $ Dp,s [y 1 , ..., y l ∈ EASY m out ] ≥ s 2 -|s| =1 Pr F ← $ Dp [y 1 ∈ EASY m out | s ] • ... • Pr F ← $ Dp [y l ∈ EASY m out | s ] = 1 - 1 p(m) l ≥ 1 - 1 p(m) cp(m) ≥ 1 4 c ∀ p(m) > 2.
where the first inequality is an equality iff y i = y j ∀i = j and the second inequality follows since (1 -1 x ) x converges monotonously to 1 e and is greater than In the case where all y 1 , ..., y l are all easy, A can invert y 1 , ..., y l using INV oracle. Note that there is only a single pre-image x i per y i and thus, given the list x 1 , ..., x l , A can use the PSPACE oracle to find an s such that pre(s) = x 1 , ..., x l .

Due to Proposition 20, for the remainder of this section, we can focus on constructions where pre makes more than c • p(m) calls. Also in the case where g makes many queries, we can always invert the easy fraction of (y 1 , .., y l ). However, if many queries are made, then (with high probability) some y i will also be hard. Of course, if pre-processing pre(s) = (x 1 , .., x l ) distributes the entropy well, then knowing some of the x i might suffice to restrict the set of suitable candidate values s to a polynomial-sized set, and once a polynomial-sized set of candidates is obtained, a random candidate s is a suitable pre-image with high enough probability. How well does this strategy work when considering arbitrary pre-processing pre?

To analyze this strategy, we study the entropy of the hard values x i given (1 -1 p(m) )l many easy values x i (note that in expectation, (1 -1 p(m) )l many values are easy) and seek to prove that their entropy is low. Towards that goal, we fix a permutation π and look at the entropy of the 1 p(m) l many first x i under that permutation:

h(π) := H(X π(1) , . . . , X π( l p(m) ) |X π( l p(m) +1) , . . . , X π(l) ),
where X i is the random variable defined as follows: sample a uniformly random s from {0, 1} n , compute pre(s) and take the ith output (i.e. the input to the ith F-call in g). First, in Lemma 21 (Small Entropy Expectation), we show that the expectation of entropy h(π) is small in our case. This is our main conceptual lemma.

Lemma 21 (Small Entropy Expectation). Suppose p(m) divides l. Then,

E π∈Π(l) [h(π)] ≤ n p(m)
, which is equivalent to

E π∈Π(l) H(X π(1) , . . . , X π( l p(m) ) |X π( l p(m) +1) , . . . , X π(l) ) ≤ n p(m) . ( 3
⎡ ⎢ ⎢ ⎣ H ⎛ ⎜ ⎜ ⎝ X π(j) , . . . , X π(j+ l p(m) -1) one block | X π(j+ l p(m) ) , . . . , X π(l)
all Xi after the block

⎞ ⎟ ⎟ ⎠ ⎤ ⎥ ⎥ ⎦ (4) = E π∈Π(l) ⎡ ⎣ j∈J H X π(j) , . . . , X π(j+ l p(m) -1) |X π(j+ l p(m) ) , . . . , X π(l) ⎤ ⎦ (5) = E π∈Π(l) H X π(1) , . . . , X π(l) (6) ≤ E π∈Π(l) [H (S)] (7) = n (8)
where (5) holds by linearity of expectation and (6) holds by Lemma 9 (Chain Rule for Entropy). The inequality (7) is equality iff the pre-processing is injective (entropy of a random variable cannot increase when it is passed through a deterministic function). The equality (8) follows from the fact that H(S) = |s| = n. Now, from (4), we have that n is greater or equal to j∈J E π∈Π(l) H X π(j) , .., X

π j+ l p(m) -1 |X π j+ l p(m) , .., X l (9) ≥ j∈J E π∈Π(l) H X π(j) , .., X π(j+ l p(m) -1) |X π(i) , i = 1, .., j -1, j + l p(m) , .., l (10)
=

j∈J E π ∈Π(l) H X π (1) , .., X π ( l p(m) ) |X π ( l p(m) +1) , .., X π (l) (11)
= p(m)

E π ∈Π(l) H X π (1) , .., X π ( l p(m) ) |X π ( l p(m) +1) , .., X π (l) (12)
where [START_REF] Goldreich | Security preserving amplification of hardness[END_REF] follows from the general property of entropy: ∀A, B, C : H(A|B) ≥ H(A|B, C), i.e. conditioning the entropy on more random variables can only decrease the entropy. In this case, we condition additionally on all X i for i < π(j) and not only on those for i ≥ π(j + l p(m) ). At [START_REF] Goldreich | On yao's xor lemma[END_REF] we change to a more convenient indexing where we choose permutation π (1) = π(j),...,π ( l p(m) ) = π(j + l p(m) -1). Now, consider any of the summands, i.e. the expectation for some fixed j. Now for that j, π still goes through all possible permutations (like π did in [START_REF] Goldreich | Security preserving amplification of hardness[END_REF]). At [START_REF] Goyal | Correlated-input secure hash functions[END_REF] we notice that the summands do not depend on j and recall that |J| = p(m). Dividing by p(m) proves the Lemma 21.

With Lemma 21 as a tool, we can now prove Theorem 19. Note that, interestingly, the result of Theorem 19, does not depend on the number of calls to F in the strong OWF construction g. That is, if the input length of the construction g is too short, then no number of calls to F can make it a strong OWF.

A(y 1 ||...||y l ||d)

for i ∈ 1, ..., l xi ← INV(yi) s ←$ pre -1 (x1, ..., x l , d) return s
Proof of Theorem 19. Let g be a (n, m)-NANPP g with input length n ≤ 1 4 p(m) and let l be the number of queries to F which g makes. The adversary A (described on the right) now tries to invert all y 1 ,..,y l using INV and put ⊥ when inversion fails. A then computes a random pre-image of the pre-processing that matches the known x i s and d which is possible in polynomial-time when using the PSPACE oracle. We now argue that a random pre-image of the pre-processing, that matches the known x i s and d, is an actual preimage of y 1 ||...||y l ||d under g with constant probability. W.l.o.g., we assume that |d| = 0. This is because the data d is known to the adversary, so it cannot add entropy. From now on, we assume that there is no d. Further and also w.l.o.g., we assume that p(m) divides l for all m, n (if there was some remainder, we could add constant dummy F-calls until there is no remainder. Such F-calls would not make g weaker nor stronger, so our result would still hold.) Note that if l ≤ p(m), then with constant probability all x i are easy and INV inverts all of them (cf. Theorem 20). In that case A can use PSPACE oracle to find a correct preimage s with probability 1. Hence, we can assume that l > p(m).

First, in Lemma 21 (Small Entropy Expectation) establishes that the expectation of entropy h(π) is small. Namely, since Theorem 19 assumes that p(m) > 4n, we have

E π ← $ Π(l) [h(π)] ≤ n p(m) < 1 4 .
Since the expectation of the entropy over π is small, an averaging argument (cf. Lemma 24 (Small Entropy w.h.p.) in Appendix A) yields that for at least half of the permutations, the entropy is small, i.e.,

Pr π∈Π(l) h(π) < 2n p(m) ≥ 1 2 . ( 13
)
We call a π such that h(π) < 2n p(m) good. If π is good, then the remaining entropy of the input is small and thus, some inputs are very likely (cf. Lemma 25 (Predictable Inputs) in Appendix A) and thus likely chosen by adversary A which chooses a random pre-image amongst the possible candidates.

With this high level intuition of the proof in mind, we can now lower-bound the probability of A's success.

Pr F,s [A inverts g(s)] ≥ Pr F ∃π : x π(1) , ..., x π((1-1 p(m) )l) ∈ EASY m in • Pr s A inverts g(s) ∃π : x π(1) , ..., x π((1-1 p(m) )l) ∈ EASY m in ≥ 1 2 Pr s A inverts g(s) ∃π : x π(1) , ..., x π((1-1 p(m) )l) ∈ EASY m in (14) ≥ 1 2 Pr s ⎡ ⎢ ⎢ ⎣ H X π(1) , . . . , X π( l p(m) ) X π( l p(m) +1) , . . . , X π(l) < 2n p(m) =:C ⎤ ⎥ ⎥ ⎦ • (15) Pr s Pr s ∀k ∈ π(1),...,π(l/p(m)), X k = pre(s ) k ∀j ∈ π(l/p(m)+1),...,π(l), X j = pre(s) j > 1 4 | C • (16) Pr s A inverts g(s) Pr s ∀k ∈ π(1),...,π(l/p(m)), X k = pre(s ) k ∀j ∈ π(l/p(m)+1),...,π(l), X j = pre(s) j > 1 4 ∧ C (17) ≥ 1 2 • 1 2 • 3 4 • 1 4 = constant (18)
where ( 14) follows from the fact that whether x i is easy or not follows binomial distribution with (1 -1 p(m) )l many easy values in expectation. Inequality (15) uses chain rule of probability. The fractions at (18) follow from the lemmas, namely, the probability on line [START_REF] Healy | Using nondeterminism to amplify hardness[END_REF] is less than 1/2 by Lemma 21 (Small Entropy Expectation) and probability on line ( 16) is less than 3/4 by Lemma 25 (Predictable Inputs). The last fraction follows from the definition of adversary A and the probability statement at [START_REF] Hsiao | Finding collisions on a public road, or do secure hash functions need secret coins?[END_REF]. Namely, if adversary guesses a random s which is consistent with the known x i , and we condition the probability on such s being correct 1/4 of the time, adversary must be right

Constructions with Post-processing

In this section, we prove Theorem 15. Towards this goal, we use the oracles F, INV and PSPACE (cf. Sect. 4), and show that there are no short input NAIPP constructions under the oracles. Proof. Let g be (n, m)-NAIPP which makes l queries to F and let A be the adversary on the right which samples a uniformly random pre-image of z under post, then inverts the easy queries and returns a seed s which is consistent with the pre-image of the easy values. Firstly observe that A runs in polynomial-time since it can use the PSPACE oracle for inverting post. Moreover, it makes only a polynomial number of queries since l is a polynomial.

As the post-processing of g is almost injective, y 1 , ..., y l , d ←$ post -1 (z) returns the values y 1 , ..., y l , d which the one-wayness experiment used to compute z with probability 1 poly(n) . This probability is independent of F. If y 1 , ..., y l , d are indeed the correct values, then adversary A also finds a pre-image s with constant probability by the same arguments as in Theorem 19. Thus, the overall success of A is adversary R make an arbitrary number of queries to INV, that is, the adversary can be assumed to know the EASY m in and EASY m out and how F maps EASY m in to EASY m out completely. This only makes the adversary stronger. Importantly, using INV does not give the adversary any information on F on the hard values (only the fact that the values are hard).

Denote the preimages to F queries by x 1 , ..., x q(m) and the adversary's guess for the pre-image of its input y by x q(m)+1 . for any c.

Pr F,INV ← $ Dp,x ← $ {0,1} m ,R R(F(x)) ∈ F -1 (F(x)) = Pr R(F(x)) ∈ F -1 (F(x)) x ∈ EASY m in • Pr[x ∈ EASY m in ] + Pr R(F(x)) ∈ F -1 (F(x)) x ∈ EASY m in • Pr[x ∈ EASY m in ] ≤ 1 • 1 - 1 p(m) + Pr R(F(x)) ∈ F -1 (F(x)) x ∈ EASY m in • 1 p(m)

Fig. 1 .

 1 Fig. 1. (n, m)-non-adaptive construction. F is the weak OWF. Length of d can be arbitrary, |xi| = |yi| = m and |s| = n.

Definition 17 (

 17 Oracle Distributions). Let p be any fixed polynomial. The oracle distribution D p over oracles O 1 and O 2 samples permutations Π m of the elements in {0, 1} m for every m ∈ N and a random subset EASY m in of {0, 1} m s.t. |EASY m in | = (1 -1/p(m))2 m . We define O 1 := (PSPACE, F) and O 2 := INV, where F and INV behave as follows:

  where D := D p , O 1 := F, PSPACE, O 2 := INV and Bad R,A,g m is defined as in Theorem 14.

)

  Proof. Let's consider a permutation π of the weak OWF inputs x π(1) , ..., x π(l) . Let's divide the inputs x i into p(m) equal-sized blocks as follows: ⎛ ⎝ x π(1) , ..., x π(l/p(m)) , x π(l/p(m)+1) , ..., x π(2l/p(m)) one block , x π(2l/p(m)+1) , ..., x π(l) ⎞ ⎠ . Each pink index starts a new block. Let's denote the set of the pink indices by J := {1, l/p(m) + 1, 2l/p(m) + 1, ..., (p(m) -1)l/p(m) + 1}. Now consider the following sum j∈J E π∈Π(l)

Theorem 22 (= constant < 1 where

 221 No Strong OWFs with Injectiveish Post-Processing). ∀ poly p, ∀(n, m)-NAIPP g with input lengthn ≤ 1 4 p(m), ∃poly q(n) = n c , c ∈ N + , ∃ poly-query A F,INV,PSPACE such that Pr (F,INV) ← $ Dp Pr s, coins of A A F,INV,PSPACE inverts g(s) ≤ q(n) = constant < 1 and thus Pr (O1,O2) ← $ D Case 2 of Bad R,A,g m Bad R,A,gm is defined as in Theorem 15. Theorems 18 and 22 together imply Theorem 15 by union bound analogously to the NANPP case. It thus remains to prove Theorem 22. A(z) y1, ..., y l , d ← post -1 (z) for i ∈ 1, ..., l xi ← INV(yi) s ←$ pre -1 (x1, ..., x l , d) return s

s

  Prs P h = p h (s ) and Pe = pe(s) • log Prs P h = p h (s ) Pe = pe(s ) = s ∈S h,e Prs P h = p h (s ) and Pe = pe(s ) • log Prs P h = p h (s ) Pe = pe(s ) + s ∈S h,e Prs P h = p h (s ) and Pe = pe(s ) • log Prs P h = p h (s ) Pe = pe(s ) ≥ ⎛ ⎝ s ∈S h,e Prs P h = p h (s ) and Pe = pe(s ) ∈S h,e Prs P h = p h (s ) and Pe = pe(s ) ⎞ ⎠ • |log 1| ≥ Pr s Prs P h = p h (s ) Pe = pe(s ) < 1 4 • 2 + 0

  x i ) = F(x) F(x 1 ), ..., F(x i-1 ) = F(x), x ∈ EASY m in when m is large enough.Next, we apply an averaging argument. Consider the random variable SuccInv F,PSPACE,INV A,R which maps F, PSPACE, INV ←$ D p to the probability that R F,PSPACE,INV,A F,PSPACE,INV inverts F over the randomness of R, A and sampling x. Then, by the previous analysis, the expected value μ of SuccInv F,PSPACE,INV A,R is at most 1-for := 1 2p(m) . Using Markov inequality on 1 -SuccInv F,PSPACE,INV A,R , we obtain that Pr F,PSPACE,INV ← $ Dp SuccInv F,PSPACE,INV A,R ≥ 1c ≤ 1 c .

  1/4 of the time.Note that since the constant c in Theorem 18 can be made arbitrarily large, in particular, it can be chosen s.t. 1/c + constant from Theorem 19 is < 1.

Now that we know that Pr F,s [A inverts g(s)] ≥ const > 0, we can use a simple averaging argument (see Appendix A, Lemma 23) to show that Pr F [Pr s [A inverts g(s)] > const > 0] ≥ const > 0 which proves Theorem 19. Theorem 14 follows from the Theorems 19 and 18 by union bound, namely Pr (O1,O2) ← $ D Bad R,A,g m = Pr Case 1 of Bad R,A,g m or Case 2 of Bad R,A,g m ≤ 1/c + constant from Theorem 19 < 1

1

  poly(n) • constant which is inverse polynomial as required by Theorem 22.Lemma 24 (Small Entropy w.h.p.). If E π∈Π(l) [h(π)] ≤ np(m) then +1) , . . . , X π(l) . The proof is a direct application of Markov bound, we defer it to the full version. Prs[X k =pre(s) k ∀k∈π(1),...,π(

					Pr π∈Π(l) h(π) <	2n p	≥ 1/2,
	where h(π) = H X π(1) , . . . , X π( l p(m) ) X π( l p(m) Lemma 25 (Predictable Inputs). If
				H X π(1) , . . . , X π( l p(m) ) X π( l p(m) +1) , . . . , X π(l) <	2n p(m)
	then
	Pr s 2n p(m)	<	1 2	(19)
			⎛
	1 2	> H	⎜ ⎜ ⎜ ⎝	X π(1) , . . . , X π	l p(m)
				=:P h

l p(m) ) | Xj =pre(s )j ∀j∈π( l p(m) +1),...,π(l) ]> 1 4 ≥ 3

4

Proof. Since 4n < p(m), we get that

H X π(1) , . . . , X π( l p(m) ) X π( l p(m) +1) , . . . , X π(l) < Let S h,e ⊆ {0,

1} m be defined as S h,e = {s : Pr s [P h = p h (s ) | P e = p e (s ) ] < 1 4 }, where we define Pr s [P h = p h (s ) | P e = p e (s ) ] below. Using (19) and the definition of conditional Shannon entropy, we get that

In a security-preserving construction, the input length of the strong OWF is linear in that of the weak OWF.

Acknowledgments. We thank the anonymous reviewers for valuable comments. Parts of this work have been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -SFB 1119 -236615297 and by the Academy of Finland.

A Additional Lemmas and Proofs

Lemma 23 (Averaging Argument). Let A n and B n be probability distributions that depend on natural number n (e.g. uniform distribution over {0, 1} n ).

For convenience, we write

The proof is standard, we defer it to the full version.

where log is the base-2 logarithm and p e (s ) := pre(s ) π( l p(m) +1) , ..., pre(s ) π(l) and p h (s ) := pre(s ) π( 1) , . . . , pre(s

which proves the statement.

B Proof of Theorem 18 (F is a weak OWF)

In order to prove Theorem 18, we need to show that F is weak OWF with inversion probability 1 -1/2cp(m) with all but small constant probability. Namely, we need to show that for all polynomials p, for all poly-query A F,PSPACE,INV , for all adversaries R making polynomially many (in m) queries to the oracles

where

is defined as

Proof. Fix p, R and A. Since A and R both make polynomially many queries to the same oracles, R can simply simulate A. Thus, w.l.o.g., we can assume that R only makes queries to F, PSPACE and INV. Additionally, we consider R to be a computationally unbounded algorithm so that w.l.o.g., we can assume that it does not make queries to the PSPACE oracle.

Let q be a polynomial such that adversary R makes exactly q(m) queries to the oracle F and an arbitrary number of queries to INV. Since we let the


P Keckhut

M L Chanin Service D'

Aeronomie Du Cn-Rs

MIDDLE ATMOSPHERE RESPONSE TO THE 27-DAY SOLAR ROTATION AS OBSERVED BY LIDAR

The response of the middle atmosphere temperature to short term solar UV radiation related to the 27day period of the sun has been studied by Rayleigh Lidar at mid-latitude in the height range 30-90 km. Among the 9 sequences, each of 3 to 4 months duration, which corresponds to clear solar signature, two types of behavior have been found' either the temperature response is positively correlated with the solar UV flux in the whole height range, or the response reverses abruptly from positive to negative within the height interval 40-60 km. It is important to notice that this second type of behavior is observed as well in summer or in winter, i.e. even in the absence of planetary wave activity, but has only been seen during the Westward phase of the QBO. If such a change of the temperature is confirmed to be solar induced, this response to change in the UV flux is clearly different from the one we observed for the 1 !-year solar cycle. Therefore the 27-day signature of atmospheric structure should not be used as a proxy for the 11-year variation.

Introduction

44øN, IøE) from 1986 to 1991, both using the Rayleigh lidar technique. The method and the characteristics of the instruments are described in details in several publications [START_REF] Hauchecorne | Density and temperature profiles obtained by lidar between 30 and 70 km[END_REF]. The measurements are obtained at each site with a good time coverage (100 profiles per year) and a good accuracy (better than 1 K at 50 kin). The altitude range covered by the measurements extends continuously from 30 km to 90 km. Each profile is integrated over several hours and the initial height resolution is degraded to 3 km to filter out the short period fluctuations due to gravity waves and improve the accuracy.

The radiative heating in the middle atmosphere is dominated by the absorption of UV wavelengths around 205 nm. Unhappily the measurements of the UV solar flux are not continuously available with an adequate accuracy. We rely on the fact that the solar UV flux variability is highly uniform as a function of wavelength [START_REF] Donnelly | Uniformity in solar UV flux variation important to the stratosphere[END_REF], and then used the Solar Lyman-alpha flux data measured on board Solar Mesosphere Explorer for the period 1982-1986 [START_REF] Mount | Solar absolute spectral irradiance 118-300 nm[END_REF] as they provide the best accuracy. When they were no more available, we used the combined Nimbus7-NOAA-9 data which are considered as a good UV proxy.

The study of solar-atmosphere relationship is crucial to understand the mechanisms of radiative heating and ozone balance and therefore to study the potential impact of the middle atmosphere on tropospheric climate. It is also necessary to identify and hopefully understand the effects of solar perturbations in order to detect possible anthropogenic effects. The study reported in this paper is limited to temperature, as they are the only lidar data available at this day in large quantity; we will anyhow always keep in mind the complex relationship between ozone and temperature in order to interpret the results.

The studies on long term cycles such as the 1 I-year solar cycle, like the one recently published by Hauchecorne eta!.

[1991], suffer mostly from the lack of statistical results. The study of middle atmospheric response to solar UV variations occurring on shorter time scales, as the 27-day period related to solar rotation, is an obvious other promising approach.

Several studies have in the recent past shown convincing correlations between ozone and short term UV variability. The periods could vary from 27 days to 34 days. The nature of quasi-random appearance and disappearance on the sun of these active regions in space and t/me leads to a very complex UV signal where the principal spectral component is around 28 days but is highly variable in amplitude, phase and frequency. A 13-day oscillation could also appear, when two active regions are situated on opposite sides of the sun.

Keating eta!. [1987], Hood and Jirikowic

The temperature in the middle atmosphere is always perturbed by internal forcing principally by upwards propagating planetary waves from the troposphere; the maximum activity occurs during winter periods when westerly winds prevail in the lower stratosphere. The temporal and vertical structure of these waves have been largely studied for several years and the lidar data obtained during the last winters have contributed to their description [START_REF] Hauchecorne | Mid-latitude lidar observations of planetary waves in the middle atmosphere during the winter of 1981-1982[END_REF]]. The temporal characteristics of the temperature perturbation correspond to Rossby waves with periods varying from 10 to 20 days and a succession of stratospheric wamaings with periods from 25 to 60 days.

Analysis of the data

The different sequences of data used in this analysis have been selected considering both the large 27-day variability of the UV flux and the quality of the time coverage of the temperature data. The periods selected in reference to the solar flux have been determined by using the method of the wavelet transform applied to the 205 nm solar flux as seen on Figure 1. This spectral analysis recently developed by [START_REF] Grossman | Time and scale representations obtained through continuous wavelet transforms[END_REF] In the ideal white noise case, a plot Q(wo) versus wo will be a straight line where the slope is a measure of the variance (5 of the original time series. Then the noise signal Wn could be deduced from o for any given probability (here 95%).

Results

In all the 9 cases which we have studied, the upper mesosphere responds positively to increases of solar UV with a significative correlation factor within the 95% confidence level. In the height range 40-60 km, in 5 cases out of the 9 selected periods, the responses are negative and highly correlated with the solar flux with temperature variations almost as large as in the upper mesosphere. Due to a possible contribution of the planetary waves to the signature which we are trying to relate to a solar response, it seems reasonable to study separately the winter and the summer cases:

-Five periods were selected in winter; the temperature response of the region 40-60 km could be classified into two types of behavior' either the whole region exhibits a positive response in all the height range; this happened only in one winter case in January-March 1982 (Figure 3). A maximum amplitude of 10 K is in this case observed at 60 krn. In the four other cases the response is alternatively positive and negative with a null response at 40 and around 60 km (Figure 4). Obviously in wintertime such temperature change may be thought to be due to planetary waves having a period in phase the UV flux could not in this case be attributed to planetary waves (Figure 7). The phase lags between temperature data and solar forcing are not always easy to determined for low level of correlation which is the case when the sign of the correlation changes. This is the reason of the appearance of peaks around the zero correlation level which are obviously not significant. Except at those levels, phase lags are well defined and they vary from 0 to a around 5 days from the upper mesosphere down to the upper stratosphere.

Compared to earlier studies of the 27-day variability, the data set considered here is obviously limited to one region and the results may be different from global ones; on the other hand the number of data treated is rather large as, after selection of the high solar variability pei'iods, a total of more than 30 months of data were used.

Comparison with recent investigations

The temperature responses to the 27-day solar forcing has never been studied with high vertical resolution at mid- -Considering the intense activity going-on to separate the 11-year solar forcing from anthropogenic trends, it is worth mentionning that, from our data analysis, we feel that the signatures observed on the 11-year and 27-day scales are too different to extrapolate the atmospherical response on the 27day cycle for the 11-year cycle response, even if in both cases dynamical processes are concerned.

  used for this study were obtained at the Observatoire de Haute Provence (France; 44øN, 6øE) from !98 ! to 1991, and at the Centre d'Essais des Landes (France; Copyright 1992 by the American Geophysical Union. of the active regions on the solar disk which have a lifetime of several solar rotations, induces variations in the UV irradiance received by the atmosphere.

Fig. 2 .

 2 Fig. l. Wavelet transform of the solar UV flux (Nimbus 7-NOAA 9) from 1981 to 1990. The horizontal axis represents the time (in years) vertical one the periods (in days). transform gives a two-dimensional and complex function F(a,b) which provides the spectral module and phase as a function of time' FCa,b)-a3 q)*( -2•a ) f(x) dx We have also used this method with the time-series of the temperature, as the correlation of spectral and temporal maxima could give a better insight of the solar induced atmospheric changes. This transform is particularly well adapted to the atmospheric solar and planetary waves forcing because the lifetime of these effects corresponds only to several oscillations. Systematic time-series correlation cannot clearly isolate the solar response of the atmosphere from the important wave activity having the same time scale. The Fourier method has to be adapted to take into account the quasi-random nature of the time series and has been applied here to obtain temperature change on the time scale of the sun's rotation with a relatively small temporal window of 3 to 4 months (each corresponding to about 30 to 40 data points), when the amplitude of the solar cycles are relatively important. During such periods the amplitude is expected not to change largely and the frequency resolution (0.008 to 0.011 day-1) is sufficient to separate solar perturbations from the atmospheric perturbations associated to wave activity.To conclude on the significance of the peaks found in the spectral decomposition, the cross spectrum analysis of the unfiltered time series is carried out applying the methods of time series analysis described by Jenkins and Watts[ 1969]. The statistical significance is given by the peak exceeding the 95% confidence level reflecting the response of the atmosphere to changes of solar UV radiation. The phase lag between both time series can be deduced from the phase of the cross spectrum analysis. The different steps of the analysis are illustrated in Figure2.

Fig. 5 .

 5 Fig. 3. Amplitude as a function of altitude of the 27-day spectral component for the period from January to March 1982. Correlation (left), temperature deviation (middle), and phase lag (right) between solar and temperature series are given. 95 % confidence level (dash line), phase lag uncertainties and white noise level (shaded area) are also plotted.

  latitude. But these results are not in contradiction with the ones obtained in previous equatorial studies based on SAMS data by Keating et al. [ 1987]. In the mesosphere, around 65-70 km, a positive maximum response is obtained in both data set, and the negative response obtained in the 40-60 km range with the lidar data was in fact seen with SAMS between 30 and 40 km, but the authors interpreted it as a positive effect with a long phase lag (>13 days). Due to the higher vertical resolution of the lidar, the abrupt change comes out more clearly, but a phase change of 10 days in about 5 km is also visible from SAMS data. Analysis of the SAMS and SBUV data at all latitudes up to 60øN, from October 1981 to April 1982, were performed by Hood and Jirikowic [1991]. They revealed that the temperature oscillations seen at higher latitudes are anticorrelated and have larger amplitudes (+_.3 K) than those obtained at lower latitudes. Such results were already suggested by Ebel et al. [1986] and Chandra [1986]. The lidar observations during the winter 1982, period used by Hood and jirikowic [ 1991] are in agreement with the satellite results at 60øN: i.e. the temperature deviation is around 3 K at 45 km and in phase with the solar flux. Considering the shifted position of the polar vortex towards Europe, it is not surprising that our site, even though at 44øN, behaves in a similar manner than the mean 60øN latitude. The expected anticorrelation between different layers of the atmosphere mentionned in that paper is confirmed by our observations. Discussion The results presented here are not consistent with the expectations based on purely radiative and photochemical considerations [Brasscur et al., 1987] 'the amplitudes are too large and the sign of the correlation is unexpected about half of the time; if we would consider •hat the response is constantly positive, the time lag would be larger than expected. The mechanism of temperature change induced by solar variations in the middle atmosphere is not yet understood both on the scale of the 27-day and the 11-year cycles. But the fact that dynamic causes take an important pan in the atmospherical response becomes more and more convincing; these new results, as well as the ones recently published [Hauchecome et al., 1991], even within their local limits, are conlofting such hypothesis. The sharp change of behavior around 40 and 60 km observed in more than half of our cases could be interpreted as due to the change of sign of the temperature-ozone relationship, which varies itself abruptly from a dynamically driven region 'to a chemically driven one; such a rapid change as a function of altitude is also seen in the vertical ozone response 'to the QBO by SAGE II [Mc Cormick et al., 1989].The fact that the sign of the QBO plays a role in the response of the atmosphere to a solar forcing is not a new issue[Labitzke .and van Loon, 1988]. In the specific case of the 27day cycle, its role can be understood if the solar response is, as suggested by several authors[Ebel et al, !986;[START_REF] Hood | Stratospheric Dynamical effects of solar Ultraviolet variations ß Evidence from zonal mean Ozone and temperature data[END_REF], amplified and modulated by dynamical processes and those will be influenced by the QBO. Contrary to earlier assurnptions that the causes of such variations would be p.urely dynamical, the newly proposed interaction between stationary and travelling waves would amplify the weak solar signal which, according tO present models would make it indetectable. Our purpose in writing this paper is to 1982), and even for the lidar data which covers now a solar cycle, very few clear cases of monochromatic 27-day cycles could be' found in the riõing phase of the cycle 22 (1•986-1990) ß most of our cases (7 Out of 9) were selected in the period 1982-1986. This implies that in the next few years, during the declining phase of the Cycle 22, there should be very intense studies on this subject, both from the ground and obviously from space, with the contrib,ution of UARS.