Theory of Cryptography

Table of Contents

1. Frontmatter

2. Foundations

   1. Frontmatter

   2. Offline-Online Indifferentiability of Cryptographic Systems

      Ashrujit Ghoshal, Ilan Komargodski, Gil Segev

      Abstract

      The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the security of a construction is captured by a “single-stage” security game, it may generally provide no meaningful guarantees when the security is captured by a “multi-stage” one. In particular, the indifferentiability framework does not capture offline-online games, where the adversary can perform an extensive offline computation to later speed up the online phase. Such security games are extremely common, both in practice and in theory. Over the past decade, there has been numerous attempts to meaningfully extend the indifferentiability framework to offline-online games, however, they all ultimately met with little success.

      In this work, our contribution is threefold. First, we propose an extension of the classical indifferentiability framework, we refer to as offline-online-indifferentiability, that applies in the context of attackers with an expensive offline phase (à la Ghoshal and Tessaro, CRYPTO ’23). Second, we show that our notion lends itself to a natural and meaningful composition theorem for offline-online security games. Lastly, as our main technical contribution, we analyze the offline-online-indifferentiability of two classical variants of the Merkle-Damgård hashing mechanism, one where the key is fed only to the first block in the chain and the other where the key is fed to each block in the chain. For both constructions, we prove a tight bound on their offline-online-indifferentiability (i.e., an upper bound and an attack that matches it). Notably, our bound for the second variant shows that the construction satisfies optimal offline-online-indifferentiability.

   3. Seedless Condensers for Efficiently Samplable Sources

      Cody Freitag, Jad Silbak, Daniel Wichs

      Abstract

      Is it possible to efficiently convert any arbitrary source with sufficiently high (min-)entropy into nearly uniformly random bits? Information-theoretically, this is achievable using seeded extractors, provided the source is independent of the seed. However, in the absence of any such independence guarantee, no solution is possible for general computationally unbounded sources. Even for efficiently samplable sources, we cannot extract randomness that is statistically close to uniform, but can at best condense the randomness into an output that is only missing logarithmically many bits of entropy compared to the uniform distribution. Dodis, Ristenpart and Vadhan (TCC ’12) constructed such seeded condensers for efficiently samplable sources that can depend arbitrarily on the seed assuming near-optimal security of collision-resistant hash functions. In this work, we investigate whether such condensers can be made seedless. We present several new results:

      • We construct seedless condensers for all efficiently samplable sources assuming near-optimal security of keyless multi-collision resistant hash functions. We justify this assumption by showing it holds in the auxiliary-input random oracle model.
      • We show that such seedless condensers cannot be proven secure via a black-box reduction from any standard game-based assumption, even if we assume optimal exact security. In fact, we give a general black-box separation that applies to a broad class of seedless primitives, with seedless condensers as a special case.
      • We consider the class of efficiently samplable distributed sources where two parties jointly sample randomness \(x=(x_0,x_1)\), with one party honestly choosing \(x_b\) uniformly at random while the other party adversarially chooses \(x_{1-b}\) depending on \(x_b\). We show how to construct seedless condensers for such sources assuming near-optimal security of game-based assumptions – either: (1) adaptive one-way functions, or (2) a certain from of (single-input) correlation-intractable hash functions that can be instantiated from key-dependent-message (KDM) secure encryption.

   4. Incompressible Encryption with Everlasting Security

      Shany Ben-David, Eylon Yogev

      Abstract

      Recently, the concept of incompressible encryption has emerged as a powerful enhancement to key-leakage resilience. In an incompressible encryption scheme, an adversary who intercepts ciphertexts is forced to dedicate a significant amount of memory to store them in full if they wish to extract any information about the plaintext later when the secret key becomes available. Given two messages, the security game involves two adversaries: the first adversary receives an encryption of one of the messages and produces a compressed state. Then, the second adversary, given both the secret key and the compressed state, attempts to determine which message was encrypted.

      Several positive results exist in incompressible cryptography. On the one hand, there are constructions based on minimal assumptions but with a poor rate (i.e., rate tends to 0). On the other hand, there are rate-1 constructions that achieve optimal efficiency but rely on strong cryptographic assumptions, such as obfuscation.

      A stronger security notion, known as everlasting security, has been proposed for incompressible encryption. In this formulation, the second adversary, who receives the compressed state and the secret key, is allowed to be computationally unbounded. While this notion is conceptually appealing, no constructions of everlasting incompressible encryption are currently known, regardless of the underlying assumption or even in idealized models.

      In this work, we give the first construction of everlasting incompressible encryption. In fact, we show that everlasting incompressible encryption is inherent in any sufficiently secure public-key encryption scheme. Specifically, we prove that any public-key encryption scheme with subexponential security (when instantiated with an appropriate security parameter) already satisfies the definition of everlasting incompressible encryption with subexponential security. Furthermore, our scheme achieves rate-1, improving upon existing results even for the weaker notion of standard incompressible encryption.

      Our results raise concerns about whether the current definition of incompressible encryption adequately captures the expected efficiency properties of such schemes, indicating that refinements may be needed. As one concrete step in this direction, we propose a storage-rate definition for ciphertexts, and show how to construct schemes with constant storage-rate.

   5. Relationships Among FuncCPA and Its Related Notions

      Takumi Shinozaki, Tatsuaki Okamoto, Keisuke Tanaka, Masayuki Tezuka, Yusuke Yoshida

      Abstract

      Akavia, Gentry, Halevi, and Vald (TCC’22, JoC’25) introduced the security notion of function-chosen-plaintext-attack (\({\textsf{FuncCPA}}\) security) for public-key encryption schemes. \({\textsf{FuncCPA}}\) is defined by adding a functional re-encryption oracle to the \(\textsf {IND-CPA} \) game. This notion is crucial for secure computation applications where the server is allowed to delegate a part of the computation to the client. Dodis, Halevi, and Wichs (TCC’23) introduced a stronger variant called \({\textsf{FuncCPA}^+}\), and conjectured that \({\textsf{FuncCPA}^+}\) is strictly stronger than \({\textsf{FuncCPA}}\), while they showed \({\textsf{FuncCPA}^+}\) implies \({\textsf{FuncCPA}}\). Seeking insights into this conjecture, they showed that \({\textsf{ReEncCPA}^+}\) is strictly stronger than \({\textsf{ReEncCPA}}\), where \({\textsf{ReEncCPA}}\) and \({\textsf{ReEncCPA}^+}\) are restricted versions of \({\textsf{FuncCPA}}\) and \({\textsf{FuncCPA}^+}\) respectively.

      In this paper, contrary to their conjecture, we show that \({\textsf{FuncCPA}^+}\) is equivalent to \({\textsf{FuncCPA}}\). We also introduce new variants of \({\textsf{FuncCPA}}\); \({\textsf{Weak}{\textsf{FuncCPA}}}\), \(\textsf {OW-}{\textsf{FuncCPA}} \), and \(\textsf {OW-}{\textsf{Weak}{\textsf{FuncCPA}}} \). \({\textsf{Weak}{\textsf{FuncCPA}}}\) is a restricted variant of \({\textsf{FuncCPA}}\) in that an oracle query is prohibited after the challenge query (like \(\textsf {IND-CCA1} \)). \(\textsf {OW-}{\textsf{FuncCPA}} \) and \(\textsf {OW-}{\textsf{Weak}{\textsf{FuncCPA}}} \) are the one-way (\(\textsf{OW}\)) versions of \({\textsf{FuncCPA}}\) and \({\textsf{Weak}{\textsf{FuncCPA}}}\), respectively. This paper shows that \({\textsf{Weak}{\textsf{FuncCPA}}}\) and \(\textsf {OW-}{\textsf{FuncCPA}} \) are equivalent to \({\textsf{FuncCPA}}\), that is, all of \({\textsf{FuncCPA}}\), \({\textsf{FuncCPA}^+}\), \({\textsf{Weak}{\textsf{FuncCPA}}}\), and \(\textsf {OW-}{\textsf{FuncCPA}} \) are equivalent. Considering the separation of \(\textsf {IND-CCA1} \) and \(\textsf {IND-CCA2} \), and that of \(\textsf{OW}\text {-}\textsf{CPA}\) and \(\textsf {IND-CPA} \), these results are surprising. To show the equivalence, we develop novel techniques to utilize functional re-encryption oracles. We then provide the separation results that \(\textsf {OW-}{\textsf{Weak}{\textsf{FuncCPA}}} \) does not imply \({\textsf{FuncCPA}}\) and \({\textsf{ReEncCPA}^+}\) does not imply \({\textsf{FuncCPA}}\).

   6. Lower Bounds on Inner-Product Functional Encryption from All-or-Nothing Encryption Primitives

      Jinye He, Shiyu Li, Wei-Kai Lin

      Abstract

      A functional encryption (FE) is a versatile encryption, where the functional key \(\textsf{sk}_\textbf{v}\) decrypts a ciphertext to the function \(\textbf{v}(\textbf{m})\) evaluated on the plaintext \(\textbf{m}\). The security requires that even when an adversary colludes multiple functional keys, it learns only the evaluations but nothing more about the plaintext. This work considers the adversary obtaining an unbounded number of colluded keys, a natural setting for many FE applications. We aim to understand which cryptographic primitives are sufficient to construct an unbounded-collusion FE.

      This work proves negative results: we separate unbounded-collusion FEs from many encryption primitives that are “all-or-nothing”. Introduced by Garg, Mahmoody and Mohammed (CRYPTO ’17), an all-or-nothing encryption scheme allows an adversary to learn either the whole plaintext if the authorized secret key is given; otherwise, the adversary learns nothing. Hence, we rule out such FE construction from fully homomorphic encryption (FHE), attribute-based encryption (ABE), and predicate encryptions (PE). Our impossibility holds for private-key and selectively secure FEs for an minimal function class, inner products, making the impossibility stronger. Our separation is in the “monolithic model”, similar to the black-box model, but the primitive is allowed to evaluate a circuit that queries the primitive itself as an oracle.

      Our result extends the beautiful work of Hajiabadi et al. (TCC ’24), which separated inner-product functional encryption (IPFE) from any primitives that exist in the random oracle model. Our result is perhaps surprising as IPFE was proposed by Abdalla et al. (PKC ’15) to be easier to construct, and indeed there are several IPFEs based on standard algebraic assumptions, such as Decisional Diffie-Hellman or Learning-with-Errors. Moreover, bounded-collusion FEs for all circuits are constructed in a black-box way from minimal assumptions, i.e., public-key FE from public-key encryption, and secret-key FE from one-way functions, by Ananth and Vaikuntanathan (TCC ’19).

   7. A Meta-complexity Theoretic Approach to Indistinguishability Obfuscation and Witness Pseudo-Canonicalization

      Noam Mazor, Rafael Pass, Tomer Solomon

      Abstract

      Indistinguishability Obfuscation (\(i\mathcal {O}\)) is a central hub of modern cryptography, with far reaching applications. Over the last decade, a handful of constructions ranging from heuristic ones to, more recently following the breakthrough of Jain, Lin and Sahai [STOC’21], provably secure constructions based on well-formed assumptions. The provably secure constructions, however, rely on various different assumptions, some of which can be broken in quantum polynomial time.

      In this work we propose meta-complexity-theoretic characterizations of \(i\mathcal {O}\). First, we consider a notion of witness pseudo-canonicalization (WPC)—which roughly speaking, requires, given a witness w for some \(\textrm{NP}\) statement x, efficiently outputting a pseudo-canonical witness \(w'\) for the same statement x (i.e., one that is computationally independent of w). We remark that WPC for the Minimum Circuit Size problem (MCSP) is essentially equivalent to the notion of (exponentially-efficient) \(i\mathcal {O}\), which in turn can be bootstrapped into \(i\mathcal {O}\) (assuming LWE and subexponential security).

      We next provide a further study of the notion of WPC, noting that this notion captures not only \(i\mathcal {O}\) but also non-interactive witness indistinguishabilty (NIWI); at the same time, (assuming OWFs) it is impossible to achieve it for any witness relation that is \(\textrm{NP}\)-complete w.r.t. (honest) Levin reductions.

      Finally, we provide a purely meta-complexity (worst-case) characterization of WPC w.r.t. some witness relation \(\mathcal{R}\) through a problem referred to as the Decisional Computational Shallowness (\(\textbf{DCS}\)) problem. Intuitively, the \(\textbf{DCS}\) problem with w.r.t. witness-relation \(\mathcal{R}\) and an instance \(\varphi \), requires deciding, given \(x, y, z \in \mathcal{R}(\varphi )\), which of \(\textbf{CD}^t(z| x)\) and \(\textbf{CD}^t(z| y)\) is smaller, where \(\textbf{CD}^t(z| x)=\textrm{K}^t(z| x)-\textrm{K}(z| x)\) is the (Kolmogorov) Computational Depth and \(t(\left| z\right| )\) is some polynomial. We show that DCS w.r.t. R is essentially equivalent to a notion of “weak" WPC (i.e., with weak indistinguishability) w.r.t. R, which leads our new complexity-theoretic characterization of (weak) \(i\mathcal {O}\).

3. Obfuscation and Functional Encryption

   1. Frontmatter

   2. Obfuscating Pseudorandom Functions is Post-quantum Complete

      Pedro Branco, Abhishek Jain, Akshayaram Srinivasan

      Abstract

      The last decade has seen remarkable success in designing and uncovering new applications of indistinguishability obfuscation (i\(\mathcal {O}\)). The main pressing question in this area is whether post-quantum i\(\mathcal {O}\) exists. All current lattice-based candidates rely on new, non-standard assumptions, many of which are known to be broken.

      To make systematic progress on this front, we investigate the following question: can general-purpose i\(\mathcal {O}\) be reduced, assuming only learning with errors (LWE), to obfuscating a smaller class of functions? The specific class of functions we consider are pseudorandom functions (PRFs), which constitute a natural functionality of independent interest. We show the following results:

      • We construct exponentially-efficient i\(\mathcal {O}\) (xi\(\mathcal {O}\)) for general circuits based on LWE in the pseudorandom oracle model – a variant of the Random Oracle model (Jain et al., CRYPTO’23). Our construction requires the pseudorandom oracle model heuristic to hold for a specific pseudorandom function and we prove its security against classical adversaries.
      • We construct (post-quantum) i\(\mathcal {O}\) for general circuits in the standard model based on (post-quantum) sub-exponentially secure LWE and (post-quantum) sub-exponentially secure average-case i\(\mathcal {O}\) – a natural notion of i\(\mathcal {O}\) for pseudorandom functions that we define.

      To obtain these results, we generalize the “encrypt-evaluate-decrypt” paradigm used in prior works by replacing the use of fully homomorphic encryption with succinct secure two-party computation where parties obtain additive output shares (Boyle et al., EUROCRYPT’25 and Abram et al., STOC’25).

   3. Pseudorandom FE, iO and Applications

      Shweta Agrawal, Simran Kumari, Shota Yamada

      Abstract

      We propose the abstractions of Functional Encryption (FE) and Indistinguishability Obfuscation (iO) for pseudorandom functionalities which are strictly weaker than their general counterparts. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from uniform for every input seen by the adversary. We then leverage weak indistinguishability style security of these tools to obtain the following applications:

      1.

      Attribute Based Encryption for Unbounded Depth Circuits. Assuming \(\text {IND}\)-secure FE for pseudorandom functionalities and LWE, we construct Attribute Based Encryption (ABE) for circuits of unbounded depth. Previously, such ABE required the circular Evasive LWE assumption (Hseih, Lin and Luo, Focs 2023) which has recently been subject to zeroizing attacks.

       

      2.

      Attribute Based Encryption for Turing Machines. Assuming \(\text {IND}\)-secure FE for pseudorandom functionalities and circular small-secret LWE, we construct Attribute Based Encryption (ABE) for Turing machines. Previously, such ABE required either private coin Evasive LWE (Agrawal, Kumari and Yamada, Crypto 2024) or circular Evasive LWE (Cini and Wee, Eurocrypt 2025), both of which admit attacks in the general case.

       

      3.

      Multi Input Predicate Encryption for Polynomial Arity. Assuming \(\text {IND}\)-secure multi-input FE for pseudorandom functionalities, we construct Multi Input Predicate Encryption (\(\textsf{MIPE}\)) for \(\textsf{P}\) for polynomial arity. Previously, \(\textsf{MIPE}\) for \(\textsf{P}\) was known only for constant arity, using private coin evasive LWE (Agrawal, Rossi, Yadav and Yamada, Crypto 2023).

       

      4.

      Instantiating the Random Oracle. We use our \(\text {IND}\)-secure iO for pseudorandom functionalities to instantiate the random oracle in several applications that previously used iO (Hohenberger, Sahai and Waters, Eurocrypt 2014) such as full-domain hash signature based on trapdoor permutations and more.

       

      We provide heuristic constructions of FE and MIFE for pseudorandom functionalities from private coin evasive LWE and plain LWE, where private coin evasive LWE is suitably parametrized to avoid all know attacks for the functionalities we consider in this work. This implies iO for pseudorandom functionalities from the same assumptions.

   4. Zeroizing Attacks Against Evasive and Circular Evasive LWE

      Shweta Agrawal, Anuja Modi, Anshu Yadav, Shota Yamada

      Abstract

      We develop new attacks against the Evasive LWE family of assumptions, in both the public and private-coin regime. To the best of our knowledge, ours are the first attacks against Evasive LWE in the public-coin regime, for any instantiation from the family. Our attacks are summarized below.

      • Public-Coin Attacks.

        1.

        The recent work by Hseih, Lin and Luo [17] constructed the first Attribute Based Encryption (ABE) for unbounded depth circuits by relying on the “circular” evasive LWE assumption. This assumption has been popularly considered as a safe, public-coin instance of Evasive LWE in contrast to its “private-coin” cousins (for instance, see [10, 11]).

        We provide the first attack against this assumption, challenging the widely held belief that this is a public-coin assumption.

         

        2.

        We demonstrate a counter-example against vanilla public-coin evasive LWE by Wee [26] in an unnatural parameter regime. Our attack crucially relies on the error in the pre-condition being larger than the error in the post-condition, necessitating a refinement of the assumption.

         
      • Private-Coin Attacks.

        1.

        The recent work by Agrawal, Kumari and Yamada [2] constructed the first functional encryption scheme for pseudorandom functionalities (\(\textsf{PRFE}\)) and extended this to obfuscation for pseudorandom functionalities (\(\textsf{PRIO}\)) [4] by relying on private-coin evasive LWE. We provide a new attack against the assumption stated in the first posting of their work (subsequently refined to avoid these attacks).

         

        2.

        The recent work by Branco et al. [8] (concurrently to [4]) provides a construction of obfuscation for pseudorandom functionalities by relying on private-coin evasive LWE. We provide a new attack against their stated assumption.

         

        3.

        Branco et al. [8] showed that there exist contrived, “self-referential” classes of pseudorandom functionalities for which pseudorandom obfuscation cannot exist. We extend their techniques to develop an analogous result for pseudorandom functional encryption.

         

      While Evasive LWE was developed to specifically avoid “zeroizing attacks”, our work shows that in certain settings, such attacks can still apply.

   5. (Multi-input) for Randomized Functionalities, Revisited

      Pratish Datta, Jiaxin Guan, Alexis Korb, Amit Sahai

      Abstract

      Randomized functional encryption (\(\textsf{rFE}\)) generalizes functional encryption (\(\textsf{FE}\)) by incorporating randomized functionalities. Randomized multi-input functional encryption (\(\textsf{rMIFE}\)) extends \(\textsf{rFE}\) to accommodate multi-input randomized functionalities.

      In this paper, we reassess the framework of \(\textsf{rFE}/\textsf{rMIFE}\) enhancing our understanding of this primitive and laying the groundwork for more secure and flexible constructions in this field. Specifically, we make three key contributions:

      • Stronger \(\textsf{IND}\) definition. We show the prevailing indistinguishability-based security definition protects only against malicious decryptors and leaves systems vulnerable to malicious encryptors – a critical requirement for \(\textsf{rFE}/\textsf{rMIFE}\) since their inception. We then propose a refined \(\textsf{IND}\) notion that simultaneously handles both threats.
      • Separating counterexample. Illustrating this definitional gap, we meticulously craft an \(\textsf{rFE}\) scheme – using standard tools (\(\textsf{FE}\), \(\textsf{PRF}\), \(\textsf{PKE}\), simulation-sound \(\textsf{NIZK}\)) – that satisfies the old definition yet is blatantly insecure in practice (and where this insecurity would be precluded by our enhanced definition).
      • Adaptive, unbounded-message \(\textsf{rMIFE}\) . The sole, viable prior \(\textsf{rMIFE}\) construction by Goldwasser et al. [EUROCRYPT 2014] permits only a fixed message bound per encryption slot and offers merely selective security. Leveraging sub-exponentially secure indistinguishability obfuscation and techniques of Goyal et al. [ASIACRYPT 2016] built for deterministic \(\textsf{MIFE}\), we give the first \(\textsf{rMIFE}\) scheme that supports an unbounded number of messages per slot and attains full adaptive security.

   6. Adaptively Secure Streaming Functional Encryption

      Pratish Datta, Jiaxin Guan, Alexis Korb, Amit Sahai

      Abstract

      This paper presents the first adaptively secure streaming functional encryption (sFE) scheme for \(\mathsf {P/Poly}\). sFE extends traditional FE to vast and/or dynamically evolving data sets, enabling incremental encryption of streaming inputs and iterative partial decryption over encrypted prefixes. The proposed sFE scheme is built from indistinguishability obfuscation for \(\mathsf {P/Poly}\) and injective PRGs. We achieve this result via two core technical contributions which may be of independent interest. First, we introduce a novel “gluing” mechanism to achieve adaptive security by intertwining two schemes, each possessing one aspect of adaptive security. Second, we enhance the powerful Koppula-Lewko-Waters [STOC 2015] framework with a “sliding window” technique, enabling authenticated iterative computation with fresh inputs at each iteration.

      Prior work by Guan, Korb, and Sahai [CRYPTO 2023] constructed sFE but only under a (semi-adaptive) function-selective security model, requiring all functional keys to be queried before observing any ciphertext. This severe limitation precludes practical scenarios and leaves adaptive security as a crucial open challenge – explicitly highlighted by their work—which we address in this paper.

4. Secret Sharing

   1. Frontmatter

   2. Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes

      Bar Alon, Amos Beimel, Or Lasri

      Abstract

      We consider 3 related cryptographic primitives, private information retrieval (PIR) protocols, conditional disclosure of secrets (CDS) protocols, and secret-sharing schemes; these primitives have many applications in cryptography. We study these primitives requiring information-theoretic security. The complexity of the three primitives has been dramatically improved in the last few years and they are closely related, i.e., the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016) was transformed to construct the CDS protocols of Liu, Vaikuntanathan, and Wee (CRYPTO 2017, Eurocrypt 2018) and these CDS protocols are the main ingredient in the construction of the best-known secret-sharing schemes. To date, the message size required in PIR and CDS protocols and the share size required in secret-sharing schemes are not understood and there are big gaps between their upper bounds and lower bounds. The goal of this paper is to try to better understand the upper bounds by simplifying current constructions and supplying tools for improving their complexity. We obtain the following results:

      • We simplify, abstract, and generalize the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016), the recent multi-server PIR protocol of Ghasemi, Kopparty, and Sudan (STOC 2025), and the 2-server and multi-server CDS protocols of Liu et al. (CRYPTO 2017, Eurocrypt 2018) and Beimel, Farràs, and Lasri (TCC 2023). In particular, we present one PIR protocol generalizing both the 2-server and multi-server PIR protocols using general share conversions. For \(k\ge 3\) servers, our main contribution is a simpler proof the correctness of the protocol, avoiding the partial derivatives and interpolation polynomials used by Ghasemi et al.
      • In addition to simplifying previous protocols, our 2-server protocols can use a relaxed variant of matching vectors over any m that is the product of two distinct primes. Our constructions do not improve the communication complexity of PIR and CDS protocols; however, construction of better relaxed matching vectors over any m that is the product of two distinct primes will improve the communication complexity of 2-server PIR and 2-server CDS protocols.
      • In many applications of secret-sharing schemes it is important that the scheme is linear, e.g., by using the fact that parties can locally add shares of two secrets and obtain shares of the sum of the secrets. In an independent result, we provide a construction of linear secret-sharing schemes for n-party access structures with improved share size of \(2^{0.7563n}\). Previously, the best share size for linear secret-sharing schemes was \(2^{0.7576n}\) and it is known that for most n-party access structures the shares’ size is at least \(2^{0.5n}\). This result is achieved by a reduction to unbalanced CDS protocols (compared to balanced CDS protocols in previous constructions).

   3. Deniable Secret Sharing

      Ran Canetti, Ivan Damgård, Sebastian Kolby, Divya Ravi, Sophia Yakoubov

      Abstract

      We introduce deniable secret sharing (DSS), which, analogously to deniable encryption, enables shareholders to produce fake shares that are consistent with a target “fake message”, regardless of the original secret. In contrast to deniable encryption, in a DSS scheme an adversary sees multiple shares, some of which might be real, and some fake. This makes DSS a more difficult task, especially in situations where the fake shares need to be generated by individual shareholders, with limited or no coordination with other shareholders.

      We define several desirable properties for DSS, and show both positive and negative results for each. The strongest property is fake hiding, which is a natural analogy of deniability for encryption: given a complete set of shares, an adversary cannot determine whether any shares are fake. We show a construction based on Shamir secret sharing that achieves fake hiding as long as (1) the fakers are qualified (number \(t\) or more), and (2) the set of real shares which the adversary sees is unqualified. Next we show a construction based on indistinguishability obfuscation that relaxes condition (1) and achieves fake hiding even when the fakers are unqualified (as long as they comprise more than half of the shareholders).

      We also extend the first construction to provide the weaker property of faker anonymity for all thresholds. (Faker anonymity requires that given some real shares and some fake shares, an adversary should not be able to tell which are fake, even if it can tell that some fake shares are present.) All of these constructions require the fakers to coordinate in order to produce fake shares.

      On the negative side, we first show that fake hiding is unachievable when the fakers are a minority, even if they coordinate. Further, if the fakers do not coordinate, then even faker anonymity is unachievable as soon as \(t< n\) (namely the reconstruction threshold is smaller than the number of parties), if faking is not unanimous. (If faking is unanimous, we show a construction based on indistinguishability obfuscation).

   4. Polynomial Secret Sharing Schemes and Algebraic Matroids

      Amos Beimel, Oriol Farràs, Adriana Moya

      Abstract

      Polynomial secret sharing schemes generalize the linear ones by adding more expressivity and giving room for efficiency improvements. In these schemes, the secret is an element of a finite field, and the shares are obtained by evaluating polynomials on the secret and some random field elements, i.e., for every party there is a set of polynomials that computes the share of the party. Notably, for general access structures, the best known polynomial schemes have better share size than the best known linear ones. This work investigates the properties of the polynomials and the fields that allow these efficiency gains and aims to characterize the access structures that benefit from them.

      We focus first on ideal schemes, which are optimal in the sense that the size of each share is the size of the secret. We prove that, under some restrictions, if the degrees of the sharing polynomials are not too big compared to the size of the field, then its access structure is a port of an algebraic matroid. This result establishes a new connection between ideal schemes and matroids, extending the known connection between ideal linear schemes and linearly representable matroids.

      For general polynomial schemes, we extend these results and analyze their privacy and correctness. Additionally, we show that given a set of polynomials over a field of large characteristic, one can construct linear schemes that realize the access structure determined by these polynomials; as a consequence, polynomial secret sharing schemes over these fields are not stronger than linear schemes.

      While there exist ports of algebraic matroids that do not admit ideal schemes, we demonstrate that they always admit schemes with statistical security and information ratio tending to one. This is achieved by considering schemes where the sharings are points in algebraic varieties.

   5. Pseudorandom Correlation Functions for Garbled Circuits

      Geoffroy Couteau, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber

      Abstract

      In this paper, we define the notion of pseudorandom correlation generators (PCGs) and functions (PCFs) for garbled circuit correlations. With a Garbling PCG or PCF, two parties can non-interactively generate a virtually unbounded number of secret-shared garbled circuits and corresponding secret-shared garbled inputs. With the shares of the garbled circuit and garbled input, anyone can recover the garbled circuit and evaluate it to obtain the result of the computation in the clear.

      In the process of constructing Garbling PCFs, we introduce a new primitive that we call a Topology-Adaptive PCF (TAPCF), which we construct from two different variants of the learning parity with noise (LPN) assumption. Informally, a TAPCF is a PCF that additionally allows the target correlation to be specified on-demand (i.e., at evaluation time). Using our TAPCF construction as a building block, we construct a Garbling PCF that allows the parties to specify the circuit they wish to garble on-the-fly. Under realistic parameter settings, we estimate that, with our construction, two parties can generate one garbled circuit per second, for garbled circuits with 10,000 AND gates.

      Garbling PCFs have several applications: We provide constructions for (1) an efficient homomorphic secret-sharing scheme for specific high-depth circuits, (2) a zero-knowledge proof system over secret shares that supports checking unstructured languages, and (3) a semi-honest reusable two-round, two-party computation protocol supporting non-interactive public outputs.

   6. Multiparty Homomorphic Secret Sharing and More from LPN and MQ

      Geoffroy Couteau, Naman Kumar, Xiaxi Ye

      Abstract

      We give the first constructions of multiparty pseudorandom correlation generators, distributed point functions, and (negligible-error) homomorphic secret sharing for constant-degree polynomials for any number of parties without using LWE or iO. Our constructions are proven secure under the combination of LPN with dimension n, 2n samples, and noise rate \(n^{\varepsilon -1}\) for a small constant \(\varepsilon \), and MQ with n variables and \(n^{1+\delta }\) equations.

      As applications of our results, we obtain from the same assumptions secure multiparty computation protocols with sublinear communication and silent preprocessing, as well as private information retrieval for M servers and size-\(\lambda ^d\) databases with optimal download rate and client-to-server communication \(M^d\cdot \lambda ^3\).

5. Backmatter