waashk/dblp huggingface dataset:
efficient secure linear algebra in the presence of covert or computationally unbounded adversaries. in this work we study the design of secure protocols for linear algebra problems. all current solutions to the problem are either inefficient in terms of communication complexity or assume that the adversary is honest but curious. we design protocols for two different adversarial settings: first, we achieve security in the presence of a covert adversary, a notion recently introduced by [aumann and lindell, tcc 2007]. roughly speaking, this guarantees that if the adversary deviates from the protocol in a way that allows him to cheat, then he will be caught with good probability. second, we achieve security against arbitrary malicious behaviour in the presence of a computationally unbounded adversary that controls less than a third of the parties. our main result is a new upper bound of o(n 2 + 1/t ) communication for testing singularity of a shared n ×n matrix in constant round, for any constant t in both of these adversarial environments. we use this construction to design secure protocols for computing the rank of a shared matrix and solving a shared linear system of equations with similar efficiency.we use different techniques from computer algebra, together with recent ideas from [cramer, kiltz, and padró, crypto 2007], to reduce the problem of securely deciding singularity to the problem of securely computing matrix product. we then design new and efficient protocols for secure matrix product in both adversarial settings. in the two-party setting, we combine cut-and-choose techniques on random additive decomposition of the input, with a careful use of the random strings of a homomorphic encryption scheme to achieve simulation-based security. thus, our protocol avoids general zero-knowledge proofs and only makes a black-box use of a homomorphic encryption scheme.
cryptanalysis of minrank. in this paper, we investigate the difficulty of one of the most relevant problems in multivariate cryptography --- namely minrank --- about which no real progress has been reported since [9, 19]. our starting point is the kipnis-shamir attack [19]. we first show new properties of the ideal generated by kipnis-shamir's equations. we then propose a new modeling of the problem. concerning the practical resolution, we adopt a gröbner basis approach that permitted us to actually solve challenges a and b proposed by courtois in [8]. using the multi-homogeneous structure of the algebraic system, we have been able to provide a theoretical complexity bound reflecting the practical behavior of our approach. namely, when r ¿ the dimension of the matrices minus the rank of the target matrix in the minrank problem is constant, then we have a polynomial time attack $\mathcal{o}\left( \ln\left( q\right) \,n^{3\,r^{\prime2}}\right) $. for the challenge c [8], we obtain a theoretical bound of 266.3 operations.
on expected constant-round protocols for byzantine agreement. in a seminal paper, feldman and micali show an n-party byzantine agreement protocol in the plain model that tolerates t
hash functions and the (amplified) boomerang attack. since crypto 2004, hash functions have been the target of many attacks which showed that several well-known functions such as sha-0 or md5 can no longer be considered secure collision free hash functions. these attacks use classical cryptographic techniques from block cipher analysis such as differential cryptanalysis together with some specific methods. among those, we can cite the neutral bits of biham and chen or the message modification techniques of wang et al. in this paper, we show that another tool of block cipher analysis, the boomerang attack, can also be used in this context. in particular, we show that using this boomerang attack as a neutral bits tool, it becomes possible to lower the complexity of the attacks on sha-1.
pirate evolution: how to make the most of your traitor keys. we introduce a novel attack concept against trace and revoke schemes called pirate evolution. in this setting, the attacker, called an evolving pirate, is handed a number of traitor keys and produces a number of generations of pirate decoders that are successively disabled by the trace and revoke system. a trace and revoke scheme is susceptible to pirate evolution when the number of decoders that the evolving pirate produces exceeds the number of traitor keys that were at his possession. pirate evolution can threaten trace and revoke schemes even in cases where both the revocation and traceability properties are ideally satisfied: this is because pirate evolution may enable an attacker to "magnify" an initial key-leakage incident and exploit the traitor keys available to him to produce a great number of pirate boxes that will take a long time to disable. even moderately successful pirate evolution affects the economics of deployment for a trace and revoke system and thus it is important that it is quantified prior to deployment. in this work, we formalize the concept of pirate evolution and we demonstrate the susceptibility of the trace and revoke schemes of naor, naor and lotspiech (nnl) from crypto 2001 to an evolving pirate that can produce up to t ċ log n generations of pirate decoders given an initial set of t traitor keys. this is particularly important in the context of aacs, the new standard for high definition dvds (hd-dvd and blue-ray) that employ the subset difference method of nnl: for example using our attack strategy, a pirate can potentially produce more than 300 pirate decoder generations by using only 10 traitor keys, i.e., key-leakage incidents in aacs can be substantially magnified.
adaptive one-way functions and applications. we introduce new and general complexity theoretic hardness assumptions. these assumptions abstract out concrete properties of a random oracle and are significantly stronger than traditional cryptographic hardness assumptions; however, assuming their validity we can resolve a number of long-standing open problems in cryptography.
full key-recovery attacks on hmac/nmac-md4 and nmac-md5. at crypto '06, bellare presented new security proofs for hmac and nmac, under the assumption that the underlying compression function is a pseudo-random function family. conversely, at asiacrypt '06, contini and yin used collision techniques to obtain forgery and partial key-recovery attacks on hmac and nmac instantiated with md4, md5, sha-0 and reduced sha-1. in this paper, we present the first full key-recovery attacks on nmac and hmac instantiated with a real-life hash function, namely md4. our main result is an attack on hmac/nmac-md4 which recovers the full mac secret key after roughly 288 mac queries and 295 md4 computations. we also extend the partial key-recovery contini-yin attack on nmac-md5 (in the related-key setting) to a full key-recovery attack. the attacks are based on generalizations of collision attacks to recover a secret iv, using new differential paths for md4.
how many oblivious transfers are needed for secure multiparty computation? oblivious transfer (ot) is an essential building block for secure multiparty computation when there is no honest majority. in this setting, current protocols for n ≥ 3 parties require each pair of parties to engage in a single ot for each gate in the circuit being evaluated. since implementing ot typically requires expensive public-key operations (alternatively, expensive setup or physical infrastructure), minimizing the number of ots is a highly desirable goal. in this work we initiate a study of this problem in both an information-theoretic and a computational setting and obtain the following results. - if the adversary can corrupt up to t = (1 - ɛ)n parties, where ɛ ≥ 0 is an arbitrarily small constant, then a total of o(n) ot channels between pairs of parties are necessary and sufficient for general secure computation. combined with previous protocols for "extending ots", o(nk) invocations of ot are sufficient for computing arbitrary functions with computational security, where k is a security parameter. - the above result does not improve over the previous state of the art in the important case where t = n - 1, when the number of parties is small, or in the information-theoretic setting. for these cases, we show that an arbitrary function f : {0, 1}n → {0, 1}* can be securely computed by a protocol which makes use of a single ot (of strings) between each pair of parties. this result is tight in the sense that at least one ot between each pair of parties is necessary in these cases. a major disadvantage of this protocol is that its communication complexity grows exponentially with n. we present natural classes of functions f for which this exponential overhead can be avoided.
indistinguishability amplification. many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. this paper presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, assuming upper bounds of certain types for the component systems. for a general type of combination operation of systems, including the xor of functions or the cascade of permutations, we prove two amplification theorems. the first is a product theorem, in the spirit of xor-lemmas: the distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. this bound is optimal. the second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers. a key technical tool of the paper is the proof of a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of winning an appropriately defined game.
domain extension of public random functions: beyond the birthday barrier. a public random function is a random function that is accessible by all parties, including the adversary. for example, a (public) random oracle is a public random function {0,1}* → {0,1}n. the natural problem of constructing a public random oracle from a public random function {0, 1}m → {0, 1}n (for some m > n) was first considered at crypto 2005 by coron et al. who proved the security of variants of the merkle-damgård construction against adversaries issuing up to o(2n/2) queries to the construction and to the underlying compression function. this bound is less than the square root of n2m, the number of random bits contained in the underlying random function. in this paper, we investigate domain extenders for public random functions approaching optimal security. in particular, for all ɛ ∈ (0, 1) and all functions m and l (polynomial in n), we provide a construction cɛ,m,l(ċ) which extends a public random function r : {0, 1}n → {0, 1}n to a function cɛ,m,l(r) : {0, 1}m(n) → {0, 1}l(n) with time-complexity polynomial in n and 1/ɛ and which is secure against adversaries which make up to θ(2n(1-ɛ)) queries. a central tool for achieving high security are special classes of unbalanced bipartite expander graphs with small degree. the achievability of practical (as opposed to complexity-theoretic) efficiency is proved by a non-constructive existence proof. combined with the iterated constructions of coron et al., our result leads to the first iterated construction of a hash function {0, 1}* → {0, 1}n from a component function {0, 1}n → {0, 1}n that withstands all recently proposed generic attacks against iterated hash functions, like joux's multi-collision attack, kelsey and schneier's second-preimage attack, and kelsey and kohno's herding attacks.
random oracles and auxiliary input. we introduce a variant of the random oracle model where oracle-dependent auxiliary input is allowed. in this setting, the adversary gets an auxiliary input that can contain information about the random oracle. using simple examples we show that this model should be preferred over the classical variant where the auxiliary input is independent of the random oracle. in the presence of oracle-dependent auxiliary input, the most important proof technique in the random oracle model--lazy sampling--does not apply directly. we present a theorem and a variant of the lazy sampling technique that allows one to perform proofs in the new model almost as easily as in the old one. as an application of our approach and to illustrate how existing proofs can be adapted, we prove that rsa-oaep is ind-cca2 secure in the random oracle model with oracle-dependent auxiliary input.
the random oracle model and the ideal cipher model are equivalent. the random oracle model and the ideal cipher model are two well known idealised models of computation for proving the security of cryptosystems. at crypto 2005, coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. the other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. in this paper we solve this open problem and show that the feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. this contrasts with the classical luby-rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.
a hybrid lattice-reduction and meet-in-the-middle attack against ntru. to date the ntruencrypt security parameters have been based on the existence of two types of attack: a meet-in-the-middle attack due to odlyzko, and a conservative extrapolation of the running times of the best (known) lattice reduction schemes to recover the private key. we show that there is in fact a continuum of more efficient attacks between these two attacks. we show that by combining lattice reduction and a meet-in-the-middle strategy one can reduce the number of loops in attacking the ntruencrypt private key from 284.2 to 260.3, for the k = 80 parameter set. in practice the attack is still expensive (dependent on ones choice of cost-metric), although there are certain space/time tradeoffs that can be applied. asymptotically our attack remains exponential in the security parameter k, but it dictates that ntruencrypt parameters must be chosen so that the meet-in-the-middle attack has complexity 2k even after an initial lattice basis reduction of complexity 2k.
reducing trust in the pkg in identity based cryptosystems. one day, you suddenly find that a private key corresponding to your identity is up for sale at e-bay. since you do not suspect a key compromise, perhaps it must be the pkg who is acting dishonestly and trying to make money by selling your key. how do you find out for sure and even prove it in a court of law? this paper introduces the concept of traceable identity based encryption which is a new approach to mitigate the (inherent) key escrow problem in identity based encryption schemes. our main goal is to restrict the ways in which the pkg can misbehave. in our system, if the pkg ever maliciously generates and distributes a decryption key for an identity, it runs the risk of being caught and prosecuted. in contrast to other mitigation approaches, our approach does not require multiple key generation authorities.
chernoff-type direct product theorems. consider a challenge-response protocol where the probability of a correct response is at least &#x03b1; for a legitimate user and at most &#x03b2;<&#x03b1; for an attacker. one example is a captcha challenge, where a human should have a significantly higher chance of answering a single challenge (e.g., uncovering a distorted letter) than an attacker; another example is an argument system without perfect completeness. a natural approach to boost the gap between legitimate users and attackers is to issue many challenges and accept if the response is correct for more than a threshold fraction, for the threshold chosen between &#x03b1; and &#x03b2;. we give the first proof that parallel repetition with thresholds improves the security of such protocols. we do this with a very general result about an attacker&#x2019;s ability to solve a large fraction of many independent instances of a hard problem, showing a chernoff-like convergence of the fraction solved incorrectly to the probability of failure for a single instance.
how should we solve search problems privately? secure multiparty computation allows a group of distrusting parties to jointly compute a (possibly randomized) function of their inputs. however, it is often the case that the parties executing a computation try to solve a search problem, where one input may have a multitude of correct answers - such as when the parties compute a shortest path in a graph or find a solution to a set of linear equations. picking one output arbitrarily from the solution set has significant implications on the privacy of the algorithm. beimel et al. [stoc 2006] gave a minimal definition for private computation of search problems with focus on proving impossibility result. in this work we aim for stronger definitions of privacy for search problems that provide reasonable privacy. we give two alternative definitions and discuss their privacy guarantees. we also supply algorithmic machinery for designing such protocols for a broad selection of search problems.
a security analysis of the nist sp 800-90 elliptic curve random number generator. an elliptic curve random number generator (ecrng) has been approved in a nist standard and proposed for ansi and secg draft standards. this paper proves that, if three conjectures are true, then the ecrng is secure. the three conjectures are hardness of the elliptic curve decisional diffie-hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem. the x-logarithm problem is shown to be hard if the decisional diffie-hellman problem is hard, although the reduction is not tight. the truncated point problem is shown to be solvable when the minimum amount of bits allowed in nist standards are truncated, thereby making it insecure for applications such as stream ciphers. nevertheless, it is argued that for nonce and key generation this distinguishability is harmless.
a note on secure computation of the moore-penrose pseudoinverse and its application to secure linear algebra. this work deals with the communication complexity of secure multi-party protocols for linear algebra problems. in our model, complexity is measured in terms of the number of secure multiplications required and protocols terminate within a constant number of rounds of communication. previous work by cramer and damgård proposes secure protocols for solving systems ax = b of m linear equations in n variables over a finite field, with m ≤ n. the complexity of those protocols is n5. we show a new upper bound of m4 + n2m secure multiplications for this problem, which is clearly asymptotically smaller. our main point, however, is that the advantage can be substantial in case m is much smaller than n. indeed, if m = √n, for example, the complexity goes down from n5 to n2.5. our secure protocols rely on some recent advances concerning the computation of the moore-penrose pseudo-inverse of matrices over fields of positive characteristic. these computations are based on the evaluation of a certain characteristic polynomial, in combination with variations on a well-known technique due to mulmuley that helps to control the effects of non-zero characteristic. we also introduce a new method for secure polynomial evaluation that exploits properties of chebychev polynomials, as well as a new secure protocol for computing the characteristic polynomial of a matrix based on leverrier's lemma that exploits this new method.
bug attacks. in this paper we present a new kind of cryptanalytic attack which utilizes bugs in the hardware implementation of computer instructions. the best known example of such a bug is the intel division bug, which resulted in slightly inaccurate results for extremely rare inputs. whereas in most applications such bugs can be viewed as a minor nuisance, we show that in the case of rsa (even when protected by oaep), pohlig-hellman, elliptic curve cryptography, and several other schemes, such bugs can be a security disaster: decrypting ciphertexts on any computer which multiplies even one pair of numbers incorrectly can lead to full leakage of the secret key, sometimes with a single well-chosen ciphertext.
pictorial recognition using affine-invariant spectral signatures. this paper describes an efficient approach to pose invariant object recognition employing pictorial recognition of image patches. a complete affine invariance is achieved by a representation which is based on a new sampling configuration in the frequency domain. employing singular value decomposition (svd), the affine transform is decomposed into slant, tilt, swing, scale and 2d translation. from this decomposition, we derive an affine invariant representation that allows to recognize image patches that correspond to object surfaces which are roughly planar -- invariant to their pose in space. the representation is in the form of spectral signatures that are derived from a set of cartesian logarithmic-logarithmic (log-log) sampling configuration in the frequency domain. unlike previous log-polar representations which are not invariant to slant (i.e. foreshortening only in one direction), our new configuration yields complete affine invariance. the proposed log-log configuration can be employed both globally or locally by a gabor or fourier transforms. local representation enables to recognize separately several objects in the same image. the actual signature recognition is performed by multi-dimensional indexing in a pictorial dataset represented in the frequency domain. the recognition also provides 3d pose information.
novel view synthesis in tensor space. we present a new method for synthesizing novel views of a 3d scene from few model images in full correspondence. the core of this work is the derivation of a tensorial operator that describes the transformation from a given tensor of three views to a novel tensor of a new configuration of three views. by repeated application of the operator on a seed tensor with a sequence of desired virtual camera positions we obtain a chain of warping functions (tensors) from the set of model images to create the desired virtual views.
mdl estimation for small sample sizes and its application to segmenting binary strings. minimum description length (mdl) estimation has proven itself of major importance in a large number of applications many of which are in the fields of computer vision and pattern recognition. a problem is encountered in applying the associated formulas, however, especially those associated with model cost. this is because most of these are asymptotic forms appropriate only for large sample sizes. j. rissanen has recently derived sharper code-length formulas valid for much smaller sample sizes. because of the importance of these results, it is our intent here to present a tutorial description of them. in keeping with this goal we have chosen a simple application whose relative tractability allows it to be explored more deeply than most problems: the segmentation of binary strings based on a piecewise bernoulli assumption. by that we mean that the strings are assumed to be divided into substrings, the bits of which are assumed to have been generated by a single (within a substring) bernoulli source.