nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Public-Key Cryptography – PKC 2016

19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II

herausgegeben von: Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The two-volume set LNCS 9614 and 9615 constitutes the refereed proceedings of the 19th IACR International Conference on the Practice and Theory in Public-Key Cryptography, PKC 2016, held in Taipei, Taiwan, in March 2016.
The 34 revised papers presented were carefully reviewed and selected from 143 submissions. They are organized in topical sections named: CCA security, functional encryption, identity-based encryption, signatures, cryptanalysis, leakage-resilient and circularly secure encryption, protocols, and primitives.

Inhaltsverzeichnis

Frontmatter

Cryptanalysis

Frontmatter

Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

Abstract

The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks.

In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards.

Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gröbner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further.

Christophe Petit, Michiel Kosters, Ange Messeng

Degenerate Curve Attacks

Extending Invalid Curve Attacks to Edwards Curves and Other Models

Abstract

Invalid curve attacks are a well-known class of attacks against implementations of elliptic curve cryptosystems, in which an adversary tricks the cryptographic device into carrying out scalar multiplication not on the expected secure curve, but on some other, weaker elliptic curve of his choosing. In their original form, however, these attacks only affect elliptic curve implementations using addition and doubling formulas that are independent of at least one of the curve parameters. This property is typically satisfied for elliptic curves in Weierstrass form but not for newer models that have gained increasing popularity in recent years, like Edwards and twisted Edwards curves. It has therefore been suggested (e.g. in the original paper on invalid curve attacks) that such alternate models could protect against those attacks.

In this paper, we dispel that belief and present the first attack of this nature against (twisted) Edwards curves, Jacobi quartics, Jacobi intersections and more. Our attack differs from invalid curve attacks proper in that the cryptographic device is tricked into carrying out a computation not on another elliptic curve, but on a group isomorphic to the multiplicative group of the underlying base field. This often makes it easy to recover the secret scalar with a single invalid computation.

We also show how our result can be used constructively, especially on curves over random base fields, as a fault attack countermeasure similar to Shamir’s trick.

Samuel Neves, Mehdi Tibouchi

Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness

Abstract

The Coppersmith methods is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate.

We provide a toolbox based on analytic combinatorics for these studies. It uses the structure of the considered polynomials to derive their generating functions and applies complex analysis techniques to get asymptotics. The toolbox is versatile and can be used for many different applications, including multivariate polynomial systems with arbitrarily many unknowns (of possibly different sizes) and simultaneous modular equations over different moduli. To demonstrate the power of this approach, we apply it to recent cryptanalytic results on number-theoretic pseudorandom generators for which we easily derive precise and formal analysis. We also present new theoretical applications to two problems on RSA key generation and randomness generation used in padding functions for encryption.

Fabrice Benhamouda, Céline Chevalier, Adrian Thillard, Damien Vergnaud

How to Generalize RSA Cryptanalyses

Abstract

Recently, the security of RSA variants with moduli \(N=p^rq\), e.g., the Takagi RSA and the prime power RSA, have been actively studied in several papers. Due to the unusual composite moduli and rather complex key generations, the analyses are more involved than the standard RSA. Furthermore, the method used in some of these works are specialized to the form of composite integers \(N=p^rq\).

In this paper, we generalize the techniques used in the current best attacks on the standard RSA to the RSA variants. We show that the lattices used to attack the standard RSA can be transformed into lattices to attack the variants where the dimensions are larger by a factor of \((r+1)\) of the original lattices. We believe the steps we took present to be more natural than previous researches, and to illustrate this point we obtained the following results:

Simpler proof for small secret exponent attacks on the Takagi RSA proposed by Itoh et al. (CT-RSA 2008). Our proof generalizes the work of Herrmann and May (PKC 2010).
Partial key exposure attacks on the Takagi RSA; generalizations of the works of Ernst et al. (Eurocrypt 2005) and Takayasu and Kunihiro (SAC 2014). Our attacks improve the result of Huang et al. (ACNS 2014).
Small secret exponent attacks on the prime power RSA; generalizations of the work of Boneh and Durfee (Eurocrypt 1999). Our attacks improve the results of Sarkar (DCC 2014, ePrint 2015) and Lu et al. (Asiacrypt 2015).
Partial key exposure attacks on the prime power RSA; generalizations of the works of Ernst et al. and Takayasu and Kunihiro. Our attacks improve the results of Sarkar and Lu et al.

The construction techniques and the strategies we used are conceptually easier to understand than previous works, owing to the fact that we exploit the exact connections with those of the standard RSA.

Atsushi Takayasu, Noboru Kunihiro

Leakage-Resilient and Circularly Secure Encryption

Frontmatter

Leakage-Resilient Public-Key Encryption from Obfuscation

Abstract

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In this work, we consider the bounded leakage and the continual leakage models. In the bounded leakage model (Akavia et al. – TCC 2009), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al. – FOCS 2010, Dodis et al. – FOCS 2010), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period.

In the continual leakage model, a challenging problem has been to provide security against leakage on key updates, that is, leakage that is a function not only of the current secret key but also the randomness used to update it. We propose a new, modular approach to overcome this problem. Namely, we present a compiler that transforms any public-key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al. – CRYPTO 2001, Garg et al. – FOCS 2013). Under the stronger assumption of public-coin differing-inputs obfuscation (Ishai et al. – TCC 2015) the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is obtained by making a new connection between the problems of leakage on key updates and so-called “sender-deniable” encryption (Canetti et al. – CRYPTO 1997). In particular, our compiler adapts and optimizes recent techniques of Sahai and Waters (STOC 2014) that make any encryption scheme sender-deniable. We then show that prior continual leakage resilient schemes can be upgraded to security against consecutive continual leakage without introducing new assumptions.

In the bounded leakage model, we develop an entirely new approach to constructing leakage-resilient encryption from obfuscation directly, based upon the public-key encryption scheme from \({\mathsf {iO}} \) and punctured pseudorandom functions due to Sahai and Waters (STOC 2014). In particular, we achieve (1) leakage-resilient public key encryption tolerating L bits of leakage for any L from \({\mathsf {iO}} \) and one-way functions, (2) leakage-resilient public key encryption with optimal leakage rate of \(1-o(1)\) based on public-coin differing-inputs obfuscation and collision-resistant hash functions.

Dana Dachman-Soled, S. Dov Gordon, Feng-Hao Liu, Adam O’Neill, Hong-Sheng Zhou

On Generic Constructions of Circularly-Secure, Leakage-Resilient Public-Key Encryption Schemes

Abstract

We propose generic constructions of public-key encryption schemes, satisfying key-dependent message (KDM) security for projections and different forms of key-leakage resilience, from CPA-secure private-key encryption schemes with two main abstract properties: (1) a form of (additive) homomorphism with respect to both plaintexts and randomness, and (2) reproducibility, providing a means for reusing encryption randomness across independent secret keys. More precisely, our construction transforms a private-key scheme with the stated properties (and one more mild condition) into a public-key one, providing:

KDM-projection security, an extension of circular security, where the adversary may also ask for encryptions of negated secret key bits;
a (\(1-o(1)\)) resilience rate in the bounded-memory leakage model of Akavia et al. (TCC 2009); and
Auxiliary-input security against subexponentially-hard functions.

We introduce homomorphic weak pseudorandom functions, a homomorphic version of the weak PRFs proposed by Naor and Reingold (FOCS ’95) and use them to realize our base encryption scheme. We in turn obtain homomorphic weak PRFs from homomorphic hash-proof systems (HHPS). We also show how the base encryption scheme may be realized using subgroup indistinguishability (implied, in particular, by quadratic residuosity (QR) and decisional composite residuosity (DCR)). As corollaries of our results, we obtain (1) the first multiple-key projection-secure bit-encryption scheme (as well as the first scheme with a (\(1-o(1)\)) resilience rate) based solely on the HHPS assumption, and (2) a unifying approach explaining the results of Boneh et al. (CRYPTO ’08) and Brakerski and Goldwasser (CRYPTO ’10). Finally, by observing that Applebaum’s KDM amplification method (EUROCRYPT ’11) preserves both types of leakage resilience, we obtain schemes providing at the same time high leakage resilience and KDM security against any fixed polynomial-sized circuit family.

Mohammad Hajiabadi, Bruce M. Kapron, Venkatesh Srinivasan

KDM-Security via Homomorphic Smooth Projective Hashing

Abstract

We present new frameworks for constructing public-key encryption schemes satisfying key-dependent message (KDM) security and that yield efficient, universally composable oblivious transfer (OT) protocols via the dual-mode cryptosystem framework of Peikert, Waters and Vaikuntanathan (Crypto 2008).

Our first framework yields a conceptually simple and unified treatment of the KDM-secure schemes of Boneh et al. (Crypto 2008), Brakerski and Goldwasser (Crypto 2010) and Brakerski, Goldwasser and Kalai (TCC 2011) in the single-key setting.
Using our second framework, we obtain new dual-mode cryptosystems based on the d-linear, quadratic residuocity and decisional composite residuocity assumptions.

Both of these frameworks build on the notion of smooth projective hashing introduced by Cramer and Shoup (Eurocrypt 2002), with the additional requirement that the hash function is homomorphic, as is the case for all known instantiations.

Hoeteck Wee

Protocols

Frontmatter

Asynchronous Secure Multiparty Computation in Constant Time

Abstract

In the setting of secure multiparty computation, a set of mutually distrusting parties wish to securely compute a joint function. It is well known that if the communication model is asynchronous, meaning that messages can be arbitrarily delayed by an unbounded (yet finite) amount of time, secure computation is feasible if and only if at least two-thirds of the parties are honest, as was shown by Ben-Or, Canetti, and Goldreich [STOC’93] and by Ben-Or, Kelmer, and Rabin [PODC’94]. The running-time of all currently known protocols depends on the function to evaluate. In this work we present the first asynchronous MPC protocol that runs in constant time.

Our starting point is the asynchronous MPC protocol of Hirt, Nielsen, and Przydatek [Eurocrypt’05, ICALP’08]. We integrate threshold fully homomorphic encryption in order to reduce the interactions between the parties, thus completely removing the need for the expensive king-slaves approach taken by Hirt et al.. Initially, assuming an honest majority, we construct a constant-time protocol in the asynchronous Byzantine agreement (ABA) hybrid model. Using a concurrent ABA protocol that runs in constant expected time, we obtain a constant expected time asynchronous MPC protocol, secure facing static malicious adversaries, assuming \(t<n/ 3\).

Ran Cohen

Adaptively Secure Multi-Party Computation from LWE (via Equivocal FHE)

Abstract

Adaptively secure Multi-Party Computation (MPC) is an essential and fundamental notion in cryptography. In this work, we construct Universally Composable (UC) MPC protocols that are adaptively secure against all-but-one corruptions based on LWE. Our protocols have a constant number of rounds and communication complexity dependant only on the length of the inputs and outputs (it is independent of the circuit size).

Such protocols were only known assuming an honest majority. Protocols in the dishonest majority setting, such as the work of Ishai et al. (CRYPTO 2008), require communication complexity proportional to the circuit size. In addition, constant-round adaptively secure protocols assuming dishonest majority are known to be impossible in the stand-alone setting with black-box proofs of security in the plain model. Here, we solve the problem in the UC setting using a set-up assumption which was shown necessary in order to achieve dishonest majority.

The problem of constructing adaptively secure constant-round MPC protocols against arbitrary corruptions is considered a notorious hard problem. A recent line of works based on indistinguishability obfuscation construct such protocols with near-optimal number of rounds against arbitrary corruptions. However, based on standard assumptions, adaptively secure protocols secure against even just all-but-one corruptions with near-optimal number of rounds are not known. However, in this work we provide a three-round solution based only on LWE and NIZK secure against all-but-one corruptions.

In addition, Asharov et al. (EUROCRYPT 2012) and more recently Mukherjee and Wichs (ePrint 2015) presented constant-round protocols based on LWE which are secure only in the presence of static adversaries. Assuming NIZK and LWE their static protocols run in two rounds where the latter one is only based on a common random string. Assuming adaptively secure UC NIZK, proposed by Groth et al. (ACM 2012), and LWE as mentioned above our adaptive protocols run in three rounds.

Our protocols are constructed based on a special type of cryptosystem we call equivocal FHE from LWE. We also build adaptively secure UC commitments and UC zero-knowledge proofs (of knowledge) from LWE. Moreover, in the decryption phase using an AMD code mechanism we avoid the use of ZK and achieve communication complexity that does not scale with the decryption circuit.

Ivan Damgård, Antigoni Polychroniadou, Vanishree Rao

Universally Composable Direct Anonymous Attestation

Abstract

Direct Anonymous Attestation (DAA) is one of the most complex cryptographic algorithms that has been deployed in practice. In spite of this and the long body of work on the subject, there is still no fully satisfactory security definition for DAA. This was already acknowledged by Bernard et al. (IJIC’13) who showed that in existing models insecure protocols can be proved secure. Bernard et al. therefore proposed an extensive set of security games which, however, aim only at a simplified setting termed pre-DAA. In pre-DAA, the host platform that runs the TPM is assumed to be trusted. Consequently, their notion does not guarantee any security if the TPM is embedded in a potentially corrupt host which is a significant restriction. In this paper, we give a comprehensive security definition for full DAA in the form of an ideal functionality in the Universal Composability model. Our definition considers the host and TPM to be separate entities that can be in different corruption states. None of the existing DAA schemes satisfy our strong security notion. We therefore propose a realization that is based on a DAA scheme supported by the TPM 2.0 standard and prove it secure in our model.

Jan Camenisch, Manu Drijvers, Anja Lehmann

Universally Composable Authentication and Key-Exchange with Global PKI

Abstract

Message authentication and key exchange are two of the most basic tasks of cryptography and are often basic components in complex and security-sensitive protocols. Thus composable security analysis of these primitives is highly motivated. Still, the state of the art in composable security analysis of these primitives is somewhat unsatisfactory in the prevalent case where solutions are based on public-key infrastructure (PKI). Specifically, existing treatments either (a) make the unrealistic assumption that the PKI is accessible only within the confines of the protocol itself, thus failing to capture real-world PKI-based authentication, or (b) impose often-unnecessary requirements—such as strong on-line non-transferability—on candidate protocols, thus ruling out natural candidates.

We give a modular and universally composable analytical framework for PKI-based message authentication and key exchange protocols. This framework guarantees security even when the PKI is pre-existing and globally available, without being unnecessarily restrictive. Specifically, we model PKI as a global set-up functionality within the Global UC security model [Canetti et al., TCC 2007] and relax the ideal authentication and key exchange functionalities accordingly. We then demonstrate the security of basic signature-based authentication and key exchange protocols. Our modeling makes minimal security assumptions on the PKI in use; in particular, “knowledge of the secret key” is not needed. Furthermore, there is no requirement of uniqueness in this binding: an identity may be represented by multiple strings of public keys.

Ran Canetti, Daniel Shahaf, Margarita Vald

Very-Efficient Simulatable Flipping of Many Coins into a Well

(and a New Universally-Composable Commitment Scheme)

Abstract

This paper presents new cryptographic protocols for a stand-alone simulatable two-party parallel coin-flipping (into a well) and a universally composable commitment scheme, with near optimal asymptotic communication rate, in the static and computational malicious model. The approach, denoted expand-mask-hash, uses in both protocols a pseudo-random generator (PRG) and a collision-resistant hash function (CR-Hash) to combine separate extractable commitments and equivocable commitments (associated with short bit-strings) into a unified extractable-and-equivocable property amplified to a larger target length, amortizing the cost of base commitments. The new stand-alone coin-flipping protocol is based on a simple augmentation of the traditional coin-flipping template. To the knowledge of the author, it is the first proposal shown to simultaneously be two-side-simulatable and have an asymptotic (as the target length increases) communication rate converging to two bits per flipped coin and computation rate per party converging to that of PRG-generating and CR-hashing a bit-string with the target length. The new universally composable commitment scheme has efficiency comparable to very recent state-of-the-art constructions – namely asymptotic communication rate as close to 1 as desired, for each phase (commit and open) – while following a distinct design approach. Notably it does not require explicit use of oblivious transfer and it uses an erasure encoding instead of stronger error correction codes.

Luís T. A. N. Brandão

Robust Secret Sharing Schemes Against Local Adversaries

Abstract

We study robust secret sharing schemes in which between one third and one half of the players are corrupted. In this scenario, robust secret sharing is possible only with a share size larger than the secrets, and allowing a positive probability of reconstructing the wrong secret. We focus on the most challenging case where the number corruptions is just one less than the number of honest players. In the standard model, it is known that at least \(m+k\) bits per share are needed to robustly share a secret of bit-length m with an error probability of \(2^{-k}\); however, to the best of our knowledge, no efficient scheme matches this lower bound: the one that gets closest has share size \(m+\widetilde{O}(n+k)\), where n is the number of players in the scheme.

We show that it is possible to obtain schemes with close to minimal share size in a model of local adversaries, i.e. in which corrupt players cannot communicate between receiving their respective honest shares and submitting corrupted shares to the reconstruction procedure, but may coordinate before the execution of the protocol and can also gather information afterwards. In this limited adversarial model, we prove a lower bound of roughly \(m+k\) bits on the minimal share size, which is (somewhat surprisingly) similar to the lower bound in the standard model, where much stronger adversaries are allowed. We then present efficient scheme that essentially meets our lower bound, and has shorter share size than any known efficient construction in the standard model for the same set of parameters. For our construction, we introduce a novel procedure that compiles an error correcting code into a new randomized one, with the following two properties: a single local portion of a codeword leaks no information on the encoded message itself, and any set of portions of a codeword reconstructs the message with error probability exponentially low in the set size.

Allison Bishop, Valerio Pastro

Primitives

Frontmatter

Reducing Depth in Constrained PRFs: From Bit-Fixing to

Abstract

The candidate construction of multilinear maps by Garg, Gentry, and Halevi (Eurocrypt 2013) has lead to an explosion of new cryptographic constructions ranging from attribute-based encryption (ABE) for arbitrary polynomial size circuits, to program obfuscation, and to constrained pseudorandom functions (PRFs). Many of these constructions require \(\kappa \)-linear maps for large \(\kappa \). In this work, we focus on the reduction of \(\kappa \) in certain constructions of access control primitives that are based on \(\kappa \)-linear maps; in particular, we consider the case of constrained PRFs and ABE. We construct the following objects:

A constrained PRF for arbitrary circuit predicates based on \((n+\ell _{\mathsf {OR}}-1)-\)linear maps (where n is the input length and \(\ell _{\mathsf {OR}}\) denotes the OR-depth of the circuit).
For circuits with a specific structure, we also show how to construct such PRFs based on \((n+\ell _{\mathsf {AND}}-1)-\)linear maps (where \(\ell _{\mathsf {AND}}\) denotes the AND-depth of the circuit).

We then give a black-box construction of a constrained PRF for \(\mathbf {NC}^{1}\) predicates, from any bit-fixing constrained PRF that fixes only one of the input bits to 1; we only require that the bit-fixing PRF have certain key homomorphic properties. This construction is of independent interest as it sheds light on the hardness of constructing constrained PRFs even for “simple” predicates such as bit-fixing predicates.

Instantiating this construction with the bit-fixing constrained PRF from Boneh and Waters (Asiacrypt 2013) gives us a constrained PRF for \(\mathbf {NC}^{1}\) predicates that is based only on n-linear maps, with no dependence on the predicate. In contrast, the previous constructions of constrained PRFs (Boneh and Waters, Asiacrypt 2013) required \((n+\ell +1)-\)linear maps for circuit predicates (where \(\ell \) is the total depth of the circuit) and n-linear maps even for bit-fixing predicates.

We also show how to extend our techniques to obtain a similar improvement in the case of ABE and construct ABE for arbitrary circuits based on \((\ell _{\mathsf {OR}}+1)-\)linear (respectively \((\ell _{\mathsf {AND}}+1)-\)linear) maps.

Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy

Non-Malleable Functions and Their Applications

Abstract

We formally study “non-malleable functions” (NMFs), a general cryptographic primitive which simplifies and relaxes “non-malleable one-way/hash functions” (NMOWHFs) introduced by Boldyreva et al. (ASIACRYPT 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on deterministic functions, rather than probabilistic one-way/hash functions considered in the literature of NMOWHFs.

We mainly follow Baecher et al. to formalize a game-based definition. Roughly, a function f is non-malleable if, given an image \(y^* \leftarrow f(x^*)\) for a randomly chosen \(x^*\), it is hard to output a mauled image y with a \(\phi \) from some transformation class s.t. \(y = f(\phi (x^*))\). A distinctive strengthening of our non-malleable notion is that \(\phi (x^*) = x^*\) is always allowed. We also consider adaptive non-malleability which stipulates non-malleability maintains even when an inversion oracle is available.

We investigate the relations between non-malleability and one-wayness in depth. In the non-adaptive setting, we show that for any achievable transformation class, non-malleability implies one-wayness for poly-to-one functions but not vise versa. In the adaptive setting, we show that for most algebra-induced transformation class, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These two results establish interesting theoretical connections between non-malleability and one-wayness for functions, which extend to trapdoor functions as well, and thus resolve some open problems left by Kiltz et al. (EUROCRYPT 2010). Notably, the implication AOW \(\Rightarrow \) ANM not only yields constructions of NMFs from adaptive trapdoor functions, which partially solves an open problem posed by Boldyreva et al. (ASIACRYPT 2009), but also provides key insight into addressing non-trivial copy attacks in the area of related-key attacks (RKA).

Finally, we show that NMFs lead to a simple black-box construction of continuous non-malleable key derivation functions recently proposed by Qin et al. (PKC 2015), which have proven to be very useful in achieving RKA-security for numerous cryptographic primitives.

Yu Chen, Baodong Qin, Jiang Zhang, Yi Deng, Sherman S. M. Chow

On Public Key Encryption from Noisy Codewords

Abstract

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, or alternatively they can work over the binary field but have a low noise entropy that gives rise to sub-exponential attacks.

Motivated by the goal of efficient public key cryptography, we study the possibility of obtaining improved security over the binary field by using different noise distributions. Inspired by an abstract encryption scheme of Micciancio (PKC 2010), we study an abstract encryption scheme that unifies all the three schemes mentioned above and allows for arbitrary choices of the underlying field and noise distributions.

Our main result establishes an unexpected connection between the power of such encryption schemes and additive combinatorics. Concretely, we show that under the “approximate duality conjecture” from additive combinatorics (Ben-Sasson and Zewi, STOC 2011), every instance of the abstract encryption scheme over the binary field can be attacked in time \(2^{O(\sqrt{n})}\), where n is the maximum of the ciphertext size and the public key size (and where the latter excludes public randomness used for specifying the code). On the flip side, counter examples to the above conjecture (if false) may lead to candidate public key encryption schemes with improved security guarantees.

We also show, using a simple argument that relies on agnostic learning of parities (Kalai, Mansour and Verbin, STOC 2008), that any such encryption scheme can be unconditionally attacked in time \(2^{O(n/\log n)}\), where n is the ciphertext size. Combining this attack with the security proof of Regev’s cryptosystem, we immediately obtain an algorithm that solves the learning parity with noise (LPN) problem in time \(2^{O(n/\log \log n)}\) using only \(n^{1+\epsilon }\) samples, reproducing the result of Lyubashevsky (Random 2005) in a conceptually different way.

Finally, we study the possibility of instantiating the abstract encryption scheme over constant-size rings to yield encryption schemes with no decryption error. We show that over the binary field decryption errors are inherent. On the positive side, building on the construction of matching vector families (Grolmusz, Combinatorica 2000; Efremenko, STOC 2009; Dvir, Gopalan and Yekhanin, FOCS 2010), we suggest plausible candidates for secure instances of the framework over constant-size rings that can offer perfectly correct decryption.

Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgård, Yuval Ishai, Noga Ron-Zewi

Indistinguishability Obfuscation with Non-trivial Efficiency

Abstract

It is well known that inefficient indistinguishability obfuscators (\(\mathbf{iO } \)) with running time \({{\mathrm{poly}}}(|C|,\lambda ) \cdot 2^n\), where C is the circuit to be obfuscated, \(\lambda \) is the security parameter, and n is the input length of C, exists unconditionally: simply output the function table of C (i.e., the output of C on all possible inputs). Such inefficient obfuscators, however, are not useful for applications.

We here consider \(\mathbf{iO } \) with a slightly “non-trivial” notion of efficiency: the running-time of the obfuscator may still be “trivial” (namely, \({{\mathrm{poly}}}(|C|,\lambda ) \cdot 2^{n}\)), but we now require that the obfuscated code is just slightly smaller than the truth table of C (namely \({{\mathrm{poly}}}(|C|,\lambda ) \cdot 2^{n(1-\epsilon )}\), where \(\epsilon >0\)); we refer to this notion as iO with exponential efficiency, or simply exponentially-efficient iO (Xio). We show that, perhaps surprisingly, under the subexponential LWE assumption, subexponentially-secure XiO for polynomial-size circuits implies (polynomial-time computable) iO for all polynomial-size circuits.

Huijia Lin, Rafael Pass, Karn Seth, Sidharth Telang

Backmatter

Titel: Public-Key Cryptography – PKC 2016
herausgegeben von: Chen-Mou Cheng
Kai-Min Chung
Giuseppe Persiano
Bo-Yin Yang
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-49387-8
Print ISBN: 978-3-662-49386-1
DOI: https://doi.org/10.1007/978-3-662-49387-8