Public-Key Cryptography – PKC 2017

We consider Galbraith’s space efficient LWE variant, where the \((m \times n)\)-matrix A is binary. In this binary case, solving a vectorial subset sum problem over the integers allows for decryption. We show how to solve this problem using (Integer) Linear Programming. Our attack requires only a fraction of a second for all instances in a regime for m that cannot be attacked by current lattice algorithms. E.g. we are able to solve 100 instances of Galbraith’s small LWE challenge \((n,m) = (256, 400)\) all in a fraction of a second. We also show under a mild assumption that instances with \(m \le 2n\) can be broken in polynomial time via LP relaxation. Moreover, we develop a method that identifies weak instances for Galbraith’s large LWE challenge \((n,m)=(256, 640)\).

We present an algorithm for the approximate k-List problem for the Euclidean distance that improves upon the Bai-Laarhoven-Stehlé (BLS) algorithm from ANTS’16. The improvement stems from the observation that almost all the solutions to the approximate k-List problem form a particular configuration in n-dimensional space. Due to special properties of configurations, it is much easier to verify whether a k-tuple forms a configuration rather than checking whether it gives a solution to the k-List problem. Thus, phrasing the k-List problem as a problem of finding such configurations immediately gives a better algorithm. Furthermore, the search for configurations can be sped up using techniques from Locality-Sensitive Hashing (LSH). Stated in terms of configuration-search, our LSH-like algorithm offers a broader picture on previous LSH algorithms.

For the Shortest Vector Problem, our configuration-search algorithm results in an exponential improvement for memory-efficient sieving algorithms. For \(k=3\), it allows us to bring down the complexity of the BLS sieve algorithm on an n-dimensional lattice from \(2^{0.4812n+o(n)}\) to \(2^{0.3962n + o(n)}\) with the same space requirement \(2^{0.1887n + o(n)}\). Note that our algorithm beats the Gauss Sieve algorithm with time resp. space of \(2^{0.415n+o(n)}\) resp. \(2^{0.208n + o(n)}\), while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to \(2^{0.3717n + o(n)}\) while retaining a memory complexity of \(2^{0.1887n+o(n)}\).

In this work, we describe a new polynomial-time attack on the multilinear maps of Coron, Lepoint, and Tibouchi (CLT13), when used in candidate indistinguishability obfuscation (iO) schemes. More specifically, we show that given the obfuscation of the simple branching program that computes the always zero functionality previously considered by Miles, Sahai and Zhandry (Crypto 2016), one can recover the secret parameters of CLT13 in polynomial time via an extension of the zeroizing attack of Coron et al. (Crypto 2015). Our attack is generalizable to arbitrary oblivious branching programs for arbitrary functionality, and allows (1) to recover the secret parameters of CLT13, and then (2) to recover the randomized branching program entirely. Our analysis thus shows that almost all single-input variants of iO over CLT13 are insecure.

Divisible e-cash, proposed in 1991 by Okamoto and Ohta, addresses a practical concern of electronic money, the problem of paying the exact amount. Users of such systems can indeed withdraw coins of a large value N and then divide it into many pieces of any desired values \(V\le N\). Such a primitive therefore allows to avoid the use of several denominations or change issues. Since its introduction, many constructions have been proposed but all of them make use of the same framework: they associate each coin with a binary tree, which implies, at least, a logarithmic complexity for the spendings.

In this paper, we propose the first divisible e-cash system without such a tree structure, and so without its inherent downsides. Our construction is the first one to achieve constant-time spendings while offering a quite easy management of the coins. It compares favorably with the state-of-the-art, while being provably secure in the standard model.

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted client to outsource storage to an untrusted server while hiding the client’s memory access patterns to the server. The last three decades of research on ORAMs have reduced the bandwidth blowup of ORAM schemes from \(O(\sqrt{N})\) to O(1). However, all schemes that achieve a bandwidth blowup smaller than \(O(\log N)\) use expensive computations such as homomorphic encryptions. In this paper, we achieve a sub-logarithmic bandwidth blowup of \(O(\log _{d} N)\) (where d is a free parameter) without using expensive computation. We do so by using a d-ary tree and a two server private information retrieval (PIR) protocol based on inexpensive XOR operations at the servers. We also show a \(\varOmega (\log _{cD} N)\) lower bound on bandwidth blowup in the modified model involving PIR operations. Here, c is the number of blocks stored by the client and D is the number blocks on which PIR operations are performed. Our construction matches this lower bound implying that the lower bound is tight for certain parameter ranges. Finally, we show that C-ORAM (CCS 15) and CHf-ORAM violate the lower bound. Combined with concrete attacks on C-ORAM/CHf-ORAM, we claim that there exist security flaws in these constructions.

We initiate a formal investigation on the power of predictability for argument of knowledge systems for NP. Specifically, we consider private-coin argument systems where the answer of the prover can be predicted, given the private randomness of the verifier; we call such protocols Predictable Arguments of Knowledge (PAoK).

Our study encompasses a full characterization of PAoK, showing that such arguments can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (i.e., two messages) of communication without loss of generality.

We additionally explore PAoK satisfying additional properties (including zero-knowledge and the possibility of re-using the same challenge across multiple executions with the prover), present several constructions of PAoK relying on different cryptographic tools, and discuss applications to cryptography.

An important problem in secure multi-party computation is the design of protocols that can tolerate adversaries that are capable of corrupting parties dynamically and learning their internal states. In this paper, we make significant progress in this area in the context of password-authenticated key exchange (\(\textsf {PAKE}\)) and oblivious transfer (\(\textsf {OT}\)) protocols. More precisely, we first revisit the notion of projective hash proofs and introduce a new feature that allows us to explain any message sent by the simulator in case of corruption, hence the notion of Explainable Projective Hashing. Next, we demonstrate that this new tool generically leads to efficient \(\textsf {PAKE}\) and \(\textsf {OT}\) protocols that are secure against semi-adaptive adversaries without erasures in the Universal Composability (UC) framework. We then show how to make these protocols secure even against adaptive adversaries, using non-committing encryption, in a much more efficient way than generic conversions from semi-adaptive to adaptive security. Finally, we provide concrete instantiations of explainable projective hash functions that lead to the most efficient \(\textsf {PAKE}\) and \(\textsf {OT}\) protocols known so far, with UC-security against adaptive adversaries, without assuming reliable erasures, in the single global CRS setting.

As an important side contribution, we also propose a new commitment scheme based on \(\textsf {DDH}\), which leads to the construction of the first one-round \(\textsf {PAKE}\) adaptively secure under plain \(\textsf {DDH}\) without pairing, assuming reliable erasures, and also improves previous constructions of \(\textsf {OT}\) and two- or three-round \(\textsf {PAKE}\) schemes.

In this work we study the problem of private set-intersection in the multi-party setting and design two protocols with the following improvements compared to prior work. First, our protocols are designed in the so-called star network topology, where a designated party communicates with everyone else, and take a new approach of leveraging the 2PC protocol of [FNP04]. This approach minimizes the usage of a broadcast channel, where our semi-honest protocol does not make any use of such a channel and all communication is via point-to-point channels. In addition, the communication complexity of our protocols scales with the number of parties.

More concretely, (1) our first semi-honest secure protocol implies communication complexity that is linear in the input sizes, namely \(O((\sum _{i=1}^n m_i)\cdot \kappa )\) bits of communication where \(\kappa \) is the security parameter and \(m_i\) is the size of \(P_i\)’s input set, whereas overall computational overhead is quadratic in the input sizes only for a designated party, and linear for the rest. We further reduce this overhead by employing two types of hashing schemes. (2) Our second protocol is proven secure in the malicious setting. This protocol induces communication complexity \(O((n^2 + nm_{\scriptscriptstyle \mathrm {MAX}}+ nm_{\scriptscriptstyle \mathrm {MIN}}\log m_{\scriptscriptstyle \mathrm {MAX}})\kappa )\) bits of communication where \(m_{\scriptscriptstyle \mathrm {MIN}}\) (resp. \(m_{\scriptscriptstyle \mathrm {MAX}}\)) is the minimum (resp. maximum) over all input sets sizes and n is the number of parties.

Chen and Wee [CRYPTO, 2013] proposed the first almost tightly and adaptively secure IBE in the standard model and left two open problems which called for a tightly secure IBE with (1) constant-size master public key and/or (2) constant security loss. In this paper, we propose an IBE scheme with constant-size master public key and tighter security reduction. This (partially) solves Chen and Wee’s first open problem and makes progress on the second one. Technically, our IBE scheme is built based on Wee’s petit IBE scheme [TCC, 2016] in the composite-order bilinear group whose order is product of four primes. The sizes of master public key, ciphertexts, and secret keys are not only constant but also nearly optimal as Wee’s petit IBE. We can prove its adaptive security in the multi-instance, multi-ciphertext setting [PKC, 2015] based on the decisional subgroup assumption and a subgroup variant of DBDH assumption. The security loss is \({\mathcal {O}}(\log q)\) where q is the upper bound of the total number of secret keys and challenge ciphertexts per instance. It’s much smaller than those for all known adaptively secure IBE schemes in a concrete sense.

A public key encryption scheme is said to be n-circular secure if no PPT adversary can distinguish between encryptions of an n length key cycle and n encryptions of zero.

One interesting question is whether circular security comes for free from IND-CPA security. Recent works have addressed this question, showing that for all integers n, there exists an IND-CPA scheme that is not n-circular secure. However, this leaves open the possibility that for every IND-CPA cryptosystem, there exists a cycle length l, dependent on the cryptosystem (and the security parameter) such that the scheme is l-circular secure. If this is true, then this would directly lead to many applications, in particular, it would give us a fully homomorphic encryption scheme via Gentry’s bootstrapping.

In this work, we show that is not true. Assuming indistinguishability obfuscation and leveled homomorphic encryption, we construct an IND-CPA scheme such that for all cycle lengths l, the scheme is not l-circular secure.

Structure-preserving cryptography is a world where messages, signatures, ciphertexts and public keys are entirely made of elements of a group over which a bilinear map is efficiently computable. While structure-preserving signatures have received much attention the last 6 years, structure-preserving encryption schemes have undergone slower development. In particular, the best known structure-preserving cryptosystems with chosen-ciphertext (IND-CCA2) security either rely on symmetric pairings or require long ciphertexts comprised of hundreds of group elements or do not provide publicly verifiable ciphertexts. We provide a publicly verifiable construction based on the SXDH assumption in asymmetric bilinear groups \(e : \mathbb {G}\times {\hat{\mathbb {G}}} \rightarrow \mathbb {G}_T\), which features relatively short ciphertexts. For typical parameters, our ciphertext size amounts to less than 40 elements of \(\mathbb {G}\). As a second contribution, we provide a structure-preserving encryption scheme with perfectly randomizable ciphertexts and replayable chosen-ciphertext security. Our new RCCA-secure system significantly improves upon the best known system featuring similar properties in terms of ciphertext size.

Non-Malleable Codes for the split state model allow to encode a message into two parts such that arbitrary independent tampering on the parts either destroys completely the content or maintains the message untouched. If the code is also leakage resilient it allows limited independent leakage from the two parts. We propose a model where the two parts can be refreshed independently. We give an abstract framework for building codes for this model, instantiate the construction under the external Diffie-Hellman assumption and give applications of such split-state refreshing. An advantage of our new model is that it allows arbitrarily many tamper attacks and arbitrarily large leakage over the life-time of the systems as long as occasionally each part of the code is refreshed. Our model also tolerates that the refreshing occasionally is leaky or tampered with.

In a recent result, Dachman-Soled et al. (TCC 2015) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was \(\varOmega (\log n)\), meaning that if the original message size was n blocks, then \(\varOmega (\log n)\) blocks of the codeword had to be accessed upon each decode and update instruction.

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack—wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back—we show that a locally decodable and updatable non-malleable code with block size \(\mathcal X \in \mathrm {poly} (\lambda )\) number of bits requires locality \(\delta (n) \in \omega (1)\), where \(n = \mathrm {poly} (\lambda )\) is message length and \(\lambda \) is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al. (TCC 2015)—which indeed allows the adversary to launch a rewind attack—and present a construction of a locally decodable and updatable non-malleable code with block size \(\mathcal X \in \varOmega (\lambda ^{1/\mu })\) number of bits (for constant \(0< \mu < 1\)) with locality \(\delta (n)\), for any \(\delta (n) \in \omega (1)\), and \(n = \mathrm {poly} (\lambda )\).

Leakage resilient codes (LRCs) are probabilistic encoding schemes that guarantee message hiding even under some bounded leakage on the codeword. We introduce the notion of fully leakage resilient codes (FLRCs), where the adversary can leak \(\lambda _0\) bits from the encoding process, namely, the message and the randomness involved during the encoding process. In addition the adversary can as usual leak from the codeword. We give a simulation-based definition requiring that the adversary’s leakage from the encoding process and the codeword can be simulated given just \(\lambda _0\) bits of leakage from the message. We give a fairly general impossibility result for FLRCs in the popular split-state model, where the codeword is broken into independent parts and where the leakage occurs independently on the parts. We then give two feasibility results for weaker models. First, we show that for \(\mathsf {NC}^0\)-bounded leakage from the randomness and arbitrary poly-time leakage from the parts of the codeword the inner-product construction proposed by Daví et al. (SCN’10) and successively improved by Dziembowski and Faust (ASIACRYPT’11) is a FLRC for the split-state model. Second, we provide a compiler from any LRC to a FLRC in the common reference string model where the leakage on the encoding comes from a fixed leakage family of small cardinality. In particular, this compiler applies to the split-state model but also to other models.

We propose a generalization of exTNFS algorithm recently introduced by Kim and Barbulescu (CRYPTO 2016). The algorithm, exTNFS, is a state-of-the-art algorithm for discrete logarithm in \(\mathbb {F}_{p^n}\) in the medium prime case, but it only applies when \(n=\eta \kappa \) is a composite with nontrivial factors \(\eta \) and \(\kappa \) such that \(\gcd (\eta ,\kappa )=1\). Our generalization, however, shows that exTNFS algorithm can be also adapted to the setting with an arbitrary composite n maintaining its best asymptotic complexity. We show that one can compute a discrete logarithm in medium case in the running time of \(L_{p^n}(1/3, \root 3 \of {48/9})\) (resp. \(L_{p^n}(1/3, 1.71)\) if multiple number fields are used), where n is an arbitrary composite. This should be compared with a recent variant by Sarkar and Singh (Asiacrypt 2016) that has the fastest running time of \(L_{p^n}(1/3, \root 3 \of {64/9})\) (resp. \(L_{p^n}(1/3, 1.88)\)) when n is a power of prime 2. When p is of special form, the complexity is further reduced to \(L_{p^n}(1/3, \root 3 \of {32/9})\). On the practical side, we emphasize that the keysize of pairing-based cryptosystems should be updated following to our algorithm if the embedding degree n remains composite.

Due to its remarkable performance and potential resistance to quantum attacks, \(\mathsf {NTRUEncrypt}\) has drawn much attention recently; it also has been standardized by IEEE. However, classical \(\mathsf {NTRUEncrypt}\) lacks a strong security guarantee and its security still relies on heuristic arguments. At Eurocrypt 2011, Stehlé and Steinfeld first proposed a variant of \(\mathsf {NTRUEncrypt}\) with a security reduction from standard problems on ideal lattices. This variant is restricted to the family of rings \(\mathbb {Z}[X]/(X^n+1)\) with n a power of 2 and its private keys are sampled by rejection from certain discrete Gaussian so that the public key is shown to be almost uniform. Despite the fact that partial operations, especially for \(\mathsf {RLWE} \), over \(\mathbb {Z}[X]/(X^n+1)\) are simple and efficient, these rings are quite scarce and different from the classical \(\mathsf {NTRU}\) setting. In this work, we consider a variant of \(\mathsf {NTRUEncrypt}\) over prime cyclotomic rings, i.e. \(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) with n an odd prime, and obtain \(\mathsf {IND\text {-}CPA}\) secure results in the standard model assuming the hardness of worst-case problems on ideal lattices. In our setting, the choice of the rings is much more flexible and the scheme is closer to the original \(\mathsf {NTRU}\), as \(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) is a large subring of the \(\mathsf {NTRU}\) ring \(\mathbb {Z}[X]/(X^{n}-1)\). Some tools for prime cyclotomic rings are also developed.

In this paper we provide new algebraic tools to study the relationship between different Matrix Diffie-Hellman (MDDH) Problems, which are recently introduced as a natural generalization of the so-called Linear Problem. Namely, we provide an algebraic criterion to decide whether there exists a generic black-box reduction, and in many cases, when the answer is positive we also build an explicit reduction with the following properties: it only makes a single oracle call, it is tight and it makes use only of operations in the base group.

It is well known that two MDDH problems described by matrices with a different number of rows are separated by an oracle computing certain multilinear map. Thus, we put the focus on MDDH problems of the same size. Then, we show that MDDH problems described with a different number of parameters are also separated (meaning that a successful reduction cannot decrease the amount of randomness used in the problem instance description).

When comparing MDDH problems of the same size and number of parameters, we show that they are either equivalent or incomparable. This suggests that a complete classification into equivalence classes could be done in the future. In this paper we give some positive and negative partial results about equivalence, in particular solving the open problem of whether the Linear and the Cascade MDDH problems are reducible to each other.

The results given in the paper are limited by some technical restrictions in the shape of the matrices and in the degree of the polynomials defining them. However, these restrictions are also present in most of the work dealing with MDDH Problems. Therefore, our results apply to all known instances of practical interest.