waashk/dblp huggingface dataset:
encrypting by random rotations. this paper gives some well-known, little known, and new results on the problem of generating random elements in groups, with particular emphasis on applications to cryptography. the groups of greatest interest are the group of all orthogonal n × n matrices and the group of all permutations of a set. the chief application is to a. d. wyner's analog scrambling scheme for voice signals.
resource requirements for the application of addition chains in modulo exponentiation. addition chains or sequences can be usecd to reduce the amount of multiplications to accomplish an exponentiation at the cost of more memory required. we examine known methods of exponentiations based on addition sequences and derive the parameters determining operation count and number of required registers for storing intermediate results. as a result an improved method is proposed to choose window distributions as a basis for using known addition sequence heuristics.
fft-hash ii, efficient cryptographic hashing. we propose an efficient algorithm that hashes messages of arbitrary bit length into an 128 bit hash value. the algorithm is designed to make the production of a pair of colliding messages computationally infeasible. the algorithm performs a discrete fourier transform and a polynomial recursion over a finite field. each hash value in {0,1}128 occurs with frequency at most 2-120. this hash function is an improved variant of the algorithm fft-hash i presented in the rump session of crypto '91. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
cryptonalysis of the data encryption standard by the method of formal coding. the "method of formal coding" consists in representing each bit of a des ciphertext block as an xor-sum-of-products of the plaintext bits and the key bits. subsequent introduction of the "mfc-complexity measure" yields interesting results on the security of the des and the influecce of various parameters. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
ic-cards in high-security applications. ic-cards, which are credit-card-size plastic cards with integrated cpu and memory, have increasingly attracted public interest in recent years. mainly used as "electronic money" in the business of banking and as a storage medium at first, the ic-card is gaining more and more importance as a secure and user-optimised component for cryptographic systems. the following article analyses ic-cards with regard to their own security and their applications in the field of "edp security". the paper is concluded with a glance at the requirements to be met by future card generations and on possible developments. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
attacking the chor-rivest cryptosystem by improved lattice reduction. we introduce algorithms for lattice basis reduction that are improvements of the famous l3-algorithm. if a random l3-reduced lattice basis b1, . . . , bn, is given such that the vector of reduced gram-schmidt coefficients ({µi, j} 1 ≤ j < i ≤ n) is uniformly distributed in (0, 1)(n 2), then the pruned enumeration finds with positive probability a shortest lattice vector. we demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the chor-rivest cryptoscheme in dimensions 103 and 151 and by breaking damgård's hash function.
on the performance of hyperelliptic cryptosystems. in this paper we discuss various aspects of cryptosystems based on hyperelliptic curves. in particular we cover the implementation of the group law on such curves and how to generate suitable curves for use in cryptography. this paper presents a practical comparison between the performance of elliptic curve based digital signature schemes and schemes based on hyperelliptic curves. we conclude that, at present, hyperelliptic curves offer no performance advantage over elliptic curves.
publicly verifiable secret sharing. a secret sharing scheme allows to share a secret among several participants such that only certain groups of them can recover it. verifiable secret sharing has been proposed to achieve security against cheating participants. its first realization had the special property that everybody not only the participants, can verify that ihe shares are correctly distributed. we will call such schemes publicly verifiable secret sharing schemes, we discuss new applications to escrow cryptosystems and to payment systems with revocable anonymity, and we present two new realizations based on elgamal's cryptosystem.
fair blind signatures. a blind signature scheme is a protocol for obtaining a signature from a signer such that the signer's view of the protocol cannot be linked to the resulting message-signature pair. blind signature schemes are used in anonymous digital payment systems. since the existing proposals of blind signature schemes provide perfect unlinkability, such payment systems could be misused by criminals, e.g. to safely obtain a ransom or to launder money. in this paper, a new type of blind signature schemes called fair blind signature schemes is proposed. such schemes have the additional property that a trusted entity can deliver information allowing the signer to link his view of the protocol and the message-signature pair. two types of fair blind signature schemes are distinguished and several realizations are presented.
why provable security matters? recently, methods from provable security, that had been developped for the last twenty years within the research community, have been extensively used to support emerging standards. this in turn has led researchers as well as practitioners to raise some concerns about this methodology. should provable security be restricted to the standard computational model or can it rely on the so-called random oracle model? in the latter case, what is the practical meaning of security estimates obtained using this model? also, the fact that proofs themselves need time to be validated through public discussion was somehow overlooked. building on two case studies, we discuss these concerns. one example covers the public key encryption formatting scheme oaep originally proposed in [3]. the other comes from the area of signature schemes and is related to the security proof of esign [43]. both examples show that provable security is more subtle than it at first appears.
hypercubic lattice reduction and analysis of ggh and ntru signatures. in this paper, we introduce a new lattice reduction technique applicable to the narrow, but important class of hypercubic lattices, (l ≅ zn). hypercubic lattices arise during transcript analysis of certain ggh, and ntrusign signature schemes. after a few thousand signatures, key recovery amounts to discovering a hidden unitary matrix u, from its gram matrix g = uut. this case of the gram matrix factorization problem is equivalent to finding the shortest vectors in the hypercubic lattice, lg, defined by the quadratic form g. our main result is a polynomial-time reduction to a conjecturally easier problem: the lattice distinguishing problem. additionally, we propose a heuristic solution to this distinguishing problem with a distributed computation of many "relatively short" vectors.
non-interactive proofs for integer multiplication. we present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a,b,c satisfy ab = c. this implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. the protocols use various set-up assumptions, but do not require the random oracle model.
ate pairing on hyperelliptic curves. in this paper we show that the ate pairing, originally defined for elliptic curves, generalises to hyperelliptic curves and in fact to arbitrary algebraic curves. it has the following surprising properties: the loop length in miller's algorithm can be up to g times shorter than for the tate pairing, with g the genus of the curve, and the pairing is automatically reduced, i.e. no final exponentiation is needed.
a fast and key-efficient reduction of chosen-ciphertext to known-plaintext security. motivated by the quest for reducing assumptions in security proofs in cryptography, this paper is concerned with designing efficient symmetric encryption and authentication schemes based on any weak pseudorandom function (prf) which can be much more efficiently implemented than prfs. damgård and nielsen (crypto '02) have shown how to construct an efficient symmetric encryption scheme based on any weak prf that is provably secure against chosen-plaintext attacks. the main ingredient is a range-extension construction for weak prfs. by using well-known techniques, they also showed how their scheme can be made secure against the stronger chosen-ciphertext attacks.the results of our paper are three-fold. first, we give a range-extension construction for weak prfs that is optimal within a large and natural class of reductions (especially all known today). second, we propose a construction of a regular prf from any weak prf. third, these two results imply a (for long messages) much more efficient chosen-ciphertext secure encryption scheme than the one proposed by damgård and nielsen. the results also give answers to open questions posed by naor and reingold (crypto '98) and by damgård and nielsen.
sub-linear zero-knowledge argument for correctness of a shuffle. a shuffle of a set of ciphertexts is a new set of ciphertexts with the same plaintexts in permuted order. shuffles of homomorphic encryptions are a key component in mix-nets, which in turn are used in protocols for anonymization and voting. since the plaintexts are encrypted it is not directly verifiable whether a shuffle is correct, and it is often necessary to prove the correctness of a shuffle using a zero-knowledge proof or argument. in previous zero-knowledge shuffle arguments from the literature the communication complexity grows linearly with the number of ciphertexts in the shuffle. we suggest the first practical shuffle argument with sub-linear communication complexity. our result stems from combining previous work on shuffle arguments with ideas taken from probabilistically checkable proofs.
resistance against general iterated attacks. in this paper we study the resistance of a block cipher against a class of general attacks which we call "iterated attacks". this class includes some elementary versions of differential and linear cryptanalysis. we prove that we can upper bound the complexity of the attack by using decorrelation techniques. our main theorem enables to prove the security against these attacks (in our model) of some recently proposed block ciphers coconut98 and peanut98, as well as the aes candidate dfc.we outline that decorrelation to the order 2d is required for proving security against iterated attacks of order d.
universally composable multi-party computation using tamper-proof hardware. protocols proven secure within the universal composability (uc) framework satisfy strong and desirable security properties. unfortunately, it is known that within the "plain" model, secure computation of general functionalities without an honest majority is impossible. this has prompted researchers to propose various "setup assumptions" with which to augment the bare uc framework in order to bypass this severe negative result. existing setup assumptions seem to inherently require some trusted party (or parties) to initialize the setup in the real world.we propose a new setup assumption -- more along the lines of a physical assumption regarding the existence of tamper-proof hardware -- which also suffices to circumvent the impossibility result mentioned above. we suggest this assumption as potentially leading to an approach that might alleviate the need for trusted parties, and compare our assumption to those proposed previously.
an efficient protocol for secure two-party computation in the presence of malicious adversaries. check if we can apply woodruff's method to our protocol. we show an efficient secure two-party protocol, based on yao's construction, which provides security against malicious adversaries. yao's original protocol is only secure in the presence of semi-honest adversaries. security against malicious adversaries can be obtained by applying the compiler of goldreich, micali and wigderson (the "gmw compiler"). however, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs.our construction is based on applying cut-and-choose techniques to the original circuit and inputs. security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). the resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running o(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. we remark that a naive implementation of the cut-and-choose technique with yao's protocol does not yield a secure protocol. this is the first paper to show how to properly implement these techniques, and to provide a full proof of security.our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. these two reductions are comparable to kilian's reduction, which uses ot alone but incurs a number of rounds which is linear in the depth of the circuit [18].
predicting lattice reduction. despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. the goal of this paper is to provide such an assessment, based on extensive experiments performed with the ntl library. the experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. we believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.
evidence that xtr is more secure than supersingular elliptic curve cryptosystems. we show that finding an efficiently computable injective homomorphism from the xtr subgroup into the group of points over gf(p<sup>2</sup>) of a particular type of supersingular elliptic curve is at least as hard as solving the diffie&#x2013;hellman problem in the xtr subgroup. this provides strong evidence for a negative answer to the question posed by vanstone and menezes at the crypto 2000 rump session on the possibility of efficiently inverting the mov embedding into the xtr subgroup. as a side result we show that the decision diffie&#x2013;hellman problem in the group of points on this type of supersingular elliptic curves is efficiently computable, which provides an example of a group where the decision diffie&#x2013;hellman problem is simple, while the diffie&#x2013;hellman and discrete logarithm problems are presumably not. so-called distortion maps on groups of points on elliptic curves that play an important role in our cryptanalysis also lead to cryptographic applications of independent interest. these applications are an improvement of joux&#x2019;s one round protocol for tripartite diffie&#x2013;hellman key exchange and a non-refutable digital signature scheme that supports escrowable encryption. we also discuss the applicability of our methods to general elliptic curves defined over finite fields which includes a classification of elliptic curve groups where distortion maps exist.
zero-knowledge sets with short proofs. zero knowledge sets, introduced by micali, rabin and kilian in [17], allow a prover to commit to a secret set s in a way such that it can later prove, non interactively, statements of the form x ∈ s (or x ∉ s), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on s, not even its size. later, chase et al. [5] abstracted away the micali, rabin and kilian's construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. using this primitive, it was shown in [5,4] how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). in this paper we introduce the notion of trapdoor q-mercurial commitments (qtmcs), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly q messages, rather than to a single one. following [17,5] we show how to construct zks from qtmcs and collision resistant hash functions. then, we present an efficient realization of qtmcs that is secure under the so called strong diffie hellman assumption, a number theoretic conjecture recently introduced by boneh and boyen in [3]. using our scheme as basic building block, we obtain a construction of zks that allows for proofs that are much shorter with respect to the best previously known implementations. in particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of non membership.
binding elgamal: a fraud-detectable alternative to key-escrow proposals. we propose a concept for a worldwide information security infrastructure that protects law-abiding citizens, but not criminals, even if the latter use it fraudulently (i.e. when not complying with the agreed rules). it can be seen as a middle course between the inflexible but fraud-resistant kmi-proposal [8] and the flexible but non-fraud-resistant concept used in tis-cke [2]. our concept consists of adding binding data to the latter concept, which will not prevent fraud by criminals but makes it p t least detectable by third parties without the need of any secret information. in [19], we depict a worldwide framework in which this concept could present a security tool that is flexible enough to be incorporated in any national cryptography policy, on both the domestic and foreign use of cryptography. here, we present a construction for binding data for elgamal type public key encryption schemes. as a side result we show that a particular simplification in a multiuser version of elgamal does not affect its security.
precise concurrent zero knowledge. precise zero knowledge introduced by micali and pass (stoc'06) guarantees that the view of any verifier v can be simulated in time closely related to the actual (as opposed to worst-case) time spent by v in the generated view. we provide the first constructions of precise concurrent zero-knowledge protocols. our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by kilian and petrank (stoc'01) and prabhakaran, rosen and sahai (focs'02) whose simulators have a quadratic worst-case overhead. additionally, we achieve a statistically-precise concurrent zero-knowledge property-which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.
strongly multiplicative ramp schemes from high degree rational points on curves. in this work we introduce a novel paradigm for the construction of ramp schemes with strong multiplication that allows the secret to be chosen in an extension field, whereas the shares lie in a base field. when applied to the setting of shamir's scheme, for example, this leads to a ramp scheme with strong multiplication from which protocols can be constructed for atomic secure multiplication with communication equal to a linear number of field elements in the size of the network. this is also achieved by the results from cramer, damgaard and de haan from eurocrypt 2007. however, our new ramp scheme has an improved privacy bound that is essentially optimal and leads to a significant mathematical simplification of the earlier results on atomic secure multiplication. as a result, by considering high degree rational points on algebraic curves, this can now be generalized to algebraic geometric ramp schemes with strong multiplication over a constant size field, which in turn leads to low communication atomic secure multiplication where the base field can now be taken constant, as opposed to earlier work.
protocols and lower bounds for failure localization in the internet. a secure failure-localization path-quality-monitoring (flpqm) protocols allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. such protocols were proposed as tools that enable internet service providers to select high-performance paths through the internet, or to enforce contractual obligations. we give the first formal definitions of security for fl-pqm protocols and construct: 1. a simple fl-pqm protocol that can localize a faulty link every time a packet is not correctly delivered. this protocol's communication overhead is o(1) additional messages of length o(n) per packet (where n is the security parameter). 2. a more efficient fl-pqm protocol that can localize a faulty link when a noticeable fraction of the packets sent during some time period are not correctly delivered. the number of additional messages is an arbitrarily small fraction of the total number of packets. we also prove lower bounds for such protocols: 1. every secure fl-pqm protocol requires each intermediate node on the path to have some shared secret information (e.g. keys). 2. if secure fl-pqm protocols exist then so do one-way functions. 3. every black-box construction of a fl-pqm protocol from a random oracle that securely localizes every packet and adds at most o(log n) messages overhead per packet requires each intermediate node to invoke the oracle. these results show that implementing fl-pqm requires active cooperation (i.e. maintaining keys and agreeing on, and performing, cryptographic protocols) from all of the intermediate nodes along the path. this may be problematic in the internet, where links operate at extremely high speeds, and intermediate nodes are owned by competing business entities with little incentive to cooperate.