Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

Vadim Lyubashevsky, Adriana Palacio, Gil Segev

Published Jan 1, 2010• 0 citations

Abstract

Abstract. We propose a semantically-secure public-key encryption scheme whose security is polynomialtime equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC ’97), Regev (STOC ’03, STOC ’05), and Peikert (STOC ’09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries. 1

Related papers

Chosen-Ciphertext Security from Subset Sum.

Sebastian Faust, Daniel Masny, Daniele Venturi

Abstract. We construct a public-key encryption (PKE) scheme whose security is polynomial-time equivalent to the hardness of the Subset Sum problem. Our scheme achieves the standard notion of indistinguishabil-ity against chosen-ciphertext attacks (IND-CCA) and can be used to encrypt messages of arbitrary polynomial length, improving upon a pre-vious construction by Lyubashevsky, Palacio, and Segev (TCC 2010) which achieved only the weaker notion of semantic security (IND-CPA) and whose concrete security decreases with the length of the message being encrypted. At the core of our construction is a trapdoor technique which originates in the work of Micciancio and Peikert (Eurocrypt 2012).

Jan 1, 20151 citation

Public-key cryptosystems from the worst-case shortest vector problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

ACM Symposium on Theory of Computing (STOC)May 31, 2009822 citations

Efficient Public Key Encryption Based on Ideal

Damien Stehlé, Ron Steinfeld, Kentaro Tanaka +1 more

We describe public key encryption schemes with security provably based on the worst case hardness of the approximate Shortest Vector Problem in some structured lattices, called ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, we achieve CPA-security against subexponential at- tacks, with (quasi-)optimal asymptotic performance: if n is the security parameter, both keys are of bit-length O(n) and the amortized costs of both encryption and decryption are O(1) per message bit. Our construc- tion adapts the trapdoor one-way function of Gentry et al. (STOC'08), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai's trapdoor key genera- tion algorithm (ICALP'99) and a re-interpretation of Regev's quantum reduction between the Bounded Distance Decoding problem and sam- pling short lattice vectors.

Jan 1, 20090 citations

Bounded Key-Dependent Message Security.

Boaz Barak, Iftach Haitner, Dennis Hofheinz +1 more

Abstract. We construct the first public-key encryption scheme that is proven secure (in the standard model, under standard assumptions) even when the attacker gets access to encryptions of arbitrary efficient functions of the secret key. Specifically, under either the DDH or LWE assumption, and for arbitrary but fixed polynomials L and N, we obtain a public-key encryption scheme that resists key-dependent message (KDM) attacks for up to N(k) public keys and functions of circuit size up to L(k), where k denotes the size of the secret key. We call such a scheme bounded KDM secure. Moreover, we show that our scheme suffices for one of the important applications of KDM security: ability to securely instantiate symbolic protocols with axiomatic proofs of security. We also observe that any fully homomorphic encryption scheme that additionally enjoys circular security and circuit privacy is fully KDM secure in the sense that its algorithms can be independent of the polynomials L and N as above. Thus, the recent fully homomorphic encryption scheme of Gentry (STOC 2009) is fully KDM secure under certain non-standard hardness assumptions. Finally, we extend an impossibility result of Haitner and Holenstein (TCC 2009), showing that it is impossible to prove KDM security against a family of query functions that contains exponentially hard pseudo-random functions if the proof makes only a black-box use of the query function and the adversary attacking the scheme. This shows that the non-black-box use of the query function in our proof of security is inherent.

Jan 1, 20091 citation

Lattice Public-Key Encryption: Richer, Tighter, Stronger

Qinyi Li

Public-key encryption allows anyone to encrypt messages that only the intended recipient can decrypt. It is an essential component of most network security protocols; however, the algorithms in widespread use are inherently vulnerable to attacks by quantum computers, should they become a practical reality. This thesis looks at public-key encryption from computationally hard problems based on high-dimensional lattices, believed to resist classical and quantum attacks. On those foundations, it proposes three post-quantum public-key encryption schemes, respectively featuring richer access control, tighter reductionist security proofs, and stronger confidentiality in the presence of external leakage.

Jun 1, 20170 citations

Lattice Signatures Without Trapdoors

Vadim Lyubashevsky, Inria École, Normale Supérieure

Abstract. We provide an alternative method for constructing lattice-based digital signatures which does not use the “hash-and-sign ” methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the Õ(n1.5)-SIVP problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also quite simple, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices. 1

Jan 1, 20122 citations