Thomas Agrikola
email: thomas.agrikola@kit.edu

Geoffroy Couteau
email: couteau@irif.fr

Yuval Ishai
email: yuvali@cs.technion.ac.il

Stanisław Jarecki

Amit Sahai
email: sahai@cs.ucla.edu

On Pseudorandom Encodings

We initiate a study of pseudorandom encodings: efficiently computable and decodable encoding functions that map messages from a given distribution to a random-looking distribution. For instance, every distribution that can be perfectly and efficiently compressed admits such a pseudorandom encoding. Pseudorandom encodings are motivated by a variety of cryptographic applications, including password-authenticated key exchange, "honey encryption" and steganography.

The main question we ask is whether every efficiently samplable distribution admits a pseudorandom encoding. Under different cryptographic assumptions, we obtain positive and negative answers for different flavors of pseudorandom encodings, and relate this question to problems in other areas of cryptography. In particular, by establishing a twoway relation between pseudorandom encoding schemes and efficient invertible sampling algorithms, we reveal a connection between adaptively secure multiparty computation for randomized functionalities and questions in the domain of steganography.

Table of Contents 1 Introduction

The problem of compression has been extensively studied in the field of information theory and, more recently, in computational complexity and cryptography [GS85; Wee04; TVZ05; HLR07]. Informally, given a distribution X, compression aims to efficiently encode samples from X as short strings while at the same time being able to efficiently recover these samples. While the typical information-theoretic study of compression considers the case of compressing multiple independent samples from the same source X, its study in computer science, and in particular in this work, considers the "single-shot" case. Compression in this setting is closely related to randomness condensers [RR99; TV00; TUZ01; DRV12] and resource-bounded Kolmogorov complexity [LV90; LV19] -two well-studied problems in computational complexity. Randomness condensers, which relax randomness extractors, are functions that efficiently map an input distribution into an output distribution with a higher entropy rate. A randomness condenser can be viewed as an efficient compression algorithm, without a corresponding efficient decompression algorithm. The resource-bounded Kolmogorov complexity of a string is the smallest description length of an efficient program that outputs this string. This program description can be viewed as a compressed string, such that decoding is efficiently possible, while finding the compressed string may be inefficient.

An important property of efficient compression algorithms, which combines the efficiency features of randomness condensers and resource-bounded Kolmogorov complexity, is their ability to efficiently produce "random-looking" outputs while allowing the original input to be efficiently recovered. Despite the large body of work on compression and its computational variants, this fundamental property has, to our knowledge, never been the subject of a dedicated study. In this work, we fill this gap by initiating such a study. Before formalizing the problem, we give a simple motivating example.

Consider the goal of encrypting a sample x from a distribution X (say, a random 5-letter English word from the Merriam-Webster Dictionary) using a low-entropy secret key k. Applying a standard symmetric-key encryption scheme with a key derived from k gives rise to the following brute-force attack: Try to decrypt with different keys until obtaining x in the support of X. In the typical case that wrong keys always lead to x outside the support of X, this attack successfully recovers x. Variants of this attack arise in different scenarios, including passwordauthenticated key exchange [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF], honey encryption [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF], subliminal communication and steganography [START_REF] Horel | How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts[END_REF], and more. A natural solution is to use perfect compression: if x can be compressed to a uniformly random string x ∈ {0, 1} n before being encrypted, it cannot be distinguished from another random string x ∈ {0, 1} n obtained by trying the wrong key. Note, however, that compression may be an overkill for this application. Instead, it suffices to efficiently encode x into a (possibly longer) pseudorandom string from which x can be efficiently decoded. This more general solution motivates the question we consider in this work.

Encoding into the uniform distribution. We initiate the study of encoding distributions into a random-looking distribution. Informally, we say that a distribution ensemble X λ admits a pseudorandom encoding if there exist efficient encoding and decoding algorithms (E X , D X ), where D X is deterministic, such that Pr y ← X λ : D X (E X (y)) = y is overwhelming and

(1)

y ← X λ : E X (y) ≈ U n(λ) . (2)
Here, "≈" denotes some notion of indistinguishability (we will consider both computational and statistical indistinguishability), and the probability is over the randomness of both E X and X λ . The polynomial n(λ) denotes the output length of the encoding algorithm E X . We refer to Equation (1) as correctness and to Equation (2) as pseudorandomness. It will also be useful to consider distribution ensembles parameterized by an input m from a language L. We say that such a distribution ensemble (X m ) m∈L admits a pseudorandom encoding if there exist efficient algorithms (E X , D X ) as above satisfying correctness and pseudorandomness for all m ∈ L, where E X and D X both additionally receive m as input. Note that we insist on the decoding algorithm being efficient. This is required for our motivating applications.1 Note also that encoding and decoding above are keyless; that is, we want encoded samples to be close to uniform even though anyone can decode them. This is a crucial distinction from, for instance, encryption schemes with pseudorandom ciphertexts, which look uniformly distributed to everyone except the owner of the decryption key, and cannot be efficiently decrypted except by the owner of the decryption key. Here, we seek to simultaneously achieve pseudorandomness and correctness for all parties.

Our motivation for studying pseudorandom encodings stems from the fact that this very natural problem appears in a wide variety of -sometimes seemingly unrelated -problems in cryptography. We already mentioned steganography, honey encryption, and password-authenticated key exchange; we will cover more such connections in this work. Yet, this notion of encoding has to our knowledge never been studied systematically. In this work we study several natural flavors of this notion, obtain positive and negative results about realizing them, and map their connections with other problems in cryptography.

The main focus of this work is on the hypothesis that all efficiently samplable distributions admit a pseudorandom encoding. Henceforth, we refer to this hypothesis the pseudorandom encoding hypothesis (PREH).

For describing our results, it will be convenient to use the following general notion of efficiently samplable distributions. A distribution family ensemble (X m ) m∈L (for some language L ⊆ {0, 1} * ) is efficiently samplable if there exists a probabilistic polynomial time (PPT) algorithm S such that S(m) is distributed according to X m for every m ∈ L. In case the distribution does not depend on additional inputs, L can be considered equal to N.

Overview of contributions.

Following is a brief summary of our main contributions along with pointers to the relevant technical sections. We will give an expanded overview of the contributions and the underlying techniques in the rest of this section.

-We provide a unified study of different flavors of pseudorandom encodings (PRE) and identify computational, randomized PRE in the CRS model as a useful and achievable notion(Section 6 and Theorem 15).

-We establish a two-way relation between PRE and the previously studied notion of invertible sampling(Theorem 2). This reveals unexpected connections between seemingly unrelated problems in cryptography (e.g., between adaptively secure computation for general functionalities and "honey encryption").

-We bootstrap "adaptive PRE" from "static PRE"(Theorem 1). As a consequence, one can base succinct adaptively secure computation on standard iO as opposed to subexponential iO [START_REF] Cohen | Adaptively Secure MPC with Sublinear Communication Complexity[END_REF](Corollary 3).

-We use PRE to obtain a compiler from standard secure multiparty computation (MPC) protocols to covert MPC protocols(Section 7.4).

Flavors of pseudorandom encoding

The notion of pseudorandom encoding has several natural flavors, depending on whether the encoding algorithm is allowed to use randomness or not, and whether the pseudorandomness property satisfies a computational or information-theoretic notion of indistinguishability. We denote the corresponding hypotheses that every efficiently samplable distribution can be pseu-dorandomly encoded according to the above variants as PREH rand ≈c , PREH rand ≡s , PREH det ≈c and PREH det ≡s .2 Further, we explore relaxations which rely on a trusted setup assumption: we consider the pseudorandom encoding hypothesis in the common reference string model, in which a common string sampled in a trusted way from some distribution is made available to the parties. This is the most common setup assumption in cryptography and it is standard to consider the feasibility of cryptographic primitives in this model to overcome limitations in the plain model. That is, we ask whether for every efficiently samplable distribution X, there exists an efficiently samplable CRS distribution and efficient encoding and decoding algorithms (E X , D X ) as above, such that correctness and pseudorandomness hold, where the encoding and decoding algorithm as well as the distinguisher receive the CRS as input, and the distributions in Equations ( 1) and (2) are additionally over the choice of the CRS.

Considering distributions which may depend on an input m ∈ L further entails two different flavors. On the one hand, we consider the notion where inputs m are chosen adversarially but statically (that is, independent of the CRS) and, on the other hand, we consider the stronger notion where inputs m are chosen adversarially and adaptively depending on the CRS. We henceforth denote these variants by the prefix "c" and "ac", respectively.

Static-to-adaptive transformation. The adaptive notion, where inputs may be chosen depending on the CRS, is clearly stronger than the static notion. However, surprisingly, the very nature of pseudorandom encodings allows one to apply an indirection argument similar to the one used in [HJKSWZ16; CPR17; CPV17], which yields a static-to-adaptive transformation.

Theorem (informal). If all efficiently samplable distributions can be pseudorandomly encoded in the CRS model with a static choice of inputs, then all efficiently samplable distributions can be pseudorandomly encoded in the CRS model with an adaptive choice of inputs.

Static-to-adaptive transformations in cryptography are generally non-trivial, and often come at a big cost in security when they rely on a "complexity leveraging" technique. This connection and its application we will discuss below are a good demonstration of the usefulness of the notion of pseudorandom encodings.

Relaxing compression. The notion of statistical deterministic pseudorandom encodings recovers the notion of optimal compression. Hence, this conflicts with the existence of one-way functions. 3In our systematic study of pseudorandom encodings, we gradually relax perfect compression in several dimensions, while maintaining one crucial property -the indistinguishability of the encoded distribution from true randomness.

Example. To illustrate the importance of this property, we elaborate on the example we outline at the beginning of the introduction, focusing more specifically on password-authenticated key exchange (PAKE). A PAKE protocol allows two parties holding a (low entropy) common password to jointly and confidentially generate a (high entropy) secret key, such that the protocol is resilient against offline dictionary attacks, and no adversary can establish a shared key with a party if he does not know the matching password. A widely used PAKE protocol due to Bellovin and Merritt [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] has a very simple structure: the parties use their low-entropy password to encrypt the flows of a key-exchange protocol using a block cipher. When the block cipher is modeled as a random cipher, it has the property that decrypting a ciphertext (of an arbitrary plaintext) under an incorrect secret key yields a fresh random plaintext. Thus, Bellovin and Merritt point out that the security of their PAKE protocol requires that "the message to be encrypted by the password must be indistinguishable from a random number." This is easy to achieve for Diffie-Hellman key exchange over the multiplicative group of integers modulo a prime p. However, for elliptic curve groups this is no longer the case, and one needs to resort to alternative techniques including nontrivial point compression algorithms that compress the representation of a random group element into a nearly uniform bitstring [START_REF] Boyd | Elliptic Curve Based Password Authenticated Key Exchange Protocols[END_REF].

Clearly, our relaxation of compression does not preserve the useful property of obtaining outputs that are shorter than the inputs. However, the remaining pseudorandomness property is good enough for many applications.

In the following, we elaborate on our weakest notion of pseudorandom encodings, that is, pseudorandom encodings allowing the encoding algorithm to be randomized and providing a computational pseudorandomness guarantee. We defer the discussion on the stronger statistical or deterministic variants to Section 1.3, where we derive negative results for most of these stronger notions, which leaves computational randomized pseudorandom encodings as the "best possible" notion that can be realized for general distributions.

1.1.1 Randomized, computational pseudorandom encodings. Computational randomized pseudorandom encodings allow the encoding algorithm to be randomized and require only computational pseudorandomness.

Relation to invertible sampling. We show a simple but unexpected connection with the notion of invertible sampling [CFGN96; DN00; GKMRV00]. Informally, invertible sampling refers to the task of finding, given samples from a distribution, random coins that explain the sample. Invertible sampling allows to obliviously sample from distributions, that is, sampling from distributions without knowing the corresponding secrets. This can be useful for, e.g., sampling common reference strings without knowing the random coins or public keys without knowing the corresponding secret keys. A natural relaxation of this notion was systematically studied by Ishai, Kumarasubramanian, Orlandi and Sahai [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. Concretely, a PPT sampler S is inverse samplable if there exists an alternative PPT sampler S and a PPT inverse sampler S -1 such that y ← S(1 λ ) : y ≈ c y ← S(1 λ ) : y , y ← S(1 λ ; r) : (r, y) ≈ c y ← S(1 λ ) : (S -1 (1 λ , y), y) .

Note that the inverse sampling algorithm is only required to efficiently inverse-sample from another distribution S, but this distribution must be computationally close to the distribution induced by S. The main question studied in [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] is whether every efficient sampler admits such an invertible sampler. They refer to this hypothesis as the invertible sampling hypothesis (ISH), and show that ISH is equivalent to adaptive MPC for general randomized functionalities that may hide their internal randomness. In this work, we show the following two-way relation with pseudorandom encoding.

Theorem (informal).

A distribution admits a pseudorandom encoding if and only if it admits invertible sampling.

Intuitively, the efficient encoding algorithm corresponds to the inverse sampling algorithm, and decoding an encoded string corresponds to sampling with the de-randomized alternative sampler S. This equivalence immediately extends to all variants of pseudorandom encodings and corresponding variants of invertible sampling we introduce in this work. Invertible sampling is itself connected to other useful cryptographic notions, such as oblivious sampling, trusted common reference string generations, and adaptively secure computation (which we will elaborate upon below).

Building on this connection, the impossibility result of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] translates to our setting. On a high level, extractable one-way functions (EOWFs) conflict with invertible sampling because they allow to extract a "secret" (in this case a pre-image) from an image, independently of how it was computed. This conflicts with invertible sampling because invertible sampling is about sampling without knowing the secrets.

Theorem (informal, [IKOS10]

). Assuming the existence of extractable one-way functions (EOWF) and a non-interactive zero-knowledge proof system, PREH rand ≈c does not hold.

This suggests that towards a realizable notion of pseudorandom encodings, a further relaxation is due. Thus, we ask whether the above impossibility result extends to the CRS model. In the CRS model, the above intuition why ISH conflicts with EOWFs fails, because the CRS can contain an obfuscated program that samples an image using some secret, but does not output this secret.

Dachman-Soled, Katz, and Rao [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] (building on the universal deniable encryption construction of Sahai and Waters [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF]) construct a so-called "explainability compiler" that implies cISH rand ≈c based on indistinguishability obfuscation4 (iO). By our equivalence theorem above, this implies pseudorandom encodings for all efficiently samplable distributions in the CRS model, with static choice of inputs, from iO. Invoking the static-to-adaptive transformation detailed above, this also applies to the adaptive variant.

Theorem (informal).

Assuming the existence of (polynomially secure) indistinguishability obfuscation and one-way functions, acPREH rand ≈c holds.

Note that [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] claim that their impossibility result extends to the CRS model, whereas the above theorem seems to suggest the opposite. We show that technically the result of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] does extend to the CRS model at the cost of assuming unbounded auxiliary-input extractable one-way functions, a strong flavor of EOWFs that seems very unlikely to exist but cannot be unconditionally ruled out.

Theorem (informal).

Assuming the existence of extractable one-way functions with unbounded common auxiliary input and a non-interactive zero-knowledge proof system, cPREH rand ≈c does not hold.

In fact, this apparent contradiction has been the source of some confusion in previous works: the work of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] makes an informal claim that their impossibility result for ISH extends to the CRS model. However, due to the connection between ISH and adaptively secure MPC (which we will discuss in more details later on), this claim was challenged in [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF]: the authors achieve a construction of adaptively secure MPC for all functionalities assuming iO, which seemingly contradicts the claim of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. The authors of [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] therefore stated that the "impossibility result of Ishai et al. [...] does not hold in the CRS model." Our extension clarifies that the distinction is in fact more subtle: the result of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] does extend to the CRS model, but at the cost of assuming EOWF with unbounded auxiliary inputs. This does not contradict the constructions based on iO, because iO and EOWF with unbounded auxiliary inputs are known to be contradictory [START_REF] Bitansky | On the existence of extractable one-way functions[END_REF].

Overview.

In Figure 1, we provide a general summary of the many flavors of the pseudorandom encoding hypothesis, and how they relate to a wide variety of other primitives. Honey encryption

[ J R 1 4 ] extractable OWFs +NIZK [IKOS10]
(computational) honey encryption

[J R 14 ]
adaptive MPC Th. 15 Fig. 1. An overview of the relations between the pseudorandom encoding hypothesis and other fields of cryptography and computational complexity theory. For simplicity, our static-to-adaptive transformation only appears in the computational, randomized setting in this overview, but also applies to the other settings. (Since the deterministic variants of the pseudorandom encoding hypothesis are impossible for some pathologic samplers, the arrows between deterministic and randomized variants of the pseudorandom encoding hypothesis are to be read as if the deterministic variant is true for some sampler, then the corresponding randomized variant is true for that sampler.) Further relaxation. We further study an additional relaxation of pseudorandom encodings, where we allow the encoding algorithm to run in super-polynomial time. We show that this relaxed variant can be achieved from cryptographic primitives similar to extremely lossy functions [START_REF] Zhandry | The Magic of ELFs[END_REF], which can be based on the exponential hardness of the decisional Diffie-Hellman problem -a strong assumption, but (still) more standard than indistinguishability obfuscation. However, the applicability of the resulting notion turns out to be rather restricted.

[IK O S1 0]
+ P K E T h . 2 5 , [ C D M W 0 9 ] adaptive MPC with global setup T h . 2 1 , [D K R 1 5 ]

Implications and applications of our results

In this section, we elaborate on the implications of the techniques we develop and the results we obtain for a variety of other cryptographic primitives.

New results for adaptively secure computation.

As mentioned above, a sampler admits invertible sampling if and only if it can be pseudorandomly encoded. A two-way connection between invertible sampling and adaptively secure MPC for general randomized functionalities was established in [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. An MPC protocol allows two or more parties to jointly evaluate a (possibly randomized) functionality F on their inputs without revealing anything to each other except what follows from their inputs and outputs. This should hold even in the presence of an adversary who can corrupt any number of parties in an adaptive (sequential) fashion. When we write "adaptive MPC", we mean adaptive MPC for all randomized functionalities. This should be contrasted with weaker notions of adaptive MPC for strict subsets of corrupted parties [BH92; CFGN96; GS12] or for adaptively well-formed functionalities 5 [CLOS02] which can both be done from mild assumptions. The connection from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] shows that adaptive MPC for all randomized functions is possible if and only if every PPT sampler admits invertible sampling, i.e., the invertible sampling hypothesis is true.

We show that this result generalizes to the global CRS model. More precisely, we prove the adaptive variant of the pseudorandom encoding hypothesis in the CRS model acPREH rand ≈c is equivalent to adaptive MPC in the global CRS model. 6 As detailed above, the static pseudorandom encoding hypothesis cPREH rand ≈c in the CRS model follows from iO (and one-way functions). Applying our static-to-adaptive transformation, the same holds for the adaptive variant. Thus, we obtain the first instantiation of an adaptive explainability compiler [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] without complexity leveraging and, hence, based only on polynomial hardness assumptions. The recent work of Cohen, shelat, and Wichs [START_REF] Cohen | Adaptively Secure MPC with Sublinear Communication Complexity[END_REF] uses such an adaptive explainability compiler to obtain succinct adaptive MPC, where "succinct" means that the communication complexity is sublinear in the complexity of the evaluated function. Due to our instantiation of acPREH rand ≈c from polynomial iO, we improve the results of [START_REF] Cohen | Adaptively Secure MPC with Sublinear Communication Complexity[END_REF] by relaxing the requirement for subexponentially secure iO to polynomially secure iO in a black-box way.

Corollary (informal). Assuming the existence of polynomially secure indistinguishability obfuscation and the adaptive hardness of the learning with errors problem, then malicious, tworound, UC-secure adaptive MPC and sublinear communication complexity is possible (in the local CRS model, for all deterministic functionalities).

Steganography and covert multi-party computation.

We explore the connection of the pseudorandom encoding hypothesis to various flavors of steganography. The goal of steganography, informally, is to embed secret messages in distributions of natural-looking messages, in order to hide them from external observers. While the standard setting for steganography relies on shared secret keys to encode the messages, we show that pseudorandom encodings naturally give rise to a strong form of keyless steganography. Namely, one can rely on pseudorandom encodings to encode any message into an innocent-looking distribution, without truly hiding the message (since anyone can decode the stream), but providing plausible deniability, in the sense that, even with the decoded message, it is impossible to tell apart whether this message was indeed encoded by the sender, or whether it is simply the result of decoding the innocent distribution.

Corollary (informal). Assuming pseudorandom encodings, then there exists a keyless steganographic protocol which provides plausible deniability.

Plausible deniability is an important security notion; in particular, an important cryptographic primitive in this area is the notion of (sender-)deniable encryption [START_REF] Canetti | Deniable Encryption[END_REF], which is known to exist assuming indistinguishability obfuscation [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF]. Deniable encryption enables to "explain" ciphertexts produced for some message to any arbitrary other message by providing corresponding random coins for a faked encryption process. We view it as an interesting open problem to build deniable encryption under the pseudorandom encoding hypothesis together with more standard cryptographic primitives; we make a first step in this direction and show the following:

5 Adaptively well-formed functionalities do not hide internal randomness. 6 Together with the conflict between cPREH rand ≈c and EOWFs with unbounded auxiliary input, this corrects a claim made in [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] that the impossibility result of adaptive MPC from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] would not extend to the CRS model.

the statistical variant of pseudorandom encodings, together with the existence of public-key encryption, implies deniable encryption. Interestingly, we also show that the computational randomized pseudorandom encoding hypothesis suffices to imply non-committing encryption, a weaker form of deniable encryption allowing to explain only simulated ciphertexts to arbitrary messages [START_REF] Canetti | Adaptively Secure Multi-Party Computation[END_REF].

Covert secure computation. Covert MPC [vHL05; CGOS07] is an intriguing flavor of MPC that aims at achieving the following strong security guarantee: if the output of the protocol is not "favorable," the transcript of the interaction should not leak any information to the parties parties, including whether any given party was actually taking part in the protocol. This strong form of MPC aims at providing security guarantees when the very act of starting a computation with other parties should remain hidden. As an example [START_REF] Luis Von Ahn | Covert two-party computation[END_REF], suppose that a CIA agent who infiltrated a terrorist group wants to make a handshake with another individual to find out whether she is also a CIA agent. Here, we show that pseudorandom encodings give rise to a general compiler transforming a standard MPC protocol into a covert one, in a round-preserving way. The idea is to encode each round of the protocol such that encoded messages look random. Together with the equivalence between adaptively secure MPC and pseudorandom encodings, this gives a connection between two seemingly unrelated notions of secure computation.

Corollary (informal).

Assuming adaptively secure MPC for all functionalities, there exists a round-preserving compiler that transforms a large class of "natural" MPC protocols into covert MPC protocols (in the static, semi-honest setting).

Other results. Due to our infeasibility results of PREH rand

≡s , distribution transforming encoders (DTEs) for all efficiently samplable distributions are infeasible. Even the computational relaxation of DTEs is infeasible assuming extractable one-way functions. Since all currently known constructions of honey encryption rely on DTEs, we conditionally refute the existence of honey encryption based on the DTE-then-encrypt framework from [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF]. On the positive side, due to our feasibility result of acPREH rand ≈c , computational honey encryption is feasible in the CRS model.

Theorem (informal). Assuming acPREH rand

≈c and a suitable symmetric-key encryption scheme (modeled as a random cipher), computational honey encryption for all efficiently samplable distributions exists in the CRS model.

Negative results for stronger notions of pseudorandom encodings

Below we describe how we gradually relax optimal compression via different notions of pseudorandom encodings and derive infeasibility results for all variants of pseudorandom encodings which restrict the encoding algorithm to be deterministic or require an information-theoretic pseudorandomness guarantee. This leaves computational randomized pseudorandom encodings as the best possible achievable notion.

Deterministic, statistical pseudorandom encodings.

The notion of pseudorandom encodings with a deterministic encoding algorithm and information-theoretic indistinguishability is perhaps the simplest notion one can consider. As we will prove in this paper, this notion recovers the notion of optimal compression: since the encoding algorithm for some source X is deterministic, it can be seen with an entropy argument that the output size of E X must be at most H ∞ (X), the min-entropy of X; otherwise, the distribution {E X (X)} can necessarily be distinguished from random with some statistically non-negligible advantage. Therefore, E X is an optimal and efficient compression algorithm for X, with decompression algorithm D X ; this is true even for the relaxation in the CRS model. The existence of efficient compression algorithms for various categories of samplers was thoroughly studied [START_REF] Luca Trevisan | Compression of Samplable Sources[END_REF]. In particular, the existence of compression algorithms for all efficiently samplable sources implies the inexistence of one-way functions (this is an observation attributed to Levin in [START_REF] Goldberg | Compression and Ranking[END_REF]) since compressing the output of a pseudorandom generator to its entropy would distinguish it from a random string, and the existence of one-way functions implies the existence of pseudorandom generators [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF]).

Theorem (informal).

Assuming the existence of one-way functions, neither PREH det ≡s nor cPREH det ≡s hold.

This is a strong impossibility result, as one-way functions dwell among the weakest assumptions in cryptography, [START_REF] Impagliazzo | A Personal View of Average-Case Complexity[END_REF]. One can circumvent this impossibility by studying whether compression can be achieved for more restricted classes of distributions, as was done e.g. in [START_REF] Luca Trevisan | Compression of Samplable Sources[END_REF]. Our work can be seen as pursuing an orthogonal direction. We seek to determine whether a relaxed notion of compression can be achieved for all efficiently samplable distributions. The relaxations we consider comprise the possibility to use randomness in the encoding algorithm, and weakening the requirement on the encoded distribution to being only computationally indistinguishable from random. Clearly, these relaxations remove one of the most important features of compression algorithms, which is that their outputs are smaller than their inputs (i.e., they compress). Nevertheless, the indistinguishability of the encoded distribution from the uniform distribution is another crucial feature of optimal compression algorithms, which has independent applications. 1.3.2 Deterministic, computational pseudorandom encodings. We now turn towards a relaxation where the encoded distribution is only required to be computationally indistinguishable from random, but the encoding algorithm is still required to be deterministic. This flavor is strongly connected to an important problem in cryptography: the problem of separating HILL entropy [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF] from Yao entropy [START_REF] Andrew | Theory and Applications of Trapdoor Functions (Extended Abstract)[END_REF]. HILL and Yao entropy are different approaches of formalizing computational entropy, i.e., the amount of entropy a distribution appears to have from the viewpoint of a computationally bounded entity. Informally, a distribution has high HILL entropy if it is computationally close to a distribution with high min-entropy; a distribution has high Yao entropy if it cannot be compressed efficiently. Finding a distribution which, under standard cryptographic assumptions, has high Yao entropy, but low HILL entropy constitutes a long standing open problem in cryptography. Currently, only an oracle separation [START_REF] Wee | On Pseudoentropy versus Compressibility[END_REF] and a separation for conditional distributions [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF] are known. To establish the connection between PREH det ≈c and this problem, we proceed as follows: informally, a deterministic pseudorandom encoding must necessarily compress its input to the HILL entropy of the distribution. That is, the output size of the encoding cannot be much larger than the HILL entropy of the distribution. This, in turn, implies that a distribution which admits such a pseudorandom encoding cannot have high Yao entropy.

In this work, we formalize the above argument, and show that the conditional separation of HILL and Yao entropy from [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF] suffices to refute PREH det ≈c . This separation holds under the assumption that non-interactive zero-knowledge proofs with some appropriate structural properties exist (which in turn can be based on standard assumptions such as the quadratic residuosity assumption). Thus, we obtain the following infeasibility result: Theorem (informal). If the quadratic residuosity assumption holds, then PREH det ≈c does not hold.

Hence, we may conclude that towards a feasible variant of pseudorandom encodings for all efficiently samplable distributions, requiring the encoding algorithm to be deterministic poses a strong restriction.

Randomized, statistical pseudorandom encodings.

We now consider the relaxation of perfect compression by allowing the encoding algorithm to be randomized while still requiring information-theoretic indistinguishability from randomness. This flavor of pseudorandom encoding was used in the context of honey encryption [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF]. Honey encryption is a cryptographic primitive which has been introduced to mitigate attacks on encryption schemes resulting from the use of low-entropy passwords. Honey encryption has the property that decrypting a ciphertext with an incorrect key always yields a valid-looking plaintext which seems to come from the expected distribution, thereby mitigating brute-force attacks. This is the same property that was useful in the previous PAKE example.

The study of honey encryption was initiated in [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF], where it was shown that honey encryption can naturally be constructed by composing a block cipher (modeled as a random cipher) with a distribution transforming encoder (DTE), a notion which is equivalent to our notion of pseudorandom encoding with randomized encoding and statistical pseudorandomness. The focus of [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF] was on obtaining such DTEs for simple and useful distributions. In contrast, we seek to understand the feasibility of this notion for arbitrary distributions. Intuitively, it is not straightforward to encode any efficient distribution into the uniform distribution; consider for example the distribution over RSA moduli, i.e., products of two random n-bit primes. Since no efficient algorithm is known to test membership in the support of this distribution, natural approaches seem to break down. In fact, we show in this work that this difficulty is inherent: building on techniques from [BCPR14; IKOS10], we demonstrate the impossibility of (randomized, statistical) pseudorandom encodings for all efficiently samplable distributions, under a relatively standard cryptographic assumption.

Theorem (informal). Assuming the sub-exponential hardness of the learning with errors (LWE) problem, PREH rand

≡s does not hold.

This result directly implies that under the same assumption, there exist efficiently samplable distributions (with input) for which no distribution transforming encoder exists. We view it as an interesting open problem whether this result can be extended to rule out the existence of honey encryption for arbitrary distributions under the same assumption.

Open questions and subsequent work

The most intriguing question left open by our work is whether the weakest variant of the pseudorandom encoding hypothesis cPREH rand ≈c , which is implied by iO, also implies iO. Very recently, this question was settled in the affirmative by Wee and Wichs [START_REF] Wee | Candidate Obfuscation via Oblivious LWE Sampling[END_REF] under the LWE assumption. More concretely, by modifying a heuristic iO construction of Brakerski et al. [START_REF] Brakerski | Candidate iO from Homomorphic Encryption Schemes[END_REF], they show that iO is implied by LWE if one is additionally given an oblivious LWE-sampler in the CRS model. Such a sampler, given a matrix A ∈ Z m×n q , generates outputs that are indistinguishable from LWE samples A • s + e without knowing the secrets s or the noise e. The existence of an oblivious LWE sampler is nontrivial even under the LWE assumption, because A can be such that A • s + e is not pseudorandom; however, such a sampler still follows from the invertible sampling hypothesis [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF], which we show to be equivalent to the pseudorandom encoding hypothesis. By proposing an explicit heuristic construction of (a relaxed flavor of) an oblivious LWE sampler, the end result of [START_REF] Wee | Candidate Obfuscation via Oblivious LWE Sampling[END_REF] is a construction of iO from a new "falsifiable" assumption.

Whether cPREH rand ≈c implies iO under weaker or different assumptions than LWE remains open. A potentially easier goal is using cPREH rand ≈c to construct public-key encryption from one-way functions. This is related to the possibility of constructing oblivious transfer from any public-key encryption in which public keys and ciphertexts are obliviously samplable [EGL85; GKMRV00], which is implied by public-key encryption and cPREH rand ≈c . Here cPREH rand ≈c is used to bypass the black-box separation between public-key encryption and oblivious transfer [START_REF] Gertner | The Relationship between Public Key Encryption and Oblivious Transfer[END_REF].

Finally, there is a lot of room for relaxing the intractability assumptions we use to rule out the statistical (cPREH rand ≡s ) and deterministic (cPREH det ≈c ) flavors of pseudorandom encodings.

Overview of techniques

In this section, we elaborate on some of our technical results in more detail. In the following, we identify a PPT sampler S with the distribution (family) ensemble it induces.

The relation to invertible sampling. A PPT sampler S is inverse samplable [DN00; IKOS10], if there exists an alternative sampler S inducing a distribution which is computationally indistinguishable to the distribution induced by S such that the computations of S can be efficiently inverted. Efficiently inverting the computation of S means that there exists an efficient inverse sampler S -1 which, given an output of S, recovers a well-distributed random tape for S to compute the given output in the following sense. The inverse sampled random tape is required to be computationally indistinguishable from the actually used random tape. More formally, a PPT sampler S is inverse samplable if there exists an efficient alternative sampler S and an efficient inverse sampler S -1 such that

y ← S(1 λ ) : y ≈ c y ← S(1 λ ) : y , ( 3
)
y ← S(1 λ ; r) : (r, y) ≈ c y ← S(1 λ ) : (S -1 (1 λ , y), y) . ( 4
)
We refer to Equation (3) as closeness and to Equation (4) as invertibility. If the sampler S admits an input m, the above is required to hold for all inputs m in the input space L, where S and S -1 both additionally receive m as input. In accordance with [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF], we refer to the hypothesis that all PPT algorithms with input are inverse samplable as the invertible sampling hypothesis. Restricting the invertible sampling hypothesis to algorithms which do not admit inputs is denoted the weak invertible sampling hypothesis. The concepts of inverse samplability and pseudorandom encodings are tightly connected. Suppose a PPT algorithm S is inverse samplable. Then, there exists an alternative and an inverse sampler (S, S -1 ) satisfying closeness and invertibility. Invertibility guarantees that the inverse sampler S -1 on input of a sample y from S(1 λ ), outputs a computationally welldistributed random tape r. Hence, with overwhelming probability over the choice of y ← S(1 λ ) and r ← S -1 (y), the alternative sampler on input of r, recovers y. In other words, the inverse sampler S -1 can be seen as encoding a given sample y, whereas the de-randomized alternative sampler S given this encoding as random tape, is able to recover y. Looking through the lens of pseudorandom encoding, this almost proves correctness except that y is sampled according to S(1 λ ) instead of S(1 λ ). This difference can be bridged due to closeness. We now turn towards showing pseudorandomness of the encoded distribution. Due to closeness, the distributions {y ← S(1 λ ) : (S -1 (1 λ , y), y)} and {y ← S(1 λ ) : (S -1 (1 λ , y), y)} are computationally indistinguishable.

Invertibility guarantees that, given a sample y from S(1 λ ), an encoding of y is indistinguishable to uniformly chosen randomness conditioned on the fact that decoding yields y. Removing y from this distribution, almost corresponds to pseudorandomness, except that y is sampled according to S(1 λ ) instead of S(1 λ ). Again, we are able to bridge this gap due to closeness. Note that we crucially use the fact that the initial randomness used by S resides outside of the view of an adversary. Summing up, if a PPT sampler S is inverse samplable, then it can be pseudorandomly encoded.

Interestingly, this connection turns out to be bidirectional. Suppose a PPT algorithm S can be pseudorandomly encoded. Then, there exists an efficient encoding algorithm E S and an efficient deterministic decoding algorithm D S satisfying correctness and pseudorandomness. Looking through the lens of invertible sampling, we identify the decoding algorithm to correspond to the alternative sampler (viewing the random tape of the alternative sampler as explicit input to D S ) and the encoding algorithm to correspond to the inverse sampler. Pseudorandomness guarantees that E S (S(1 λ )) is indistinguishable from uniform randomness. Hence, applying the decode algorithm D S on uniform randomness is indistinguishable from applying D S to outputs of E S (S(1 λ )). Correctness guarantees that D S (E S (y)) for y sampled according to S(1 λ ) recovers y with overwhelming probability. Thus, the distribution induced by applying D S on uniform randomness is computationally close to the distribution induced by S(1 λ ). This shows closeness. For the purpose of arguing about invertibility, consider the distribution A := {y ← D S (r) : (r, y)}. Due to pseudorandomness r can be considered an encoded sample from S(1 λ ). Hence, A is indistinguishable to the distribution, where r is produced by E S (y ) for some independent y ← S(1 λ ), i.e.

y ← D S (r) : (r, y) ≈ c y ← S(1 λ ), r ← E S (y ), y ← D S (r) : (r, y) .
Note that by correctness, y and y are identical with overwhelming probability. Therefore, A is indistinguishable to y ← S(1 λ ), r ← E S (y ) : (r, y ) . Since sampling y via D S applied on uniform randomness is computationally close to the above distribution due to closeness, invertibility follows. Summing up, a sampler S can be pseudorandomly encoded if and only if it is inverse samplable.

Likewise to the variations and relaxations described for pseudorandom encodings, we vary and relax the notion of invertible sampling. The inverse sampler can be required to be deterministic or allowed to be randomized. Further, closeness and invertibility can be required to hold information theoretically or computationally. We denote these variants as ISH rand ≈c , ISH rand ≡s , ISH det ≈c and ISH det ≡s . To circumvent impossibilities in the plain model, we also define the relaxations in the common reference string model in static and adaptive flavors, denoted the prefix "c" and "ac", respectively. The above equivalence extends to all introduced variations of the pseudorandom encoding and invertible sampling hypotheses.

The static-to-adaptive transformation. The static variant of pseudorandom encodings in the CRS model only guarantees correctness and pseudorandomness as long as the input m for the sampler S is chosen independently of the CRS. The adaptive variant, on the other hand, provides correctness and pseudorandomness even for adaptive choices of inputs. Adaptive notions always imply their static analogues. Interestingly, for pseudorandom encodings, the opposite direction is true as well. The core idea is to use an indirection argument (similar to [HJKSWZ16; CPR17; CPV17]) to delay CRS generation until during the actual encoding process. Thus, the advantage stemming from adaptively choosing the input is eliminated.

Suppose that the static variant of the pseudorandom encoding hypothesis in the CRS model is true and let S be some PPT sampler. Since S can be pseudorandomly encoded in the CRS model with static choice of inputs, there exist algorithms (Setup , E , D ) such that static correctness and pseudorandomness hold. Further, the algorithm Setup can also be pseudorandomly encoded as above. Let (Setup , E , D ) be the corresponding algorithms such that static correctness and pseudorandomness hold. Note that since the sampler Setup does not expect an input, static and adaptive guarantees are equivalent.

Then, the sampler S can be pseudorandomly encoded in the CRS model with adaptive choice of inputs as follows. Initially, we sample a common reference string crs via Setup (1 λ ) and make it available to the parties. Given crs and a sample y from S(m), adaptive encoding works in two phases. First, a fresh CRS crs is sampled via Setup (1 λ ) and pseudorandomly encoded via r 1 ← E (crs , crs ). Second, the given sample y is pseudorandomly encoded via r 2 ← E (crs , m, y). The encoding of y then consists of (r 1 , r 2 ). To decode, the CRS crs is restored via D (crs , r 1 ). Then, using crs , the original sample y is recovered via D (crs , m, r 2 ).

Since crs is chosen freshly during the encoding process, the input m which may depend on crs , cannot depend on crs . Further, the distribution Setup does not expect an input. Hence, static guarantees suffice.

To realize that adaptive pseudorandomness holds, consider the encoding of S(m) for some adaptively chosen message m. Since the view of A when choosing the message m is independent of crs , static pseudorandomness can be applied to replace the distribution E (crs , m, S(m)) with uniform randomness. Further, since the sampler Setup does not expect any input, static pseudorandomness suffices to replace the distribution E (crs , Setup (1 λ )) with uniform randomness. This proves adaptive pseudorandomness.

The adaptive variant of correctness follows similarly from the static variant of correctness. Consider the distribution of decoding an encoded sample of S(m), where m is adaptively chosen. Since the sampler Setup does not expect an input, static correctness can be applied to replace decoding D (crs , r 1 ) with the crs sampled during encoding. Again, since crs does not lie in the view of the adversary when choosing the message m, static correctness guarantees that decoding succeeds with overwhelming probability. This proves adaptive correctness.

On deterministic pseudorandom encoding and compression. The notion of pseudorandom encoding is inspired by the notion of compression. A tuple of deterministic functions (E X , D X ) is said to compress a source X λ to length m(λ) with decoding error (λ [START_REF] Wee | On Pseudoentropy versus Compressibility[END_REF][START_REF] Luca Trevisan | Compression of Samplable Sources[END_REF]. Pseudorandom encoding partially recovers the notion of compression if we require the encoding algorithm to be deterministic. If a source X λ can be pseudorandomly encoded with a deterministic encoding algorithm having output length n(λ), then X λ is compressible to length n(λ). Note, however, that the converse direction is not true. Compression and decompression algorithms for a compressible source do not necessarily encode that source pseudorandomly. The output of a compression algorithm is not required to look pseudorandom and, in some cases, admits a specific structure which makes it easily distinguishable from uniform randomness, e.g. instances using Levin search, [START_REF] Luca Trevisan | Compression of Samplable Sources[END_REF].

), if (i) Pr[D X (E X (X λ )) = X λ ] ≤ (λ) and (ii) E[|E X (X λ )|] ≤ m(λ), see
Clearly, the requirement for correctness, poses a lower bound on the encoding length n(λ), [START_REF] Elwood | A mathematical theory of communication[END_REF]. Conversely, requiring the encoding algorithm E X to be deterministic means that the only source of entropy in the distribution E X (X λ ) originates from the source X λ itself. Hence, for the distributions E X (X λ ) and the uniform distribution over {0, 1} n(λ) to be indistinguishable, the encoding length n(λ) must be "sufficiently small". We observe that correctness together with the fact that E X is deterministic implies that the event E X (D X (E X (X λ ))) = E X (X λ ) occurs with overwhelming probability. Applying pseudorandomness yields that E X (D X (U n(λ) )) = U n(λ) holds with overwhelming probability, wherefore we can conclude that D X operates almost injectively on the set {0, 1} n(λ) . Hence, the (smooth) min-entropy of D X (U n(λ) ) is at least n(λ).

Considering information theoretical pseudorandomness, the distributions D X (U n(λ) ) and X λ are statistically close. Hence, by the reasoning above, the encoding length n(λ) is upper bounded by the (smooth) min-entropy of the source X λ . In conclusion, if a distribution can be pseudorandomly encoded such that the encoding algorithm is deterministic satisfying statistical pseudorandomness, then this distribution is compressible to its (smooth) min-entropy. Using a technical "Splitting Lemma", this extends to the relaxed variant of the pseudorandom encoding hypothesis in the CRS model.

Considering computational pseudorandomness, by a similar argument as above, we obtain that X λ is computationally close to a distribution with min-entropy n(λ). This does not yield a relation between the encoding length and the min-entropy of the source. However, we do obtain relations to computational analogues of entropy. Computational entropy is the amount of entropy a distribution appears to have from the perspective of a computationally bounded entity. The notion of HILL entropy [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF] is defined via the computational indistinguishability from a truly random distribution. More formally, a distribution X λ has HILL entropy at least k, if there exists a distribution with min-entropy k which is computationally indistinguishable from X λ . Hence, the encoding length n(λ) is upper bounded by the HILL entropy of the source X λ . Another important notion of computational entropy is the notion of Yao entropy [START_REF] Andrew | Theory and Applications of Trapdoor Functions (Extended Abstract)[END_REF]. Yao entropy is defined via the incompressibility of a distribution. More precisely, a distribution X λ has Yao entropy at least k if X λ cannot be efficiently compressed to length less than k (and successfully decompressed). If a distribution can be pseudorandomly encoded with deterministic encoding, then it can be compressed to the encoding length n(λ). This poses an upper bound on the Yao entropy of the source. In summary, this yields n(λ) ≤ H HILL (X λ ) and H Yao (X λ ) ≤ n(λ).

(5)

However, due to [HLR07; LMs05], if the Quadratic Residuosity Assumption (QRA) is true, then there exist distributions which have low conditional HILL entropy while being conditionally incompressible, i.e. have high conditional Yao entropy. 7 The above observations, particularly Equation ( 5), can be extended to conditional HILL and conditional Yao entropy, by considering PREH det ≈c for PPT algorithms with input. Therefore, if the Quadratic Residuosity Assumption is true, PREH det ≈c cannot be true for those distributions. Unfortunately, we do not know whether this extends to the relaxed variants of the pseudorandom encoding hypothesis admitting access to a CRS. On a high level, the problem is that the HILL entropy, in contrast to the min-entropy, does not remain untouched when additionally conditioning on some common reference string distribution, even though the initial distribution is independent of the CRS. Hence, the splitting technique can not be applied here.

Preliminaries

We denote by [n] the set {1, . . . , n}. Throughout this paper, λ denotes a security parameter which is given as input to all algorithms. A probabilistic polynomial time (PPT) algorithm (also referred to as an efficient algorithm) runs in time polynomial in the (implicit) security parameter λ. In this paper, we consider non-uniform polynomial time adversaries, i.e. polynomial time adversaries receiving a polynomially bounded auxiliary input (or advice) depending only on the security parameter.8 A function f (λ) is negligible if for any polynomial p there exists a bound B ∈ N such that, for any integer

k ≥ B, |f (k)| ≤ 1 |p(k)| . A function g is overwhelming if 1 -g(λ) is a negligible function.
Given a finite set A, the notation x ← A means a uniformly random assignment of an element of A to the variable x. Given a probability distribution D, the notation x ← D means sampling an element according to the distribution D and assigning that element to x. We denote the uniform distribution over bitstrings of length n by U n . Let X, Y be two distributions over a set A. Then, the statistical distance between X and Y is defined as

∆(X, Y ) := a∈A |Pr[X = a] -Pr[Y = a]|.
We say that two distributions are statistically close if their statistical distance is negligible.

A source X is a probability distribution on strings. A family of sources is a probability ensemble (X λ ) λ∈N , where X λ is distributed on {0, 1} p(λ) for some polynomial p. A family of sources (X m ) m∈L can also be indexed by strings from some language L ⊆ {0, 1} + , where X m is distributed on {0, 1} p(|m|) for some polynomial p. We say that a source X λ is efficiently samplable if there is a PPT algorithm S such that S(1 λ ) is distributed according to X λ for all λ ∈ N. We say that a source X m indexed by strings is efficiently samplable if there exists a PPT algorithm S such that S(m) is distributed according to X m for all m ∈ L.

In game based proofs, it will be useful to let out i denote the output of game G i . If we want to make the adversary A playing G i explicit, we write out i,A . Unless stated otherwise, we consider stateful adversaries.

The hypotheses stated in the following are formulated for the class of all PPT algorithms S, possibly excluding pathological cases. In some cases it is sufficient to consider a weaker variant of these hypotheses which is only required to be true for a specific class of PPT algorithms S. In this case we say that the respective hypothesis holds for the class S.

The pseudorandom encoding hypothesis

We the study the ability to encode efficiently samplable distributions into the uniform distribution. In the following, an efficiently samplable distribution will be defined by the corresponding sampler S with input space L. A distribution defined via S can be pseudorandomly encoded if there exists an efficient potentially randomized encoding algorithm E S and an efficient deterministic decoding algorithm D S such that for all m ∈ L, the probability for the event D S (E S (S(m))) = S(m) is overwhelming and the distribution E S (S(m)) is indistinguishable from the uniform distribution U n(λ) . We work with the hypothesis that every efficiently samplable distribution can be pseudorandomly encoded. In this section, we formally define the pseudorandom encoding hypothesis and its variations.

Definition 1 (Pseudorandom encoding hypothesis, PREH rand ≈c ). For every PPT algorithm S, there exist efficient algorithms E S (the encoding algorithm) with output length n(λ) and D S (the decoding algorithm), where D S is deterministic and E S is randomized satisfying the following two properties.

Correctness. For all inputs

m ∈ L, dec-error (λ) := Pr y ← S(m) : D S (m, E S (m, y)) = y is negligible.
Pseudorandomness. For all PPT adversaries A and all inputs m ∈ L,

Adv pre A,m (λ) := Pr[Exp pre A,m,0 (λ) = 1] -Pr[Exp pre A,m,1 (λ) = 1] ≤ negl(λ),
where Exp pre A,m,0 and Exp pre A,m,1 are defined in Figure 2. Remark 1. Definition 1 formulated for PPT algorithms S which do not admit an input m is called the weak PREH rand ≈c .

Exp pre A,m,0 (λ) r ← {0, 1} p(λ) y := S(m; r) return A(m, ES(m, y)) Exp pre A,m,1 (λ) u ← {0, 1} n(λ) return A(m, u)
Remark 2 (PREH det ≈c , PREH rand ≡s , PREH det ≡s ). Definition 1 can be tuned in two dimensions: the encode algorithm can be required to be deterministic or allowed to be randomized, and the pseudorandomness property can be required to hold statistically or computationally. We denote these variants as PREH β α , where α ∈ {≈ c , ≡ s } and β ∈ {rand, det}.

Remark 3. Definition 1 demands indistinguishability between encoded samples and the uniform distribution over all bitstrings of some length n(λ). This requirement can be relaxed to indistinguishability from the uniform distribution over some efficiently samplable and efficiently recognizable set R of size N , where elements in R can be represented with O(log N ) bits.

Deterministic encoding and compatible samplers

Requiring the encoding algorithm E S to be deterministic entails the existence of what we call "incompatible samplers" for which PREH det ≡s and even PREH det ≈c are unconditionally false. For instance, consider the sampler S * which on input of 1 λ uniformly chooses an element from the set {00, 01, 10} ⊂ {0, 1} 2 . Assume PREH det ≈c is true for S * . Then, correctness requires that with overwhelming probability over the sampling process y ← S * (1 λ ), D S * (E S * (y)) = y. Hence, E S * must map into the set {0, 1} k for k ≥ 2 (otherwise there is an correctness error of at least 1 3 ). Pseudorandomness, on the other hand, requires that E S * (S * (1 λ )) is computationally indistinguishable from uniform distribution over {0, 1} k . However, since E S * is a deterministic algorithm, |supp(E S * (S * (1 λ )))| = 3. Therefore, there exists at least an element in {0, 1} k \ supp(E S * (S * (1 λ ))). An adversary can easily determine this element by evaluating E S * on each element in the support of S * (if the support of the sampler was super-polynomial, this would not be possible for a PPT adversary, but very well possible for an unbounded one).

Another example of such an incompatible sampler is a sampler with large support but low min-entropy (i.e. a sampler that has (at least one) very likely output and many much less likely outputs). For instance, consider the sampler S with probability distribution

Pr[S (1 λ ) = 0 λ ] = 1 2 Pr[S (1 λ ) = 1 x] = 1 2 λ for each x ∈ {0, 1} λ-1
Assume PREH det ≈c is true for S . Then, correctness requires that an overwhelming fraction of the elements of the form 1 x for x ∈ {0, 1} λ-1 are correctly decodable. Furthermore, since the element 0 λ has a non-negligible probability to occur, it needs to be correctly decodable. Let the support of E S (S (1 λ )) be (a subset of) {0, 1} λ-1 . Pseudorandomness requires that E S (S (1 λ )) is indistinguishable from uniform distribution over {0, 1} λ-1 . However, since E S is deterministic, the value E S (0 λ ) occurs with probability at least 1 2 and, due to correctness, all other values E S (1 x) occur with far lower probability.

In order to obtain a meaningful definition of PREH det ≈c and PREH det ≡s , we restrict these hypotheses to only hold for specific classes of what we refer to as "compatible samplers" S comp and S stat , respectively.

Definition 2 (Compatibility with deterministic encodings).

A sampler S is statistically compatible with deterministic encodings if there exists a set A whose cardinality is a power of 2, such that Pr[S(1 λ ) ∈ A] is overwhelming, and S is -flat on A, i.e. for all a ∈ A we have

|Pr[S(1 λ ) = a] -1 |A| | ≤ (λ)
, for some negligible function . The class S stat contains all samplers which statistically compatible with deterministic encodings.

A sampler S is computationally compatible with deterministic encodings if S ∈ S stat or if

|supp(S(1 λ ))| is super-polynomial and the min-entropy H ∞ (S(1 λ )) ∈ ω(log(λ)) (i.

e. the most likely event occurs with negligible probability). The class S comp contains all samplers which are computationally compatible with deterministic encodings.

If S admits an input z ∈ L, S is statistically or computationally compatible with deterministic encodings if the corresponding criterion is met for all z ∈ L.

The above criterion for S stat may seem unnatural. We note that by relaxing Definition 1 as noted in Remark 3, requiring high min-entropy suffices for a sampler to be statistically compatible with deterministic encodings.

We note that -flatness is a weaker criterion than statistical closeness to the uniform distribution over A. -flatness on A corresponds to closeness to the uniform distribution over A with respect to the infinity norm. Statistical closeness, however, is formalized with respect to the Manhatten norm. The deterministic pseudorandom encodings restricted to compatible samplers still has interesting connections.

Let iPRG be an injective PRG with stretch . Let S be the sampler which on input of 1 λ draws a uniform seed s ∈ {0, 1} λ and outputs iPRG(s) ∈ {0, 1} (λ) . Clearly, S is statistically compatible with deterministic encodings.

Lemma 1. Let PRG be a PRG with stretch and let S be the sampler which on input of 1 λ produces the distribution PRG(U λ ). Then, S ∈ S stat .

Proof. Let

A := PRG({0, 1} λ ) and let A ⊆ {0, 1} (λ) \ A such that for A := A ∪ A we have |A| = 2 λ . We have Pr[S(1 λ ) ∈ A] = 1.
For flatness on A, we upper bound the probability of the most likely event in A. Due to pseudorandomness of PRG, all (non-uniform) PPT adversary distinguishing the distributions S(1 λ ) and U (λ) have a negligible advantage. Assume there exists an a ∈ A , such that Pr[S(1 λ ) = a] ≥ δ(λ), for a non-negligible function δ. Then, the most likely value in A could be used as polynomial advice string allowing a non-uniform adversary to recognize the distribution S(1 λ ) with non-negligible probability δ(λ). (A uniform adversary can sample a random seed and evaluate the PRG. The thereby obtained output equals the most likely event a with probability δ(λ). Hence, a uniform adversary has advantage at least δ(λ) 2 in distinguishing.) Therefore, for all a ∈ A , Pr[S(1 λ ) = a] ≤ (λ) for some negligible function . Hence, for all a ∈ A, we have

|Pr[S(1 λ ) = a] -1 |A| | ≤ (λ) + 2 -λ which is negligible.
Lemma 2. Let PRG be a PRG with stretch . Let S be the sampler which on input of x ∈ L produces the distribution {y 1 ← PRG(U |x| ), y 2 ← D x,y 1 : (y 1 , y 2 )} for any distribution D. Then, S ∈ S comp .

Proof. Let λ := |x|. Using the argument of Lemma 1, all images in PRG({0, 1} λ ) have only a negligible probability to occur. Therefore, for all x ∈ L and all (y 1 , y 2 ) ∈ supp(S(x)), we have Pr[S(1 λ , x) = (y 1 , y 2 )] is negligible. Therefore, S ∈ S comp .

Impossibility of universal encoding

It is essential that the decoding algorithm D S depends on the sampler S, since due to pseudorandomness, D S on input of a random string needs to produce a sample that is in some sense close to the distribution produced by S. This argument does not hold necessarily for the encode algorithm. In [START_REF] Luca Trevisan | Compression of Samplable Sources[END_REF], universal compression was studied. This translates to the following definition of PREH with universal encoding.

Definition 3 (PREH β α with universal encoding). Let S be a class of sampling algorithms. We say PREH β α with universal sampling is true for the class S, if there exists a universal encoding algorithm E, such that for every PPT algorithm S ∈ S, there exists an efficient deterministic decoding algorithm D S , such that correctness and pseudorandomness are satisfied.

In contrast to universal compression, pseudorandom encoding with universal encoding is impossible.

Lemma 3. PREH with universal encoding is not possible for arbitrary classes of samplers.

Proof. Consider the class of sampling algorithms

S = {S 1 , S 2 , S 3 } over {0, 1} p(λ) with support Y i,λ := supp(S i (1 λ )). We require that for i ∈ {1, 2}, |Y i,λ | = 2 k+1 , |Y 1,λ ∩ Y 2,λ | = 2 k , Y 1,λ ∩ Y 2,λ = Y 3,λ for k ∈ O(log λ)
, and that S 1 , S 2 and S 3 produce uniform samples over their support (i.e. correspond to flat distributions). We note that S 1 , S 2 , S 3 ∈ S stat . For notational convenience we omit the dependency on λ in the following.

Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. Assume toward a contradiction, that PREH β α with universal encoding is true for the class S of sampling algorithms above. Let {0, 1} n(λ) be the range of E. Due to correctness, for i ∈ {1, 2}, there is a negligible function , such that

Pr y←Y i [D S i (E(y)) = y] = y ∈Y i Pr y←Y i [D S i (E(y)) = y ∧ y = y ] = 1 |Y i | y ∈Y i Pr y←Y i [D S i (E(y)) = y | y = y ] ≤ (λ) Since |Y i | is polynomial, for each y ∈ Y i , Pr[D S i (E(y)) = y] ≥ 1-(λ)
for some negligible function , where the probability is solely over the randomness of E. Hence, for all

y ∈ Y 3 = Y 1 ∩ Y 2 , Pr[u ← E(y) : y = D S 1 (u) = D S 2 (u) = D S 3 (u)] ≥ 1 -(λ)
for some negligible function . Due to Theorem 2 (see Section 5.3), for i ∈ {1, 2, 3}, the distribution {u ← U n(λ) : D S i (u)} is computationally (statistically) close to the distribution produced by S i (1 λ ). Hence, (up to some negligible fraction ) the algorithms D S 1 and D S 2 map at most half of the strings in {0,

1} n(λ) into the same set Y 1 ∩ Y 2 = Y 3 .
We build an adversary A on pseudorandomness with respect to sampler S 3 as follows. On input of u, A outputs 1 if and only if

D S 1 (u) = D S 2 (u). Pr[Exp pre A,0 (λ) = 1] ≥ 1 -(λ) Pr[Exp pre A,1 (λ) = 1] ≤ 1 2 -(λ)
Therefore, A has a non-negligible advantage Adv pre A (λ).

The pseudorandom encoding hypothesis with setup

We obtain a natural relaxation of the pseudorandom encoding hypothesis by introducing public parameters. We refer to these public parameters as global or non-programmable common reference string. That is, a distribution defined via S can be pseudorandomly encoded in this relaxed sense, if there exists a probabilistic setup algorithm Setup S and encode and decode algorithms as before such that for all m ∈ L, the event D S (crs, E S (crs, S(m))) = S(m) is overwhelming, where the probability is also over the choice of crs, and the distribution (Setup Correctness. For all PPT adversaries A,

S (1 λ ), E S (Setup S (1 λ ), S(m))) is indistinguishable from the distribution (Setup S (1 λ ), U n(λ)
c-dec-error A (λ) := Pr    m ← A(1 λ ) crs ← Setup S (1 λ ) y ← S(m) : D S (crs, m, E S (crs, m, y)) = y   
is negligible. Pseudorandomness. For all PPT adversaries A,

Adv crs-pre A (λ) := Pr[Exp crs-pre A,0 (λ) = 1] -Pr[Exp crs-pre A,1 (λ) = 1]
is negligible, where Exp crs-pre A,0

and Exp crs-pre

A,1
are defined in Figure 3.

Exp crs-pre A,0 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) r ← {0, 1} p(λ)
y := S(m; r) return A(crs, m, ES(crs, m, y))

Exp crs-pre A,1 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) u ← {0, 1} n(λ)
return A(crs, m, u) We note that assuming non-uniform adversaries, correctness and pseudorandomness defined in Definition 4 can be equivalently defined by quantifying over all messages m ∈ L. Definition 4 is static in the sense that the inputs m ∈ L are required to be chosen statically, i.e. independently of crs. In the following, we define the corresponding adaptive variant.

Definition 5 (Adaptive pseudorandom encoding hypothesis with setup, acPREH rand ≈c ). For every PPT algorithm S, there exists a PPT algorithm Setup S , efficient algorithms (E S , D S ), where D S is deterministic and E S is randomized (with output length n(λ)) satisfying the following two requirements.

Correctness. For all PPT adversaries

A, ac-dec-error A (λ) := Pr    crs ← Setup S (1 λ ) m ← A(crs) y ← S(m) : D S (crs, m, E S (crs, m, y)) = y    is negligible. Pseudorandomness. For all PPT adversaries A, Adv a-crs-pre A (λ) := Pr[Exp a-crs-pre A,0 (λ) = 1] -Pr[Exp a-crs-pre A,1 (λ) = 1]
is negligible, where Exp a-crs-pre A,0 and Exp a-crs-pre A,1 are defined in Figure 4. Definition 6 (cPREH det ≈c , cPREH rand ≡s , cPREH det ≡s , acPREH det ≈c , acPREH rand ≡s , acPREH det ≡s ). Definitions 4 and 5 can be tuned in two dimensions: the encoding algorithm can be required to be deterministic or allowed to be randomized, and the closeness and invertibility properties can be required to hold statistically or computationally. We denote these variants as cPREH β α and acPREH β α , respectively, where α ∈ {≈ c , ≡ s } and β ∈ {rand, det}.

Exp a-crs-pre A,0 (λ) crs ← Setup S (1 λ ) m ← A(crs) r ← {0, 1} p(λ) y := S(m; r) return A(crs, m, ES(crs, m, y)) Exp a-crs-pre A,1 (λ) crs ← Setup S (1 λ ) m ← A(crs) u ← {0, 1} n(λ) return A(crs, m, u)
Remark 4 (Universal setup). In Definitions 4 and 5, we allow the algorithm Setup S to depend on the sampler S. A somewhat incomparable variant of this definition is to require the existence of a universal setup algorithm Setup(1 λ , B) for B ∈ N which provides the above guarantees for all samplers which can be represented with B bits. We refer to this variant as universal cPREH β α and universal acPREH β α , respectively.

Remark 5 (Common random string). We will denote the strengthening of the pseudorandom encoding hypothesis as in Definitions 4 and 5, where the setup algorithm Setup S is required to sample uniform random strings, as the pseudorandom encoding hypothesis with a common random string.

Note that in Definitions 4 and 5, we implicitly only consider legitimate adversaries which guarantee that m ∈ L. For the sake of avoiding notational overhead, we do not make this explicit.

Static-to-adaptive transformation

Clearly, Definition 5 implies Definition 4. Interestingly, the opposite direction is true as well by an "indirection" argument similar as in [START_REF] Hofheinz | How to Generate and Use Universal Samplers[END_REF]. Similar techniques where also used in the context of non-committing encryption [START_REF] Canetti | Optimal-Rate Non-Committing Encryption[END_REF] and adaptive multi-party computation [START_REF] Canetti | Better Two-Round Adaptive Multi-party Computation[END_REF].

Theorem 1. Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. If cPREH β α is true, then acPREH β α is true.
Proof. We prove the statement for the computational randomized case. The proof directly extends to the remaining cases.

Let S be a PPT sampler with input space L. Since cPREH rand ≈c is true, for the PPT sampler S, there exist (Setup S , E S , D S ) with output length n (λ) such that correctness and pseudorandomness hold (statically) as in Definition 4. Again, since cPREH rand ≈c is true, for the PPT sampler Setup S , there exist (Setup , E , D ) with output length n (λ) such that correctness and pseudorandomness hold (statically).9 Note that Setup S does not expect an input.

In Figure 5, we define algorithms (Setup S , E S , D S ) satisfying adaptive correctness and pseudorandomness, as in Definition 5.

On a high level, since crs is chosen freshly and independently after the adversary fixes the message m, selective security suffices. Furthermore, since the distribution of crs has no input, selective security is sufficient.

Adaptive correctness

We define a series of hybrid games to prove correctness, see Figure 6. The game hop from G 0 to G 1 only conceptional and Pr[out Claim. For all PPT adversaries A, there exists a PPT adversary A, such that |Pr

0 = 1] = Pr[out 1 = 1]. Setup S (1 λ ) crs ← Setup (1 λ ) crs := crs return crs ES(crs, m, y) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) r2 ← E S (
G0 crs ← Setup (1 λ ) m ← A(crs ) y ← S(m) / / encode crs ← Setup S (1 λ ) r1 ← E (crs , crs ) r2 ← E S (crs , m, y) / / decode crs D := D (crs , r1) yD := D S (crs D , m, r2) return yD = y G1 crs ← Setup (1 λ ) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) crs D := D (crs , r1) m ← A(crs ) y ← S(m) r2 ← E S (crs , m, y) yD := D S (crs D , m, r2) return yD = y G2 crs ← Setup (1 λ ) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) crs D := D (crs , r1) m ← A(crs ) y ← S(m) r2 ← E S (crs , m, y) yD := D S (crs , m, r2) return yD = y G3 crs ← Setup (1 λ ) m ← A(crs ) crs ← Setup S (1 λ ) y ← S(m) r2 ← E S (
[out 2 = 1] -Pr[out 1 = 1]| ≤ c-dec-error (Setup ,E ,D ),A (λ). Proof. The games G 1 and G 2 proceed exactly identically if crs D = crs . Let E be the event that crs = crs D . We have that out 1 = 1 ∧ ¬E ⇔ out 2 ∧ ¬E. Due to correctness of (Setup , E , D ), Pr      crs ← Setup(1 λ ) crs ← Setup S (1 λ ) r 1 ← E (crs , crs ) crs D := D (crs , r 1 ) : crs D = crs     
is negligible. Hence, the Difference Lemma (due to Shoup, [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF]) upper bounds

|Pr[out 2 = 1] -Pr[out 1 = 1]| ≤ Pr[E].
The game hop from G 2 to G 3 only conceptional and Pr[out

2 = 1] = Pr[out 3 = 1].
Claim. For all PPT adversaries A, there exists a PPT adversary A, such that Pr[out

3 = 1] ≥ 1 -c-dec-error (Setup S ,E S ,D S ),A (λ).
Proof. Due to correctness of (Setup S , E S , D S ), we have that for all PPT adversaries A,

Pr        m ← A(1 λ ) crs ← Setup S (1 λ ) y ← S(m) r ← E S (crs , m, y) y D := D S (crs , m, r) : y = y D       
is overwhelming. Consider the PPT adversary A which proceeds as follows.

A(1 λ ) crs ← Setup (1 λ ) m ← A(crs ) return m
Therefore, for all PPT adversaries A, Pr[out 3 = 1] is overwhelming.

Thus, we have ac-dec-error

(Setup S ,E S ,D S ),A (λ) ≤ c-dec-error (Setup ,E ,D ),A (λ) + c-dec-error (Setup S ,E S ,D S ),A (λ)
for some PPT adversaries A and A .

Adaptive pseudorandomness

We define a series of hybrid games to prove pseudorandomness, see Figure 7.

G0 crs ← Setup (1 λ ) m ← A(crs ) y ← S(m) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) r2 ← E S (crs , m, y) return A(crs , m, r1 r2) G1 crs ← Setup (1 λ ) m ← A(crs ) y ← S(m) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) r2 ← {0, 1} n (λ) return A(crs , m, r1 r2) G2 crs ← Setup (1 λ ) crs ← Setup S (1 λ ) r1 ← E (crs , crs ) m ← A(crs ) r2 ← {0, 1} n (λ) return A(crs , m, r1 r2) G3 crs ← Setup (1 λ ) r1 ← {0, 1} n (λ) m ← A(crs ) r2 ← {0, 1} n (λ)
return A(crs , m, r1 r2) Fig. 7. Hybrid games for the proof of adaptive pseudorandomness.

Claim. For all PPT adversaries A, there exists a PPT adversary A, such that |Pr[out

1 = 1] -Pr[out 0 = 1]| ≤ Adv crs-pre (Setup S ,E S ,D S ),A (λ).
Proof. Construct an adversary A on static pseudorandomness relative to (Setup S , E S , D S ) as follows. On input of 1 λ , A samples crs ← Setup (1 λ ) calls A on input of crs , and outputs the message m produced by A. In return, A receives crs ← Setup S (1 λ ) and either u := E S (crs , m, S(m)) or a uniform random string u ← {0, 1} n (λ) from Exp crs-pre (Setup S ,E S ,D S ),A,b (λ). A computes r 1 ← E (crs , crs ), calls A on input of (crs , m, r 1 u) and returns A's output. See Figure 8 for a description of A. If A plays Exp crs-pre (Setup S ,E S ,D S ),A,0 (λ), then it perfectly simulates G 0 . On the other hand, if A plays Exp crs-pre (Setup S ,E S ,D S ),A,1 (λ), then it perfectly simulates G 1 . Hence, we have

A(1 λ ) crs ← Setup (1 λ ) crs := crs m ← A(crs ) return m A(crs , m, u) / / u ← E S (crs , m, S(m)) or u ← {0, 1} n (λ) r1 ← E (crs , crs ) return A(crs , m, r1 u)
|Pr[out 1 = 1] -Pr[out 0 = 1]| ≤ Adv crs-pre (Setup S ,E S ,D S ),A (λ).
The game hop from G 1 to G 2 is only conceptional and Pr[out

2 = 1] = Pr[out 1 = 1].
Claim. For all PPT adversaries A, there exists a PPT adversary A, such that

|Pr[out 3 = 1] -Pr[out 2 = 1]| ≤ Adv crs-pre (Setup ,E ,D ),A (λ).
Proof. Construct an adversary A on static pseudorandomness relative to (Setup , E , D ) as follows. On input of 1 λ , A returns ⊥ since the input space L of the sampler Setup S (1 λ ) is

A(1 λ ) return ⊥ A(crs , u) / / u ← E (crs , Setup (1 λ )) or u ← {0, 1} n (λ) m ← A(crs ) r2 ← {0, 1} n (λ)
return A(crs , m, u r2) Fig. 9. Adversary used for the game hop from G2 to G3.

empty. In return, A receives crs sampled via Setup (1 λ ) and u which is either produced via E (crs , Setup (1 λ )) or via uniform sampling from {0, 1} n (λ) . A calls A on input of crs and receives a message m from A. Finally, A samples r 2 ← {0, 1} n (λ) , calls A on input of (crs , m, u r 2 ) and outputs his output. See Figure 9 for a description of A.

If A plays Exp crs-pre (Setup ,E ,D ),A,0 (λ), then it perfectly simulates G 2 . On the other hand, if A plays Exp crs-pre (Setup ,E ,D ),A,1 (λ), then it perfectly simulates G 3 . Hence, we have

|Pr[out 3 = 1] -Pr[out 2 = 1]| ≤ Adv crs-pre (Setup ,E ,D ),A (λ).
Therefore, we have

Adv a-crs-pre (Setup S ,E S ,D S ),A (λ) = |Pr[out 3 = 1] -Pr[out 0 = 1]| ≤ Adv crs-pre (Setup ,E ,D ),A (λ) + Adv crs-pre (Setup S ,E S ,D S ),A (λ)
for some PPT adversaries A and A .

Pseudorandom encodings and invertible sampling

In this section we explain relation between pseudorandom encodings and invertible sampling, [START_REF] Damgård | Improved Non-committing Encryption Schemes Based on a General Complexity Assumption[END_REF]. In Sections 5.1 and 5.2, we restate the invertible sampling hypothesis of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] and define several variants thereof. In Section 5.3, we prove that a distribution can be pseudorandomly encoded if and only if it is inverse samplable. This extends to all of the introduced variations of the pseudorandom encoding hypothesis and the invertible sampling hypothesis.

The invertible sampling hypothesis

A PPT algorithm S is inverse samplable according to [DN00; IKOS10] if there exists an alternative PPT algorithm S and a corresponding inverse sampler S -1 such that S (on every input) induces a distribution which is computationally indistinguishable from the distribution induced by S (on identical inputs) and S -1 inverses the computation of S. That is, S -1 on input of an output produced by S produces computationally well-distributed random coins for S to produce the given output.

Definition 7 (Invertible sampling hypothesis, ISH rand ≈c , [IKOS10]). For every PPT algorithm S, there exists a PPT algorithm S (the alternate sampler) with randomness space {0, 1} n(λ) and an efficient randomized algorithm S -1 (the inverse sampler), satisfying the following two properties.

Closeness. For all PPT adversaries A and all inputs m ∈ L,

Adv close A,m (λ) := Pr[Exp close A,m,0 (λ) = 1] -Pr[Exp close A,m,1 (λ) = 1] ≤ negl(λ),
where Exp close A,m,0 and Exp close A,m,1 are defined in Figure 10.

Invertibility. For all PPT adversaries A and all inputs m ∈ L,

Adv inv A,m (λ) := Pr[Exp inv A,m,0 (λ) = 1] -Pr[Exp inv A,m,1 (λ) = 1] ≤ negl(λ),
where Exp inv A,m,0 and Exp inv A,m,1 are defined in Figure 10. Definition 8 (ISH det ≈c , ISH rand ≡s , ISH det ≡s ). Definition 7 can be tuned in two dimensions: the inverse sampler can be required to be deterministic or allowed to be randomized, and the closeness and invertibility properties can be required to hold statistically or computationally. We denote these variants as ISH β α , where α ∈ {≈ c , ≡ s } and β ∈ {rand, det}.

Exp close A,m,0 (λ) r ← {0, 1} p(λ) y := S(m; r) return A(m, y) Exp close A,m,1 (λ) r ← {0, 1} n(λ) y := S(m; r) return A(m, y) Exp inv A,m,0 (λ) r ← {0, 1} n(λ) y := S(m; r) return A(m, r, y) Exp inv A,m,1 (λ) r ← {0, 1} n(λ) y := S(m; r) r ← S -1 (m,

The invertible sampling hypothesis with setup

The invertible sampling hypothesis can be naturally relaxed by introducing public parameters (or global CRS), henceforth denoted crs. This allows the alternative sampler and the inverse sampler to use crs. Closeness and invertibility are defined against adversaries knowing the crs but choosing the inputs statically.

Definition 9 (Invertible sampling hypothesis with setup, cISH rand ≈c ). For every PPT algorithm S there exists a PPT algorithm Setup S , a PPT algorithm S (with randomness space {0, 1} n(λ) ) and an efficient randomized S -1 satisfying the following two properties.

Closeness. For all PPT adversaries A,

Adv crs-close A (λ) := Pr[Exp crs-close A,0 (λ) = 1] -Pr[Exp crs-close A,1 (λ) = 1] ≤ negl(λ),
where Exp crs-close A,0

and Exp crs-close

A,1
are defined in Figure 11. Invertibility. For all PPT adversaries A,

Adv crs-inv A (λ) := Pr[Exp crs-inv A,0 (λ) = 1] -Pr[Exp crs-inv A,1 (λ) = 1] ≤ negl(λ),
where Exp crs-inv A,0

and Exp crs-inv

A,1
are defined in Figure 11. Definition 9 is static in the sense that closeness and invertibility adversaries are required to statically choose the challenge input m ∈ L. In the following, we define the corresponding adaptive version, where adversaries are allowed to choose the challenge input m ∈ L depending on crs.

Exp crs-close A,0 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) r ← {0, 1} p(λ) y := S(m; r) return A(crs, y) Exp crs-close A,1 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) r ← {0, 1} n(λ) y := S(crs, m; r) return A(crs, y) Exp crs-inv A,0 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) r ← {0, 1} n(λ) y := S(crs, m; r) return A(crs, r, y) Exp crs-inv A,1 (λ) m ← A(1 λ ) crs ← Setup S (1 λ ) r ← {0, 1} n(λ)
Definition 10 (Adaptive invertible sampling hypothesis with setup, acISH rand ≈c ). For every PPT algorithm S, there exists a PPT algorithm Setup S , a PPT algorithm S (with randomness space {0, 1} n(λ) ) and an efficient randomized S -1 satisfying the following two properties.

(Adaptive) closeness. For all PPT adversaries A,

Adv a-crs-close A (λ) := Pr[Exp a-crs-close A,0 (λ) = 1] -Pr[Exp a-crs-close A,1 (λ) = 1] ≤ negl(λ),
where Exp a-crs-close A,0

and Exp a-crs-close

A,1
are defined in Figure 12. (Adaptive) invertibility. For all PPT adversaries A,

Adv a-crs-inv A (λ) := Pr[Exp a-crs-inv A,0 (λ) = 1] -Pr[Exp a-crs-inv A,1 (λ) = 1] ≤ negl(λ),
where Exp a-crs-inv A,0 and Exp a-crs-inv A,1 are defined in Figure 12. Definition 11 (cISH det ≈c , cISH rand ≡s , cISH det ≡s , acISH det ≈c , acISH rand ≡s , acISH det ≡s ). Definitions 9 and 10 can be tuned in two dimensions: the inverse sampler can be required to be deterministic or allowed to be randomized, and the closeness and invertibility properties can be required to hold statistically or computationally. We denote these variants as cISH β α and acISH β α , respectively, where α ∈ {≈ c , ≡ s } and β ∈ {rand, det}.

Exp a-crs-close A,0 (λ) crs ← Setup S (1 λ ) m ← A(crs) r ← {0, 1} p(λ) y := S(m; r) return A(y) Exp a-crs-close A,1 (λ) crs ← Setup S (1 λ ) m ← A(crs) r ← {0, 1} n(λ) y := S(crs, m; r) return A(y) Exp a-crs-inv A,0 (λ) crs ← Setup S (1 λ ) m ← A(crs) r ← {0, 1} n(λ) y := S(crs, m; r) return A(r, y) Exp a-crs-inv A,1 (λ) crs ← Setup S (1 λ ) m ← A(crs) r ← {0, 1} n(λ) y := S(crs, m; r) r ← S -1 (crs, m, y) return A(r, y)
Remark 6 (Universal setup). In Definitions 9 and 10, we allow the algorithm Setup S to depend on the sampler S. A somewhat incomparable variant of this definition is to require the existence of a universal setup algorithm Setup(1 λ , B) for B ∈ N which provides the above guarantees for all samplers which can be represented with B bits. We refer to this variant as universal cISH β α and universal acISH β α , respectively.

Remark 7 (Common random string). We will denote the strengthening of the invertible sampling hypothesis as in Definitions 9 and 10, where the setup algorithm Setup S is required to sample uniform random strings, as the invertible sampling hypothesis with a common random string.

Again, we note that in Definitions 9 and 10, we implicitly only consider legitimate adversaries which guarantee that m ∈ L.

Equivalence of pseudorandom encodings and invertible sampling

We prove the following theorem.

Theorem 2. Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. PREH β α is true if and only if ISH β α is true.
It is straight forward to extend Theorem 2 to the non-adaptive and adaptive variants with setup. Proof. We prove this for the computational randomized case. The remaining cases are similar. Assume ISH rand ≈c holds. Let S be a PPT algorithm. ISH rand ≈c implies that there exists an alternative sampler S (with randomness space {0, 1} n(λ) ) and a corresponding inverse sampler S -1 satisfying closeness and invertibility.

Every inverse samplable distribution can be pseudorandomly encoded

For m ∈ L, y ∈ {0, 1} * , r ∈ {0, 1} n(λ) , we define the algorithms E S (m, y) := S -1 (m, y) (potentially randomized) and D S (m, r) := S(m; r) (deterministic).

Correctness

We consider a series of hybrids, see Figure 13. Game G 0 is identical to Exp inv A,m,0 and game

G 1 is identical to Exp inv A,m,1 . Hence, |Pr[out 1 = 1] -Pr[out 0 = 1]| ≤ Adv inv A,m (λ).
Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that

|Pr[out 2 = 1] -Pr[out 1 = 1]| ≤ Adv close A,m (λ)
.

Proof. Construct an adversary A on closeness. On input of (m, y), A computes r ← S -1 (m, y), calls A on input of (m, r, y) and outputs the resulting output. If y is sampled using S(m; r) (for r ← {0, 1} n(λ) ), A perfectly simulates game G 1 for A. If y is sampled using S(m; r) (for f ← {0, 1} p(λ) ), A perfectly simulates game G 2 for A. Therefore, Pr[out

1 = 1] = Pr[Exp close A,m,1 (λ) = 1] and Pr[out 2 = 1] = Pr[Exp close A,m,0 (λ) = 1]. Thus, we have that |Pr[out 2 = 1] -Pr[out 0 = 1]| ≤ Adv close A,m (λ) + Adv inv A ,m
(λ) for some PPT adversaries A, A . Consider the adversary A distinguishing between game G 0 and game G 2 that on input of (m, r, y), outputs 0 if S(m; r) = y and outputs 1 otherwise. By definition, A always outputs 0 in

G 0 . Hence, dec-error (λ) = Pr[y ← S(m) : S(m, S -1 (m, y)) = y] = Pr[out 2,A = 1] = |Pr[out 2,A = 1] -Pr[out 0,A = 1]|.

Pseudorandomness

We consider a sequence of hybrids starting from Exp pre A,m,0 and concluding in Exp pre A,m,1 , see Figure 14. Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that

|Pr[out 1 = 1] -Pr[out 0 = 1]| ≤ Adv close A,m (λ).
Proof. Construct a PPT adversary A on the closeness property as follows. On input of (m, y), A calls A on input of (m, S -1 (m, y)) and outputs the resulting output. Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that

|Pr[out 2 = 1] -Pr[out 1 = 1]| ≤ Adv inv A,m (λ).
Proof. We construct a PPT adversary A on the invertibility property. On input of (m, r, y), A calls A on input of (m, r) and outputs its output. If

r ← S -1 (m, y) for y ← S(m), A simulates game G 1 for A. If r ← {0, 1} n(λ) , A simulates game G 2 for A. Therefore, Pr[out 1 = 1] = Pr[Exp inv A,m,0 (λ) = 1] and Pr[out 2 = 1] = Pr[Exp inv A,m,1 (λ) = 1]. Hence, Adv pre A,m (λ) = |Pr[out 2 = 1] -Pr[out 0 = 1]| ≤ Adv close A,m (λ) + Adv inv A ,m
(λ) for some PPT adversaries A and A .

Every pseudorandomly encodable distribution can be inversely sampled

Lemma 5. Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. If PREH β α holds, then ISH β α holds.

Proof. We prove the statement for the computational randomized case. The remaining cases are similar.

Assume PREH rand ≈c holds. Let S be a PPT algorithm. PREH rand ≈c implies that for S there exist efficient algorithms E S (potentially randomized) with output length n(λ) and D S (deterministic) satisfying correctness and pseudorandomness.

For m ∈ L, r ∈ {0, 1} n(λ) , y ∈ {0, 1} * , we define the alternative sampler as S(m; r) := D S (m, r) (randomized) and the corresponding inverse sampler S -1 (m, y) := E S (m, y) (potentially randomized).

Closeness

Let A be an adversary on closeness. We consider a sequence of games starting from Exp close A,m,0 and concluding in Exp close A,m,1 , see Figure 15. Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that

|Pr[out 3 = 1] -Pr[out 2 = 1]| ≤ Adv pre A,m (λ).
Proof. Construct an adversary A on pseudorandomness as follows. On input of (m, u =: r D ), A calls A on input (m, D S (m, r D )) and outputs the resulting output. If u ← E S (m, y) for y ← S(m), A perfectly simulates game G 2 for A. Otherwise, if u is uniformly random over {0, 1} n(λ) , A perfectly simulates game G 3 for A. Hence, Pr[out

3 = 1] = Pr[Exp pre A,m,1 (λ) = 1] and Pr[out 2 = 1] = Pr[Exp pre A,m,0 (λ) = 1].
Finally, the difference between G 3 and G 4 is only conceptional and Pr[out

3 = 1] = Pr[out 4 = 1]. Hence, Adv close A,m (λ) = |Pr[out 4 = 1] -Pr[out 0 = 1]| ≤ Adv pre A,m (
λ) + dec-error (λ) for some PPT adversary A.

Invertibility

We consider a sequence of hybrids, see Figure 16. Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that

|Pr[out 1 = 1] -Pr[out 0 = 1]| ≤ Adv pre A,m (λ) + dec-error (λ).
Proof. Let A be an adversary distinguishing G 0 and G 1 . Construct an adversary A on the closeness property. On input of (m, y), A computes r ← E S (m, y) and calls A on input (m, r, y).

If y ← S(m), A simulates game G 0 for A. Else, if y ← S(m), A simulates game G 1 for A. Hence, |Pr[out 1 = 1] -Pr[out 0 = 1]| = Adv close A,m (λ).
The difference between G 1 and G 2 is purely conceptional. Hence, Pr[out

1 = 1] = Pr[out 2 = 1]. G 2 and G 3 behave identical if y D = y S . Let F denote the failure event y D = y S . We have that out 2 = 1 ∧ ¬ ⇔ out 3 ∧ ¬F . The Difference Lemma (due to Shoup, [Sho04]) bounds |Pr[out 3 = 1] -Pr[out 2 = 1]| ≤ Pr[F ]. Due to correctness, for all m ∈ L, Pr[F ] = Pr[y S ← S(m) : D S (m, E S (m, y S )) = y S ] = dec-error (λ) is negligible.
Claim. For all PPT adversaries A, for all m ∈ L, there exists a PPT adversary A, such that The above proof directly generalizes to the non-adaptive and adaptive variants of pseudorandom encodings and invertible sampling with public parameters. As a demonstration, consider the proof of closeness of Lemma 5. More specifically, consider the game hop from G 1 to G 2 . In these games, the (stateful) adversary A picks m (either statically or adaptively after seeing crs). The error event F occurs if y S = y D , where y S ← S(m) and y D ← D S (crs, m, E S (crs, m, y S )). We can hence construct an adversary A against correctness which chooses m (non-)adaptively like A. Hence, the probability that F occurs can be upper bounded by c-dec-error A (λ) or ac-dec-error A (λ), respectively, which are both negligible by correctness.

|Pr[out 4 = 1] -Pr[out 3 = 1]| ≤ Adv pre A,m (λ)
Theorem 2 together with Theorem 1 yields the following corollaries.

Corollary 1. Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. cPREH β α is true, then acISH β α is true.

Corollary 2. Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. cISH β α is true, then acISH β α is true.
This is an excellent example of the potential pseudorandom encodings offer. Looking through the lens of invertible sampling, it is rather unclear how the static and adaptive notions relate, whereas pseudorandom encodings directly provide a static-to-adaptive transformation.

Particularly, Corollary 2 together with [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] yields the first instantiation of an adaptive explainability compiler without complexity leveraging and, hence, based only on polynomial hardness assumptions. The recent paper [START_REF] Cohen | Adaptively Secure MPC with Sublinear Communication Complexity[END_REF] uses such an adaptive explainability compiler to obtain adaptive MPC with communication complexity which is sub-linear in the circuit size. Their construction relies on complexity leveraging which entails a sub-exponential loss relative to IO and one-way functions. Hence, we obtain the following corollary improving on Theorem 7 in the proceedings version of [START_REF] Cohen | Adaptively Secure MPC with Sublinear Communication Complexity[END_REF] in a black-box way.

Corollary 3. Assuming polynomially secure IO and the adaptive hardness of LWE, then succinct adaptive two-round MPC in the malicious setting is possible (for all deterministic n-party functionalities f : ({0, 1} in ) n → {0, 1} out with circuit depth d) in the (local) CRS model such that the size of the CRS, the communication complexity, and online-computational complexity of the protocol are polynomial in λ, in , out , d and n.

Classification of the different flavors of pseudorandom encodings

In this section we classify the different variants of the pseudorandom encoding hypothesis. In Section 6.1, we study the pseudorandom encoding hypothesis with deterministic encoding algorithm and identify a relation to compression. In Section 6.2, we study the pseudorandom encoding hypothesis with randomized encoding and its conflicts with extractable one-way functions. In Section 6.3, we describe an instantiation of cPREH rand ≈c (with universal setup) based on indistinguishability obfuscation and one-way functions due to [SW14; DKR15]. Finally, in Section 6.4, we bootstrap cPREH rand ≈c with a common random string from the construction in Section 6.3 additionally assuming weak cPREH rand ≈c with a common random string.

Deterministic encoding

For the purpose of classifying pseudorandom encodings with a deterministic encoding algorithm, we first introduce some notions of entropy and computational analogues thereof.

Definition 12 (Min-entropy, [Rey11]

). The min-entropy of a distribution X is defined as

H ∞ (X) = -log max x∈supp(X) Pr[X = x].
(By log we always mean the logarithm to base 2.) Intuitively, this captures the ability to guess the value of a distribution in a single attempt. However, this is a very pessimistic view. For many purposes, it suffices to work with a distribution with is statistically close (i.e. has negligible statistical distance) to a distribution with high min-entropy.10

Definition 13 ( -smooth min-entropy, [Rey11]).

A source X has -smooth min-entropy at least k, denoted as

H ∞ (X) ≥ k, if there exists a distribution Y with ∆(X, Y ) ≤ such that H ∞ (Y ) ≥ k.
In many cases, some information Z that is correlated to the actual source X is known. Since for our purposes, the conditional part Z is not under adversarial control, we use the notion of average conditional min-entropy as used in [HLR07; DORS08].

Definition 14 (Average min-entropy, [HLR07; DORS08; Rey11]

). Let (Y, Z) be a joint distribution. The average min-entropy of X conditioned on Z is

H ∞ (X | Z) := -log( E z←Z [max x Pr[X z = x]]).

Definition 15 (Average -smooth min-entropy, [DORS08; Rey11]). Let (Y, Z) be a joint distribution. The distribution Y has average -smooth min-entropy at least

k conditioned on Z, denoted as H ∞ (Y | Z) ≥ k, if there exists a joint distribution (Y , Z ) with ∆((Y, Z), (Y , Z )) ≤ such that H ∞ (Y | Z ) ≥ k.
Let X be an efficiently samplable distribution. In the literature, there are several computational notions of entropy. HILL entropy [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF] constitutes a natural computational variant of min-entropy. A source has high HILL entropy, if it is computationally indistinguishable from a source that has high min-entropy. Shannon's theorem [START_REF] Elwood | A mathematical theory of communication[END_REF] states that the minimum compression length (over all compression and decompression algorithms) of a distribution equals its average entropy (up to small additive terms). Yao entropy [START_REF] Andrew | Theory and Applications of Trapdoor Functions (Extended Abstract)[END_REF] constitutes the corresponding computational counterpart. Intuitively, a source has high Yao entropy, if it can not be efficiently compressed.

Definition 16 (HILL entropy, [HILL99; BSW03]). A distribution

Definition 17 (Yao entropy, [Yao82; BSW03]). A distribution X has Yao entropy at least k, denoted by H Yao

,s (X) ≥ k, if for every pair of circuits (E, D) of total size s with outputs of E having length ,

Pr x←X [D(E(x)) = x] ≤ 2 -k + .
When we omit the subscripts for H HILL and H Yao , we mean H HILL ,s and H Yao ,s for any negligible and polynomial s, respectively. Since compressibility implies distinguishability, HILL entropy implies Yao entropy. The converse, however, is believed to be false, [Wee04; HLR07].

Definition 18 (Conditional HILL entropy, [HLR07]). For a distribution (X, Z), we say that X has HILL entropy at least k conditioned on Z, denoted by H

HILL ,s (X | Z) ≥ k, if there exists a collection of distributions Y z giving rise to a joint distribution (Y, Z), such that H ∞ (Y | Z) ≥ k and |Pr[(x, z) ← (X, Z) : A(x, z) = 1] -Pr[(y, z) ← (Y, Z) : A(y, z) = 1]| ≤ for all circuits A of size at most s.
Conditional Yao entropy is defined by simply giving the compressor and decompressor algorithm the value z as input.

Definition 19 (Conditional Yao entropy, [HLR07]). For a distribution (X, Z), we say that X has Yao entropy at least k conditioned on Z, denoted by H Yao

,s (X | Z) ≥ k, if for every pair of circuits (E, D) of total size at most s with outputs of E having length , Pr (x,z)←(X,Z) [D(z, E(z, x)) = x] ≤ 2 -k + .

Information theoretic guarantees and compression

Traditionally, the theory of compression mostly considers family of sources that are not indexed by strings. Let Σ be some alphabet. In this work, we always consider Σ := {0, 1}.

Definition 20 ([Wee04; TVZ05]).

For functions E X : Σ * → Σ * and D X : Σ * → Σ * , we say (E X , D X ) compresses source X to length m with decoding error if

1. Pr[x ← X : D X (E X (x)) = x] ≤ , and 2. E[|E X (X)|] ≤ m.

Definition 21 ([Wee04; TVZ05]).

We say source X is compressible to length (exactly) m if there exist functions E X and D X such that (E X , D X ) compresses X to length (exactly) m.

Lemma 6 ([TVZ05]

). Let X λ be a source on {0, 1} λ which is compressible to length m with decoding error by algorithms (E X , D X ). Further, let m 0 ∈ N be a lower bound on the output length of E X , i.e. such that for all x ∈ supp(X λ ), |E X (x)| ≥ m 0 . Then, X λ is compressible to length m + (λ -m 0 ) + 1 with decoding error 0.

Proof (sketch). To show this, [TVZ05] construct an encoding algorithm E

X which on input of x tests if the D X (E X (x)) = x. If this is the case, E X outputs 0 E X (x). Else, E X outputs 1 x.
The statistical deterministic variant of the pseudorandom encoding hypothesis is strongly related to compression.

Theorem 3. If (weak) PREH det

≡s is true for X, i.e. there exist deterministic algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, the -smooth min-entropy H ∞ (X) ≥ n for some negligible function .

Proof. Consider the distribution Y := D X (U n ). As already seen in the proof of Theorem 2, Y and X are statistically indistinguishable due to correctness and pseudorandomness. Hence, the statistical distance ∆(X, Y ) ≤ δ(λ) for some negligible δ.

Due to correctness and since

E X is deterministic, Pr[x ← X : D X (E X (x)) = x] = Pr[x ← X : E X (D X (E X (x))) = E X (x)] ≥ 1 -ν(λ)
for some negligible function ν. Applying pseudorandomness, we get that the probability

Pr u ← U n : E X (D X (u)) = u ≥ 1 -ν (λ)
for some negligible function ν , where the probability is only over the choice of u. Therefore, D X operates almost injectively on the set {0, 1} n . More formally, let

V 0 ⊂ {0, 1} n denote the set of all u such that E X (D X (u)) = u and let V 1 := {0, 1} n \ V 0 . We have that, |V 1 | /|{0,1} n | ≤ ν (λ). Let V 1 be some arbitrary subset of {0, 1} p(λ) \ D X (V 0 ) such that |V 1 | = |V 1 | (for some polynomial p). Let Y be the uniform distribution over D X (V 0 ) ∪ V 1 . Note that |D X (V 0 ) ∪ V 1 | = 2 n and Pr[Y ∈ V 1 ] ≤ Pr[Y ∈ D X (V 0 )] ≤ ν (λ). The statistical distance between Y and Y is negligible. ∆(Y , Y ) = a∈D X (V 0 )∪V 1 Pr[Y = a] -Pr[Y = a] = a∈D X (V 0 ) Pr[Y = a] -Pr[Y = a] ≤1-|V 0 |•2 -n ≤1-(1-ν (λ)) + a∈V 1 Pr[Y = a] -Pr[Y = a] ≤ a∈V 1 (Pr[Y =a]+Pr[Y =a])≤2•ν (λ) ≤ 3 • ν (λ)
Furthermore, since Y is the uniform distribution over a set of size 2 n , its min-entropy equals n. Since ∆(X, Y ) ≤ δ(λ) and ∆(Y , Y ) ≤ 3ν (λ) for negligible functions δ and ν , we have

H δ+3ν ∞ (X) ≥ H ∞ (Y ) = n.
Corollary 4. If PREH det ≡s is true for some source X, there exists an n ≤ H ∞ (X) (for some negligible function ), such that X is compressible to length exactly n. The decoding error can then be eliminated applying Lemma 6.

Hence, for PREH det ≡s to be true for a source X, it is necessary that X is efficiently compressible. However, this is not a sufficient criterion since a compression algorithm can have some structure which makes it easily distinguishable from uniform randomness (e.g. the compression algorithm used in the proof of Lemma 6).

The distribution induced by pseudorandom generators can provably not be compressed. However, those distributions have low -smooth min-entropy.

Lemma 7. Let iPRG be an injective pseudorandom generator with polynomial stretch poly(•) and let be a negligible function. Then, H ∞ (iPRG(U λ )) ≤ λ + δ(λ) for some negligible function δ.

Proof. Since iPRG(U λ ) is a uniform distribution over iPRG({0, 1} λ ), it suffices to consider all -close flat distributions over {0, 1} poly(λ) to obtain an upper bound on H ∞ (iPRG(U λ )). Let D the uniform distribution on supp(iPRG(U λ )) ∪ A, where supp(iPRG

(U λ )) ∩ A = ∅. Let |A| := k. Then, ∆(iPRG(U λ ), D) = a∈supp(iPRG(U λ )) 1 2 λ - 1 2 λ + k + a∈A 1 2 λ + k = 1 - 2 λ 2 λ + k + k 2 λ + k = 2k 2 λ + k .
Hence, for ∆(iPRG(U λ ), D) ≤ (λ), k is upper bounded by

k ≤ k(2 -(λ) ≥1 ) ≤ 2 λ • (λ).
Therefore, the min-entropy of

D is at most H ∞ (D) = log(2 λ + k) ≤ log(2 λ + 2 λ ) = λ + log(1 + ),
which is negligibly close to λ. Hence, H ∞ (iPRG(U λ )) ≤ λ + δ(λ) for some negligible function δ.

Lemma 8. Let PRG be a pseudorandom generator with polynomial stretch poly(•) and let be a negligible function. Then, H ∞ (PRG(U λ )) ≤ λ + δ(λ) for some negligible function δ.

Proof. Due to Lemma 1, there exists a uniform distribution D over a set of size 2 λ such that PRG(U λ ) and D are statistically close. By a similar argument as in Lemma 7, in order to upper bound the -smooth min-entropy of PRG(U λ ), it suffices to consider all -close flat distributions. Then, due to the computations already made in the proof of Lemma 7, Lemma 8 follows.

Therefore, we obtain the following corollary.

Corollary 5. If one-way functions exist, PREH det ≡s is false.

Intuitively, a common reference string can not add additional entropy to E X (crs, X). I.e. if cPREH det ≡s is true for some source X, the algorithms (E X , D X ) implied by cPREH det ≡s compress that source to its -smooth min-entropy. To prove this, we introduce the following technical lemma.

Lemma 9 (Splitting lemma). Let X and Y x be distributions giving rise to a joint distribution (Y, X).

Let A ⊂ supp(Y, X) such that Pr (y,x)←(Y,X) [(y, x) ∈ A] ≥ 1 -µ(λ) for some negligible function µ. Further, for all x, let p x := Pr y←Yx [(y, x) ∈ A]. Then, there exists negligible functions ν, ν and a set G ⊆ supp(X), such that for all x ∈ G, p x ≥ 1-ν(λ) and Pr

x←X [x ∈ G] ≥ 1-ν (λ). Proof. Define G n := {x ∈ supp(X) : p x ≥ 1 -n • µ(λ)}. 1 -µ(λ) ≤ Pr (y,x)←(Y,X) [(y, x) ∈ A] = x∈Gn Pr[X = x] • p x ≤1 + x ∈Gn Pr[X = x] • p x <1-n•µ(λ) < Pr x←X [x ∈ G n ] + (1 -n • µ(λ)) • x ∈Gn Pr[X = x] =1-Pr x←X [x∈Gn] = Pr x←X [x ∈ G n ] + 1 -n • µ(λ) -Pr x←X [x ∈ G n ] + n • µ(λ) • Pr x←X [x ∈ G n ] Hence, Pr x←X [x ∈ G n ] ≥ 1 - 1 n .
Without loss of generality, we assume µ(λ) > 0 for all λ ∈ N. (If µ(λ) = 0 for some λ, then for G := supp(X), p x = 1 for all x ∈ G, and Pr x←X [x ∈ G] = 1.) Then, µ(λ) is well defined and negligible. Let n := µ(λ) -1 . Then, by definition of G n , for all x ∈ G n ,

p x ≥ 1 -n • µ(λ) = 1 -µ(λ). Furthermore, Pr x←X [x ∈ G n ] ≥ 1 -1 n = 1 -µ(λ).
Theorem 4. If (weak) cPREH det ≡s is true for X, i.e. there exist a setup algorithm Setup X and deterministic algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, the -smooth min-entropy H ∞ (X) ≥ n for some negligible function .

Proof. Note that H ∞ (X) = H ∞ (X | Setup X (1 λ )) as the distribution X is independent of the CRS. Hence, it suffices to upper bound the average -smooth min-entropy H ∞ (X | Setup X (1 λ )).

The proof is similar to the proof of Theorem 3. We consider the distribution Y crs := D X (crs, U n ). Due to Theorem 2, the distributions {crs ← Setup X (1 λ ), u ← U n : (crs, D X (crs, u))} and {crs ← Setup X (1 λ ), y ← X : (crs, y)} are statistically indistinguishable. Hence,

∆ (X | Setup X (1 λ ), (Y | Setup X (1 λ ) ≤ δ(λ)
for some negligible function δ.

By a similar argument as in Theorem 3, due to correctness and pseudorandomness we have

Pr crs ← Setup X (1 λ ), u ← U n : E X (crs, D X (crs, u)) = u ≥ 1 -ν (λ)
for some negligible function ν , where the probability is over the choice of crs and u.

The Splitting lemma (Lemma 9) implies that there is exists G

⊆ supp(Setup X (1 λ )) such that Pr[crs ← Setup X (1 λ ) : crs ∈ G] ≥ 1-ν (λ) and for all crs ∈ G, Pr[u ← U n : E X (crs, D X (crs, u)) = u] ≥ 1 -ν (λ)
for some negligible functions ν , ν . Hence, conditioned on crs ∈ G, D X (crs, •) operates almost injectively on the set {0, 1} n . More formally, let V crs 0 ⊂ {0, 1} n denote the set of all u such that E X (crs, D X (crs, u)) = u and let V crs

1 := {0, 1} n \ V crs 0 .
For crs ∈ G, we have

|V crs 1 | /|{0,1} n | ≤ ν (λ). Let V crs 1 be some arbitrary subset of {0, 1} p(λ) \ D X (crs, V crs 0 ) such that |V crs 1 | = |V crs 1 | (for some polynomial p). Let Y be the uniform distribution over D X (V crs 0 ) ∪ V crs 1 . Note that |D X (crs, V crs 0 ) ∪ V crs 1 | = 2 n and for crs ∈ G, we have Pr[Y crs ∈ V crs 1 ] ≤ Pr[Y crs ∈ D X (crs, V crs 0 )] ≤ ν (λ). Hence, crs∈G Pr[Setup X = crs] •      a∈D X (crs,V crs 0 ) Pr[Y crs = a] -Pr[Y crs = a] + a∈V crs 1 Pr[Y crs = a] -Pr[Y crs = a]      ≤ crs∈G Pr[Setup X = crs] • 1 - |V crs 0 | 2 n + Pr[Y crs ∈ V crs 1 ] + Pr[Y crs ∈ V crs 1 ] ≤ crs∈G Pr[Setup X = crs] • |V crs 1 | 2 n + Pr[Y crs ∈ D X (crs, V crs 0 )] + |V crs 1 | 2 n ≤ 3 • ν (λ) (6) crs ∈G Pr[Setup X = crs] • a∈supp(Y crs ) Pr[Y crs = a] -Pr[Y crs = a] ≤ crs ∈G Pr[Setup X = crs] • 2 ≤ 2 • ν (λ) (7)
Due to Equations ( 6) and ( 7) we have that

∆((Y , Setup X ), (Y , Setup X )) ≤ 2 • ν (λ) + 3 • ν (λ). Furthermore, since for all crs ∈ supp(Setup X (1 λ )), Y crs is the uniform distribution over a set of 2 n elements, H ∞ Y | Setup X (1 λ ) = -log E crs←Setup X (1 λ ) max a Pr[Y crs = a] = n. Therefore, we have H δ+2ν +3ν ∞ (X) = H δ+2ν +3ν ∞ (X | Setup X (1 λ ))
≥ n, where δ, ν , ν are negligible functions.

Corollary 6. If one-way functions exist, cPREH det

≡s is false.

Computational guarantees and pseudoentropy

We study the relation of the pseudorandom encoding hypothesis with deterministic encoding algorithm to HILL and Yao entropy. Interestingly, PREH det ≈c poses a lower bound on the HILL entropy of a source and an upper bound on its Yao entropy. HILL entropy. Intuitively, the algorithms (E X , D X ) implied by PREH det ≈c compress a source X to its HILL entropy.

Theorem 5. If (weak) PREH det

≈c is true for X, i.e. there exist deterministic algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, H HILL (X) ≥ n.

Proof. We employ a similar strategy as in the proof of Theorem 3. Let Y := D X (U n ). As already seen in the proof of Theorem 2, Y and X are computationally indistinguishable due to correctness and pseudorandomness.

Due to correctness, Pr[x ← X :

D X (E X (x)) = x] ≥ 1 -ν(λ) for some negligible function ν. Since E X is required to be deterministic, we get Pr[x ← X : E X (D X (E X (x))) = E X (x)] ≥ 1-ν(λ).
Applying pseudorandomness, we get that the probability

Pr u ← U n : E X (D X (u)) = u ≥ 1 -ν (λ)
for some negligible function ν , where the probability is only over the choice of u. Let V 0 ⊂ {0, 1} n denote the set of all u such that E X (D X (u)) = u and let V 1 := {0, 1} n \ V 0 . We have that,

|V 1 | /|{0,1} n | ≤ ν (λ). Let V 1 be some arbitrary subset of {0, 1} p(λ) \ D X (V 0 ) such that |V 1 | = |V 1 | (for some polynomial p). Let Y be the uniform distribution over D X (V 0 ) ∪ V 1 .
The min-entropy of Y equals n. By an argument already made in Theorem 3, the statistical distance between Y and Y is negligible.

Therefore, the distributions X and Y are computationally indistinguishable and, hence, H HILL (X) ≥ n.

This result can be generalized to conditional HILL entropy using strong PREH det ≈c . Theorem 6. Let (X, Z) be a joint distribution. More precisely, let Z be a distribution over words of length λ. For z ∈ supp(Z), let X z denote the conditional distribution when Z = z. If (strong) PREH det ≈c is true for X, i.e. there exist two deterministic polynomial time algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then,

H HILL (X | Z) ≥ n.
Proof. For each z ∈ supp(Z), consider the distribution Y z := D X (z, U n ). Due to Theorem 2, for all adversarially chosen z, the distributions {(Y z , z)} and {(X z , z)} are computationally indistinguishable due to correctness and pseudorandomness.

Due to correctness, for all adversarially chosen z, Pr[x ← X z : D X (z, E X (z, x)) = x] ≥ 1-ν(λ) for some negligible function ν. Since E X is required to be deterministic, we have that for all adversarially chosen z,

Pr[x ← X z : E X (z, D X (z, E X (z, x))) = E X (z, x)] ≥ 1 -ν(λ).
Applying pseudorandomness, we get that there exists a negligible function ν such that for all adversarially chosen z,

Pr u ← U n : E X (z, D X (z, u)) = u ≥ 1 -ν (λ),
where the probability is only over the choice of u.

Let V 0,z ⊆ {0, 1} n denote the set of all u ∈ {0, 1} n such that E X (z, D X (z, u)) = u holds and let V 1,z := {0, 1} n \ V 0,z . We have that, |V 1,z | /|{0,1} n | ≤ ν (λ). Let V 1,z be some arbitrary subset of {0, 1} p(λ) \ D X (z, V 0,z ) such that |V 1,z | = |V 1,z | (for some polynomial p). Let Y z be the uniform distribution over D X (z, V 0,z ) ∪ V 1,z . H ∞ (Y | Z) = -log E z←Z max y∈supp(Y z ) Pr[Y z = y] = n.
By a similar argument as in Theorem 3, for all adversarially chosen z, the statistical distance between Y z and Y z is negligible.

∆(Y z , Y z ) = a∈D X (z,V z,0 ) Pr[Y z = a] -Pr[Y z = a] ≤1-|V 0,z |•2 -n ≤1-(1-ν (λ)) + a∈V 1,z Pr[Y = a] -Pr[Y = a] ≤ a∈V 1,z (Pr[Y =a]+Pr[Y =a])≤2•ν (λ) ≤ 3 • ν (λ)
Hence, the (joint) distributions (X, Z) and (Y , Z) are computationally indistinguishable. Therefore, H HILL (X | Z) ≥ n.

We recall that in the proof of Theorem 4, we used the observation that independent random variables A and B satisfy H ∞ (A) = H ∞ (A | B). However, this does not necessarily extend to the computational case, meaning that in our case H HILL (X | Setup X (1 λ ), Z) and H HILL (X | Z) are not equal even though the random variables X and Setup X are independent. Hence, in order to extend Theorem 6 to cPREH det ≈c , we need that there exists a "good" CRS crs such that Y crs,z is almost injective on {0, 1} n and such that {(crs, y)} and {(crs, D X (crs, z, u))} are computationally indistinguishable for this fixed crs. However, since the adversary is quantified after the crs, a non-uniform adversary could know the randomness which was used to generate crs compromising all security guarantees. Therefore, we can only hope to obtain an upper bound on n depending on the conditional HILL entropy H HILL (X | Setup X (1 λ ), Z). Theorem 7. Let (X, Z) be a joint distribution. More precisely, let Z be a distribution over words of length λ. For z ∈ supp(Z), let X z denote the conditional distribution when Z = z. If (strong) cPREH det ≈c is true for X, i.e. there exists a PPT algorithm Setup X and two deterministic polynomial time algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then,

H HILL (X | Setup X (1 λ ), Z) ≥ n.
Proof. The proof is similar to the proof of Theorem 6. We consider the distribution Y crs,z := D X (crs, z, U n ).

Due to Theorem 2, we have that for all adversarially chosen z, the distributions {crs ← Setup X (1 λ ), y ← X z : (crs, z, y)} and {crs ← Setup X (1 λ ), u ← U n : (crs, z, D X (crs, z, u))} are computationally indistinguishable.

Due to correctness and pseudorandomness we have that there exists a negligible function ν , such that for all adversarially chosen z,

Pr crs ← Setup X (1 λ ), u ← U n : E X (crs, z, D X (crs, z, u)) = u ≥ 1 -ν (λ),
where the probability is over the choice of crs and u. The Splitting lemma (Lemma 9) implies that for all z11 , there is exists

G z ⊆ supp(Setup X (1 λ )) such that Pr[crs ← Setup X (1 λ ) : crs ∈ G z ] ≥ 1 -ν z (λ) and for all crs ∈ G z , Pr[u ← U n : E X (crs, z, D X (crs, z, u)) = u] ≥ 1 -ν z (λ) for some negligible functions ν z , ν z . Hence, conditioned on crs ∈ G z , D X (crs, z, •) operates almost injectively on the set {0, 1} n . Let V crs 0,z ⊆ {0, 1} n denote the set of all u ∈ {0, 1} n such that E X (crs, z, D X (crs, z, u)) = u holds and let V crs 1,z := {0, 1} n \ V crs 0,z . For crs ∈ G z , we have |V crs 1,z | /|{0,1} n | ≤ ν z (λ). Let V crs 1,z be some arbitrary subset of {0, 1} p(λ) \ D X (crs, z, V crs 0,z ) such that |V crs 1,z | = |V crs 1,z | (for some polynomial p). Let Y crs,z be the uniform distribution over D X (crs, z, V crs 0,z ) ∪ V crs 1,z . H ∞ (Y | Setup X (1 λ ), Z) = -log E crs←Setup X (1 λ ),z←Z max y∈supp(Y crs,z ) Pr[Y crs,z = y] = n.
Furthermore, a similar computation as in Theorem 4, for all adversarially chosen z, the statistical distance between (Y z , Setup X (1 λ )) and (Y z , Setup X (1 λ )) is negligible. Hence, the (joint) distributions (X, Setup X (1 λ ), Z) and (Y , Setup X (1 λ ), Z) are computationally indistinguishable. Therefore, H HILL (X | Setup X (1 λ ), Z) ≥ n.

Yao entropy. Furthermore, the existence of algorithms (E X , D X ) as implied by PREH det ≈c give an upper bound for the Yao entropy of a source.

Lemma 10. If (weak) PREH det

≈c is true for X, i.e. there exist deterministic algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, H Yao (X) < n + δ(λ) for some negligible δ.

Proof. Due to correctness, there exists a pair of efficient algorithms (E X , D X ) (with

E X having output length n) such that Pr x←X [D X (E X (x)) = x] ≥ 1 -ν(λ) for some negligible function ν. Hence, by Definition 17, H Yao (X) < k, for all k satisfying 1 -ν(λ) ≥ 2 n-k + (λ) ⇐⇒ 2 k • (1 -ν(λ) -(λ)) ≥ 2 n ⇐⇒ k ≥ n -log(1 -ν(λ) -(λ)).
This result can be generalized to conditional Yao entropy as follows.

Lemma 11. Let (X, Z) be a joint distribution. More precisely, let Z be a distribution over words of length λ. For z ∈ supp(Z), let X z denote the conditional distribution when Z = z. If (strong) PREH det ≈c is true for X, i.e. there exist two deterministic polynomial time algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, H Yao (X | Z) < n + δ(λ) for some negligible δ.

Proof. Due to correctness, for all adversarially chosen z,

Pr x←Xz [D X (z, E X (z, x)) = x] ≥ 1 -ν(λ) for some negligible function ν. Hence, by Definition 19, H Yao (X | Z) < k, for all k satisfying k ≥ n -log(1 -ν(λ) -(λ)).
Lemma 12. Let (X, Z) be a joint distribution. More precisely, let Z be a distribution over words of length λ. For z ∈ supp(Z), let X z denote the conditional distribution when Z = z. If (strong) cPREH det ≈c is true for X, i.e. there exists a setup algorithm Setup and two deterministic polynomial time algorithms (E X , D X ) with E X having output length n satisfying correctness and pseudorandomness. Then, H Yao (X | Z) < n + δ(λ) for some negligible δ.

Proof. The Splitting lemma (Lemma 9) implies that for all z,12 there is exists

G z ⊆ supp(Setup X (1 λ )) such that Pr[crs ← Setup X (1 λ ) : crs ∈ G z ] ≥ 1 -ν z (λ) and for all crs ∈ G z , Pr[u ← U n : E X (crs, z, D X (crs, z, u)) = u] ≥ 1 -ν z (λ) for some negligible functions ν z , ν z .
We exploit the non-uniformity of the definition. In particular, we define the compression and decompression algorithms E X (y, z; aux λ ) := E X (aux λ , z, y) and D X (u, z; aux λ ) := D X (aux λ , z, u), where aux λ denotes the non-uniform auxiliary input.

Due to [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF], assuming suitable non-interactive zero-knowledge proof systems and pseudorandom generators, there exists a joint distribution (X, Z) with high conditional Yao entropy but low conditional HILL entropy. The sampler S from [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF] takes as input a NIZK common random string σ, samples a seed from U λ and outputs y 1 := PRG(s) together with a proof y 2 that y 1 is in the image of PRG. Due to Lemma 2, S ∈ S comp . This yields the following corollary.

Corollary 7. If there exist a pseudorandom generator and a (single-theorem) NIZK proof system such that (i) for an overwhelming fraction of common random strings, the number of accepting proofs for each statement are limited, and (ii) the simulated random string is independent of the statement as in [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF]. Then PREH det ≈c is false.

Together with the results of [HLR07; LMs05], we obtain the following corollary.

Corollary 8. A Blum integer is a natural number N = p • q such that p, q are primes with p ≡ q ≡ 3 mod 4. Assume that for a randomly chosen Blum integer N = p • q, the distributions {y ← Z × N s.t. y p = y q = 1 : (N, y)} and {y ← Z × N s.t. y N = 1 : (N, y)} are computationally indistinguishable. Then, PREH det ≈c is false.

On refuting cPREH det ≈c . Theorem 7 only yields an upper bound on the encoding length n depending on H HILL (X | Setup X (1 λ ), Z). Since the Yao entropy of any source H Yao (X | Setup X (1 λ ), Z) is upper bounded by n + negl(λ), we can not apply the result from [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF] to refute cPREH det ≈c .

On refuting weak PREH det ≈c . It is currently not known if plain HILL and plain Yao entropy can be separated as in [START_REF] Hsiao | Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility[END_REF]. Such a separation would refute weak PREH det ≈c .

Randomized encoding

In the following we prove positive and negative results on the validity of the pseudorandom encoding hypothesis with a randomized encoding algorithm. In particular, in Section 6.2.2 we refute PREH rand ≡s based on sub-exponential LWE, in Section 6.2.3 we refute cPREH rand ≈c based on extractable one-way functions with unbounded auxiliary input. On the positive side, in Section 6.3, give a construction of perfectly correct cPREH rand ≈c with universal setup based on indistinguishability obfuscation and one-way functions following [SW14; DKR15] together with Theorem 2. In Section 6.4, we bootstrap cPREH rand ≈c with a common random string from the construction in Section 6.3 additionally assuming weak cPREH rand ≈c with a common random string. Since cPREH rand ≈c with a common random string in conjunction with NIZK proof systems contradicts EOWFs with common but benign auxiliary information, this refutes even weak cPREH rand ≈c with common random string.

(Generalized) extractable one-way functions

In this section, we define (generalized) extractable one-way functions (with respect to common auxiliary input) as in [START_REF] Bitansky | On the existence of extractable one-way functions[END_REF].

Definition 22 (Function family ensemble).

A function family, indexed by a key space K λ , is a set of functions f λ = {f k } k∈K λ where each function has the same domain and range. A function family ensemble F = {f λ } λ∈N is an ensemble of function families with key spaces {K λ } λ∈N .

Definition 23 (Extractable one-way function family ensembles (EOWFs) without auxiliary information, [BCPR14]).

A function family ensemble is called a extractable oneway function family ensemble without auxiliary information if the following two properties are satisfied.

One-wayness. For every PPT adversary A, Pr[Exp ow

A (λ) = 1] is negligible, where Exp ow A is defined in Figure 17. Extractability. For every PPT adversary X (using a random tape of length m(λ)), there exists a PPT algorithm K X such that Pr[Exp ext X,K X (λ) = 1] is overwhelming, where Exp ext X,K X is defined in Figure 17.

Exp ow A (λ) k ← K λ x ← domain(f k ) y := f k (x) x ← A(k, y) return f k (x ) = y Exp ext X,K X (λ) k ← K λ rX ← {0, 1} m(λ) y = X(k; rX ) x ← KX (k, rX ) return f k (x) = y ∨ ∀x : f k (x ) = y

Definition 24 (Extractable one-way function family ensembles (EOWFs) with common auxiliary information, [BCPR14]). A function family ensemble is called a one-way extractable function family ensemble with common auxiliary information if the following properties are satisfied.

One-wayness. As in Definition 23.

One-wayness (stronger). For every PPT adversary A, for every polynomial b and for every

z ∈ {0, 1} b(λ) , Pr[Exp ow-aux A,z (λ) = 1] is negligible, where Exp ow-aux A,z
is defined in Figure 18. Extractability. For every PPT adversary X, there exists a PPT algorithm K X such that for every polynomial b and every z ∈ {0, 1} b(λ) , Pr[Exp ext-aux X,K X ,z (λ) = 1] is overwhelming, where Exp ext-aux X,K X ,z is defined in Figure 18.

Exp ow-aux A,z (λ) k ← K λ x ← domain(f k ) y := f k (x)
x ← A(k, y, z) We note that the weaker notion of one-wayness without auxiliary input is sufficient for us. Assuming non-uniform adversaries, one-wayness without auxiliary input and one-wayness with auxiliary input are equivalent. λ) , if the following properties are satisfied. R F -Hardness. For every PPT adversary A, for every polynomial b and every

return f k (x ) = y Exp ext-aux X,K X ,z (λ) k ← K λ rX ← {0, 1} m(λ) y = X(k, z; rX ) x ← KX (k, z, rX ) return f k (x) = y ∨ ∀x : f k (x ) = y

Definition 25 (Extractable one-way function family ensembles (EOWFs) with bbounded common auxiliary information, [BCPR14]). Like Definition 24 but with a fixed polynomial b determining the length of the common auxiliary information.

Definition 26 (Generalized extractable one-way function family ensembles (GE-OWFs) with common auxiliary information, [BCPR14]). A function family ensemble F is called a generalized one-way extractable function family ensemble with common auxiliary information, with respect to a relation

R F k over triplets (k, y, x) ∈ K λ × {0, 1} n(λ) × {0, 1} m(
z ∈ {0, 1} b(λ) , Pr[Exp g-hard-aux A,z (λ) = 1] is negligible, where Exp g-hard-aux A,z
is defined in Figure 19. R F -Extractability. For every PPT adversary X, there exists a PPT algorithm K X such that for every polynomial b and every z ∈ {0, 1} b(λ) , Pr[Exp g-ext-aux X,K X ,z (λ) = 1] is overwhelming, where Exp g-ext-aux X,K X ,z is defined in Figure 19.

We call F publicly verifiable if there exists a PPT algorithm T such that

T (k, f k (x), x ) = 1 ⇔ R F k (f k (x), x ) = 1. -privately verifiable if there exists a PPT algorithm T such that T (k, x, x ) = 1 ⇔ R F k (f k (x), x ) = 1. Exp g-hard-aux A,z (λ) k ← K λ x ← domain(f k ) y := f k (x) x ← A(k, y, z) return R F k (y, x ) Exp g-ext-aux X,K X ,z (λ) k ← K λ rX ← {0, 1} m(λ) y = X(k, z; rX ) x ← KX (k, z, rX ) return R F k (y, x) ∨ ∀x : f k (x ) = y

Definition 27 (Generalized extractable one-way function family ensembles (GE-OWFs) with b-bounded common auxiliary information, [BCPR14]). Like Definition 26 but with a fixed polynomial b determining the length of the common auxiliary information.

Privately verifiable generalized extractable one-way functions with bounded auxiliary input can be instantiated based on falsifiable assumptions due to [START_REF] Bitansky | On the existence of extractable one-way functions[END_REF].

Theorem 8 ([BCPR14]

). Assuming the learning with errors problem is sub-exponentially hard, there exists a (b(λ) -ω(1))-bounded privately verifiable GEOWF family ensemble.

Information theoretic guarantees and privately verifiable GEOWFs

Assuming information theoretic indistinguishability, adversaries are unbounded and, hence, private verifiability is not a restriction.

Theorem 9. If privately verifiable generalized extractable one-way function family ensembles without auxiliary information exist, then PREH rand

≡s is false. Proof. The proof strategy follows the ideas of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. Let F be a privately verifiable GEOWF family ensemble (without auxiliary input) with respect to relation R F .

PREH rand ≡s implies that for the algorithm S (given in Figure 20) there exists an alternative sampler S and a corresponding inverse sampler S -1 satisfying closeness and invertibility of Definition 7 against unbounded adversaries. Since F is a GEOWF family ensemble, for the algorithm S, there exists an extractor K S satisfying extractability from Definition 26 (without auxiliary information).

S(k)

x ← domain(f k ) We prove that for A given in Figure 20, Pr[Exp g-hard A (λ) = 1] is overwhelming. Let T be an unbounded algorithm that given (k, y, x), computes the relation R F k (y, x). 13 We proceed over a series of hybrids, see Figure 21. The individual game hops are justified as follows. The difference between games G 0 and G 1 , and games G 1 and G 2 are both only conceptual, hence, Pr[out

y := f k (x) return y A(1 λ , k, y) r S ← S -1 (k, y) x ← K S (k, r X ) return x
G0 k ← K λ x ← domain(f k ) y := f k (x) x ← A(k, y) return T (k, y, x ) G1 k ← K λ x ← domain(f k ) y := f k (x) r S ← S -1 (k, y) x ← K S (k, r S ) return T (k, y, x ) G2 k ← K λ y ← S(k) r S ← S -1 (k, y) x ← K S (k, r S ) return T (k, y, x ) G3 k ← K λ y ← S(k) r S ← S -1 (k, y) x ← K S (k, r S ) return T (k, y, x ) G4 k ← K λ r S ← {0, 1} * y ← S(k; r S ) r S ← S -1 (k, y) x ← K S (k, r S ) return T (k, y, x ) G5 k ← K λ r S ← {0, 1} * y ← S(k; r S ) x ← K S (k, r S ) return T (k, y, x )
0 = 1] = Pr[out 1 = 1] = Pr[out 2 = 1].

Claim. There exists an unbounded adversary

A such that |Pr[out 3 = 1] -Pr[out 2 = 1]| ≤ Adv close A,k (λ) (for some k ∈ K λ ).
Proof. Construct an adversary A on statistical closeness. A receives as input a key k and some y that has either been sampled via S(k) or via S(k). A computes r S and x as in game G 2 , calls the (inefficient) testing algorithm T on input of (k, y, x ) and outputs the resulting output. Hence,

Pr[Exp close A,k,0 (λ) = 1] = Pr[out 2 = 1 | k = k] and Pr[Exp close A,k,1 (λ) = 1] = Pr[out 3 = 1 | k = k]. Since |Pr[out 3 = 1] -Pr[out 2 = 1]| = | k∈K λ Pr k←K λ [k = k] • (Pr[out 3 = 1 | k = k] -Pr[out 2 = 1 | k = k])| = | k∈K λ Pr k←K λ [k = k] • Adv close A,k (λ)|, |Pr[out 3 = 1] -Pr[out 2 = 1]| is negligible.
The difference between the games G 3 and G 4 is again only conceptual and Pr[out

3 = 1] = Pr[out 4 = 1].
Claim. There exists an unbounded adversary A such that |Pr[out

5 = 1] -Pr[out 4 = 1]| ≤ Adv inv A,k (
λ) (for some k ∈ K λ ). Proof. Construct an unbounded adversary A on statistical invertibility. On input of (k, r, y), A calls K S on input of (k, r) and obtains x . Finally, A calls the inefficient testing algorithm T on input of (k, y, x ) and outputs the resulting output. If A plays the experiment Exp inv A,k,0 , r is the randomness used to produce y as S(k; r). Hence, in this case, A perfectly simulates game G 5 and Pr

[Exp inv A,k,0 (λ) = 1] = Pr[out 5 = 1 | k = k].
If, on the other hand, A plays the experiment Exp inv A,k,1 , r is some inverse sampled randomness (i.e. the output of S -1 (k, y)). Hence, in this case, A perfectly simulates game G 4 and Pr

[Exp inv A,k,1 (λ) = 1] = Pr[out 4 = 1 | k = k].
Thus, by the same computations made in the reduction to closeness, the claim follows.

Summing up, we have that |Pr[out

5 = 1] -Pr[out 0 = 1]| is negligible. Lemma 13. Pr[out 5 = 1] is overwhelming. Proof (of Lemma 13). Since F is a GEOWF family ensemble, we have that Pr G 5 [R F k (y, x ) = 1 ∨ y ∈ image(f k )] is overwhelming. Using a union bound, we get Pr G 5 [R F k (y, x ) = 1 ∨ y ∈ image(f k )] ≤ Pr G 5 [R F k (y, x ) = 1] + Pr G 5 [y ∈ image(f k )]. In the following, we prove that Pr G 5 [y ∈ image(f k )] is negligible. By construction, S on input k always produces values y ∈ image(f k ). Intuitively, if Pr G 5 [y ∈ image(f k )] = Pr[k ← K λ , y ← S(k) : y ∈ image(f k )
] is non-negligible, an unbounded adversary can distinguish between outputs of S(k) and outputs of S(k) simply by testing all possible preimages. Let A be the adversary on closeness which outputs 1 if and only if y ∈ image(f k ). Hence,

Pr G 5 [y ∈ image(f k )] = k∈K λ Pr[k = k] • Adv close A,k (λ). Since for all k ∈ K λ , Adv close A,k (λ) is negligible, Pr G 5 [y ∈ image(f k )] is negligible.
From Theorem 9 together with Theorem 8, we obtain the following corollary.

Corollary 9. Assuming the learning with errors problem is sub-exponentially hard, PREH rand

≡s is false.

Theorem 10. If privately verifiable generalized extractable one-way function family ensembles with unbounded auxiliary information exist, then cPREH rand

≡s is false. The proof is an easy modification of the proof of Theorem 9.

Computational guarantees and EOWFs with common auxiliary information

Assuming computational indistinguishability, the above proof strategy must be adapted since the adversary actually uses the alternative sampler of a sampler which outputs an image in the range of the EOWF. Computational indistinguishability does not suffice to force the alternative sampler to output an image in the range of the EOWF. Hence, for the purpose to force the alternative sampler to output an image of a given extractable one-way function, we follow the lines of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] and require the original sampler to additionally provide a non-interactive zeroknowledge proof certifying that the provided image is in the range of the given EOWF.

Definition 28 (Non-interactive zero-knowledge proof system).

A non-interactive zeroknowledge (NIZK) proof system for the N P-language L with witness relation R L is a tuple of PPT algorithms (P, V ) satisfying the following conditions for all sufficiently large λ (for some polynomial ).

Correctness. For all (x, w) ∈ R L , for all σ ∈ {0, 1} (λ) , Pr[V (σ, x, P (σ, x, w)) = 1] = 1. Statistical soundness. For all unbounded adversaries A,

Adv soundness A (λ) := Pr[σ ← {0, 1} (λ) , (x, π) ← A(σ) : V (σ, x, π) = 1 ∧ x ∈ L]
is negligible. Computational zero-knowledge. There exists a tuple of PPT algorithms Sim = (Sim 1 , Sim 2 ) such that for all non-uniform PPT algorithms A,

Adv zk A (λ) := |Pr[Exp zk A,0 (λ) = 1] -Pr[Exp zk A,1 (λ) = 1]|
is negligible, where Exp zk A,0 and Exp zk A,1 are defined in Figure 22. As already observed in [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF], PREH rand ≈c in conjunction with NIZK proof systems conflicts with EOWFs.

Exp zk A,0 (λ) σ ← {0, 1} (λ) (x, w) ← A(σ) s.t. (x, w) ∈ RL π ← P (σ, x, w) return A(π) Exp zk A,1 (λ) (σ, τ ) ← Sim1(1 λ ) (x, w) ← A(σ) s.t. (x, w) ∈ RL π ← Sim2(τ, x) return A(π)

Theorem 11 ([IKOS10]). If extractable one-way function family ensembles without auxiliary information and NIZK proof systems for N P exist, then PREH rand

≈c is false.

This result extends to cPREH rand ≈c at the cost of assuming unbounded common auxiliary inputs.

Theorem 12. If there exist extractable one-way function family ensembles with unbounded common auxiliary information and NIZK proof systems for N P, then cPREH rand ≈c is false. Proof. We adapt the proof from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. Let F be an extractable one-way function family ensemble with common auxiliary information. Let

L λ := {(k, y) ∈ K λ × {0, 1} m(λ) | ∃x ∈ domain(f k ) : f k (x) = y}. Let (P, V ) be a NIZK proof system for L λ .
cPREH rand ≈c implies that for the PPT algorithm S (see Figure 23), there exists a PPT algorithm Setup S , an alternative sampler S and a corresponding inverse sampler S -1 satisfying closeness and invertibility as in Definition 9.

The common auxiliary input is necessary to give the adversary X and the extractor K X access to the same common reference string. Further, it is crucial to assume unbounded auxiliary input since the adversary X can be considered to be a universal adversary which simply executes the code which is contained in the auxiliary input. Since the size of the adversary can not be bounded in advance, neither can the size of the auxiliary input.

Since F is an extractable one-way function family ensemble with common auxiliary information, we have that for the algorithm X, there exists an extractor K X such that for every polynomial b and every crs ∈ {0, 1} b(λ) (hence, in particular, for every z := crs produced by Setup S (1 λ )), Pr[Exp ext-aux X,K X ,z (λ) = 1] is overwhelming. We prove that adversary A given in Figure 23 has an overwhelming probability to break the one-wayness of F. We proceed over a sequence of hybrids, see Figures 24 and25.

The individual game hops are justified as follows. The difference between the games G 0 and G 1 is only conceptual, hence, Pr[out

0 = 1] = Pr[out 1 = 1]. S(k, σ) x ← domain(f k ) y := f k (x) π ← P (σ, (k, y), x) return (y, π) X(k, z =: crs; σ r S ) (y, π) ← S(crs, (k, σ); r S ) return y A(1 λ , k, y) crs ← Setup S (1 λ ) (σ, τ ) ← Sim1(1 λ ) π ← Sim2(τ, (k, y)) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return x
Fig. 23. Description of the sampler S, of the adversary X on extractability of the EOWF and of the adversary A on one-wayness of the EOWF. Note that depending on definition of one-wayness, the CRS crs could also be auxiliary input to A.

G0 k ← K λ x ← domain(f k ) y := f k (x)
x ← A(k, y) Claim. There exists a PPT adversary A, such that |Pr[out

return f k (x ) = y G1 k ← K λ x ← domain(f k ) y := f k (x) crs ← Setup S (1 λ ) (σ, τ ) ← Sim1(1 λ ) π ← Sim2(τ, (k, y)) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y G2 k ← K λ x ← domain(f k ) y := f k (x) crs ← Setup S (1 λ ) σ ← {0, 1} (λ) π ← P (crs, (k, y), x) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y G3 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) ← S(k, σ) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y
2 = 1] -Pr[out 1 = 1]| ≤ Adv zk A (λ).
Proof. Construct adversary A. Initially, A receives σ as input and produces k, x, y, crs as in game G 1 and outputs the statement (k, y) together with a witness x to the experiment. In return, A receives a proof π and proceeds as in G 1 to produce r S , r X , x . Finally, A outputs 1 if f k (x ) = y and 0 otherwise. If A plays experiment Exp zk A,1 , σ was sampled along with some trapdoor τ and the proof π is simulated, hence, Pr[out

1 = 1] = Pr[Exp zk A,1 (λ) = 1]. If,

on the other hand, A plays experiment Exp zk

A,0 , σ is uniformly random from {0, 1} (λ) and the proof π is produced by P using the given witness, hence, Pr[out

2 = 1] = Pr[Exp zk A,0 (λ) = 1].
The difference between G 2 and G 3 is again only conceptual and Pr[out

2 = 1] = Pr[out 3 = 1].
Claim. There exists a PPT adversary A, such that |Pr[out Proof. Construct a PPT adversary A on (static) closeness. Initially, A produces (k, σ) as in game G 3 and outputs them to the experiment. In the second phase, A receives crs and (y, π), where (y, π) has either been sampled using S(k, σ) or using S(crs, (k, σ)). Further, A proceeds as in G 3 producing r S , r X , x . Finally, A outputs f k (x ) = y. Hence, Pr[out

4 = 1] -Pr[out 3 = 1]| ≤ Adv crs-close A (λ). G4 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) ← S(crs, (k, σ)) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y G5 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) r S ← {0, 1} * (y, π) ← S(crs, (k, σ); r S ) r S ← S -1 (crs, (k, σ), (y, π)) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y G6 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) r S ← {0, 1} * (y, π) ← S(crs, (k, σ); r S ) r X := σ r S x ← KX (k, crs, r X ) return f k (x ) = y G7 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) r S ← {0, 1} * r X := σ r S y ← X(k, crs; r X ) x ← KX (k, crs, r X ) return f k (x ) = y
3 = 1] = Pr[Exp crs-close A,0 (λ) = 1]
and Pr[out

4 = 1] = Pr[Exp crs-close A,1 (λ) = 1].
The difference between games G 4 and G 5 is again only conceptual, hence, Pr[out

4 = 1] = Pr[out 5 = 1].
Claim. There exists a PPT adversary A, such that |Pr[out

6 = 1] -Pr[out 5 = 1]| ≤ Adv crs-inv A (λ).
Proof. Construct a PPT adversary A on (static) invertibility. Initially, A (statically) produces (k, σ) as in G 5 and outputs them to the experiment. In the second phase, A receives (crs, r * , (y, π)), where (y, π) has been sampled using S(crs, (k, σ)) and r * either is the actual randomness used for that or the inverse sampled randomness produced via S -1 (crs, (k, σ), (y, π)). Afterwards,

A proceeds as in G 5 producing r X := σ r * and x . Finally, A outputs f k (x ) = y. Hence,

Pr[out 5 = 1] = Pr[Exp crs-inv A,1 (λ) = 1] and Pr[out 6 = 1] = Pr[Exp crs-inv A,0 (λ) = 1].
The difference between games G 6 and G 7 is again only conceptual, hence, Pr[out

6 = 1] = Pr[out 7 = 1]. Thus, we have that |Pr[out 0 = 1] -Pr[out 7 = 1]| is negligible. Lemma 14. Pr[out 7 = 1] is overwhelming.
Proof (of Lemma 14). Since F is an extractable one-way function, we have that Pr

G 7 [f k (x ) = y ∨ (k, y) ∈ L λ ] ≤ Pr G 7 [f k (x ) = y] + Pr G 7 [(k, y) ∈ L λ ] is overwhelming.
In the following, we prove that Pr G 7 [(k, y) ∈ L λ ] is negligible. We proceed over a series of hybrids, see Figures 26 and27. The individual game hops are justified as follows. The difference between H 0 and H 1 is only conceptual and Pr[out

H0 k ← K λ σ r S = rX ← {0, 1} (λ) crs ← Setup S (1 λ ) y = X(k, crs; rX ) return (k, y) ∈ L λ H1 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) = S(crs, (k, σ)) return (k, y) ∈ L λ H2 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) = S(crs, (k, σ)) return (k, y) ∈ L λ ∧V (σ, (k, y), π) = 0

H3

k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) = S(crs, (k, σ)) return V (σ, (k, y), π) = 0 H4 k ← K λ σ ← {0, 1} (λ) crs ← Setup S (1 λ ) (y, π) = S((k, σ)) return V (σ, (k, y), π) = 0
H 0 = 1] = Pr[out H 1 = 1].
Claim. There exists a PPT adversary A such that |Pr[out

H 2 = 1]-Pr[out H 1 = 1]| ≤ Adv soundness A (λ).
Proof. The only possibility that the output of H 1 and H 2 differ is the case that (k, y) ∈ L λ but V (σ, (k, y), π) = 1 (assuming, that the output of V is binary). Hence, |Pr[out

H 2 = 1]-Pr[out H 1 = 1]| ≤ Pr H 1 [(k, y) ∈ L λ ∧ V (σ, (k, y), π) = 1].
Construct adversary A on soundness of the NIZK proof system. On input of σ, A produces k, crs, (y, π) as in H 1 and outputs the statement (k, y) and the proof π. Thus, Pr H

1 [(k, y) ∈ L λ ∧ V (σ, (k, y), π) = 1] ≤ Adv soundness A (λ).
The distribution underlying H 2 and H 3 is identical. The only difference between these games is that the condition that H 3 outputs 1 is less restrictive than the one of H 2 , hence, Pr[out

H 2 = 1] ≤ Pr[out H 3 = 1].
In contrast to the preceding games, the simulation of game H 3 is efficient.

Claim. There exists a PPT adversary A such that |Pr[out

H 4 = 1]-Pr[out H 3 = 1]| ≤ Adv crs-close A (λ).
Proof. Construct a PPT adversary A on static closeness. Initially, A produces (k, σ) as in H 3 and outputs it to the experiment. On input of (crs, y := (y, π)), where y is either sampled via S(k, σ) or via S(crs, (k, σ)). Finally, A outputs V (σ, (k, y), π) = 0. We have that Pr[out

H 3 = 1] = Pr[Exp crs-close A,1 (λ) = 1] and Pr[out H 4 = 1] = Pr[Exp crs-close A,0 (λ) = 1].
Finally, due to the definition of S and the correctness of the NIZK proof system (P, V ), Pr[out H 4 = 1] = 0. This proves that Pr[out

H 0 = 1] is negligible.
This concludes the proof.

By an easy modification of the above proof, we can refute cPREH rand ≈c with universal setup.

Theorem 13. If there exist extractable one-way function family ensembles with unbounded common auxiliary information and NIZK proof systems for N P, then cPREH rand ≈c with universal setup is false.

We stress that assuming unbounded common auxiliary input is necessary since the adversary X can be considered the universal adversary. On a technical level, the common auxiliary input which leads to a contradiction is an output of the universal setup algorithm Setup on input of a sufficiently large bound B on the supported circuit size. This bound B depends on the adversary size.

Discussion. We stress that we are able to prove that EOWFs with unbounded common auxiliary input (in conjunction with NIZK proof systems) implies that cPREH rand ≈c is false. Furthermore, due to Theorems 15 and 16 in Section 6.3, cPREH rand ≈c can be instantiated from indistinguishability obfuscation and one-way functions. We restate a theorem from [START_REF] Bitansky | On the existence of extractable one-way functions[END_REF].

Theorem 14 ([BCPR14]). Assuming indistinguishability obfuscation for all circuits, neither EOWFs nor GEOWFs exist with respect to unbounded common auxiliary information.

Thus, the above is not a contradiction because due to Theorem 14, indistinguishability obfuscation for all polynomial sized circuits does not exist assuming EOWFs with unbounded common auxiliary input.

Common but benign auxiliary information. The definition due to [START_REF] Bitansky | On the existence of extractable one-way functions[END_REF] of (G)EOWFs with common auxiliary input requires that extractability holds for all common auxiliary inputs and hence also for a worst-case choice of common auxiliary input. This requirement can be weakened such that the common auxiliary input is drawn from some specific distribution. This distribution is called benign if it is unlikely that a common auxiliary input sampled according to this distribution encodes a malicious obfuscation 14 . In particular, the uniform distribution over {0, 1} b(λ) is conjectured to be benign. This notion of (G)EOWFs with common but benign auxiliary information does not contradict IO. However, by an easy modification of the proof of Theorem 12, the existence (G)EOWFs with common but benign auxiliary input (drawn uniformly at random from {0, 1} b(λ) ) contradicts cPREH rand ≈c with common random string.

Corollary 10. If there exist extractable one-way function family ensembles with common but benign auxiliary information, particularly for auxiliary inputs drawn uniformly at random from {0, 1} b(λ) , and NIZK proof systems for N P, then cPREH rand ≈c , where the setup algorithm produces uniform random strings, is false.

Key-less extractable one-way function ensembles. Definitions 23, 25 and 27 can be defined for key-less function ensembles, where the key space K λ contains exactly one element (for every λ). This poses much stronger requirements on one-wayness and extractability since these properties are bound to be met for one fixed key as opposed to the keyed variants.

As observed in [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF], Theorems 9 and 11 can be adapted to the weak variants of PREH rand ≈c and PREH rand ≡s , respectively.15 However, key-less (G)EOWFs with unbounded auxiliary input are impossible since the adversary might get a random image of the (fixed) (G)EOWF as auxiliary input. An extractor given the output of the adversary together with its random tape and the same auxiliary input must break one-wayness in order to produce a pre-image. Hence, Theorem 12 can not be adapted to refute weak cPREH rand ≈c .

Static pseudorandom encodings with universal setup from IO

cISH rand ≈c (and hence cPREH rand ≈c ) is implied by the existence of an explainability compiler [DKR15] which can be built from indistinguishability obfuscation and one-way functions. Using the ideas from [SW14; DKR15], we obtain perfectly correct cPREH rand ≈c with universal setup. Let S be a PPT algorithm and let U B (C, x; r) be the universal circuit that accepts any circuit C which can be represented with B bits and evaluates C on input x and randomness r. Let B be an upper bound on the bitlength which is necessary to describe a sampler. Let in = |m| be an upper bound on the bitlength of the inputs, out be an upper bound on bitlength of the outputs and r be an upper bound on the bitlength of random tape of such samplers. Let PRG be a PRG that maps {0, 1} λ to {0, 1} 2λ . Let

|u 1 | = 1 = 2B + 2 in + 2 out + 5λ, |u 2 | = 2 = B + in + out + 2λ.
Theorem 15. Let iO be a perfectly correct indistinguishability obfuscator, F 1 , F 2 , F 3 be puncturable PRFs satisfying the following additional properties -F 1 is extracting when the input min-entropy is greater than r + 2(λ + 1) + 2 with error less than 2 -(λ+1) and has input length 1 + 2 + in + B and output length r (such a PRF exists from one-way functions since 1 + 2 + in + B ≥ r + 2(λ + 1) + 2), -F 2 is statistically injective and has input length B + in + out + 2λ and output length 1 (such a PRF exists from one-way functions since 1 ≥ 2(B + in + out + 2λ) + λ), -F 3 has input length 1 and output length 2 . Then, perfectly correct cPREH rand ≈c with universal setup is true. )) = y.

Pseudorandomness. The proof can be divided into two main steps, see Figure 29.

Lemma 15. For all (potentially unbounded) adversaries A, |Pr[out

1 = 1] -Pr[out 0 = 1]| is negligible.
The proof works as the proof of IND-CPA security of the deniable encryption scheme from [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] or the proof of statistical functional equivalence from [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF].

Lemma 16. For all PPT adversaries A, |Pr[out

2 = 1] -Pr[out 1 = 1]| is negligible.
The proof is similarly as the proof of explainability of the deniable encryption scheme from [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] or the proof of explainability from [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF].

By allowing the setup algorithm Setup S to depend on S and replacing the universal circuit in C D with S, we obtain cPREH rand ≈c without universal setup. Let S be a PPT sampler. Let in = |m| be an upper bound on the bitlength of the inputs, out be an upper bound on bitlength of the outputs and r be an upper bound on the bitlength of random tape of S. Let PRG be a PRG that maps {0, 1} λ to {0, 1} 2λ . Let

|u 1 | = 1 = 2 in + 2 out + 5λ + r and |u 2 | = 2 = in + out + 2λ.
Theorem 16. Let iO be a perfectly correct indistinguishability obfuscator, PRF 1 , PRF 2 , PRF 3 be puncturable PRFs satisfying the following additional properties -PRF 1 is extracting when the input min-entropy is greater than r + 2(λ + 1) + 2 with error less than 2 -(λ+1) and has input length 1 + 2 + in and output length r (such a PRF exists from one-way functions since 1 + 2 + in + r ≥ r + 2(λ + 1) + 2), -PRF 2 is statistically injective and has input length in + out + 2λ and output length 1 (such a PRF exists from one-way functions since 1 ≥ 2( in + out + 2λ) + λ), -PRF 3 has input length 1 and output length 2 . Then, perfectly correct cPREH rand ≈c is true.

The proof of Theorem 16 proceeds identically to Theorem 15. The only differences are changed input and output lengths for the pseudorandom functions.

Theorems 15 and 16 together with Theorem 1 yield the following corollary.

Corollary 11. Assuming polynomially secure IO for all circuits and one-way functions, then acPREH rand ≈c (with or without universal setup) is true.

Bootstrapping pseudorandom encodings with a common random string

Recall that cPREH rand ≈c where the setup algorithm produces uniform random strings (i.e., in the common random string model) conflicts with EOWFs with common but benign auxiliary input -an assumptions which we believe to be true. However, the very nature of pseudorandom encodings allows to bootstrap pseudorandom encodings in the common random string model from pseudorandom encodings with arbitrary setup if this setup algorithm -interpreted as a sampler -can be pseudorandomly encoded such that the corresponding setup algorithm produces common random strings. Note that this sampler does not expect an input. Via this bootstrapping, we are able to refute that even the weak pseudorandom encoding hypothesis with common random string.

Theorem 17. Assume (i) cPREH rand

≈c is true for all PPT samplers, i.e., for all PPT algorithms S, there exists a pseudorandom encoding scheme (Setup S , E S , D S ), and (ii) weak cPREH rand ≈c is true for the class of PPT algorithms Setup S such that the corresponding setup algorithm Setup Setup S produces uniform random strings. Then, cPREH rand ≈c with common random strings is true for all PPT samplers. Proof. (i) implies that for all PPT algorithms S, there exists a pseudorandom encoding scheme (Setup S , E S , D S ). Further, (ii) guarantees the existence of a pseudorandom encoding scheme (Setup Setup S , E Setup S , D Setup S ) such that Setup Setup S produces uniform random strings.

Let {0, 1} n (λ) be the range of E Setup S (note that {0, 1} n (λ) is allowed to depend on the sampler Setup S ). For notational convenience, we henceforth omit the dependency on the sampler Setup S .

adversaries A,

Pr        m ← A(1 λ ) crs ← Setup S (1 λ ) y ← S(m) u ← E S (crs, m, y) : A(crs, m, y, u) = 1        -Pr        m ← A(1 λ ) crs ← Setup S (1 λ ) u ← {0, 1} n(λ) y ← D S (crs, m, u) : A(crs, m, y, u) = 1        is negligible.
Proof (Proof of Lemma 17). We proceed over a series of hybrids, see Figure 33. H 0 corresponds to the left-hand-side of the difference, where A receives a sample y from S(m) and the corresponding encoded sample u ← E S (crs, m, y).

H 1 is identical to H 0 except that A receives the decoded sample y D instead of the actual sample y S . If y S = y D both games behave identically, hence, by correctness, |Pr[out

1 = 1] - Pr[out 0 = 1]| ≤ c-dec-error A (λ)].
H 2 is identical to H 1 except that u is not produced as an encoding of y, but sampled uniformly at random from {0, 1} n(λ) . This game hop is justified by pseudorandomness |Pr G 2 is identical to G 1 except that G 2 samples u uniformly at random from {0, 1} n (λ) , whereas G 1 produces u as E S (crs , m, y). For all PPT adversaries A, |Pr[out 2 = 1] -Pr[out 1 = 1]| is negligible due to pseudorandomness (i).

[out 2 = 1] -Pr[out 1 = 1]| ≤ Adv crs-pre A (λ)].
Combining Theorem 17 and Corollary 10, we obtain the following corollary refuting weak cPREH rand ≈c with common random string. Corollary 12. If there exist extractable one-way function family ensembles with common but benign auxiliary information and indistinguishability obfuscation for all circuits, then weak cPREH rand ≈c with common random string is false. Remark 8. If weak cPREH rand ≈c was true such that the setup algorithms always produce uniform random strings, then the global common reference string model could be replaced with the global common random string model (or the non-programmable random oracle model) in every setting in cryptography.

Relations and applications of pseudorandom encodings

In this section we describe further applications of pseudorandom encodings. This unifies several areas in cryptography. In Section 7.1, we show that adaptively secure pseudorandom encodings with setup are equivalent to fully adaptive multi-party computation in the global CRS model for all PPT functionalities. This extends the results from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. In Section 7.2, we show that pseudorandom encodings yields honey encryption due to [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF] for arbitrary message distributions, even such which admit inputs. In Section 7.3, we define a keyless version of steganography. That is, in contrast to symmetric-key or public-key steganography, parties do not need any secret information in order to covertly communicate with each other. In Section 7.4, we define the notion of covert secure computation and give a general compiler which transforms secure computation protocol into a covert MPC protocol. In Section 7.5, we analyze the relation of pseudorandom encodings and certain PKE variants which are known to imply (fully) adaptive MPC.

Fully adaptively secure multi-party computation in the CRS model

Due to the equivalence of pseudorandom encodings and invertible sampling, we obtain an equivalence between pseudorandom encodings and fully adaptively secure multi-party computation. Due to [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF], PREH rand ≈c in conjunction with some adaptively secure oblivious transfer protocol implies fully adaptively secure multi-party computation for all randomized functionalities in the plain model.

In this section we first introduce some preliminaries on adaptive multi-party computation, henceforth denoted AMPC. In Sections 7.1.1 and 7.1.2, we extend the results on the relation between ISH and AMPC from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] to the global CRS model. This is directly possible since, due to Theorem 1 and Corollary 1, we have an instantiation of acISH rand ≈c .

Adaptive MPC

The definition of security of multi-party protocols follows the real/ideal model paradigm, [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]. A protocol Π is said to be secure if the output of the real execution of the protocol is indistinguishable from the output of an ideal computation, where a trusted third party exists.

Let F be a PPT functionality. Let x i be the input to party P i . We only consider semi-honest adversaries. Semi-honest adversaries are bound to follow the protocol specification while trying to obtain as much information as possible. There are general techniques to transform protocols which are secure with respect to semi-honest adversaries to protocols which are secure with respect to malicious adversaries at the cost of a local CRS which is inherent for malicious security, [START_REF] Canetti | Universally composable two-party and multi-party secure computation[END_REF]. In the following, we describe the stand-alone model for adaptive MPC on a very high level. We refer the reader to [Can00; Lin09] for more details.

The ideal execution, [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]. The ideal execution involves an ideal PPT adversary Sim (also called the simulator), a PPT environment Z and a trusted third party T . The ideal execution proceeds through several stages. In the first corruption stage, Sim adaptively decides to corrupt a party. When Sim corrupts a party, Sim learns that party's input and Z learns the identity of the corrupted party. In the computation stage, the uncorrupted and the corrupted parties send their inputs to T . The trusted party T evaluates the (possibly randomized) function (z 1 , . . . , z n ) ← F(x 1 , . . . , x n ) and sends the output to the respective parties. In the second corruption stage, Sim learns the outputs of the corrupted parties and again adaptively decides to corrupt a party. Upon corruption of a party, Sim learns that party's input and output and Z learns the corrupted party's identity. In the output stage, the uncorrupted parties output what they received from T to Z, the corrupted parties output ⊥ to Z and Sim outputs an arbitrary string to Z. Finally, in the post-execution corruption stage, as long as the environment Z did not halt, Z sends corruption requests to Sim. Sim generates an arbitrary answer based on its view so far. Furthermore, Sim may additionally corrupt parties as in the second corruption stage.

Let Z Sim,F (1 λ ) denote the output distribution of the environment Z when interacting as described above with the simulator Sim and parties P 1 , . . . , P n on inputs x 1 , . . . , x n chosen by Z.

The real execution, [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]. Initially, the environment Z (adaptively) chooses inputs x 1 , . . . , x n and sends each party P i its input. Before the communication rounds start, the adversary A receives an initial message from Z. While there exist uncorrupted parties which did not halt, A may adaptively decide to corrupt new parties. Upon corruption of P i , Z learns the identity of P i , A learns the input x i , P i 's internal state (i.e. the random tape) and all messages received so far. From that time on, A is in control of the messages this party sends. Furthermore, if a corrupted party receives a message, A also learns that message. Additionally, A determines the order in which the uncorrupted parties are activated. If all parties are corrupted or all uncorrupted parties halted, each uncorrupted party and A produce outputs. The environment Z learns all of these outputs. Similarly to the post-execution corruption stage in the ideal execution, while Z did not halt, Z may instruct A to corrupt more parties or A may decide himself to corrupt more parties. Upon corruption, A learns P i 's input, randomness and all messages received so far and Z learns the corrupted party's identity. Additionally, A sends P i 's internal state to Z.

Let Z A,Π (1 λ ) denote the output of the environment Z when interacting with the adversary A and parties P 1 , . . . , P n running the protocol Π on inputs x 1 , . . . , x n chosen by Z.

Definition 29 (Adaptive security in the stand-alone model, [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]). We say a protocol Π computes functionality F in the adaptive semi-honest model if for every PPT adversary A, there exists a PPT simulator Sim, such that for all PPT environments Z,

Pr[Z A,Π (1 λ ) = 1] -Pr[Z Sim,F (1 λ ) = 1] is negligible.
Common reference string model. In the common reference string (CRS) model, all parties have access to a string which is honestly generated by a trusted third non-participating party. There are two widely used variants of the CRS model. In the programmable or local CRS model, the simulator may generate the CRS. This enables the simulator to sample the CRS along with corresponding trapdoors which results in an asymmetry between the simulator and the adversary facilitating simulation. However, as soon as two different protocols use the same programmable CRS, all security guarantees related to that CRS break down, see [START_REF] Canetti | Universally Composable Security with Global Setup[END_REF]. In the nonprogrammable or global CRS model, the simulator receives the CRS as input and, hence, has no additional power compared to the adversary. A global CRS can be made public and used by any number of protocols without compromising security.

Adaptive security in the global CRS model (with respect to some efficiently samplable CRS distribution Setup) is defined as Definition 29 with the difference that all parties including the environment, the adversary and the simulator receive the CRS as input. We stress that the environment may decide on the inputs for the parties adaptively after seeing the CRS.

The universal composability (UC) framework, [START_REF] Canetti | Universally Composable Security: A New Paradigm for Cryptographic Protocols[END_REF]. The following paragraph describes the UC framework on a very high level. We refer the reader to [START_REF] Canetti | Universally Composable Security: A New Paradigm for Cryptographic Protocols[END_REF] for more details on the model.

In contrast to the stand-alone model for secure computation, the UC model allows the environment to be interactive. In particular, every message that is transmitted between parties is sent to the environment which can arbitrarily decide how to deal with it. Hence, the strongest possible adversary in this model is the so called dummy adversary who simply forwards all instructions he receives from the environment. The UC framework offers a set of securitypreserving composition theorems which allow for a modular analysis. If a protocol Π UC-realizes a functionality F, a protocol Π which uses protocol Π as a subroutine can be proven to securely realize a functionality F in the F-hybrid model, that is having access to the ideal functionality F.

Definition 30 (Adaptive UC-security, [Can01]).

Let A be the dummy adversary and let θ denote the dummy protocol. We say a protocol Π UC-realizes a functionality F in the G-hybrid model in the presence of semi-honest adaptive adversaries if for all PPT environments Z, there exists a simulator Sim, such that

Pr[real[Z, A, π G ] = 1] -Pr[ideal[Z, Sim, θ F ] = 1]
is negligible, where real[Z, A, π G ] denotes the output distribution of Z when interacting in the real world with A and π G and ideal[Z, Sim, θ F ] denotes the output distribution of Z when interacting in the ideal world with Sim and θ F . UC-security is a stronger notion than stand-alone security. More precisely, if there exists a protocol which UC-realizes a functionality according to Definition 30, then there exists a protocol which securely computes that functionality according to Definition 29.

In the UC framework, the global CRS model corresponds to the F crs Setup -hybrid model. The ideal functionality F crs Setup can be queried by any party and the adversary. Upon receiving such a query, F crs Setup gives the CRS crs to the querying party. If crs is not initialized, F crs Setup samples crs according to Setup(1 λ ). [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] already observed that adaptively secure oblivious transfer in conjunction with PREH rand ≈c yields AMPC for all randomized functionalities in the plain model.

Pseudorandom encodings imply UC-secure AMPC in the plain model

Theorem 18 (informal, [Kil88; IPS08]). Any deterministic functionality can be UC-realized in the OT-hybrid model in the presence of semi-honest adversaries adaptively corrupting any number of parties.

Theorem 19 ([IKOS10]

). Assume PREH rand ≈c holds, then any functionality F can be UCrealized, in the F OT -hybrid-model, in the presence of semi-honest adaptive adversaries corrupting any number of parties.

Assuming acPREH rand ≈c , the above strategy of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF] can be applied to show that every randomized functionality can be UC-realized in the (global CRS, OT)-hybrid model in the presence of semi-honest adversaries adaptively corrupting any number of parties.

Theorem 20. Assume acPREH rand ≈c holds, then any functionality F can be UC-realized, in the (global CRS, F OT )-hybrid-model, in the presence of semi-honest adaptive adversaries corrupting any number of parties.

Proof. The proof follows the strategy from [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. We consider functionalities F giving the same output to all parties. (This is without loss of generality since evaluating the function F ((x 1 , k 1 ), (x 2 , k 2 )) := F 1 (x 1 , x 2 ) ⊕ k 1 F 2 (x 1 , x 2 ) ⊕ k 2 yields the general case, see [START_REF] Goldwasser | Fair Computation of General Functions in Presence of Immoral Majority[END_REF].) I.e. the functionality F takes as input x 1 , x 2 (the inputs of the parties P 1 , P 2 , respectively) and internal randomness ρ, and outputs z to both parties. We consider the case of two parties (the proof easily extends to the case of many parties).

We view F as a PPT algorithm S. Due to acPREH rand ≈c , there exist Setup S , S, S -1 satisfying adaptive closeness and invertibility. Define a deterministic functionality G which takes inputs (x 1 , ρ 1 ) from party P 1 and (x 2 , ρ 2 ) from party P 2 , and evaluates S(crs, (x 1 , x 2 ); ρ 1 ⊕ ρ 2 ), where crs comes from F Setup S crs

. Due to Theorem 18, G can be UC-realized in the OT-hybrid model in the presence of semi-honest adversaries adaptively corrupting any number of parties. Now we turn to realize F in the G-hybrid model. Party P i chooses randomness ρ i , feeds (x i , ρ i ) into G and waits for the output. We assume that Z first observes the entire protocol before corrupting parties. The simulator Sim works as follows. Sim initially only receives the output z of the ideal functionality F as input and calls F Setup S crs to obtain crs. If both parties are corrupted (first P 1 , then P 2 ), Sim outputs a uniformly random string ρ 1 to explain the internal randomness of party P 1 , computes ρ ← S -1 (crs, (x 1 , x 2 ), z) and outputs ρ 2 := ρ ⊕ ρ 1 to explain the internal randomness of party P 2 (note that Sim learns the inputs x 1 , x 2 at the time of corrupting P 1 , P 2 , respectively). Due to invertibility and closeness, for all environments

Z, |Pr[real[Z, A, π G ] = 1] -Pr[ideal[Z, Sim, θ F ] = 1]| is negligible. More precisely, consider the hybrids in Figure 35. Note that Pr[out 0 = 1] = Pr[real[Z, A, π G ] = 1] and Pr[out 3 = 1] = Pr[ideal[Z, Sim, θ F ] = 1]. The difference between G 0 and G 1 is only conceptional. Furthermore, |Pr[out 2 = 1]-Pr[out 1 = 1]| ≤ Adv a-crs-inv A (λ) and |Pr[out 3 = 1]-Pr[out 2 = 1]| ≤ Adv a-crs-close A (λ). G0 crs ← Setup S (1 λ ) (x1, x2) ← Z(crs) ρ1
ρ 2 := ρ2 give (x2, ρ 2 ) to Z G2 crs ← Setup S (1 λ ) (x1, x2) ← Z(crs) ρ1, ρ2 ← {0, 1} n(λ) z := S(crs, x1, x2; ρ1 ⊕ ρ2) upon corruption of P1 do give (x1, ρ1, z) to Z upon corruption of P2 do ρ 2 ← ρ1 ⊕ S -1 (crs, (x1, x2), z) give (x2, ρ 2 ) to Z G3 crs ← Setup S (1 λ ) (x1, x2) ← Z(crs) ρ1 ← {0, 1} n(λ) z ← S(x1, x2) upon corruption of P1 do give (x1, ρ1, z) to Z upon corruption of P2 do ρ 2 ← ρ1 ⊕ S -1 (crs, (x1, x2), z)
give (x2, ρ 2 ) to Z Note that due to [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF], it is possible to realize UC-AMPC for every functionality only assuming the static version cPREH rand ≈c at the cost of additionally assuming the existence of adaptively secure two-round oblivious transfer protocol. This can be avoided due to Corollary 1.

AMPC with global setup implies adaptive pseudorandom encodings with setup

In the following we consider the standalone model [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]. Note that in the standalone model, the environment is strictly weaker than in the UC-framework.

Theorem 21. If for all (two party) PPT functionalities F, there exists a protocol Π that securely implements F in the global CRS model in the presence of adaptive semi-honest adversaries with post-execution corruption corrupting any number of parties, then acISH rand ≈c (without universal setup) is true.

Proof. The proof follows the ideas of [START_REF] Ishai | On Invertible Sampling and Adaptive Security[END_REF]. Let S be an arbitrary PPT algorithm. Let x 1 denote the input of party P 1 and x 2 denote the input of party P 2 .

Consider the randomized functionality F which computes z := S(x 1 , x 2 ; ρ) and outputs z to P 1 and ⊥ to P 2 , where ρ is the internal random coins of the functionality. We denote the message space of S by L. Let Π be a protocol which securely realizes F in the global CRS model (where the common reference string is drawn according some distribution Setup F possibly depending on the functionality F) in the presence of adaptive semi-honest adversaries (with post-execution corruption). Further, let p 1 and p 2 be stateful PPT algorithms modeling the protocol messages exchanged between the parties P 1 and P 2 . More formally, (m 2i+1 , z i ) ← p 1 (crs, x 1 , m 2i ; r 1 ) and m 2j ← p 2 (crs, x 2 , m 2j-1 ; r 2 ) for i ≥ 0, j ≥ 1 and r 1 , r 2 ← {0, 1} poly(λ) (for some sufficiently large polynomial poly). (Without loss of generality, we let p 1 additionally output z i which equals ⊥ during the protocol execution and contains the output of party P 1 after the execution.) Proof. Since we only consider protocols Π with at most polynomially many rounds, S is a PPT algorithm.

S(crs, (x1, x2); (r1, r2)) z := ⊥, m := ⊥ while z = ⊥ do (m, z) ← p1(crs, x1, m, r1) m ← p2(crs, x2, m, r2) return z S -1 (crs, (x1, x2), z; rS) {m i } i∈[poly(λ)] ← Sim1(crs; rS) (z, r 1 ) ← Sim2(x1, z) r 2 ← Sim3(x2) return (r 1 , r 2 )
Intuitively, the output distributions of S and S are computationally close because of "correctness" of the protocol Π.

Let B be the adversary on the protocol Π which only observes the protocol and does not interfere at all. By Definition 29, there exists a simulator Sim such that for all environments Z, |Pr

[crs ← Setup F (1 λ ) : Z A,Π (crs) = 1] -Pr[crs ← Setup F (1 λ ) : Z Sim,F (crs) = 1]| is negligible.
Note that since B corrupts no parties, Sim also corrupts no parties.

Let A be an adversary on closeness. We construct an environment Z which distinguishes between the real and the ideal world as follows. Initially, Z receives crs as input, calls A on input of crs and obtains (x 1 , x 2 ) ∈ L. Z uses x 1 as input for party P 1 and x 2 as input for P 2 . Then, Z executes the protocol (without any interference) and finally receives the output (z, ⊥). Z calls A on input z and outputs the A's output.

In the ideal world, Z receives the outputs z and ⊥ for P 1 and P 2 from the trusted third party T (since no party is corrupted) which are computed by F. Hence, if Z is in the ideal world, it simulates Exp a-crs-close A,0 . In the real world, Z interacts with the actual parties running protocol Π and, hence, simulates Exp a-crs-close A,1

. Therefore, Adv a-crs-close

A (λ) ≤ |Pr[crs ← Setup F (1 λ ) : Z A,Π (crs) = 1] -Pr[crs ← Setup F (1 λ ) : Z Sim,F (crs) = 1]|
for the environment Z and the adversary B which do not interfere with the protocol execution. which is negligible by assumption and Equation (8).

Therefore, for every PPT algorithm S, there exists an algorithm Setup S , an alternative sampler S and an inverse sampler S -1 such that adaptive closeness and adaptive invertibility hold. This concludes the proof.

Combining Theorems 20 and 21 and since semi-honest adaptive MPC in the non-programmable common random string model implies semi-honest adaptive MPC in the plain model, we obtain the following corollary improving Corollary 12.

Corollary 13. If there exist extractable one-way function family ensembles (without auxiliary information) and indistinguishability obfuscation for all circuits, then weak cPREH rand ≈c with common random string is false.

Honey encryption

Honey encryption schemes [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF] are symmetric key encryption schemes which offer security even against unbounded adversaries, i.e. even against adversaries which are able find the used symmetric key. This is a particularly useful notion when the key comes from a distribution with low min-entropy like passwords. On decryption with a wrong key, a honey encryption scheme behaves indistinguishably from decryption with the actually used key.

Let D 1 be an efficiently samplable key distribution over the key space K λ and let D 2 be an efficiently samplable message distribution over the message space M λ .

Definition 31 (Honey encryption, [JR14]

). A symmetric encryption scheme (Enc, Dec) is called honey encryption scheme for key distribution D 1 and plaintext distribution D 2 if it satisfies the following property.

Security against message recovery (with respect to D 1 , D 2 ). For all unbounded adversaries A, the advantage Adv mr

A,D 1 ,D 2 (λ) = Pr[Exp mr A,D 1 ,D 2 (λ) = 1]
is negligibly close to 2 -µ 1 , where µ 1 = H ∞ (D 1 ) and Exp mr A,D 1 ,D 2 is defined as in Figure 37. The above notions are defined with respect to unbounded adversaries. This is a simplification meant to capture the fact that an adversary is able to perform work proportional to 2 -µ 1 . For low-entropic key distributions, a computational variant of the above definition suffices. We refer to this as computational honey encryption.

Exp mr A,D 1 ,D 2 (λ) k ← D1(1 λ ) m * ← D2(1 λ ) c * ← Enc(k, m * ) m ← A(c * ) return m = m * Exp dte A,0 (λ) y * ← S(1 λ ) u * ← ES(m * ) return A(u * , y * ) Exp dte A,1 (λ) u * ← {0, 1} n(λ)
Relaxing the perfect correctness requirement from Definition 32 recovers the definition of (weak) PREH rand ≡s (or weak PREH rand ≈c in the computational case) by Lemma 17 and still suffices to imply honey encryption via the DTE-then-Encrypt framework due to [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF] given a secretkey encryption scheme (with message space matching the range of E S ). Applying the DTE-then-Encrypt framework on acPREH rand ≡s and acPREH rand ≈c yields honey encryption in a CRS model for high-entropic and low-entropic key distributions, respectively. Note that the adaptive versions are only necessary when considering message distributions D 2 with input.

Theorem 22. If acPREH rand ≡s (or acPREH rand ≈c ) is true an a suitable secret-key encryption scheme (modeled as random cipher) exists, then (computational) honey encryption exists for all efficiently samplable message distributions in the CRS model.

The proof directly follows from [START_REF] Juels | Honey Encryption: Security Beyond the Brute-Force Bound[END_REF]. Together with Theorems 15 and 16, we obtain the following corollary.

Corollary 14. If polynomially secure IO exists and a (suitable) secret-key encryption scheme (modeled as random cipher) exists, then computational honey encryption exists for all efficiently samplable message distributions in the CRS model.

Keyless steganography

Pseudorandom encodings yield a notion of keyless steganography. In the case of acPREH rand ≈c all parties need access to some public parameters, but none of the parties needs access to a secret key. We adopt the notation from [START_REF] Berndt | On the Gold Standard for Security of Universal Steganography[END_REF]. Since decoding does not involve any secret information, any attack corresponds to an equivalent of SS-CCA-security for public-key stegosystems (PKStS), where the decoding may even be applied on the challenge. Hence, the definition of SS-CCAsecurity must be adapted such that the message to be hidden is not chosen by the adversary but sampled according to a predefined message distribution. Let dl(λ) be the document length and ol(λ) be the output length.

Definition 33 (Keyless stegosystem (KlStS) for distribution S). A keyless stegosystem for message distribution S is a triple of PPT algorithms (KlStS.Setup, KlStS.E S , KlStS.D S ), where -KlStS.Setup(1 λ ) produces public parameters pp (without corresponding secret information), -KlStS.E S on input of pp, a message y sampled from S, a history hist ∈ (Σ dl(λ) ) * and some state information s ∈ {0, 1} * , produces a document d ∈ Σ dl (by being able to sample from C λ,dl(λ) ). KlStS.E C S (pp, m, hist) denotes sampling ol(λ) documents using KlStS.E S one-by-one. -KlStS.D S on input of pp, and a sequence of documents d 1 , . . . , d ol(λ) , and outputs a message m .

We require KlStS to meet the following properties.

Universality. KlStS works on any channel without prior knowledge of the distribution of the channel. Reliability. The probability Pr KlStS.D S (pp, KlStS.E S (pp, m, hist), hist) = m that decoding fails is negligible, where the probability is over the choice of pp, m and the random coins of KlStS.E S .

Functionality F CMPC (f, g) F CMPC runs with an adversary A and a set of n parties (Pi) i≤n , some of whome might not be actually taking part to the protocol, and knows the description of two n-entry functions f and g (the latter is the admissibility function). Before the protocol, A can corrupt a subset of the parties; the remaining parties are denoted honest parties. Honest non-participating parties are assumed to automatically send ⊥ to the trusted party. The trusted party ignores all messages that are not correctly formatted.

Input. The trusted party waits until it received an input xi from each party Pi. Send output to adversary. Let x = (xi) i≤n . If any entry of x is ⊥, F CMPC sets the output y to ⊥. Else, it checks that g(x) = 1, and sets y to ⊥ if this check fails. If the check passes, it sets y ← f (x). The trusted party sends y to A. Send output to honest parties. The trusted party waits until it receives from A a list of honest parties that should get the output. It sends y to those parties, and ⊥ to the remaining honest parties.

The honest participating parties output whatever output they received from the functionality. Nonparticipating and corrupted parties output ⊥ by convention. The adversary outputs its entire view. Real Model. Honest participating parties follow the specifications of the protocol. Honest nonparticipating parties are assumed to send uniformly random messages. We consider static semi-honest corruption of players, in which the corrupted players are chosen once-for-all by the adversary before the start of the protocol, and follow the specifications of the protocol.

Honest participating parties compute their output as specified, non-participating and corrupted parties output ⊥ by convention, and the adversary outputs its entire view of the execution of the protocol. For an adversary A, an execution of a protocol Π(f, g) in the real model with participation data p and input x is defined as the output of the parties together with the output of the adversary. It is denoted REAL Π(f,g),A (p, x).

Definition 34 (Covert security [CGOS07]

). A protocol Π(f, g) securely implements F CMPC (f, g) if for every probabilistic polynomial-time adversary A statically corrupting up to n -1 players in the real model, there is an expected polynomial-time adversary S corrupting at most n -1 players in the ideal model, such that for any (p, x) ∈ {0, 1} n × ({0, 1} * ) n , {IDEAL f,g,S (p, x)} ≈ c {REAL Π(f,g),A (p, x)}

We now show that pseudorandom encodings enable to convert a large class of secure computation protocols (satisfying the standard static semi-honest security notion) into protocols secure in the covert model of [START_REF] Chandran | Covert Multi-Party Computation[END_REF]. Covertness is a very strong security notion, protecting the participants from even leaking the information that they took part to the protocol. Interestingly, since the pseudorandom encoding hypothesis is equivalent to the existence of adaptive MPC for all functionalities, our result create a link between two extreme but seemingly unrelated notions of secure computation: adaptive multi-party computation for all functionalities implies the existence of a generic compiler for covert multi-party computation. We find this link to be intriguing.

A compiler for covert oblivious transfer

As a warm-up, we start from a static, semi-honest oblivious transfer protocol, and show how to compile it into a covert OT using pseudorandom encodings. Consider a two-round OT, as follows:

R OT (1 λ , b; r R ) takes as input a bit b and randomness r R and outputs the first protocol message OT 1 . S OT (OT 1 , (y 0 , y 1 ); r S ) takes as input the first message OT 1 , a tuple (y 0 , y 1 ) ∈ ({0, 1} λ ) 2 and randomness r S and outputs the second protocol message OT 2 .

E OT (OT 2 , b, r R ) takes as input OT 2 the bit b and the randomness r R and outputs y ∈ {0, 1} λ .

Covert oblivious transfer was defined in [START_REF] Luis Von Ahn | Covert two-party computation[END_REF]; a covert OT protocol realizes the standard OT functionality, and satisfies two additional properties:

-(receiver indistinguishability) For any b, the distribution induced by R OT (1 λ , b) is indistinguishable from the uniform distribution (over bistrings of an appropriate size); -(sender indistinguishability) For any OT 1 , the distribution {OT 2 ← S OT (OT 1 , (y 0 , y 1 )) : (y 0 , y 1 ) ← ({0, 1} n ) 2 } is indistinguishable from the uniform distribution (over bistrings of an appropriate size). Now, let (E 1 , D 1 ) be a pseudorandom encoding for the sampler R OT (1 λ , b) which takes as input (1 λ , b), and let (E 2 , D 2 ) be a pseudorandom encoding for the sampler S OT (OT 1 , (y 0 , y 1 )) which takes as input a string OT 1 and samples (y 0 , y 1 ) at random. Consider the following covert OT protocol, built from an arbitrary two-round OT: covR OT (1 λ , b; r R ) compute a 1 ← R OT (1 λ , b; r 0 R ) and output OT 1 ← E 1 (a 1 , 0; r 1 R ). covS OT (OT 1 , (y 0 , y 1 )) compute a 1 ← D 1 (OT 1 , 0), a 2 ← S OT (a 1 , (y 0 , y 1 )), and output OT 2 ← E 2 (a 2 , a 1 ). covE OT (OT 2 , b, r R ) reconstruct (a 1 , OT 1 ) from r R = (r 0 R , r 1 R ). compute a 2 ← D 2 (OT 2 , a 1 ) and output E OT (a 2 , b, r 0 R ). We now prove that the above protocol realizes the OT functionality and satisfies receiver and sender indistinguishability.

-(receiver indistinguishability) E 1 (R OT (1 λ , b), 0) ≈ c E 1 (R OT (1 λ , 0), 0) ≈ c U , where U denotes the uniform distribution (over bitstrings of some appropriate length). The first indistinguishability follows from the receiver security of the underlying semi-honest OT protocol, and the second follows from the pseudorandomness of E 1 . -(sender indistinguishability) follows directly from the pseudorandomness of E 2 . -(OT functionality) sender security and receiver security are trivially inherited from the underlying semi-honest OT: neither E 1 nor E 2 use any of the private inputs of the parties. It remains to verify that correctness is preserved. This follows from the receiver security of the underlying OT and the correctness of the encoding: it must hold for any b that D 1 (E 1 (m, 0), 0) = m when m ← R OT (1 λ , b), since correctness of encoding guarantees that this holds when m ← R OT (1 λ , 0); but then, it must hold as well when b = 1, otherwise (E 1 , D 1 ) would allow to break the receiver security of the underlying OT. The correctness of covE OT follows directly from the correctness of the encoding, which concludes the proof.

A general compiler for covert protocols

Compiling a secure computation protocol into a covert MPC protocol requires some care, since both models have syntactic differences: a covert MPC protocol must, by design, have an admissibility function g defining whether the inputs of the parties are admissible, in addition to the target function f to be computed. We therefore focus on compiling secure protocols which already satisfy this syntactic requirement. Consider an arbitrary two-party protocol Π f,g , where A has input x and B has input y, which implements the following functionality F f,g : it first computes an admissibility function g(x, y) on the inputs. If g(x, y) = 1, it outputs random shares of the target function f (x, y) to the parties; else, it outputs random values to all parties. We assimilate A (resp. B) to a sampler that take as input x (resp. y) together with the transcript T of the protocol so far, and outputs the next message of A (resp. B). Eventually, we only assume from Π a weak indistinguishability-style security guarantee, namely that for any inputs x, y, no adversary passively corrupting B (resp.

A) can distinguish the transcript of an interaction with A on input x (resp. B on input y) from the transcript of an interaction with A on input 0 (resp. B on input 0). Note that the protocol outputs random shares, so the output distribution of B is independent of A's input.

Let (E A , D A ) be a pseudorandom encoding associated to the sampler A, and (E B , D B ) be a pseudorandom encoding associated to the sampler B. The compiled protocol covΠ f,g is constructed as follows: at round i, given a transcript T up to round i -2, the message m B received from Bob at round i -1, and an input x, Alice computes m ← D B (||0), appends m to T , samples m ← A(T ||x), and sends m A ← E A (m, T ||0). Bob proceeds symmetrically.

Proof Sketch. A straightforward generalization of the argument for the covert OT protocol shows that covΠ f,g satisfies an indistinguishability-style notion of covertness: at each round, it holds that

E A (A(T ||x), T ||0) ≈ c E A (A(T ||0), T ||0) ≈ c U,
where U denotes the uniform distribution over strings of appropriate length; the first indistinguishability follows from the security of Π f,g , and the second from the pseudorandomness of E A . Similarly, security of Π f,g and correctness of the pseudorandom encodings guarantee the correctness of covΠ f,g . If the protocol Π f,g further satisfies a simulation-style security notion and securely implements the functionality F f,g , the protocol covΠ f,g can be shown to covertly implement the functionality F CMPC (f, g).

Deniable encryption

As noted in [START_REF] Canetti | Deniable Encryption[END_REF], sender deniable encryption is related to adaptively secure MPC (for adaptively well-formed functionalities). In this section, we analyze if cPREH rand ≈c together with the existence of a PKE scheme suffices to obtain deniable encryption.

Recall, that the explainability compiler of [START_REF] Dachman-Soled | Adaptively Secure, Universally Composable, Multiparty Computation in Constant Rounds[END_REF] which is based on the deniable encryption scheme of [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] corresponds to cISH rand ≈c , where closeness actually holds information theoretically. Let cISH denote this variant of cISH rand ≈c , where closeness holds information theoretically.

Definition 35 (Publicly deniable encryption, [SW14]

). A publicly deniable encryption scheme for message space M is a tuple (Gen, Enc, Dec, Explain) such that (Gen, Enc, Dec) is an IND-CPA secure encryption scheme and the following property is satisfied. We only consider publicly deniable encryption schemes with message space {0, 1}, since a deniable encryption scheme with message space {0, 1} implies a publicly deniable encryption scheme for message space {0, 1} n (for a polynomial n in λ).

Indistinguishability of explanation. For all PPT adversaries

For message space {0, 1}, indistinguishability of explanation is equivalent to the indistinguishability of Exp ind-expl A,0 and Exp ind-expl A,1 as defined in Figure 40. cISH in conjunction with a PKE scheme yields (publicly) sender deniable encryption.

Theorem 24. Let (Gen, Enc, Dec) be a public-key encryption scheme for message space {0, 1}. If cISH holds, then there exists a publicly deniable encryption scheme for message space {0, 1}.

Proof. cISH implies that for the PPT algorithm Enc there is a setup algorithm Setup Enc , an alternative sampler Enc and an inverse sampler Enc -1 satisfying statistical closeness and computational invertibility. We define a publicly deniable encryption scheme (Gen , Enc , Dec , Explain ) in Figure 41. Proof. Let A be an unbounded adversary distinguishing G 0 and G 1 . Construct an adversary A on closeness. Initially, A samples (pk, sk) ← Gen(1 λ ) and outputs m := (pk, 0) to the experiment. In return, A receives (crs, y), where y is either sampled using Enc(m) or Enc(m). A calls A on input of ((crs, pk), y). The game hop from G 1 to G 2 is justified by the IND-CPA security of (Gen, Enc, Dec). The game hop from G 2 to G 3 is justified by statistical closeness. Indistinguishability of explanation. We need to prove indistinguishability between the games described in Figure 43.

Claim. For all PPT adversaries A, Adv ind-expl A (λ) is negligible.

polynomial time and, hence, a reduction to closeness against PPT adversaries is not possible. We do, however, obtain a non-standard notion of adaptive MPC with super-polynomial simulation, namely for any functionality F we are able to adaptively realize a functionality F which produces a computationally (against PPT adversaries) indistinguishable output distribution to the original functionality. We view it as an interesting problem to further study this notion of adaptive MPC.

Fig. 2 .

 2 Fig. 2. The pseudorandomness experiments.

Fig. 3 .

 3 Fig. 3. The static pseudorandomness experiments with setup.

Fig. 4 .

 4 Fig. 4. The adaptive pseudorandomness experiments with setup.

Fig. 5 .

 5 Fig. 5. Adaptive pseudorandom encodings.

  Fig. 6. Hybrid games for the proof of adaptive correctness.

Fig. 8 .

 8 Fig. 8. Adversary used for the game hop from G0 to G1.

Fig. 10 .

 10 Fig. 10. The closeness and invertibility experiments.

yFig. 11 .

 11 Fig. 11. The static closeness and invertibility experiments with setup.

Fig. 12 .

 12 Fig. 12. The adaptive closeness and invertibility experiments with setup.

Lemma 4 .

 4 Let α ∈ {≈ c , ≡ s } and β ∈ {rand, det}. If ISH β α holds, then PREH β α holds.

G0rFig. 13 .

 13 Fig. 13. Hybrids used in the proof of correctness of Lemma 4.

G0rFig. 14 .

 14 Fig. 14. Hybrids used in the proof of pseudorandomness of Lemma 4.

  If y ← S(m), A simulates game G 0 for A, and if y ← S(m), A simulates game G 1 for A. Hence, Pr[out 0 = 1] = Pr[Exp close A,m,0 (λ) = 1] and Pr[out 1 = 1] = Pr[Exp close A,m,1 (λ) = 1].

G0Fig. 15 .

 15 Fig. 15. Hybrids used in the proof of closeness of Lemma 5.The difference between game G 0 and game G 1 is only conceptional, hence, Pr[out0 = 1] = Pr[out 1 = 1].G 1 and G 2 proceed exactly identical if y S = y D . More formally, let F be the event that y S = y D . We have that out 1 = 1 ∧ ¬F ⇔ out 2 ∧ ¬F . Hence, the Difference Lemma (due to Shoup,[START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF]) bounds |Pr[out 2 = 1] -Pr[out 1 = 1]| ≤ Pr[F ]. Correctness guarantees that for all m ∈ L, Pr[F ] = Pr[y S ← S(m) : D S (m, E S (m, y S )) = y S ] = dec-error (λ) is negligible.

G0rFig. 16 .

 16 Fig. 16. Hybrids used in the proof of invertibility of Lemma 5.

.

  Proof. Construct a PPT adversary A on the pseudorandomness property. On input of (m, u), A calls A on input (m, u =: r D , D S (m, u) =: y D ) and outputs the resulting output. If u ← E S (m, y) for y ← S(m), A perfectly simulates game G 3 for A. Otherwise, if u is uniformly random over {0, 1} n(λ) , A perfectly simulates game G 4 for A. Hence, Pr[out 3 = 1] = Pr[Exp pre A,m,0 (λ) = 1] and Pr[out 4 = 1] = Pr[Exp pre A,m,1 (λ) = 1]. The difference between G 4 and G 5 is again only conceptional and Pr[out 4 = 1] = Pr[out 5 = 1]. Hence, |Pr[out 5 = 1] -Pr[out 0 = 1]| ≤ 2 • Adv pre A,m (λ) + 2 • dec-error (λ) for some PPT adversary A.

  X has HILL entropy at least k, denoted by H HILL ,s (X) ≥ k, if there exists a distribution Y such that H ∞ (Y ) ≥ k and |Pr[x ← X : A(x) = 1] -Pr[y ← Y : A(y) = 1]| ≤ for all A of size at most s.

Fig. 17 .

 17 Fig. 17. One-way and extraction game.

Fig. 18 .

 18 Fig. 18. One-way and extraction game with common auxiliary input.

Fig. 19 .

 19 Fig. 19. R F -hardness and R F -extraction game with common auxiliary input.

Fig. 20 .

 20 Fig. 20. Description of the sampler S and of the adversary A on one-wayness of the privately verifiable GEOWF.

Fig. 21 .

 21 Fig. 21. Hybrids used in the proof of Theorem 9.

Fig. 22 .

 22 Fig. 22. Zero-knowledge games.

Fig. 24 .

 24 Fig. 24. Hybrids used in the proof of Theorem 12.

Fig. 25 .

 25 Fig. 25. Hybrids used in the proof of Theorem 12.

Fig. 26 .

 26 Fig. 26. Hybrids used in the proof of Lemma 14.

Fig. 27 .

 27 Fig. 27. Hybrids used in the proof of Lemma 14.

Setup( 1 Fig. 28 .

 128 Fig. 28. Instantiation of perfectly correct cPREH rand ≈c due to [SW14; DKR15].

Proof.

  Perfect correctness. Let crs =: (Λ E , Λ D ) be parameters in the support of Setup(1 λ , B). Let S be a PPT algorithm represented as a polynomial sized circuit, m ∈ L be an input for S and let y ∈ supp(S(m)). Due to perfect correctness of iO we have D S (crs, m, E S (crs, m, y; r)) = C D (S, m, C E (S, m, y, r)) = C D (S, m, (F 2 (S, m, y, PRG(r)) =e 1 , F 3 (e 1 ) ⊕ (S, m, y, PRG(r)) =e 2

G0mFig. 29 .

 29 Fig. 29. Hybrids used in the proof of pseudorandomness for Theorem 15.

Fig. 30 .

 30 Fig. 30. Instantiation of perfectly correct cPREH rand ≈c due to [SW14; DKR15] without universal setup.

H0mFig. 33 .

 33 Fig. 33. Hybrids used in the proof of Lemma 17.

  , ρ2 ← {0, 1} n(λ) z := G(x1, ρ1, x2, ρ2) upon corruption of P1 do give (x1, ρ1, z) to Z upon corruption of P2 do give (x2, ρ2) to Z G1 crs ← Setup S (1 λ ) (x1, x2) ← Z(crs) ρ1, ρ2 ← {0, 1} n(λ) z := S(crs, (x1, x2); ρ1 ⊕ ρ2) upon corruption of P1 do give (x1, ρ1, z) to Z upon corruption of P2 do

Fig. 35 .

 35 Fig. 35. Hybrids used in proof of Theorem 20.

Fig. 36 .

 36 Fig. 36. Definition of the alternative sampler S (left) and the corresponding inverse sampler S -1 (right).

yFig. 37 .

 37 Fig. 37. Message recovery experiment and DTE security experiment.

Fig. 39 .

 39 Fig. 39. Ideal Functionality for Covert Multi-Party Computation.

Fig. 40 .

 40 Fig. 40. Indistinguishability of explanation experiments in its adaptive variant (left) and static variant (right).

Gen ( 1 Fig. 41 .

 141 Fig. 41. Publicly deniable encryption scheme from cISH .

G0crs←Fig. 42 .

 42 Fig. 42. Hybrids used in the proof of IND-CPA security for Theorem 24.

Claim.

  For all (unbounded) adversaries A there exists an (unbounded) adversary A such that|Pr[out 1 = 1] -Pr[out 0 = 1]| ≤ Adv crs-close A (λ).

  Hence, Pr[out b = 1] = Pr[Exp crs-close A,1-b (λ) = 1] for b ∈ {0, 1}.

  ).

	Definition 4 (Pseudorandom encoding hypothesis with setup, cPREH rand ≈c ). cPREH rand

≈c holds if for every PPT algorithm S, there exists a PPT algorithm Setup S , efficient algorithms (E S , D S ), where D S is deterministic and E S is randomized (with output length n(λ)) satisfying the following two requirements.

Without this requirement, the problem can be solved using non-interactive commitment schemes with the additional property that commitments are pseudorandom (which exist under standard cryptographic assumptions).

We note that not all efficiently samplable distributions can be pseudorandomly encoded with a deterministic encoding algorithm. For instance, a distribution which has one very likely event and many less likely ones requires one specific encoding to appear with high probability. Thus, we formally restrict the deterministic variants of the pseudorandom encoding hypothesis to only hold for "compatible" samplers, which still results in interesting connections. In this overview, however, we ignore this restriction.

If perfect compression exists, pseudorandom generators cannot exist (observation attributed to Levin in[START_REF] Goldberg | Compression and Ranking[END_REF]).

Informally, an iO scheme is a PPT algorithm that takes as input a circuit C and produces another circuit iO(C) such that C and iO(C) compute the same function, but iO(C) is unintelligible in the following sense. If two circuits C1 and C2 compute the same function, then iO(C1) and iO(C2) are computationally indistinguishable. The notion of iO was introduced in [BGIRSVY01] and first instantiated in[START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF].

Let (X, Z) be a joint distribution. The conditional computational entropy is the entropy X appears to have to a bounded adversary when additionally given Z.

Note that by a coin-fixing argument, it is sufficient to consider non-uniform deterministic adversaries. Most of our results apply for uniform PPT adversaries as well. In case we make explicit use of the non-uniformity of the adversary, we remark this explicitly.

For notational convenience, we do not write the sampler Setup S as index.

We note that if some distribution Y is -close to a distribution Z, H∞(Y ) ≥ -log(2 -H∞(Z) + (λ)) = H∞(Z) -log(1 + (λ)2 H∞(Z) ).

Note that here we use that the adversary is non-uniform.

Note that here we use that the adversary is non-uniform.

Since F is privately verifiable, an efficient algorithm computing the relation R F k additionally requires the preimage of y as an input. For our purpose, it suffices to consider an inefficient testing algorithm T .

By malicious obfuscation we mean an obfuscated circuit which renders extraction from an adversary which simply executes the obfuscated circuit on the given key infeasible, see[START_REF] Bitansky | On the existence of extractable one-way functions[END_REF].

For weak PREH rand ≈c , the NIZK proof system must be replaced by a NIWI proof system (without CRS) and therefore the sampler S samples two images of the EOWF and a NIWI proof using one of the preimages as witness.

Acknowledgments. We thank Daniel Wichs for suggesting the unconditional static-to-adaptive transformation, as well as anonymous reviewers for extremely useful feedback.

* Supported by ERC Project PREP-CRYPTO 724307 and by the German Federal Ministry of Education and Research within the framework of the project KASTEL_SKI in the Competence Center for Applied Security Technology (KASTEL). † Supported by ERC Projects PREP-CRYPTO 724307 and CryptoCloud 339563. Work done in part while visiting UCLA and the Technion. ‡ Supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, ISF grant 2774/20, and a grant from the Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India. Work done in part while visiting UCLA. § Supported by the NSF SaTC award 1817143. ¶ Supported in part by DARPA SAFEWARE and SIEVE awards, NTT Research, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, NTT Research, or the U.S. Government.

Let S be some PPT algorithm. We define (Setup S , E S , D S ) corresponding to S as in Figure 31. Correctness. We use a sequence of hybrids, see Figure 32. G 0 encodes and decodes a sample y (using a statically chosen input m) using (Setup S , E S , D S ). G 1 is identical to G 0 except that G 1 uses the implementations of Setup S , E S and D S explicitly. This difference is only conceptual.

G 2 is identical to G 1 except for crs being sampled using Setup S (1 λ ) instead of decoding u using D (crs , u ).

Due to Lemma 5, by correctness and pseudorandomness (ii), the two distributions crs ← Setup (1 λ ), crs ← Setup S (1 λ ) : (crs , crs ) crs ← Setup (1 λ ), crs ← D (crs , U n (λ) ) : (crs , crs ) are computationally indistinguishable. Hence, |Pr[out 2 = 1] -Pr[out 1 = 1]| is negligible. Due to correctness (i), for all PPT adversaries A,

and, hence, Pr[out 2 = 1] are overwhelming. Before we prove pseudorandomness, we introduce a technical lemma.

Lemma 17. Let S be a PPT sampler such that cPREH rand ≈c is true for S and let (Setup S , E S , D S ) be the corresponding algorithms (such that E S has output length n(λ)). Then, for all PPT This concludes the proof of Lemma 17.

Pseudorandomness.

To prove pseudorandomness, we proceed over a sequence of hybrids, see Figure 34.

return A(crs, u) G 0 corresponds to Exp crs-pre A,0 (λ). G 1 is identical to G 0 except for the following difference. G 1 produces crs directly via Setup S (1 λ ) and produces u via encoding crs with E (crs , crs ). G 0 , on the other hand, samples u uniformly at random from {0, 1} n (λ) and produces crs via decoding u as D (crs , u ). Due to Lemma 17, |Pr[out

Let B be an adversary that operates as follows. During the protocol, B records the transcripts {m i } i∈[poly (λ)] and outputs them. At the end of the protocol, B corrupts P 1 obtaining the input x 1 , output z and random tape r 1 . B directly outputs (z, r 1 ). Afterwards, B (post-execution) corrupts P 2 and obtains the input x 2 and the random tape r 2 and outputs r 2 .

Since we assume Π securely realizes F (in particular in the presence of B), there exists a (stateful) simulator Sim := (Sim 1 , Sim 2 , Sim 3 ) producing outputs that are computationally indistinguishable from the outputs B produces. Sim 1 simulates the execution before a corruption occurs. On input of crs and a random tape r S , Sim 1 produces {m i } i∈[poly (λ)] . On corruption of P 1 (in the post-execution corruption stage), Sim 2 obtains x 1 , z and outputs a string r 1 corresponding to the randomness that P 1 used to produce its messages in the protocol (using input x 1 ) and outputs (z, r 1 ). On corruption of P 2 (in the post-execution corruption stage), Sim 3 obtains x 2 and outputs a string r 2 corresponding to the randomness that P 2 used to produce its messages (using input x 2 ).

Lemma 19. The setup algorithm Setup S := Setup F together with the alternative sampler S and the inverse sampler S -1 defined in Figure 36 satisfy adaptive invertibility.

Proof. Since Sim 1 , Sim 2 , Sim 3 are PPT algorithms, S -1 is a PPT algorithm.

Recall that F(x 1 , x 2 ; ρ) := S(x 1 , x 2 ; ρ). Let F (x 1 , x 2 ; ρ ) := S(x 1 , x 2 ; ρ ). Intuitively, we consider an intermediate game, where Z interacts with the simulator Sim and the modified ideal functionality F .

Claim. For all PPT environments Z,

Proof. Let Z be a PPT environment. We construct an adversary B on adaptive closeness. B simulates the entire interaction between the Z, the simulator Sim and the trusted party T , which evaluates the functionality F (or F ). In particular, B takes control of the party T . On input of crs, B simulates the interaction between Z and Sim (given crs) until the computation stage. In the computation stage, the parties P 1 and P 2 send their inputs (which may have been adaptively chosen based on crs) to B. B outputs (

and receives an output z := y b , where y 0 ← S(x 1 , x 2 ) and y 1 ← S(x 1 , x 2 ). B sends z to P 1 and P 2 and continues to simulate the interaction between Z and Sim. This is possible, because the randomness which is actually used by T is not never needs to be known. Finally, Z halts and outputs a bit b . B outputs b .

Let A be an adversary on adaptive invertibility. We construct an environment Z that distinguishes between the real execution of Π with adversary B and the ideal execution with Sim and the ideal functionality F . Initially, Z receives crs and calls A on input of crs to obtain (x 1 , x 2 ) ∈ L. Z uses x 1 as input for P 1 and x 2 as input for P 2 . After the execution of the protocol and the post-execution corruptions, Z receives (r 1 , r 2 ), z (either by the adversary B or the simulator Sim). Finally, Z calls A on input of ((r 1 , r 2 ), z) and outputs A s output.

In the real world, z is the output of the real protocol and r 1 , r 2 is the actual randomness used by the parties. Hence, by definition of S, (r 1 , r 2 ) is the randomness actually used by S to produce the output z. Therefore, Pr[Exp a-crs-inv A,0

In the ideal world, z is produced by the functionality F (hence, by S) and (r 1 , r 2 ) :

KlStS.DS((crs, H), (d1, . . . , d ))

Security. KlStS is secure (on channel C), if for all PPT adversaries A,

Applying a similar strategy as in [vH04; Hop05], we obtain the following theorem.

Theorem 23. Let S be an efficiently samplable message distribution and let H be a family of pairwise independent hash functions. If acPREH rand ≈c is true for S, then (KlStS.Setup S , KlStS.E S , KlStS.D S ) defined above and in Figure 38 is a keyless stegosystem for the message distribution S.

The result basically follows from the Leftover Hash Lemma [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF] and the ability to embed the message distribution into the uniform distribution due to acPREH rand ≈c . Note that since in Exp klsts-sec A,C,b (λ), the adversary does not know the challenge message m * , it is not necessary that each encoding of a message corresponds to exactly one stegotext, see [START_REF] Hopper | On Steganographic Chosen Covertext Security[END_REF].

Covert multi-party computation

The notion of covert secure computation was first introduced in [START_REF] Luis Von Ahn | Covert two-party computation[END_REF] as a collection of desirable properties, such as strong internal covertness, strong fairness and final covertness. Later in [START_REF] Chandran | Covert Multi-Party Computation[END_REF], Chandran et al. proposed a more unified, simulation-based definition. We start by recalling the model of [START_REF] Chandran | Covert Multi-Party Computation[END_REF].

Ideal Model. We consider n parties, each party P i holding an input x i . Let x be the vector (x 1 , • • • , x n ). All the participating parties send their input to the functionality, while the nonparticipating parties are assumed to send ⊥. Then, if any of the parties had input a ⊥, the functionality sets ⊥ to be the output of the protocol. Else, let g : ({0, 1} * ) n → {0, 1} be the function which determines whether on input x, the output is favorable (g(x) = 1) or nonfavorable (g(x) = 0). In the latter case, the functionality sets ⊥ to be the output of the protocol. In the former case, the functionality computes the output f (x). The output is sent to any subset of players, chosen by the adversary. The functionality is represented on Figure 39. For an adversary A, an execution of F CMPC (f, g) with participation data p (indicating which players are taking part to the protocol) and input x (where the input of non-participating parties is ⊥) is defined as the output of the parties together with the output of the adversary. It is denoted IDEAL f,g,A (p, x). Proof. Let A be an adversary distinguishing Exp ind-expl A,0

and Exp ind-expl A,1

above. Construct an adversary A on invertibility. Initially, A calls A, obtains m * , samples (pk, sk) ← Gen(1 λ ) and outputs m := (pk, m * ) to the experiment. In return, A receives (crs, r, y) from the experiment, where y is sampled using Enc(pk, m * ) and r either is the randomness used or itself sampled from Enc -1 (pk, m * , y). A calls A on input of ((crs, pk), y, r). Hence, Pr[Exp ind-expl

Whether cISH rand ≈c (without statistical closeness) implies deniable encryption remains open.

Non-committing encryption

Non-committing encryption is a powerful notion which is known to imply adaptive MPC for well-formed functionalities [START_REF] Canetti | Adaptively Secure Multi-Party Computation[END_REF][START_REF] Canetti | Universally composable two-party and multi-party secure computation[END_REF]. On a high level, if acPREH rand ≈c is true, then any IND-CPA secure PKE scheme is a simulatable PKE scheme [START_REF] Damgård | Improved Non-committing Encryption Schemes Based on a General Complexity Assumption[END_REF] (in the CRS model). The strategy of [START_REF] Choi | Improved Non-committing Encryption with Applications to Adaptively Secure Protocols[END_REF] translates to the CRS model (where inputs may be chosen depending on the CRS) directly.

Definition 36 (Non-committing bit encryption encryption in the global CRS model).

A non-committing bit encryption scheme in the global CRS model is a tuple of PPT algorithms (Setup, Gen, Enc, Dec, Sim), such that (Gen, Enc, Dec) is a PKE scheme and the following distributions are computationally indistinguishable. crs ← Setup(1 λ ), (pk, sk) := Gen(1 λ , crs; r Gen ), c := Enc(crs, pk, b; r Enc ) : (crs, pk, c, r Gen , r Enc )

Following the lines of [START_REF] Choi | Improved Non-committing Encryption with Applications to Adaptively Secure Protocols[END_REF], if acPREH rand ≈c is true and there exists an IND-CPA secure PKE scheme, then there exists a non-committing encryption scheme.

Theorem 25. Let (Gen , Enc , Dec ) be an IND-CPA secure PKE scheme for message space {0, 1} λ . If acPREH rand ≈c holds, then there exists a non-committing encryption scheme.

Proof (sketch). Let OGen be the algorithm which on input of 1 λ calls Gen (1 λ ) and outputs only (pk, ⊥). Further let OEnc be the algorithm which on input of (1 λ , pk) samples m ← {0, 1} λ and outputs c ← Enc (1 λ , pk, m). If acPREH rand ≈c is true, then there exists alternative and inverse sampler for OGen and OEnc, denoted by (OGen, OGen -1 ) and (OEnc, OEnc -1 ), respectively.

Note that the alternative sampler and the inverse sampler need access to the CRS. If the setup algorithm Setup is trivial, this corresponds to the notion of simulatable encryption due to [START_REF] Damgård | Improved Non-committing Encryption Schemes Based on a General Complexity Assumption[END_REF] and yields non-committing encryption directly due to [START_REF] Choi | Improved Non-committing Encryption with Applications to Adaptively Secure Protocols[END_REF]. Figures 44 and45 shows the construction of non-committing encryption in the global CRS model. Note that assuming

Dec(crs, sk, c) Sim(crs)

) and r b Enc := (S b , (u adaptive acPREH rand ≈c is necessary since the inputs to the sampler OEnc are sampled via OGen(crs) during the simulation and, hence, depend on the CRS. The indistinguishability between the real and the simulated distribution follows the same ideas as in [START_REF] Choi | Improved Non-committing Encryption with Applications to Adaptively Secure Protocols[END_REF].

Super-polynomial encoding

Extremely lossy functions due to [START_REF] Zhandry | The Magic of ELFs[END_REF] are functions which can be set up in two computationally indistinguishable modes -an injective mode and a extremely lossy mode, where the range of the function is merely polynomial. A slight relaxation of this notion is what we call very lossy functions (VLFs). The difference to ELFs is that we require indistinguishability between functions with exponential range and super-polynomial range. The existence of these functions implies a relaxation of cPREH rand ≈c . A VLF is called strongly efficiently enumerable, if there exists a (potentially randomized) algorithm running in polynomial time in log M and r which given f ← VLF.Gen(M, r, lossy) and r outputs a set S ⊆ [N ] such that with overwhelming probability (over the choice of f and the randomness of the algorithm), S = f ([M ]). If VLF is strongly regular, then it also is strongly efficiently enumerable, [START_REF] Zhandry | The Magic of ELFs[END_REF]. [START_REF] Zhandry | The Magic of ELFs[END_REF] shows that strongly regular ELFs are implied by the exponential decisional Diffie-Hellman (DDH) assumption.

Definition 37 (Very lossy function

We note that in contrast to ELFs, an adversary learning r does not harm security.

Assuming the sub-exponential hardness of the decisional Diffie-Hellman (DDH) problem, the bounded adversary extremely lossy function instantiation from [START_REF] Zhandry | The Magic of ELFs[END_REF] is a strongly regular very lossy function according to Definitions 37 and 38.

Theorem 26. If strongly regular very lossy functions exist, then acPREH rand

≈c with super-polynomial encoding is true.

Proof. Let S be a PPT sampler with input space L. For m ∈ L, let r (|m|) denote the polynomial which upper bounds the number of random bits S(m) takes, i.e. the random tape of S is uniform over {0, 1} r = [2 r ]. Further, let ξ be a super-polynomial function. The setup algorithm, the encoding and decoding algorithms are defined in Figure 46. We prove the equivalent properties closeness and invertibility. Invertibility. The encoding algorithm produces perfectly distributed inverse sampled random tapes. Hence, adaptive invertibility follows. Closeness. We start from the game Exp a-crs-close A and switch the VLF to injective mode f ← VLF.Gen(2 r , ξ, inj). This is computationally indistinguishable for the adversary. The inverse sampler will not work anymore, but since the adversary is polynomially bounded, he can not call the inverse sampler anyway. Strong regularity implies that for f ← VLF.Gen(2 r , ξ, inj) the distribution {x ← [2 r ] : f (x)} is statistically close to uniform distribution over f ([2 r ]). Hence, S(m; f (r)) and S(m; r) for uniform r from [2 r ] are statistically close.

Unfortunately, acPREH rand ≈c with super-polynomial encoding algorithm (or, equivalently acISH rand ≈c with super-polynomial inverse sampler) does not suffice to imply adaptive MPC even if the simulator is allowed to run in super-polynomial time, [START_REF] Pass | Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition[END_REF]. This is because plugging cPREH rand ≈c with super-polynomial encoding algorithm into the proof of Theorem 19, the game hop from G 2 to G 3 can not be made, since the simulation of these games requires super-