waashk/dblp huggingface dataset:
secure computation from random error correcting codes. secure computation consists of protocols for secure arithmetic: secret values are added and multiplied securely by networked processors. the striking feature of secure computation is that security is maintained even in the presence of an adversary who corrupts a quorum of the processors and who exercises full, malicious control over them. one of the fundamental primitives at the heart of secure computation is secret-sharing. typically, the required secret-sharing techniques build on shamir's scheme, which can be viewed as a cryptographic twist on the reed-solomon error correcting code. in this work we further the connections between secure computation and error correcting codes. we demonstrate that threshold secure computation in the secure channels model can be based on arbitrary codes. for a network of size n, we then show a reduction in communication for secure computation amounting to a multiplicative logarithmic factor (in n) compared to classical methods for small, e.g., constant size fields, while tolerating $t players to be corrupted, where ¿> 0 can be arbitrarily small. for large networks this implies considerable savings in communication. our results hold in the broadcast/negligible error model of rabin and ben-or, and complement results from crypto 2006 for the zero-error model of ben-or, goldwasser and wigderson (bgw). our general theory can be extended so as to encompass those results from crypto 2006 as well. we also present a new method for constructing high information rate ramp schemes based on arbitrary codes, and in particular we give a new construction based on algebraic geometry codes.
atomic secure multi-party multiplication with low communication. we consider the standard secure multi-party multiplication protocol due to m. rabin. this protocol is based on shamir's secret sharing scheme and it can be viewed as a practical variation on one of the central techniques in the foundational results of ben-or, goldwasser, and wigderson and chaum, crépeau, and damgaard on secure multi-party computation. rabin's idea is a key ingredient to virtually all practical protocols in threshold cryptography.given a passive t-adversary in the secure channels model with synchronous communication, for example, secure multiplication of two secret-shared elements from a finite field k based on this idea uses one communication round and has the network exchange o(n 2) field elements, if t = ¿(n) and t < n/2 and if n is the number of players. this is because each of o(n) players must perform shamir secret sharing as part of the protocol. this paper demonstrates that under a few restrictions much more efficient protocols are possible; even at the level of a single multiplication.we demonstrate a twist on rabin's idea that enables one-round secure multiplication with just o(n) bandwidth in certain settings, thus reducing it from quadratic to linear. the ideas involved can additionally be employed in the evaluation of arithmetic circuits, where under appropriate circumstances similar efficiency gains can be obtained.
non-wafer-scale sieving hardware for the nfs: another attempt to cope with 1024-bit. significant progress in the design of special purpose hardware for supporting the number field sieve (nfs) has been made. from a practical cryptanalytic point of view, however, none of the published proposals for coping with the sieving step is satisfying. even for the best known designs, the technological obstacles faced for the parameters expected for a 1024-bit rsa modulus are significant.below we present a new hardware design for implementing the sieving step. the suggested chips are of moderate size and the inter-chip communication does not seem unrealistic. according to our preliminary analysis of the 1024-bit case, we expect the new design to be about 2 to 3.5 times slower than twirl (a wafer-scale design). due to the more moderate technological requirements, however, from a practical cryptanalytic point of view the new design seems to be no less attractive than twirl.
round-efficient secure computation in point-to-point networks. essentially all work studying the round complexity of secure computation assume broadcast as an atomic primitive. protocols constructed under this assumption tend to have very poor round complexity when compiled for a point-to-point network due to the high overhead of emulating each invocation of broadcast. this problem is compounded when broadcast is used in more than one round of the original protocol due to the complexity of handling sequential composition (when using round-efficient emulation of broadcast).we argue that if the goal is to optimize round complexity in point-to-point networks, then it is preferable to design protocols -- assuming a broadcast channel -- minimizing the number of rounds in which broadcast is used rather than minimizing the total number of rounds. with this in mind, we present protocols for secure computation in a number of settings that use only a single round of broadcast. in all cases, we achieve optimal security threshold for adaptive adversaries, and obtain protocols whose round complexity (in a point-to-point network) improves on prior work.
on the security of cryptosystems with quadratic decryption: the nicest cryptanalysis. we describe the first polynomial time chosen-plaintext total break of the nice family of cryptosystems based on ideal arithmetic in imaginary quadratic orders, introduced in the late 90's by hartmann, paulus and takagi [hpt99]. the singular interest of these encryption schemes is their natural quadratic decryption time procedure that consists essentially in applying euclid's algorithm. the only current specific cryptanalysis of these schemes is jaulmes and joux's chosen-ciphertext attack to recover the secret key [jj00]. originally, hartmann et al. claimed that the security against a total break attack relies only on the difficulty of factoring the public discriminant $\delta_q=-pq^2$, although the public key was also composed of a specific element of the class group of the order of discriminant δ q , which is crucial to reach the quadratic decryption complexity. in this article, we propose a drastic cryptanalysis which factors δ q (and hence recovers the secret key), only given this element, in cubic time in the security parameter. as a result, performing our cryptanalysis on a cryptographic example takes less than a second on a standard pc.
feistel networks made public, and applications. feistel network, consisting of a repeated application of the feistel transform, gives a very convenient and popular method for designing "cryptographically strong" permutations from corresponding "cryptographically strong" functions. up to now, all usages of the feistel network, including the celebrated luby-rackoff's result, critically rely on (a) the (pseudo)randomness of round functions; and (b) the secrecy of (at least some of) the intermediate round values appearing during the feistel computation. moreover, a small constant number of feistel rounds was typically sufficient to guarantee security under assumptions (a) and (b). in this work we consider several natural scenarios where at least one of the above assumptions does not hold, and show that a constant, or even logarithmic number of rounds is provably insufficient to handle such applications, implying that a new method of analysis is needed.on a positive side, we develop a new combinatorial understanding of feistel networks, which makes them applicable to situations when the round functions are merely unpredictable rather than (pseudo)random and/or when the intermediate round values may be leaked to the adversary (either through an attack or because the application requires it). in essence, our results show that in any such scenario a super-logarithmic number of feistel rounds is necessary and sufficient to guarantee security.of independent interest, our technique yields a novel domain extension method for messages authentication codes and other related primitives, settling a question studied by an and bellare in crypto 1999.
cryptanalysis of sflash with slightly modified parameters. sflash is a signature scheme which belongs to a family of multivariate schemes proposed by patarin et al. in 1998 [9]. the sflash scheme itself has been designed in 2001 [8] and has been selected in 2003 by the nessie european consortium [6] as the best known solution for implementation on low cost smart cards. in this paper, we show that slight modifications of the parameters of sflash within the general family initially proposed renders the scheme insecure. the attack uses simple linear algebra, and allows to forge a signature for an arbitrary message in a question of minutes for practical parameters, using only the public key. although sflash itself is not amenable to our attack, it is worrying to observe that no rationale was ever offered for this "lucky" choice of parameters.
ideal multipartite secret sharing schemes. multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. several particular families of multipartite schemes, such as the weighted threshold schemes, the hierarchical and the compartmented schemes, and the ones with bipartite or tripartite access structure have been considered in the literature. the characterization of the access structures of ideal secret sharing schemes is one of the main open problems in secret sharing. in this work, the characterization of ideal multipartite access structures is studied with all generality. our results are based on the well-known connections between ideal secret sharing schemes and matroids. one of the main contributions of this paper is the application of discrete polymatroids to secret sharing. they are proved to be a powerful tool to study the properties of multipartite matroids. in this way, we obtain some necessary conditions and some sufficient conditions for a multipartite access structure to be ideal.our results can be summarized as follows. first, we present a characterization of matroid-related multipartite access structures in terms of discrete polymatroids. as a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. second, we use linear representations of discrete polymatroids to characterize the linearly representable multipartite matroids. in this way we obtain a sufficient condition for a multipartite access structure to be ideal. finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.
non-trivial black-box combiners for collision-resistant hash-functions don't exist. a (k,¿)-robust combiner for collision-resistant hash-functions is a construction which from ¿ hash-functions constructs a hash-function which is collision-resistant if at least k of the components are collision-resistant. one trivially gets a (k,¿)-robust combiner by concatenating the output of any ¿¿ k + 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. we show that this is unavoidable as no black-box (k,¿)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. this answers a question of boneh and boyen (crypto'06).
the power of proofs-of-possession: securing multiparty signatures against rogue-key attacks. multiparty signature protocols need protection against rogue-key attacks, made possible whenever an adversary can choose its public key(s) arbitrarily. for many schemes, provable security has only been established under the knowledge of secret key (kosk) assumption where the adversary is required to reveal the secret keys it utilizes. in practice, certifying authorities rarely require the strong proofs of knowledge of secret keys required to substantiate the kosk assumption. instead, proofs of possession (pops) are required and can be as simple as just a signature over the certificate request message. we propose a general registered key model, within which we can model both the kosk assumption and in-use pop protocols. we show that simple pop protocols yield provable security of boldyreva's multisignature scheme [11], the lossw multisignature scheme [28], and a 2-user ring signature scheme due to bender, katz, and morselli [10]. our results are the first to provide formal evidence that pops can stop rogue-key attacks.
endomorphisms for faster elliptic curve cryptography on a large class of curves. efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the gallant-lambert- vanstone (glv) method. we extend results of iijima, matsuo, chao and tsujii which give such homomorphisms for a large class of elliptic curves by working over ${\mathbb f}_{p^2}$ and demonstrate that these results can be applied to the glv method.in general we expect our method to require about 0.75 the time of previous best methods (except for subfield curves, for which frobenius expansions can be used). we give detailed implementation results which show that the method runs in between 0.70 and 0.84 the time of the previous best methods for elliptic curve point multiplication on general curves.
oblivious-transfer amplification. oblivious transfer (ot) is a primitive of paramount importance in cryptography or, more precisely, two- and multi-party computation due to its universality. unfortunately, ot cannot be achieved in an unconditionally secure way for both parties from scratch. therefore, it is a natural question what information-theoretic primitives or computational assumptions ot can be based on.the results in our paper are threefold. first, we give an optimal proof for the standard protocol to realize unconditionally secure ot from a weak variant of ot called universal ot, for which a malicious receiver can virtually obtain any possible information he wants, as long as he does not get all the information. this result is based on a novel distributed leftover hash lemma which is of independent interest.second, we give conditions for when ot can be obtained from a faulty variant of ot called weak ot, for which it can occur that any of the parties obtains too much information, or the result is incorrect. these bounds and protocols, which correct on previous results by damgård et. al., are of central interest since in most known realizations of ot from weak primitives, such as noisy channels, a weak ot is constructed first.finally, we carry over our results to the computational setting and show how a weak ot that is sometimes incorrect and is only mildly secure against computationally bounded adversaries can be strengthened.
generic and practical resettable zero-knowledge in the bare public-key model. we present a generic construction for constant-round concurrsound resettable zero-knowledge (rzk-cs) arguments for $\mathcal{np}$ in the bare public-key (bpk) model under any (sub-exponentially strong) one-way function (owf), which is a traditional assumption in this area. the generic construction in turn allows round-optimal implementation for $\mathcal{np}$ still under general assumptions, and can be converted into a highly practical instantiation (under specific number-theoretic assumptions) for any language admitting σ-protocols. further, the rzk-cs arguments developed in this work also satisfy a weak (black-box) concurrent knowledge-extractability property as proofs of knowledge, in which case some super-polynomial-time assumption is intrinsic.
efficient two party and multi party computation against covert adversaries. recently, aumann and lindell introduced a new realistic security model for secure computation, namely, security against covert adversaries. the main motivation was to obtain secure computation protocols which are efficient enough to be usable in practice. aumann and lindell presented an efficient two party computation protocol secure against covert adversaries. they were able to utilize cut and choose techniques rather than relying on expensive zero knowledge proofs. in this paper, we design an efficient multi-party computation protocol in the covert adversary model which remains secure even if a majority of the parties are dishonest. we also substantially improve the two-party protocol of aumann and lindell. our protocols avoid general np-reductions and only make a black box use of efficiently implementable cryptographic primitives. our two-party protocol is constant-round while the multi-party one requires a logarithmic (in number of parties) number of rounds of interaction between the parties. our protocols are secure as per the standard simulation-based definitions of security. although our main focus is on designing efficient protocols in the covert adversary model, the techniques used in our two party case directly generalize to improve the efficiency of two party computation protocols secure against standard malicious adversaries.
finding preimages in full md5 faster than exhaustive search. in this paper, we present the first cryptographic preimage attack on the full md5 hash function. this attack, with a complexity of 2116.9, generates a pseudo-preimage of md5 and, with a complexity of 2123.4, generates a preimage of md5. the memory complexity of the attack is 245 ×11 words. our attack is based on splice-and-cut and local-collision techniques that have been applied to step-reduced md5 and other hash functions. we first generalize and improve these techniques so that they can be more efficiently applied to many hash functions whose message expansions are a permutation of message-word order in each round. we then apply these techniques to md5 and optimize the attack by considering the details of md5 structure.
zero knowledge and soundness are symmetric. we give a complexity-theoretic characterization of the class of problems in np having zero-knowledge argument systems. this characterization is symmetric in its treatment of the zero knowledge and the soundness conditions, and thus we deduce that the class of problems in np ¿ conp having zero-knowledge arguments is closed under complement. furthermore, we show that a problem in np has a statistical zero-knowledge argument system if and only if its complement has a computational zero-knowledge proof system. what is novel about these results is that they are unconditional, i.e., do not rely on unproven complexity assumptions such as the existence of one-way functions.our characterization of zero-knowledge arguments also enables us to prove a variety of other unconditional results about the class of problems in np having zero-knowledge arguments, such as equivalences between honest-verifier and malicious-verifier zero knowledge, private coins and public coins, inefficient provers and efficient provers, and non-black-box simulation and black-box simulation. previously, such results were only known unconditionally for zero-knowledge proof systems, or under the assumption that one-way functions exist for zero-knowledge argument systems.
breaking rsa generically is equivalent to factoring. we show that a generic ring algorithm for breaking rsa in ¿ n can be converted into an algorithm for factoring the corresponding rsa-modulus n. our results imply that any attempt at breaking rsa without factoring n will be non-generic and hence will have to manipulate the particular bit-representation of the input in ¿ n . this provides new evidence that breaking rsa may be equivalent to factoring the modulus.
efficient two-party secure computation on committed inputs. we present an efficient construction of yao's "garbled circuits" protocol for securely computing any two-party circuit on committed inputs. the protocol is secure in a universally composable way in the presence of malicious adversaries under the decisional composite residuosity (dcr) and strong rsa assumptions, in the common reference string model. the protocol requires a constant number of rounds (four-five in the standard model, two-three in the random oracle model, depending on whether both parties receive the output), o(|c|) modular exponentiations per player, and a bandwidth of o(|c|) group elements, where |c| is the size of the computed circuit.our technical tools are of independent interest. we propose a homomorphic, semantically secure variant of the camenisch-shoup verifiable cryptosystem, which uses shorter keys, is unambiguous (it is infeasible to generate two keys which successfully decrypt the same ciphertext), and allows efficient proofs that a committed plaintext is encrypted under a committed key.our second tool is a practical four-round (two-round in rom) protocol for committed oblivious transfer on strings (string-cot) secure against malicious participants. the string-cot protocol takes a few exponentiations per player, and is uc-secure under the dcr assumption in the common reference string model. previous protocols of comparable efficiency achieved either committed ot on bits, or standard (non-committed) ot on strings.
chosen-prefix collisions for md5 and colliding x.509 certificates for different identities. we present a novel, automated way to find differential paths for md5. as an application we have shown how, at an approximate expected cost of 250 calls to the md5 compression function, for any two chosen message prefixes p and p¿, suffixes s and s¿ can be constructed such that the concatenated values p||s and p¿||s¿ collide under md5. although the practical attack potential of this construction of chosen-prefix collisions is limited, it is of greater concern than random collisions for md5. to illustrate the practicality of our method, we constructed two md5 based x.509 certificates with identical signatures but different public keys and different distinguished name fields, whereas our previous construction of colliding x.509 certificates required identical name fields. we speculate on other possibilities for abusing chosen-prefix collisions. more details than can be included here can be found on www.win.tue.nl/hashclash/chosenprefixcollisions/ .
on the security of padding-based encryption schemes - or - why we cannot prove oaep secure in the standard model. we investigate the security of "padding-based" encryption schemes in the standard model. this class contains all public-key encryption schemes where the encryption algorithm first applies some invertible public transformation to the message (the "padding"), followed by a trapdoor permutation. in particular, this class contains oaep and its variants.our main result is a black-box impossibility result showing that one cannot prove any such padding-based scheme chosen-ciphertext secure even assuming the existence of ideal trapdoor permutations. the latter is a strong ideal abstraction of trapdoor permutations which inherits all security properties of uniform random permutations.
the collision intractability of mdc-2 in the ideal-cipher model. we provide the first proof of security for mdc-2, the most well-known construction for turning an n-bit blockcipher into a 2n-bit cryptographic hash function. our result, which is in the ideal-cipher model, shows that mdc-2, when built from a blockcipher having blocklength and keylength n, has security much better than that delivered by any hash function that has an n-bit output. when the blocklength and keylength are n = 128 bits, as with mdc-2 based on aes-128, an adversary that asks fewer than 274.9 queries usually cannot find a collision.