Catálogo de publicaciones - libros

We provide evidence that the unforgeability of several discrete-log based signatures like Schnorr signatures cannot be equivalent to the discrete log problem in the standard model. This contradicts in nature well-known proofs standing in weakened proof methodologies, in particular proofs employing various formulations of the Forking Lemma in the random oracle Model. Our impossibility proofs apply to many discrete-log-based signatures like ElGamal signatures and their extensions, DSA, ECDSA and KCDSA as well as standard generalizations of these, and even RSA-based signatures like GQ. We stress that our work sheds more light on the provable (in)security of popular signature schemes but does not explicitly lead to actual attacks on these.

The aim of this paper is to justify the common cryptographic practice of selecting elliptic curves using their order as the primary criterion. We can formalize this issue by asking whether the discrete log problem ( dlog ) has the same difficulty for all curves over a given finite field with the same order. We prove that this is essentially true by showing polynomial time random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). We do so by constructing certain expander graphs, similar to Ramanujan graphs, with elliptic curves as nodes and low degree isogenies as edges. The result is obtained from the rapid mixing of random walks on this graph. Our proof works only for curves with (nearly) the same endomorphism rings. Without this technical restriction such a dlog equivalence might be false; however, in practice the restriction may be moot, because all known polynomial time techniques for constructing equal order curves produce only curves with nearly equal endomorphism rings.

Cryptosystems based on the knapsack problem were among the first public-key systems to be invented. Their high encryption/ decryption rate attracted considerable interest until it was noticed that the underlying knapsacks often had a low density, which made them vulnerable to lattice attacks, both in theory and practice. To prevent low-density attacks, several designers found a subtle way to increase the density beyond the critical density by decreasing the weight of the knapsack, and possibly allowing non-binary coefficients. This approach is actually a bit misleading: we show that low-weight knapsacks do not prevent efficient reductions to lattice problems like the shortest vector problem, they even make reductions more likely. To measure the resistance of low-weight knapsacks, we introduce the novel notion of pseudo-density, and we apply the new notion to the Okamoto-Tanaka-Uchiyama (OTU) cryptosystem from Crypto ’00. We do not claim to break OTU and we actually believe that this system may be secure with an appropriate choice of the parameters. However, our research indicates that, in its current form, OTU cannot be supported by an argument based on density. Our results also explain why Schnorr and Hörner were able to solve at Eurocrypt ’95 certain high-density knapsacks related to the Chor-Rivest cryptosystem, using lattice reduction.

In this paper, we propose a efficient and secure point multiplication algorithm, based on double-base chains. This is achieved by taking advantage of the sparseness and the ternary nature of the so-called double-base number system (DBNS). The speed-ups are the results of fewer point additions and improved formulæ for point triplings and quadruplings in both even and odd characteristic. Our algorithms can be protected against simple and differential side-channel analysis by using side-channel atomicity and classical randomization techniques. Our numerical experiments show that our approach leads to speed-ups compared to windowing methods, even with window size equal to 4, and other SCA resistant algorithms.

We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an n -party randomized function and show that if f can be computed by a circuit of size c , then $\mathcal{O}(cn^2\kappa)$ is an upper bound for active security with optimal resilience t < n /2 and security parameter κ . This improves on the communication complexity of previous protocols by a factor of at least n . This improvement comes from the fact that in the new protocol, only $\mathcal{O}(n)$ messages (of size $\mathcal{O}(\kappa)$ each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least $\mathcal{O}(n)$ broadcasts per gate . Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience t < n from $\mathcal{O}(cn^2\kappa)$ to $\mathcal{O}(cn\kappa)$ . This improvement is mainly due to a simple observation.

We present generic frameworks for constructing efficient broadcast encryption schemes in the subset-cover paradigm, introduced by Naor et.al., based on various key derivation techniques. Our frameworks characterize any instantiation completely to its underlying graph decompositions , which are purely combinatorial in nature. This abstracts away the security of each instantiated scheme to be guaranteed by the generic one of the frameworks; thus, gives flexibilities in designing schemes. Behind these are new techniques based on (trapdoor) RSA accumulators utilized to obtain practical performances. We then give some efficient instantiations from the frameworks. Our first construction improves the currently best schemes, including the one proposed by Goodrich et.al., without any further assumptions (only pseudo-random generators are used) by some factors. The second instantiation, which is the most efficient, is instantiated based on RSA and directly improves the first scheme. Its ciphertext length is of order O ( r ), the key size is O (1), and its computational cost is O ( n ^1/klog^2 n ) for any (arbitrary large) constant k ; where r and n are the number of revoked users and all users respectively. To the best of our knowledge, this is the first explicit collusion-secure scheme in the literature that achieves both ciphertext size and key size independent of n simultaneously while keeping all other costs efficient, in particular, sub-linear in n . The third scheme improves Gentry and Ramzan’s scheme, which itself is more efficient than the above schemes in the aspect of asymptotic computational cost.

A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information ε ( f ) required for computing f and claim that f is privately-computable if and only if ε ( f ) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with ε ( f ) ≠ 0 and another function g with ε ( g ) = 0 that is not privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function.

We propose Gate Evaluation Secret Sharing (GESS) – a new kind of secret sharing, designed for use in secure function evaluation (SFE) with minimal interaction. The resulting simple and powerful GESS approach to SFE is a generalization of Yao’s garbled circuit technique. We give efficient GESS schemes for evaluating binary gates and prove (almost) matching lower bounds. We give a more efficient information-theoretic reduction of SFE of a boolean formula F to oblivious transfer. Its complexity is ≈ ∑ d _ i ^2, where d _ i is the depth of the i -th leaf of F .

As an extension of multi-party computation (MPC), we propose the concept of secure parallel multi-party computation which is to securely compute multi-functions against an adversary with multi-structures. Precisely, there are m functions f _1,..., f _ m and m adversary structures $\mathcal{A}_1,...,\mathcal{A}_m$ , where f _ i is required to be securely computed against an $\mathcal{A}_i$ -adversary. We give a general construction to build a parallel multi-party computation protocol from any linear multi-secret sharing scheme (LMSSS), provided that the access structures of the LMSSS allow MPC at all. When computing complicated functions, our protocol has more advantage in communication complexity than the “direct sum” method which actually executes a MPC protocol for each function. The paper also provides an efficient and generic construction to obtain from any LMSSS a multiplicative LMSSS for the same multi-access structure.

Micali, Rabin, and Kilian [9] recently introduced zero- knowledge sets and databases, in which a prover sets up a database by publishing a commitment, and then gives proofs about particular values. While an elegant and useful primitive, zero-knowledge databases do not offer any good way to perform updates. We explore the issue of updating zero-knowledge databases. We define and discuss transparent updates, which (1) allow holders of proofs that are still valid to update their proofs, but (2) otherwise maintain secrecy about the update. We give rigorous definitions for transparently updatable zero- knowledge databases, and give a practical construction based on the Chase et al [2] construction, assuming that verifiable random functions exist and that mercurial commitments exist, in the random oracle model. We also investigate the idea of updatable commitments , an attempt to make simple commitments transparently updatable. We define this new primitive and give a simple secure construction.