waashk/dblp huggingface dataset:
asymptotically good ideal linear secret sharing with strong multiplication over fixed finite field. this work deals with "mpc-friendly" linear secret sharing schemes (lsss), a mathematical primitive upon which secure multi-party computation (mpc) can be based and which was introduced by cramer, damgaard and maurer (eurocrypt 2000). chen and cramer proposed a special class of such schemes that is constructed from algebraic geometry and that enables efficient secure multi-party computation over fixed finite fields (crypto 2006). we extend this in four ways. first, we propose an abstract coding-theoretic framework in which this class of schemes and its (asymptotic) properties can be cast and analyzed. second, we show that for every finite field ${\mathbb f}_q$, there exists an infinite family of lsss over ${\mathbb f}_q$ that is asymptotically good in the following sense: the schemes are "ideal," i.e., each share consists of a single ${\mathbb f}_q$-element, and the schemes have t-strong multiplication on n players, where the corruption tolerance $\frac{3t}{n-1}$ tends to a constant ¿(q) with 0 < ¿(q) < 1 when n tends to infinity. moreover, when $|{\mathbb f}_q|$ tends to infinity, ¿(q) tends to 1, which is optimal. this leads to explicit lower bounds on $\widehat{\tau}(q)$, our measure of asymptotic optimal corruption tolerance. we achieve this by combining the results of chen and cramer with a dedicated field-descent method. in particular, in the ${\mathbb f}_2$-case there exists a family of binary t-strongly multiplicative ideal lsss with $\frac{3t}{n-1}\approx 2.86\%$ when n tends to infinity, a one-bit secret and just a one-bit share for every player. previously, such results were shown for ${\mathbb f}_q$ with q ¿ 49 a square. third, we present an infinite family of ideal schemes with t-strong multiplication that does not rely on algebraic geometry and that works over every finite field ${\mathbb f}_q$. its corruption tolerance vanishes, yet still $\frac{3t}{n-1}= \omega(1/(\log\log n)\log n)$. fourth and finally, we give an improved non-asymptotic upper bound on corruption tolerance.
abstraction in cryptography. abstraction means to eliminate irrelevant details from consideration, thereby focusing only on the relevant aspects of a problem or context. abstraction is of paramount importance in most scientific fields, especially in computer science and mathematics. the purpose of abstraction is to provide, at the same time, simpler definitions, higher generality of results, simpler proofs, improved elegance, and often better didactic suitability.abstraction can be a gradual process and need not be unique, but in many contexts, the highest achievable level of abstraction, once identified, appears natural and stable. for example, the abstract and natural concepts of a group or a field in algebra capture exactly what is required to prove many important results.in the spirit of algebraic abstraction, we advocate the definition and use of higher levels of abstraction in cryptography, with the goal of identifying the highest possible level at which a definition or theorem should be stated and proved. some questions one can ask are: what are abstractions of a system, a game, indistinguishability, a hybrid argument, a reduction, indifferentiability, or of (universal) composability? what are abstractions of efficient and negligible, and at which level of abstraction can computational and information-theoretic models be unified? and, of course: can the abstract viewpoint lead to new concepts and results that are perhaps otherwise missed?
the round complexity of verifiable secret sharing revisited. the round complexity of interactive protocols is one of their most important complexity measures. in this work we prove that existing lower bounds for the round complexity of vss can be circumvented by introducing a negligible probability of error in the reconstruction phase. previous results show matching lower and upper bounds of three rounds for vss, with n = 3t + 1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. in contrast we show that with a negligible probability of error in the reconstruction phase: 1 there exists an efficient 2-round vss protocol for n = 3t + 1. if we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase. 1 there exists an efficient 1-round vss for t = 1 and n > 3. 1 we prove that our results are optimal both in resilience and number of sharing rounds by showing: 1 there does not exist a 2-round wss (and hence vss) for n ≤ 3t. 1 there does not exist a 1-round vss protocol for t ¿ 2 and n ¿ 4.
smooth projective hashing for conditionally extractable commitments. the notion of smooth projective hash functions was proposed by cramer and shoup and can be seen as special type of zero-knowledge proof system for a language. though originally used as a means to build efficient chosen-ciphertext secure public-key encryption schemes, some variations of the cramer-shoup smooth projective hash functions also found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer. in this paper, we first address the problem of building smooth projective hash functions for more complex languages. more precisely, we show how to build such functions for languages that can be described in terms of disjunctions and conjunctions of simpler languages for which smooth projective hash functions are known to exist. next, we illustrate how the use of smooth projective hash functions with more complex languages can be efficiently associated to extractable commitment schemes and avoid the need for zero-knowledge proofs. finally, we explain how to apply these results to provide more efficient solutions to two well-known cryptographic problems: a public-key certification which guarantees the knowledge of the private key by the user without random oracles or zero-knowledge proofs and adaptive security for password-based authenticated key exchange protocols in the universal composability framework with erasures.
how to encipher messages on a small domain. we analyze the security of the thorp shuffle, or, equivalently, a maximally unbalanced feistel network. roughly said, the thorp shuffle on n cards mixes any n 1 ¿ 1/r of them in $o(r\lg n)$ steps. correspondingly, making o(r) passes of maximally unbalanced feistel over an n-bit string ensures cca-security to 2 n(1 ¿ 1/r) queries. our results, which employ markov-chain techniques, enable the construction of a practical and provably-secure blockcipher-based scheme for deterministically enciphering credit card numbers and the like using a conventional blockcipher.
leakage-resilient public-key cryptography in the bounded-retrieval model. we study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ¿. we construct a variety of leakage-resilient public-key systems including the first known identification schemes (id), signature schemes and authenticated key agreement protocols (aka). our main result is an efficient three-round aka in the random-oracle model, which is resilient to key-leakage attacks that can occur prior-to and after a protocol execution. our aka protocol can be used as an interactive encryption scheme with qualitatively stronger privacy guarantees than non-interactive encryption schemes (constructed in prior and concurrent works), which are inherently insecure if the adversary can perform leakage attacks after seing a ciphertext.moreover, our schemes can be flexibly extended to the bounded-retrieval model, allowing us to tolerate very large absolute amount of adversarial leakage ¿ (potentially many gigabytes of information), only by increasing the size of the secret key and without any other loss of efficiency in communication or computation. concretely, given any leakage parameter ¿, security parameter ¿, and any desired fraction 0 < ¿ ≤ 1, our schemes have the following properties: secret key size is ¿(1 + ¿) + o(¿). public key size is o(¿), and independent of ¿. communication complexity is o(¿/¿), and independent of ¿. computation reads o(¿/¿ 2) locations of the secret key, independent of ¿. lastly, we show that our schemes allow for repeated "invisible updates" of the secret key, allowing us to tolerate up to ¿ bits of leakage in between any two updates, and an unlimited amount of leakage overall. these updates require that the parties can securely store a short "master update key" (e.g. on a separate secure device protected against leakage), which is only used for updates and not during protocol execution. the updates are invisible in the sense that a party can update its secret key at any point in time, without modifying the public key or notifying the other users.
computational differential privacy. the definition of differential privacy has recently emerged as a leading standard of privacy guarantees for algorithms on statistical databases. we offer several relaxations of the definition which require privacy guarantees to hold only against efficient--i.e., computationally-bounded--adversaries. we establish various relationships among these notions, and in doing so, we observe their close connection with the theory of pseudodense sets by reingold et al.[1]. we extend the dense model theorem of reingold et al. to demonstrate equivalence between two definitions (indistinguishability- and simulatability-based) of computational differential privacy.our computational analogues of differential privacy seem to allow for more accurate constructions than the standard information-theoretic analogues. in particular, in the context of private approximation of the distance between two vectors, we present a differentially-private protocol for computing the approximation, and contrast it with a substantially more accurate protocol that is only computationally differentially private.
how risky is the random-oracle model? rsa-fdh and many other schemes secure in the random-oracle model (rom) require a hash function with output size larger than standard sizes. we show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by bellare and rogaway from 1993 and 1996, and the ones implicit in ieee p1363 and pkcs standards: for instance, we obtain a 267 preimage attack on br93 for 1024-bit digests. next, we study the security impact of hash function defects for rom signatures. as an extreme case, we note that any hash collision would suffice to disclose the master key in the id-based cryptosystem by boneh et al. from focs '07, and the secret key in the rabin-williams signature for which bernstein proved tight security at eurocrypt '08. interestingly, for both of these schemes, a slight modification can prevent these attacks, while preserving the rom security result. we give evidence that in the case of rsa and rabin/rabin-williams, an appropriate pss padding is more robust than all other paddings known.
merkle puzzles are optimal - an ()-query attack on any key exchange from a random oracle. we prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making o(n 2) queries to the oracle. this improves on the previous $\tilde{\omega}(n^6)$ query attack given by impagliazzo and rudich (stoc '89), and answers an open question posed by them. our bound is optimal up to a constant factor since merkle (cacm '78) gave a key exchange protocol that can easily be implemented in this model with n queries and cannot be broken by an adversary making o(n 2) queries.
short and stateless signatures from the rsa assumption. we present the first signature scheme which is "short", stateless and secure under the rsa assumption in the standard model. prior short, standard model signatures in the rsa setting required either a strong complexity assumption such as strong rsa or (recently) that the signer maintain state. a signature in our scheme is comprised of one element in ${\mathcal {z}{^*}_{n}}$ and one integer. the public key is also short, requiring only the modulus n, one element of ${\mathcal {z}{^*}_{n}}$, one integer and one prf seed.to design our signature, we employ the known generic construction of fully-secure signatures from weakly-secure signatures and a chameleon hash. we then introduce a new proof technique for reasoning about weakly-secure signatures. this technique enables the simulator to predict a prefix of the message on which the adversary will forge and to use knowledge of this prefix to embed the challenge. this technique has wider applications beyond rsa.we use it to provide an entirely new analysis of the security of the waters signatures: the only short, stateless signatures known to be secure under the computational diffie-hellman assumption in the standard model.
reconstructing rsa private keys from random key bits. we show that an rsa private key with small public exponent can be efficiently recovered given a 0.27 fraction of its bits at random. an important application of this work is to the "cold boot" attacks of halderman et al. we make new observations about the structure of rsa keys that allow our algorithm to make use of the redundant information in the typical storage format of an rsa private key. our algorithm itself is elementary and does not make use of the lattice techniques used in other rsa key reconstruction problems. we give an analysis of the running time behavior of our algorithm that matches the threshold phenomenon observed in our experiments.
new birthday attacks on some macs based on block ciphers. this paper develops several new techniques of cryptanalyzing macs based on block ciphers, and is divided into two parts.the first part presents new distinguishers of the mac construction alred and its specific instance alpha-mac based on aes. for the alred construction, we first describe a general distinguishing attack which leads to a forgery attack directly with the complexity of the birthday attack. a 2-round collision differential path of alpha-mac is adopted to construct a new distinguisher with about 265.5 chosen messages and 265.5 queries. one of the most important results is to use this new distinguisher to recover the internal state, which is an equivalent subkey of alpha-mac. moreover, our distinguisher on alred construction can be applied to the macs based on cbc and cfb encryption modes.the second part describes the first impossible differential attack on macs-pelican, mt-mac-aes and pc-mac-aes. using the birthday attack, enough message pairs that produce the inner near-collision with some specific differences are detected, then the impossible differential attack on 4-round aes to the above mentioned macs is performed. for pelican, our attack recovers its internal state, which is an equivalent subkey. for mt-mac-aes, the attack turns out to be a subkey recovery attack directly. the complexity of the two attacks is 285.5 chosen messages and 285.5 queries. for pc-mac-aes, we recover its 256-bit key with 285.5 chosen messages and 2128 queries.
on bounded distance decoding, unique shortest vectors, and the minimum distance problem. we prove the equivalence, up to a small polynomial approximation factor $\sqrt{n/\log n}$, of the lattice problems usvp (unique shortest vector problem), bdd (bounded distance decoding) and gapsvp (the decision version of the shortest vector problem). this resolves a long-standing open problem about the relationship between usvp and the more standard gapsvp, as well the bdd problem commonly used in coding theory. the main cryptographic application of our work is the proof that the ajtai-dwork ([2]) and the regev ([33]) cryptosystems, which were previously only known to be based on the hardness of usvp, can be equivalently based on the hardness of worst-case gapsvp${_{o({n^{2.5}})}}$ and gapsvp${_{o(n^{2})}}$, respectively. also, in the case of usvp and bdd, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory.
batch binary edwards. this paper sets new software speed records for high-security diffie-hellman computations, specifically 251-bit elliptic-curve variable-base-point scalar multiplication. in one second of computation on a $200 core 2 quad q6600 cpu, this paper's software performs 30000 251-bit scalar multiplications on the binary edwards curve d(x + x 2 + y + y 2) = (x + x 2)(y + y 2) over the field ${\bf f}_2[t]/(t^{251}+t^7+t^4+t^2+1)$ where d = t 57 + t 54 + t 44 + 1. the paper's field-arithmetic techniques can be applied in much more generality but have a particularly efficient interaction with the completeness of addition formulas for binary edwards curves.
on the composition of public-coin zero-knowledge protocols. we show that only languages in bpp have public-coin, black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. this result holds both in the plain model (without any set-up) and in the bare public-key model (where the prover and the verifier have registered public keys). we complement this result by showing the existence of a public-coin black-box zero-knowledge proof that remains secure under any a-priori bounded number of concurrent executions.
randomizable proofs and delegatable anonymous credentials. we construct an efficient delegatable anonymous credentials system. users can anonymously and unlinkably obtain credentials from any authority, delegate their credentials to other users, and prove possession of a credential l levels away from a given authority. the size of the proof (and time to compute it) is o(lk), where k is the security parameter. the only other construction of delegatable anonymous credentials (chase and lysyanskaya, crypto 2006) relies on general non-interactive proofs for np-complete languages of size k ¿(2 l ). we revise the entire approach to constructing anonymous credentials and identify randomizable zero-knowledge proof of knowledge systems as the key building block. we formally define the notion of randomizable non-interactive zero-knowledge proofs, and give the first instance of controlled rerandomization of non-interactive zero-knowledge proofs by a third-party. our construction uses groth-sahai proofs (eurocrypt 2008).
improving the security of quantum protocols via commit-and-open. we consider two-party quantum protocols starting with a transmission of some random bb84 qubits followed by classical messages. we show a general "compiler" improving the security of such protocols: if the original protocol is secure against an "almost honest" adversary, then the compiled protocol is secure against an arbitrary computationally bounded (quantum) adversary. the compilation preserves the number of qubits sent and the number of rounds up to a constant factor. the compiler also preserves security in the bounded-quantum-storage model (bqsm), so if the original protocol was bqsm-secure, the compiled protocol can only be broken by an adversary who has large quantum memory and large computing power. this is in contrast to known bqsm-secure protocols, where security breaks down completely if the adversary has larger quantum memory than expected. we show how our technique can be applied to quantum identification and oblivious transfer protocols.
dual system encryption: realizing fully secure ibe and hibe under simple assumptions. we present a new methodology for proving security of encryption systems using what we call dual system encryption. our techniques result in fully secure identity-based encryption (ibe) and hierarchical identity-based encryption (hibe) systems under the simple and established decisional bilinear diffie-hellman and decisional linear assumptions. our ibe system has ciphertexts, private keys, and public parameters each consisting of a constant number of group elements. these results are the first hibe system and the first ibe system with short parameters under simple assumptions.in a dual system encryption system both ciphertexts and private keys can take on one of two indistinguishable forms. a private key or ciphertext will be normal if they are generated respectively from the system's key generation or encryption algorithm. these keys and ciphertexts will behave as one expects in an ibe system. in addition, we define semi-functional keys and ciphertexts. a semi-functional private key will be able to decrypt all normally generated ciphertexts; however, decryption will fail if one attempts to decrypt a semi-functional ciphertext with a semi-functional private key. analogously, semi-functional ciphertexts will be decryptable only by normal private keys.dual system encryption opens up a new way to prove security of ibe and related encryption systems. we define a sequence of games where we change first the challenge ciphertext and then the private keys one by one to be semi-functional. we finally end up in a game where the challenge ciphertext and all private keys are semi-functional at which point proving security is straightforward.
probabilistically checkable arguments. we give a general reduction that converts any public-coin interactive proof into a one-round (two-message) argument. the reduction relies on a method proposed by aiello et al. [1], of using a private-information-retrieval (pir) scheme to collapse rounds in interactive protocols. for example, the reduction implies that for any security parameter t, the membership in any language in pspace can be proved by a one-round (two-message) argument of size poly(n,t), which is sound for malicious provers of size 2 t . (note that the honest prover in this construction runs in exponential time, since she has to prove membership in pspace, but we can choose t such that 2 t is significantly larger than the running time of the honest prover).a probabilistically checkable argument (pca) is a relaxation of the notion of probabilistically checkable proof (pcp). it is defined analogously to pcp, except that the soundness property is required to hold only computationally. we consider the model where the argument is of one round (two-message), where the verifier's message depends only on his (private) randomness. we show that for membership in many np languages, there are pcas (with efficient honest provers) that are of size polynomial in the size of the witness. this compares to the best pcps that are of size polynomial in the size of the instance (that may be significantly larger). the number of queries to these pcas is poly-logarithmic.the soundness property, in all our results, relies on exponential hardness assumptions for pir schemes.
short chosen-prefix collisions for md5 and the creation of a rogue ca certificate. we present a refined chosen-prefix collision construction for md5 that allowed creation of a rogue certification authority (ca) certificate, based on a collision with a regular end-user website certificate provided by a commercial ca. compared to the previous construction from eurocrypt 2007, this paper describes a more flexible family of differential paths and a new variable birthdaying search space. combined with a time-memory trade-off, these improvements lead to just three pairs of near-collision blocks to generate the collision, enabling construction of rsa moduli that are sufficiently short to be accepted by current cas. the entire construction is fast enough to allow for adequate prediction of certificate serial number and validity period: it can be made to require about 249 md5 compression function calls. finally, we improve the complexity of identical-prefix collisions for md5 to about 216 md5 compression function calls and use it to derive a practical single-block chosen-prefix collision construction of which an example is given.