Search

We propose a new rank metric code based encryption based on the hard problem of rank syndrome decoding problem. We consider a generator matrix for Gabidulin codes in the form of k-partial circulant matrix. We distort the matrix G by adding it with another random k-partial circulant matrix and multiplying the product with a random circulant matrix. We also convert our encryption into an IND-CCA2 secured encryption scheme under assumption of Rank Syndrome Decoding problem. Our encryption has the smallest key size (of 4.306 KB) at 256-bit security level as compared to all the other rank code based encryption schemes with zero decryption failure and hidden structure for the decodable codes. [ABSTRACT FROM AUTHOR]

Middle-product learning with errors ( MP - LWE ) is a variant of the LWE problem introduced at CRYPTO 2017 by Rosca et al. (Advances in cryptology—CRYPTO, Springer, Berlin, 2017). Asymptotically, the theoretical results of Rosca et al. (2017) suggest that MP - LWE gives lattice-based public-key cryptosystems offering a 'security-risk vs. efficiency' trade-off: higher performance than cryptosystems based on unstructured lattices (LWE problem) and lower risk than cryptosystems based on structured lattices (Polynomial/Ring LWE problem). However, although promising in theory, Rosca et al. (2017) left the practical implications of MP - LWE for lattice-based cryptography unclear. In this paper, we show how to build practical public-key cryptosystems with strong security guarantees based on MP - LWE . On the implementation side, we present optimised fast algorithms for computing the middle-product operation over polynomial rings Z q [ x ] , the dominant computation for MP - LWE -based cryptosystems. On the security side, we show how to obtain a nearly tight security proof for MP - LWE from the hardest Polynomial LWE problem over a large family of rings, improving on the loose reduction of Rosca et al. (2017). We also show and analyze an optimised cryptanalysis of MP - LWE that narrows the complexity gap between best known attacks on MP - LWE and Polynomial LWE . To evaluate the practicality of MP - LWE , we apply our results to construct, implement and optimise parameters for a practical MP - LWE -based public-key cryptosystem, Titanium , and compare its benchmarks to other lattice-based systems. Our results show that MP - LWE offers a new 'security-risk vs. efficiency' trade-off in lattice-based cryptography in practice, not only asymptotically in theory. [ABSTRACT FROM AUTHOR]

Structure-preserving primitives are important building blocks in cryptographic protocols. Up to now, the only structure-preserving public-key encryption (SP-PKE) with CCA security over asymmetric pairing groups is based on the SXDH assumption, due to Libert et al. [18]. In this work, we propose a general framework of constructing SP-PKE with leakage-resilient CCA security (which implies the IND-CCA2 security). The corresponding instantiations result in the first leakage-resilient CCA secure SP-PKE from the Matrix Decision Diffie-Hellman (MDDH) assumption (including the SXDH and k -Linear assumptions) over asymmetric pairing groups. The ciphertext of our SP-PKE also enjoys the publicly verifiable property. [ABSTRACT FROM AUTHOR]

The advent of quantum computing threatens to break many classical cryptographic schemes, leading to innovations in public key cryptography that focus on post-quantum cryptography primitives and protocols resistant to quantum computing threats. Lattice-based cryptography is a promising post-quantum cryptography family, both in terms of foundational properties as well as in its application to both traditional and emerging security problems such as encryption, digital signature, key exchange, and homomorphic encryption. While such techniques provide guarantees, in theory, their realization on contemporary computing platforms requires careful design choices and tradeoffs to manage both the diversity of computing platforms (e.g., high-performance to resource constrained), as well as the agility for deployment in the face of emerging and changing standards. In this work, we survey trends in lattice-based cryptographic schemes, some recent fundamental proposals for the use of lattices in computer security, challenges for their implementation in software and hardware, and emerging needs for their adoption. The survey means to be informative about the math to allow the reader to focus on the mechanics of the computation ultimately needed for mapping schemes on existing hardware or synthesizing part or all of a scheme on special-purpose har dware. [ABSTRACT FROM AUTHOR]

In this work, we explore a combinatorial optimization problem stemming from the Naccache–Stern cryptosystem. We show that solving this problem results in bandwidth improvements, and suggest a polynomial-time approximation algorithm to find an optimal solution. Our work suggests that using optimal radix encoding results in an asymptotic 50% increase in bandwidth. [ABSTRACT FROM AUTHOR]

Public-key encryption is an important security mechanism used in cloud environment. To ensure the confidentiality of data encrypted using public-key encryption, countermeasures against cryptographic key leakage by side-channel attacks should be applied to the encryption scheme implemented both in locality and in cloud server. Traditional public-key encryption does not capture side-channel attacks. Moreover, the adversary can inject fault to tamper with the secret key and observe the output of the public-key encryption scheme under this modified key which is called "tampering attack". In this paper, we present two continuous leakage and tampering resilient CCA secure public-key encryption schemes. For implementations of our schemes during the key update, bounded number of tampering queries for arbitrary key relations and bounded leakage is allowed. By updating the secret key, our schemes are secure against continuous leakage and tampering attacks. [ABSTRACT FROM AUTHOR]

Outsourcing of data is a very common scenario in the present-day world and quite often we need to outsource confidential data whose privacy is of utmost concern. Performing encryption before outsourcing the data is a simple solution to preserve privacy. Preferably a public-key encryption technique is used to encrypt the data. A demerit of encrypting data is that while requesting the data from the cloud we need to have some technique which supports search functionality on encrypted data. Without the searchable encryption technique, the cloud is forced to send the whole database, which is highly inefficient and impractical. To address this problem, we consider the email scenario, in which the sender of the email will encrypt email contents using receiver's public key; hence, only the receiver can decrypt email contents. We propose a scheme that will have encrypted emails stored on the cloud and have capabilities that support searching through the encrypted database. This enables the cloud to reply to a request with a more precise response without compromising any privacy in terms of email contents and also in terms of access patterns. We provide a solution for the email scenario in which we can tag or associate emails with some keywords, and during retrieval, the email owner can request all the emails associated with a particular keyword. Although attempts are seen in the literature to solve this issue they do not have the flexibility of dissociating keywords from an email. Keyword dissociation is essential to modify the association between keywords and emails to enable better filtering of emails. Our technique also supports the functionality of keyword dissociation. The solution allows single-database private information retrieval writing in an oblivious way with sublinear communication cost. We have theoretically proved the correctness and security of our technique. [ABSTRACT FROM AUTHOR]

Security against selective opening attack (SOA) for receivers requires that in a multi-user setting, even if an adversary has access to all ciphertexts, and adaptively corrupts some fraction of the users to obtain the decryption keys corresponding to some of the ciphertexts, the remaining (potentially related) ciphertexts retain their privacy. In this paper, we study simulation-based selective opening security for receivers of public key encryption (PKE) schemes under chosen-ciphertext attacks (RSIM-SO-CCA). Concretely, we first show that some known PKE schemes meet RSIM-SO-CCA security. Then, we introduce the notion of master-key SOA security for identity-based encryption (IBE), and extend the Canetti–Halevi–Katz transformation to show generic PKE constructions achieving RSIM-SO-CCA security. Finally, we show how to construct an IBE scheme achieving master-key SOA security. [ABSTRACT FROM AUTHOR]

Self-updatable encryption (SUE) is a new kind of public-key encryption, motivated by cloud computing, which enables anyone (i.e. cloud server with no access to private keys) to update a past ciphertext to a future ciphertext by using a public key. The main applications of SUE are revocable-storage attribute-based encryption (RS-ABE) that provides an efficient and secure access control to encrypted data stored in cloud storage. In this setting, there is a new threat such that a revoked user still can access past ciphertexts given to him by a storage server. RS-ABE solves this problem by combining user revocation and ciphertext updating functionalities. We propose the first SUE and RS-ABE schemes secure against a relevant form of chosen-ciphertext security (CCA). Due to the fact that some ciphertexts are easily derived from others, we employ a different notion of CCA that avoids easy challenge related messages. Specifically, we define "time extended challenge" CCA security for SUE which excludes ciphertexts that are easily derived from the challenge (over time periods) from being queried on. We then propose an efficient SUE scheme with such CCA security, and we also present an RS-ABE scheme with this CCA security. [ABSTRACT FROM AUTHOR]

ℱ -Related-Key Attacks (RKAs) allow an adversary to tamper the key k stored in a cryptographic device by specifying related-key deriving (RKD) functions f in ℱ and subsequently learn the outcome of the device under related keys f (k) ⁠. In this paper, we present RKA secure public-key encryption (PKE) and symmetric encryption (SE) schemes admitting a tight security reduction to the standard s -Linear assumption. The security loss depends only on the security parameter and is independent of the number of tampering queries made by the adversary. Our encryption schemes are resilient to RKAs w.r.t. the set of restricted affine functions ℱ raff ⁠, of which the set of linear functions ℱ lin is a subset. In particular, • Our encryption schemes serve as the first ones possessing tight RKA security for a non-trivial RKD function class ℱ under standard assumptions. • Moreover, our encryption schemes enjoy tight super-strong RKA securities, which are the strongest ones among the existing RKA security notions. [ABSTRACT FROM AUTHOR]

Identity-based hash proof system is a basic and important primitive. It is widely utilized to construct cryptographic schemes and protocols that are secure against key-leakage attacks. In this paper, we introduce the concept of updatable identity-based hash proof system, in which the related master secret key and the identity secret key can be updated securely. Then, we instantiate this primitive based on lattices in the standard model. Moreover, we introduce an application of this new primitive by giving a generic construction of leakage-resilient public-key encryption schemes with anonymity. This construction can be considered as the integration of the bounded-retrieval model and the continual leakage model. Compared with the existing leakage-resilient schemes, our construction not only is more efficient but also can resist much more key leakage. [ABSTRACT FROM AUTHOR]

Bellare, Boldyreva, and O’Neill (CRYPTO ’07) initiated the study of deterministic public-key encryption as an alternative in scenarios where randomized encryption has inherent drawbacks. The resulting line of research has so far guaranteed security only for adversarially chosen-plaintext distributions that are independent of the public key used by the scheme. In most scenarios, however, it is typically not realistic to assume that adversaries do not take the public key into account when attacking a scheme. We show that it is possible to guarantee meaningful security even for plaintext distributions that depend on the public key. We extend the previously proposed notions of security, allowing adversaries to adaptively choose plaintext distributions after seeing the public key, in an interactive manner. The only restrictions we make are that: (1) plaintext distributions are unpredictable (as is essential in deterministic public-key encryption), and (2) the number of plaintext distributions from which each adversary is allowed to adaptively choose is upper bounded by 2p, where p can be any predetermined polynomial in the security parameter and plaintext length. For example, with p=0 we capture plaintext distributions that are independent of the public key, and with p=O(slogs) we capture, in particular, all plaintext distributions that are samplable by circuits of size s. Within our framework we present both constructions in the random oracle model based on any public-key encryption scheme, and constructions in the standard model based on lossy trapdoor functions (thus, based on a variety of number-theoretic assumptions). Previously known constructions heavily relied on the independence between the plaintext distributions and the public key for the purposes of randomness extraction. In our setting, however, randomness extraction becomes significantly more challenging once the plaintext distributions and the public key are no longer independent. Our approach is inspired by research on randomness extraction from seed-dependent distributions. Underlying our approach is a new generalization of a method for such randomness extraction, originally introduced by Trevisan and Vadhan (FOCS ’00) and Dodis (Ph.D. Thesis, MIT, ’00). [ABSTRACT FROM AUTHOR]

F-related-key attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say k, but also related keys f(k), with f adaptively chosen from F by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called super-strong RKA securities, which stipulate minimal restrictions on the adversary’s forgery or oracle access, thus turn out to be the strongest ones among existing RKA security requirements. We present paradigms for constructing super-strong RKA secure MAC, PKE and SE from a common ingredient, namely Tag-based hash proof system (THPS). We also present constructions for THPS based on the k-linear and the DCR assumptions. When instantiating our paradigms with concrete THPS constructions, we obtain super-strong RKA secure MAC, PKE and SE schemes for the class of restricted affine functions Fraff, of which the class of linear functions Flin is a subset. To the best of our knowledge, our MACs, PKEs and SEs are the first ones possessing super-strong RKA securities for a non-claw-free function class Fraff in the standard model and under standard assumptions. Our constructions are free of pairing and are as efficient as those proposed in previous works. In particular, the keys, tags of MAC and ciphertexts of PKE and SE all consist of only a constant number of group elements. [ABSTRACT FROM AUTHOR]

Artifact-centric workflows describe possible executions of a business process through constraints expressed from the point of view of the documents exchanged between principals. A sequence of manipulations is deemed valid as long as every document in the workflow follows its prescribed lifecycle at all steps of the process. So far, establishing that a given workflow complies with artifact lifecycles has mostly been done through static verification, or by assuming a centralized access to all artifacts where these constraints can be monitored and enforced. We present in this paper an alternate method of enforcing document lifecycles that requires neither static verification nor single-point access. Rather, the document itself is designed to carry fragments of its history, protected from tampering using hashing and public-key encryption. Any principal involved in the process can verify at any time that the history of a document complies with a given lifecycle. Moreover, the proposed system also enforces access permissions: not all actions are visible to all principals, and one can only modify and verify what one is allowed to observe. These concepts have been implemented in a software library called Artichoke, and empirically tested for performance and scalability. [ABSTRACT FROM AUTHOR]

We propose a framework for constructing efficient code-based encryption schemes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Alekhnovich’s approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the hamming quasi-cyclic cryptosystem (HQC), based on the hamming metric, and the rank quasi-cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the indistinguishability under chosen plaintext attack security of our systems to a decision version of the well-known problem of decoding random families of quasi-cyclic codes for the hamming and rank metrics (the respective \mathsf QCSD and \mathsf RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for \lambda the security parameter, the public key sizes are respectively in \mathcal {O}({\lambda }^{2}) for HQC and in \mathcal {O}\left({\lambda ^{\frac {4}{3}}}\right)$ for RQC. Practical parameter compares well to the systems based on ring-learning parity with noise or the recent moderate density parity check codes system. [ABSTRACT FROM PUBLISHER]

We give a new black-box transformation from any semantically secure encryption scheme into a non-malleable one which has a better rate than the best previous work of Coretti et al. (in: Kushilevitz and Malkin (eds) TCC 2016-A, Part I, Springer, Heidelberg, 2016). We achieve a better rate by departing from the “matrix encoding” methodology used by previous constructions, and working directly with a single codeword. We also use a Shamir secret-share packing technique to improve the rate of the underlying error-correcting code. [ABSTRACT FROM AUTHOR]

In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012. [ABSTRACT FROM AUTHOR]

Motivated by applications in large storage systems, we initiate the study of incremental deterministic public-key encryption. Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security for low-entropy plaintexts distributions, but Bellare et al. demonstrated that a strong notion of security can in fact be realized for relatively high-entropy plaintext distributions. In order to achieve a meaningful level of security, a deterministic encryption algorithm should be typically used for encrypting rather long plaintexts for ensuring a sufficient amount of entropy. This requirement may be at odds with efficiency constraints, such as communication complexity and computation complexity in the presence of small updates. Thus, a highly desirable property of deterministic encryption algorithms is incrementality: Small changes in the plaintext translate into small changes in the corresponding ciphertext. We present a framework for modeling the incrementality of deterministic public-key encryption. Our framework extends the study of the incrementality of cryptography primitives initiated by Bellare, Goldreich and Goldwasser (CRYPTO '94). Within our framework, we propose two schemes, which we prove to enjoy an optimal tradeoff between their security and incrementality up to lower-order factors. Our first scheme is a generic method which can be based on any deterministic public-key encryption scheme, and, in particular, can be instantiated with any semantically secure (randomized) public-key encryption scheme in the random-oracle model. Our second scheme is based on the Decisional Diffie-Hellman assumption in the standard model. The approach underpinning our schemes is inspired by the fundamental 'sample-then-extract' technique due to Nisan and Zuckerman (JCSS '96) and refined by Vadhan (J. Cryptology '04), and by the closely related notion of 'locally computable extractors' due to Vadhan. Most notably, whereas Vadhan used such extractors to construct private-key encryption schemes in the bounded-storage model, we show that techniques along these lines can also be used to construct incremental public-key encryption schemes. [ABSTRACT FROM AUTHOR]

We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto '06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt '07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryption. Instead, we encrypt an encoding of the message; the encoding is based on an error-correcting code with certain properties of reconstruction and secrecy from partial views, satisfied, e.g., by a Reed-Solomon code. [ABSTRACT FROM AUTHOR]