waashk/dblp huggingface dataset:
efficient algorithms for solving overdefined systems of multivariate polynomial equations. the security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. this problem is np-hard over any field. when the number of equations m is the same as the number of unknowns n the best known algorithms are exhaustive search for small fields, and a gröbner base algorithm for large fields. gröbner base algorithms have large exponential complexity and cannot solve in practice systems with n ≥ 15. kipnis and shamir [9] have recently introduced a new algorithm called "relinearization". the exact complexity of this algorithm is not known, but for sufficiently overdefined systems it was expected to run in polynomial time. in this paper we analyze the theoretical and practical aspects of relinearization. we ran a large number of experiments for various values of n and m, and analysed which systems of equations were actually solvable. we show that many of the equations generated by relinearization are linearly dependent, and thus relinearization is less efficient that one could expect. we then develop an improved algorithm called xl which is both simpler and more powerful than relinearization. for all 0 < ∈ ≤ 1/2, and m ≥ ∈n2, xl and relinearization are expected to run in polynomial time of approximately no(1/√ɛ). moreover, we provide strong evidence that relinearization and xl can solve randomly generated systems of polynomial equations in subexponential time when m exceeds n by a number that increases slowly with n.
construction of t-resilient functions over a finite alphabet. we extend the notions of correlation-immune functions and resilient functions to functions over any finite alphabet endowed with the structure of an abelian group. thus we generalize the results of gopalakrishnan and stinson as we give an orthogonal array characterization and a fourier transform characterization for resilient functions over any finite alphabet. this leads to a generalization of some related cryptographic objects as perfect local randomizers. it also enables us to construct new resilient functions by composition of resilient functions of smaller order.
algebraic attacks on stream ciphers with linear feedback. a classical construction of stream ciphers is to combine several lfsrs and a highly non-linear boolean function f. their security is usually analysed in terms of correlation attacks, that can be seen as solving a system of multivariate linear equations, true with some probability. at icisc'02 this approach is extended to systems of higher-degree multivariate equations, and gives an attack in 292 for toyocrypt, a cryptrec submission. in this attack the key is found by solving an overdefined system of algebraic equations. in this paper we show how to substantially lower the degree of these equations by multiplying them by well-chosen multivariate polynomials. thus we are able to break toyocrypt in 249 cpu clocks, with only 20 kbytes of keystream, the fastest attack proposed so far. we also successfully attack the nessie submission lili-128, within 257 cpu clocks (not the fastest attack known). in general, we show that if the boolean function uses only a small subset (e.g. 10) of state/lfsr bits, the cipher can be broken, whatever is the boolean function used (worst case). our new general algebraic attack breaks stream ciphers satisfying all the previously known design criteria in at most the square root of the complexity of the previously known generic attack.
the knapsack hash function proposed at crypto'89 can be broken. ivan damgård [4] suggested at crypto'89 concrete examples of hash functions among which a knapsack scheme. we will here show that a probabilistic algorithm can break this scheme with a number in the region of 232 computations. that number of operations is feasible in realistic time with modern computers. thus the proposed hash function is not very secure. among those computations a substantial number can be performed once for all. a faster result can be obtained since parallelism is easy. moreover, ways to extend the present algorithm to other knapsacks than the present (256, 128) suggested by damgård are investigated.
fast and secure immunization against adaptive man-in-the-middle impersonation. we present a simple method for constructing identification schemes resilient against impersonation and man-in-the-middle attacks. though zero-knowledge or witness hiding protocols are known to withstand attacks of the first kind, all such protocols previously proposed suffer from a weakness observed by bengio et al.: a malicious verifier may simply act as a moderator between the prover and yet another verifier, thus enabling the malicious verifier to pass as the prover. we exhibit a general class of identification schemes that can be efficiently and securely tranformed into identification schemes withstanding an adaptive man-in-the-middle attacker. the complexity of the resulting (witness hiding) schemes is roughly twice that of the originals. basically, any three-move, public coin identification scheme that is zero knowledge against the honest verifier and that is secure against passive impersonation attacks, is eligible for our transformation. this indicates that we need only seemlingly weak cryptographic intractability assumptions to construct a practical identification scheme resisting adative man-in-the-middle impersonation attacks. moreover, the required primitive protocols can efficiently be constructed under the factoring or discrete logarithm assumptions.
efficient multiparty computations secure against an adaptive adversary. we consider verifiable secret sharing (vss) and multiparty computation (mpc) in the secure-channels model, where a broadcast channel is given and a non-zero error probability is allowed. in this model rabin and ben-or proposed vss and mpc protocols secure against an adversary that can corrupt any minority of the players. in this paper, we first observe that a subprotocol of theirs, known as weak secret sharing (wss), is not secure against an adaptive adversary, contrary to what was believed earlier. we then propose new and adaptively secure protocols for wss, vss and mpc that are substantially more efficient than the original ones. our protocols generalize easily to provide security against general q2-adversaries.
exposure-resilient functions and all-or-nothing transforms. we study the problem of partial key exposure. standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. we show how to build cryptographic primitives that remain secure even when an adversary is able to learn almost all of the secret key. the key to our approach is a new primitive of independent interest, which we call an exposure-resilient function (erf) - a deterministic function whose output appears random (in a perfect, statistical or computational sense) even if almost all the bits of the input are known. erf's by themselves efficiently solve the partial key exposure problem in the setting where the secret is simply a random value, like in private-key cryptography. they can also be viewed as very secure pseudorandom generators, and have many other applications. to solve the general partial key exposure problem, we use the (generalized) notion of an all-or-nothing transform (aont), an invertible (randomized) transformation t which, nevertheless, reveals "no information" about x even if almost all the bits of t(x) are known. by applying an aont to the secret key of any cryptographic system, we obtain security against partial key exposure. to date, the only known security analyses of aont candidates were made in the random oracle model. we show how to construct erf's and aont's with nearly optimal parameters. our computational constructions are based on any one-way function. we also provide several applications and additional properties concerning these notions.
general secure multi-party computation from any linear secret-sharing scheme. we show that verifiable secret sharing (vss) and secure multi-party computation (mpc) among a set of n players can efficiently be based on any linear secret sharing scheme (lsss) for the players, provided that the access structure of the lsss allows mpc or vss at all. because an lsss neither guarantees reconstructability when some shares are false, nor verifiability of a shared value, nor allows for the multiplication of shared values, an lsss is an apparently much weaker primitive than vss or mpc. our approach to secure mpc is generic and applies to both the information-theoretic and the cryptographic setting. the construction is based on 1) a formalization of the special multiplicative property of an lsss that is needed to perform a multiplication on shared values, 2) an efficient generic construction to obtain from any lsss a multiplicative lsss for the same access structure, and 3) an efficient generic construction to build verifiability into every lsss (always assuming that the adversary structure allows for mpc or vss at all). the protocols are efficient. in contrast to all previous information-theoretically secure protocols, the field size is not restricted (e.g, to be greater than n). moreover, we exhibit adversary structures for which our protocols are polynomial in n while all previous approaches to mpc for non-threshold adversaries provably have super-polynomial complexity.
an efficient public key cryptosystem secure against adaptive chosen ciphertext attack. this paper proposes a simple threshold public-key cryptosystem (pkc) which is secure against adaptive chosen ciphertext attack, under the decisional diffie-hellman (ddh) intractability assumption. previously, it was shown how to design non-interactive threshold pkc secure under chosen ciphertext attack, in the random-oracle model and under the ddh intractability assumption [25]. the random-oracle was used both in the proof of security and to eliminate interaction. general completeness results for multi-party computations [6,13] enable in principle converting any single server pkc secure against cca (e.g., [19,17]) into a threshold one, but the conversions are inefficient and require much interaction among the servers for each ciphertext decrypted. the recent work by cramer and shoup [17] on single server pkc secure against adaptive cca is the starting point for the new proposal.
a forward-secure public-key encryption scheme. cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. in an effort to mitigate the damage caused by exposure of secret data (e.g., keys) stored on such devices, the paradigm of forward security was introduced. in a forward-secure scheme, secret keys are updated at regular periods of time; furthermore, exposure of a secret key corresponding to a given time period does not enable an adversary to "break" the scheme (in the appropriate sense) for any prior time period. a number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known. we present the first constructions of a (non-interactive) forward-secure public-key encryption scheme. our main construction achieves security against chosen plaintext attacks under the decisional bilinear diffie-hellman assumption in the standard model. it is practical, and all complexity parameters grow at most logarithmically with the total number of time periods. the scheme can also be extended to achieve security against chosen ciphertext attacks.
efficient multi-party computation over rings. secure multi-party computation (mpc) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. however, all current techniques for secure mpc apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. we are motivated by two limitations of these techniques: - generality. existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). - efficiency. the best known constant-round protocols do not efficiently scale even to the case of large finite fields. our contribution goes in these two directions. first, we propose a basis for unconditionally secure mpc over an arbitrary finite ring, an algebraic object with a much less nice structure than a field, and obtain efficient mpc protocols requiring only a black-box access to the ring operations and to random ring elements. second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. we demonstrate the usefulness of the above results by presenting a novel application of mpc over (non-field) rings to the round-efficient secure computation of the maximum function.
multi-autority secret-ballot elections with linear work. we present new cryptographic protocols for multiauthority secret ballot elections that guarantee privacy, robustness, and universal verifiability. application of some novel techniques, in particular the construction of witness hiding/indistinguishable protocols from cramer, damgård and schoenmakers, and the verifiable secret sharing scheme of pedersen, reduce the work required by the voter or an authority to a linear number of cryptographic operations in the population size (compared to quadratic in previous schemes). thus we get significantly closer to a practical election scheme.
a secure and optimally efficient multi-authority election scheme. in this paper we present a new multi-authority secret-ballot election scheme that guarantees privacy, universal verifiability, and robustness. it is the first scheme for which the performance is optimal in the sense that time and communication complexity is minimal both for the individual voters and the authorities. an interesting property of the scheme is that the time and communication complexity for the voter is independent of the number of authorities. a voter simply posts a single encrypted message accompanied by a compact proof that it contains a valid vote. our result is complementary to the result by cramer, franklin, schoenmakers, and yung in the sense that in their scheme the work for voters is linear in the number of authorities but can be instantiated to yield information-theoretic privacy, while in our scheme the voter's effort is independent of the number of authorities but always provides computational privacy-protection. we will also point out that the majority of proposed voting schemes provide computational privacy only (often without even considering the lack of information-theoretic privacy), and that our new scheme is by far superior to those schemes.
on the limitations of universally composable two-party computation without set-up assumptions. the recently proposed universally composable (uc) security framework, for analyzing security of cryptographic protocols, provides very strong security guarantees. in particular, a protocol proven secure in this framework is guaranteed to maintain its security even when deployed in arbitrary multi-party, multi-protocol, multi-execution environments. protocols for securely carrying out essentially any cryptographic task in a universally composable way exist, both in the case of an honest majority (in the plain model, i.e., without set-up assumptions) and in the case of no honest majority (in the common reference string model). however, in the plain model, little was known for the case of no honest majority and, in particular, for the important special case of two-party protocols. we study the feasibility of universally composable two-party function evaluation in the plain model. our results show that very few functions can be computed in this model so as to provide the uc security guarantees. specifically, for the case of deterministic functions, we provide a full characterization of the functions computable in this model. (essentially, these are the functions that depend on at most one of the parties' inputs, and furthermore are "efficiently invertible" in a sense defined within.) for the case of probabilistic functions, we show that the only functions computable in this model are those where one of the parties can essentially uniquely determine the joint output.
efficient communication-storage tradeoffs for multicast encryption. we consider re-keying protocols for secure multicasting in a dynamic multicast group with a center. there is a variety of different scenarios using multicast, presenting a wide range of efficiency requirements with respect to several parameters. we give an upper bound on the tradeoff between storage and communication parameters. in particular, we suggest an improvement of the schemes by wallner et al. and wong et al. [13,14] with sub-linear center storage, without a significant loss in other parameters. correctly selecting the parameters of our scheme we can efficiently accommodate a wide range of scenarios. this is demonstrated by applying the protocol to some known benchmark scenarios. we also show lower bounds on the tradeoff between communication and user storage, and show that our scheme is almost optimal with respect to these lower bounds.
efficient cryptographic protocols based on noisy channels. the wire-tap channel of wyner [19] shows that a binary symmetric channel may be used as a basis for exchanging a secret key, in a cryptographic scenario of two honest people facing an eavesdropper. later crépeau and kilian [9] showed how a bsc may be used to implement oblivious transfer in a cryptographic scenario of two possibly dishonest people facing each other. unfortunately this result is rather impractical as it requires ω(n11) bits to be transmitted through the bsc to accomplish a single ot. the current paper provides efficient protocols to achieve the cryptographic primitives of bit commitment and oblivious transfer based on the existence of a binary symmetric channel. our protocols respectively require sending o(n) and o(n3) bits through the bsc. these results are based on a technique known as generalized privacy amplification [1] that allow two people to extract secret information from partially compromised data.
propagation characteristics and correlation-immunity of highly nonlinear boolean functions. we investigate the link between the nonlinearity of a boolean function and its propagation characteristics. we prove that highly nonlinear functions usually have good propagation properties regarding different criteria. conversely, any boolean function satisfying the propagation criterion with respect to a linear subspace of codimension 1 or 2 has a high nonlinearity. we also point out that most highly nonlinear functions with a three-valued walsh spectrum can be transformed into 1-resilient functions.
improved fast correlation attacks using parity-check equations of weight 4 and 5. this paper describes new techniques for fast correlation attacks, based on gallager iterative decoding algorithm using parity-check equations of weight greater than 3. these attacks can be applied to any key-stream generator based on lfsrs and it does not require that the involved feedback polynomial have a low weight. we give a theoretical analysis of all fast correlation attacks, which shows that our algorithm with parity-check equations of weight 4 or 5 is usually much more efficient than correlation attacks based on convolutional codes or on turbo codes. simulation results confirm the validity of this comparison. in this context, we also point out the major role played by the nonlinearity of the boolean function used in a combination generator.
on the reversibility of oblivious transfer. a(2 1)-ot2, (one-out-of-two bit oblivious transfer) is a technique by which a party s owning two secret bits b0, b1, can transfer one of them bc, to another party r, who chooses c. this is done in a way that does not release any bias about bt to r nor any bias about c to s. how can one build a 2to-(2 1) ((2 1)-ot2 from r to s) given a (2 1)-ot2, (from s to r)? this question is interesting because in many scenarios, one of the two parties will be much more powerful than the other. in the current paper we answer this question and show a number of related extensions. one interesting extension of this transfer is the (2 1)-ot2k (one-out-of-two string o.t.) in which the two secrets q0, q1 are elements of gfk(2) instead of bits. we show that 2kto-(2 1) can be obtained at about the same cost as (2 1)-ot2k, in terms of number of calls to (2 1)-ot2.
quantum oblivious mutual identification. we consider a situation where two parties, alice and bob, share a common secret string and would like to mutually check their knowledge of that string. we describe a simple and efficient protocol based on the exchange of quantum information to check mutual knowledge of a common string in such a way that honest parties will always succeed in convincing each other, while a dishonest party interacting with an honest party will have vanishingly small probability of convincing him. moreover, a dishonest party gains only a very small amount of information about the secret string from running the protocol: whoever enters the protocol with no knowledge of the secret string would have to enter this protocol an exponential number of times in order to gain non-negligible information about the string. our scheme offers an efficient identification technique with a security that depends on no computational assumption, only on the correctness of quantum mechanics. we believe such a system should be used in smartcards to avoid frauds from typing pin codes to dishonest teller machines.
more correlation-immune and resilient functions over galois fields and galois rings. we show that the usual constructions of bent functions, when they are suitably modified, allow constructions of correlation-immune and resilient functions over galois fields and, in some cases, over galois rings.
recycling random bits in composed perfect zero-knowledge. in this paper we give techniques for recycling random bits both in the interactive and in the non-interactive model for perfect zero-knowledge proofs. our first result is a non-interactive perfect zero-knowledge proof system for proving that at least one out of any given polynomial number of statements is true, in which the amount of public random bits used is the same as that for proving a single statement. our second result is an interactive perfect zero-knowledge proof system for proving any given polynomial number of statements, in which the amount of private random bits used by the prover is, apart from a constant factor, the same as that for proving a single statement. in order to get a randomness-efficient proof system, we also reduce the random string of the verifier by using a multi-bit commitment scheme. the statements considered are of quadratic non residuosity modulo a blum integer.
computing inverses over a shared secret modulus. we discuss the following problem: given an integer φ shared secretly among n players and a prime number e, how can the players efficiently compute a sharing of e-1 mod φ. the most interesting case is when φ is the euler function of a known rsa modulus n, φ = φ(n). the problem has several applications, among which the construction of threshold variants for two recent signature schemes proposed by gennaro-halevi-rabin and cramer-shoup. we present new and efficient protocols to solve this problem, improving over previous solutions by boneh-franklin and frankel et al. our basic protocol (secure against honest but curious players) requires only two rounds of communication and a single gcd computation. the robust protocol (secure against malicious players) adds only a couple of rounds and a few modular exponentiations to the computation.