waashk/dblp huggingface dataset:
secure identification and qkd in the bounded-quantum-storage model. we consider the problem of secure identification: user u proves to server s that he knows an agreed (possibly low-entropy) password w, while giving away as little information on w as possible, namely the adversary can exclude at most one possible password for each execution of the scheme. we propose a solution in the bounded-quantum-storage model, where u and s may exchange qubits, and a dishonest party is assumed to have limited quantum memory. no other restriction is posed upon the adversary. an improved version of the proposed identification scheme is also secure against a man-in-the-middle attack, but requires u and s to additionally share a high-entropy key k. however, security is still guaranteed if one party loses k to the attacker but notices the loss. in both versions of the scheme, the honest participants need no quantum memory, and noise and imperfect quantum sources can be tolerated. the schemes compose sequentially, and w and k can securely be re-used. a small modification to the identification scheme results in a quantum-key-distribution (qkd) scheme, secure in the bounded-quantum-storage model, with the same re-usability properties of the keys, and without assuming authenticated channels. this is in sharp contrast to known qkd schemes (with unbounded adversary) without authenticated channels, where authentication keys must be updated, and unsuccessful executions can cause the parties to run out of keys.
practical cryptanalysis of sflash. in this paper, we present a practical attack on the signature scheme sflash proposed by patarin, goubin and courtois in 2001 following a design they had introduced in 1998. the attack only needs the public key and requires about one second to forge a signature for any message, after a one-time computation of several minutes. it can be applied to both sflashv2 which was accepted by nessie, as well as to sflashv3 which is a higher security version.
invertible universal hashing and the tet encryption mode. this work describes a mode of operation, tet, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. when using an n-bit block cipher, the resulting scheme can handle input of any bit-length between n and 2n and associated data of arbitrary length. the mode tet is a concrete instantiation of the generic mode of operation that was proposed by naor and reingold, extended to handle tweaks and inputs of arbitrary bit length. the main technical tool is a construction of invertible "universal hashing" on wide blocks, which is as efficient to compute and invert as polynomial-evaluation hash.
improved analysis of kannan's shortest lattice vector algorithm. the security of lattice-based cryptosystems such as ntru, ggh and ajtai-dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. the best algorithms for these tasks are due to kannan, and, though remarkably simple, their complexity estimates have not been improved since over twenty years. kannan's algorithm for solving the shortest vector problem (svp) is in particular crucial in schnorr's celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryption schemes mentioned above. in this paper we improve the complexity upper-bounds of kannan's algorithms. the analysis provides new insight on the practical cost of solving svp, and helps progressing towards providing meaningful key-sizes.
distributed private data analysis: simultaneously solving how and what. we examine the combination of two directions in the field of privacy concerning computations over distributed private inputs --- secure function evaluation (sfe) and differential privacy. while in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. the general feasibility results for sfe suggest a natural paradigm for implementing differentially private analyses distributively: first choose what to compute, i.e., a differentially private analysis; then decide how to compute it, i.e., construct an sfe protocol for this analysis. we initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. in particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including binary sum, gap threshold, and approximate median queries. our results yield new separations between the local and global models of computations for private data analysis.
rerandomizable rcca encryption. we give the first perfectly rerandomizable, replayable-cca (rcca) secure encryption scheme, positively answering an open problem of canetti et al. (crypto 2003). our encryption scheme, which we call the double-strand cramer-shoup scheme, is a non-trivial extension of the popular cramer-shoup encryption. its security is based on the standard ddh assumption. to justify our definitions, we define a powerful "replayable message posting" functionality in the universally composable (uc) framework, and show that any encryption scheme that satisfies our definitions of rerandomizability and rcca security is a uc-secure implementation of this functionality. finally, we enhance the notion of rerandomizable rcca security by adding a receiver-anonymity (or key-privacy) requirement, and show that it results in a correspondingly enhanced uc functionality. we leave open the problem of constructing a scheme achieving this enhancement.
a tight high-order entropic quantum uncertainty relation with applications. we derive a new entropic quantum uncertainty relation involving min-entropy. the relation is tight and can be applied in various quantum-cryptographic settings. protocols for quantum 1-out-of-2 oblivious transfer and quantum bit commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions. as another application, we consider the realistic setting of quantum key distribution (qkd) against quantum-memory-bounded eavesdroppers. the uncertainty relation allows to prove the security of qkd protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. for instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. previously, the key uncertainty of these ciphers was only known with respect to shannon entropy.
on secure multi-party computation in black-box groups. we study the natural problem of secure n-party computation (in the passive, computationally unbounded attack model) of the n-product function fg(x1, . . . , xn) = x1 ċ x2 . . . xn in an arbitrary finite group (g, ċ), where the input of party pi is xi ∈ g for i = 1, . . . , n. for flexibility, we are interested in protocols for fg which require only black-box access to the group g (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). our results are as follows. first, on the negative side, we show that if (g, ċ) is non-abelian and n ≥ 4, then no ⌈n/2⌉-private protocol for computing fg exists. second, on the positive side, we initiate an approach for construction of black-box protocols for fg based on k-of-k threshold secret sharing schemes, which are efficiently implementable over any black-box group g. we reduce the problem of constructing such protocols to a combinatorial colouring problem in planar graphs. we then give two constructions for such graph colourings. our first colouring construction gives a protocol with optimal collusion resistance t < n/2, but has exponential communication complexity o(n(2t+1/t)2) group elements (this construction easily extends to general adversary structures). our second probabilistic colouring construction gives a protocol with (close to optimal) collusion resistance t < n/µ for a graph-related constant µ ≤ 2.948, and has efficient communication complexity o(nt2) group elements. furthermore, we believe that our results can be improved by further study of the associated combinatorial problems.
cryptography in the multi-string model. the common random string model introduced by blum, feldman and micali permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. we can think of this model as a trusted party generating a random string and giving it to all parties in the protocol. however, the introduction of such a third party should set alarm bells going off: who is this trusted party? why should we trust that the string is random? even if the string is uniformly random, how do we know it does not leak private information to the trusted party? the very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. in this paper, we propose the more realistic multi-string model. instead of having one trusted authority, we have several authorities that generate random strings. we do not trust any single authority; we only assume a majority of them generate the random string honestly. this security model is reasonable, yet at the same time it is very easy to implement. we could for instance imagine random strings being provided on the internet, and any set of parties that want to execute a protocol just need to agree on which authorities' strings they want to use. we demonstrate the use of the multi-string model in several fundamental cryptographic tasks. we define multi-string non-interactive zero-knowledge proofs and prove that they exist under general cryptographic assumptions. our multistring nizk proofs have very strong security properties such as simulation-extractability and extraction zero-knowledge, which makes it possible to compose them with arbitrary other protocols and to reuse the random strings. we also build efficient simulation-sound multi-string nizk proofs for circuit satisfiability based on groups with a bilinear map. the sizes of these proofs match the best constructions in the single common random string model. we suggest a universally composable commitment scheme in the multistring model. it has been proven that uc commitment does not exist in the plain model without setup assumptions. prior to this work, constructions were only known in the common reference string model and the registered public key model. one of the applications of the uc commitment scheme is a coin-flipping protocol in the multi-string model. armed with the coin-flipping protocol, we can securely realize any multi-party computation protocol.
universally-composable two-party computation in two rounds. round complexity is a central measure of efficiency, and characterizing the round complexity of various cryptographic tasks is of both theoretical and practical importance. we show here a universally-composable (uc) protocol (in the common reference string model) for two-party computation of any functionality, where both parties receive output, using only two rounds. (this assumes honest parties are allowed to transmit messages simultaneously in any given round; we obtain a three-round protocol when parties are required to alternate messages.) our results match the obvious lower bounds for the round complexity of secure two-party computation under any reasonable definition of security, regardless of what setup is used. thus, our results establish that secure two-party computation can be obtained under a commonly-used setup assumption with maximal security (i.e., security under general composition) in a minimal number of rounds. to give but one example of the power of our general result, we observe that as an almost immediate corollary we obtain a two-round uc blind signature scheme, matching a result by fischlin at crypto 2006 (though, in contrast to fischlin, we use specific number-theoretic assumptions).
cryptography with constant input locality. we study the following natural question: which cryptographic primitives (if any) can be realized by functions with constant input locality, namely functions in which every bit of the input influences only a constant number of bits of the output? this continues the study of cryptography in low complexity classes. it was recently shown by applebaum et al. (focs 2004) that, under standard cryptographic assumptions, most cryptographic primitives can be realized by functions with constant output locality, namely ones in which every bit of the output is influenced by a constant number of bits from the input. we (almost) characterize what cryptographic tasks can be performed with constant input locality. on the negative side, we show that primitives which require some form of non-malleability (such as digital signatures, message authentication, or non-malleable encryption) cannot be realized with constant input locality. on the positive side, assuming the intractability of certain problems from the domain of error correcting codes (namely, hardness of decoding a random binary linear code or the security of the mceliece cryptosystem), we obtain new constructions of one-way functions, pseudorandom generators, commitments, and semantically-secure public-key encryption schemes whose input locality is constant. moreover, these constructions also enjoy constant output locality and thus they give rise to cryptographic hardware that has constant-depth, constant fan-in and constant fan-out. as a byproduct, we obtain a pseudorandom generator whose output and input locality are both optimal (namely,&#x00a0;3).
public key encryption that allows pir queries. consider the following problem: alice wishes to maintain her email using a storage-provider bob (such as a yahoo! or hotmail email account). this storage-provider should provide for alice the ability to collect, retrieve, search and delete emails but, at the same time, should learn neither the content of messages sent from the senders to alice (with bob as an intermediary), nor the search criteria used by alice. a trivial solution is that messages will be sent to bob in encrypted form and alice, whenever she wants to search for some message, will ask bob to send her a copy of the entire database of encrypted emails. this however is highly inefficient. we will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of alice. in this paper, we show how to create a public-key encryption scheme for alice that allows pir searching over encrypted documents. our solution is the first to reveal no partial information regarding the user's search (including the access pattern) in the public-key setting and with nontrivially small communication complexity. this provides a theoretical solution to a problem posed by boneh, dicrescenzo, ostrovsky and persiano on "public-key encryption with keyword search." the main technique of our solution also allows for single-database pir writing with sublinear communication complexity, which we consider of independent interest.
simulatable vrfs with applications to multi-theorem nizk. this paper introduces simulatable verifiable random functions (svrf). vrfs are similar to pseudorandom functions, except that they are also verifiable: corresponding to each seed sk, there is a public key pk, and for y = fpk(x), it is possible to prove that y is indeed the value of the function seeded by sk. a simulatable vrf is a vrf for which this proof can be simulated, so a simulator can pretend that the value of fpk(x) is any y. our contributions are as follows. we introduce the notion of svrf. we give two constructions: one from general assumptions (based on nizk), but inefficient, just as a proof of concept; the other construction is practical and based on a special assumption about composite-order groups with bilinear maps. we then use an svrf to get a direct transformation from a single-theorem non-interactive zero-knowledge proof system for a language l to a multi-theorem non-interactive proof system for the same language l.
scalable and unconditionally secure multiparty computation. we present a multiparty computation protocol that is unconditionally secure against adaptive and active adversaries, with communication complexity o(cn)k + o(dn2)k + poly(nκ), where c is the number of gates in the circuit, n is the number of parties, k is the bit-length of the elements of the field over which the computation is carried out, d is the multiplicative depth of the circuit, and κ is the security parameter. the corruption threshold is t < n/3. for passive security the corruption threshold is t < n/2 and the communication complexity is o(nc)k. these are the first unconditionally secure protocols where the part of the communication complexity that depends on the circuit size is linear in n. we also present a protocol with threshold t < n/2 and complexity o(cn)k+poly(nκ) based on a complexity assumption which, however, only has to hold during the execution of the protocol - that is, the protocol has so called everlasting security.
collusion-free protocols in the mediated model. prior approaches [14, 15] to building collusion-free protocols require exotic channels. by taking a conceptually new approach, we are able to use a more digitally-friendly communication channel to construct protocols that achieve a stronger collusion-free property.we consider a communication channel which can filter and rerandomize message traffic. we then provide a new security definition that captures collusion-freeness in this new setting; our new setting even allows for the mediator to be corrupted in which case the security gracefully fails to providing standard privacy and correctness. this stronger notion makes the property useful in more settings.to illustrate feasibility, we construct a commitment scheme and a zero-knowledge proof of knowledge that meet our definition in its two variations.
one-time programs. in this work, we introduce one-time programs, a new computational paradigm geared towards security applications. a one-time program can be executed on a single input, whose value can be specified at run time. other than the result of the computation on this input, nothing else about the program is leaked. hence, a one-time program is like a black box function that may be evaluated once and then "self destructs." this also extends to k-time programs, which are like black box functions that can be evaluated k times and then self destruct.one-time programs serve many of the same purposes of program obfuscation, the obvious one being software protection, but also including applications such as temporary transfer of cryptographic ability. moreover, the applications of one-time programs go well beyond those of obfuscation, since one-time programs can only be executed once (or more generally, a limited number of times) while obfuscated programs have no such bounds. for example, one-time programs lead naturally to electronic cash or token schemes: coins are generated by a program that can only be run once, and thus cannot be double spent.most significantly, the new paradigm of one-time computing opens new avenues for conceptual research. in this work we explore one such avenue, presenting the new concept of "one-time proofs," proofs that can only be verified once and then become useless and unconvincing.all these tasks are clearly impossible using software alone, as any piece of software can be copied and run again, enabling the user to execute the program on more than one input. all our solutions employ a secure memory device, inspired by the cryptographic notion of interactive oblivious transfer protocols, that stores two secret keys (k 0,k 1). the device takes as input a single bit b ¿ {0,1}, outputs k b , and then self destructs. using such devices, we demonstrate that for every input length, any standard program (turing machine) can be efficiently compiled into a functionally equivalent one-time program. we also show how this memory device can be used to construct one-time proofs. specifically, we show how to use this device to efficiently convert a classical witness for any np statement, into "one-time proof" for that statement.
beyond uniformity: better security/efficiency tradeoffs for compression functions. suppose we are given a perfect n + c-to-n bit compression function f and we want to construct a larger m + s-to-s bit compression function h instead. what level of security, in particular collision resistance, can we expect from h if it makes r calls to f? we conjecture that typically collisions can be found in 2(nr + cr ¿ m)/(r + 1) queries. this bound is also relevant for building a m + s-to-s bit compression function based on a blockcipher with k-bit keys and n-bit blocks: simply set c = k, or c = 0 in case of fixed keys.we also exhibit a number of (conceptual) compression functions whose collision resistance is close to this bound. in particular, we consider the following four scenarios: 1 a 2n-to-n bit compression function making two calls to an n-to-n bit primitive, providing collision resistance up to 2 n/3/n queries. this beats a recent bound by rogaway and steinberger that 2 n/4 queries to the underlying random n-to-n bit function suffice to find collisions in any rate-1/2 compression function. in particular, this shows that rogaway and steinberger's recent bound of 2(nr ¿ m ¿ s/2)/r) queries (for c = 0) crucially relies upon a uniformity assumption; a blanket generalization to arbitrary compression functions would be incorrect. 1 a 3n-to-2n bit compression function making a single call to a 3n-to-n bit primitive, providing collision resistance up to 2 n queries. 1 a 3n-to-2n bit compression function making two calls to a 2n-to-n bit primitive, providing collision resistance up to 2 n queries. 1 a single call compression function with parameters satisfying m ≤ n + c, n ≤ s, c ≤ m. this result provides a tradeoff between how many bits you can compress for what level of security given a single call to an n + c-to-n bit random function.
a framework for efficient and composable oblivious transfer. we propose a simple and general framework for constructing oblivious transfer (ot) protocols that are efficient, universally composable, and generally realizable under any one of a variety of standard number-theoretic assumptions, including the decisional diffie-hellman assumption, the quadratic residuosity and decisional composite residuosity assumptions, and worst-case lattice assumptions.our ot protocols are round-optimal (one message each way), quite efficient in computation and communication, and can use a single common string for an unbounded number of executions between the same sender and receiver. furthermore, the protocols can provide statistical security to either the sender or the receiver, simply by changing the distribution of the common string. for certain instantiations of the protocol, even a common uniformly random string suffices.our key technical contribution is a simple abstraction that we call a dual-mode cryptosystem. we implement dual-mode cryptosystems by taking a unified view of several cryptosystems that have what we call "messy" public keys, whose defining property is that a ciphertext encrypted under such a key carries no information (statistically) about the encrypted message.as a contribution of independent interest, we also provide a multi-bit amortized version of regev's lattice-based cryptosystem (stoc 2005) whose time and space complexity are improved by a linear factor in the security parameter n. the resulting amortized encryption and decryption times are only $\tilde{o}(n)$ bit operations per message bit, and the ciphertext expansion can be made as small as a constant; the public key size and underlying lattice assumption remain essentially the same.