Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner
Security of the FiatShamir Transformation
in the Quantum RandomOracle Model
In Advances in Cryptology  CRYPTO 2019, volume 11693 of Lecture Notes in Computer Science, pages 356383.
Also: Accepted to QCRYPT 2019 and QIP 2020.
Abstract:
The famous FiatShamir transformation turns any publiccoin threeround interactive proof,i.e., any socalled Σprotocol, into a noninteractive proof in the randomoracle model. We study this transformation in the setting of a quantum adversary that in particular may query the random oracle in quantum superposition. Our main result is a generic reduction that transforms any quantum dishonest prover attacking the FiatShamir transformation in the quantum randomoracle model into a similarly successful quantum dishonest prover attacking the underlying Σprotocol (in the standard model). Applied to the standard soundness and proofofknowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the FiatShamir transformation even when allowing quantum attacks. Our result improves and completes the partial results that have been known so far, but it also proves wrong certain claims made in the literature. In the context of postquantum secure signature schemes, our results imply that for any Σprotocol that is a proofofknowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding FiatShamir signature scheme is secure in the quantum randomoracle model. For example, we can conclude that the nonoptimized version of Fish, which is the bare FiatShamir variant of the NIST candidate Picnic, is secure in the quantum randomoracle model.
Serge Fehr and Chen Yuan
Towards Optimal Robust Secret Sharing with Security against a Rushing Adversary
In Advances in Cryptology  EUROCRYPT 2019, volume 11478 of Lecture Notes in Computer Science, pages 472499.
Abstract:
Robust secret sharing enables the reconstruction of a secretshared message in the presence of up to t (out of n) incorrect shares. The most challenging case is when n=2t+1, which is the largest t for which the task is still possible, up to a small error probability 2^{k} and with some overhead in the share size.
Recently, Bishop, Pastro, Rajaraman and Wichs [3] proposed a scheme with an (almost) optimal overhead of O(k). This seems to answer the open question posed by Cevallos et al. [6] who proposed a scheme with overhead of O(n+k) and asked whether the linear dependency on n was necessary or not. However, a subtle issue with Bishop et al.'s solution is that it (implicitly) assumes a nonrushing adversary, and thus it satisfies a weaker notion of security compared to the scheme by Cevallos et al. [6], or to the classical scheme by Rabin and BenOr [13].
In this work, we almost close this gap. We propose a new robust secret sharing scheme that offers full security against a rushing adversary, and that has an overhead of O(kn𝜀), where 𝜀>0 is arbitrary but fixed. This n𝜀factor is obviously worse than the polylog(n)factor hidden in the O notation of the scheme of Bishop et al. [3], but it greatly improves on the linear dependency on n of the best known scheme that features security against a rushing adversary (when k is substantially smaller than n).
A small variation of our scheme has the same O(k) overhead as the scheme of Bishop et al. and achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.
Available files:


Serge Fehr
Classical Proofs for the Quantum Collapsing
Property of Classical Hash Functions
In Theory of Cryptography Conference  TCC2018, volume 11240 of Lecture Notes in Computer Science, pages 315338.
Abstract:
Hash functions are of fundamental importance in theoretical and in practical cryptography, and with the threat of quantum computers possibly emerging in the future, it is an urgent objective to understand the security of hash functions in the light of potential future quantum attacks. To this end, we reconsider the collapsing property of hash functions, as introduced by Unruh, which replaces the notion of collision resistance when considering quantum attacks. Our contribution is a formalism and a framework that offers significantly simpler proofs for the collapsing property of hash functions. With our framework, we can prove the collapsing property for hash domain extension constructions entirely by means of decomposing the iteration function into suitable elementary composition operations. In particular, given our framework, one can argue purely classically about the quantumsecurity of hash functions; this is in contrast to previous proofs which are in terms of sophisticated quantuminformationtheoretic and quantumalgorithmic reasoning.
Available files:


Frédéric Dupuis, Serge Fehr, Philippe
Lamontagne, Louis Salvail, and Bart Mennink
Secure Certification of Mixed Quantum States with Application to TwoParty Randomness Generation
In Theory of Cryptography Conference  TCC2018, volume 11240 of Lecture Notes in Computer Science, pages 282314.
Abstract:
We investigate sampling procedures that certify that an arbitrary quantum state on n subsystems is close to an ideal mixed state 𝜑^{⊗𝑛} for a given reference state 𝜑, up to errors on a few positions. This task makes no sense classically: it would correspond to certifying that a given bitstring was generated according to some desired probability distribution. However, in the quantum case, this is possible if one has access to a prover who can supply a purification of the mixed state.
In this work, we introduce the concept of mixedstate certification, and we show that a natural sampling protocol offers secure certification in the presence of a possibly dishonest prover: if the verifier accepts then he can be almost certain that the state in question has been correctly prepared, up to a small number of errors.
We then apply this result to twoparty quantum cointossing. Given that strong coin tossing is impossible, it is natural to ask “how close can we get”. This question has been well studied and is nowadays well understood from the perspective of the bias of individual coin tosses. We approach and answer this question from a different—and somewhat orthogonal—perspective, where we do not look at individual coin tosses but at the global entropy instead. We show how two distrusting parties can produce a common highentropy source, where the entropy is an arbitrarily small fraction below the maximum.
Available files:


Serge Fehr, Pierre Karpman, and Bart Mennink
Short NonMalleable Codes from RelatedKey Secure Block Ciphers
In IACR Transactions on Symmetric Cryptology, volume 2018, issue 1. Presented at the International Conference on Fast Software Encryption  FSE 2018.
Abstract:
A nonmalleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in
the original message, or in an unrelated message.
We consider the simplest possible construction in the computational splitstate model, which encodes a message m simply as kE_k(m) for a uniformly random key k, where E is a block cipher.
This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS 2016), who eschewed this simple scheme in fear of
relatedkey attacks on E.
In this work, we prove this construction to be a strong nonmalleable code in the splitstate tampering model as long as E is
(i) a pseudorandom permutation under leakage and (ii) relatedkey secure with respect to an arbitrary but fixed key relation.
Both properties are believed to hold for ``good'' block ciphers, such as AES128, making this nonmalleable code very efficient with short codewords of
length m + 2 kappa (where kappa is the security parameter, e.g., 128 bits), without significant security penalty.
Available files:


Serge Fehr and Louis Salvail
Quantum Authentication and Encryption with Key Recycling
In Advances in Cryptology  EUROCRYPT 2017, volume 10212 of Lecture Notes in Computer Science, pages 311338. SpringerVerlag, 2017.
Abstract:
We propose an informationtheoretically secure encryption scheme for classical messages with quantum ciphertexts that offers detection of eavesdropping attacks, and reusability of the key in case no eavesdropping took place: the entire key can be securely reused for encrypting new messages as long as no attack is detected.
This is known to be impossible for fully classical schemes, where there is no way to detect plain eavesdropping attacks.
This particular application of quantum techniques to cryptography was originally proposed by Bennett, Brassard and Breidbart in 1982, even before proposing quantumkeydistribution, and a simple candidate scheme was suggested but no rigorous security analysis was given.
The idea was picked up again in 200
5, when Damgård, Pedersen and Salvail suggested a new scheme for the same task, but now with a rigorous security analysis. However, their scheme is much more demanding in terms of quantum capabilities: it requires the users to have a quantum computer.
In contrast, and like the original scheme by Bennett et al., our new scheme requires from the honest users merely to prepare and measure single BB84 qubits.
As such, we not only show the first provablysecure scheme that is within reach of current technology, but we also confirm Bennett et al.'s original intuition that a scheme in the spirit of their original construction is indeed secure.
Frédéric Dupuis, Serge Fehr, Philippe Lamontagne, and Louis Salvail
Adaptive Versus NonAdaptive Strategies in the Quantum Setting with Applications
In Advances in Cryptology  CRYPTO 2016, volume 9816 of Lecture Notes in Computer Science, pages 3359. SpringerVerlag, 2016.
Abstract:
We prove a general relation between adaptive and nonadaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bitsize of the side information, or, more generally, its ``information content". Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to
nonadaptive attacks.
We demonstrate the usefulness of this methodology with two examples.
The first is a quantum bit commitment scheme based on 1bit cutandchoose. Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for twoparty computation, this implies the universality of 1bit cutandchoose, and thus solves the main open problem of [9]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al. It was originally suggested as an unconditionally secure scheme, back when this was thought
to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model.
In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a nonadaptive version, which can be done by means of known techniques, and applying our main result.
Serge Fehr and Max Fillinger
On the Composition of TwoProver Commitments, and Applications to MultiRound Relativistic Commitments
In Advances in Cryptology  EUROCRYPT 2016, volume 9666 of Lecture Notes in Computer Science, pages 477496. SpringerVerlag, 2016.
Also: Accepted to QCRYPT 2015.
Abstract:
We consider the related notions of twoprover and of relativistic commitment schemes. In recent work, Lunghi et al. proposed a new relativistic commitment scheme with a multiround sustain phase that enables to keep the binding property alive as long as the sustain phase is running.
They prove security of their scheme against classical attacks; however, the proven bound on the error parameter is very weak: it blows up doubly exponentially in the number of rounds.
In this work, we give a new analysis of the multiround scheme of Lunghi et al., and we show a linear growth of the error parameter instead (also considering classical attacks only). Our analysis is based on a new composition theorem for twoprover commitment schemes. The proof of our composition theorem is based on a better understanding of the binding property of twoprover commitments that we provide in the form of new definitions and relations among them.
As an additional consequence of these new insights, our analysis is actually with respect to a strictly stronger notion of security as considered by Lunghi et al.
Serge Fehr and Max Fillinger
MultiProver Commitments Against NonSignaling Attacks
In Advances in Cryptology  CRYPTO 2015, volume 9216 of Lecture Notes in Computer Science, pages 403421. SpringerVerlag, 2015.
Also: Accepted to QCRYPT 2015.
Abstract:
We reconsider the concept of twoprover (and more generally: multiprover) commitments,
as introduced in the late eighties in the seminal work by BenOr et al. As was recently
shown by Crépeau et al., the security of known twoprover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have quantum information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general socalled nonsignaling provers, which are restricted solely by the requirement that no communication takes place.
This poses the natural question whether there exists a twoprover commitment scheme that is secure under the sole assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known.
In this work, we give strong evidence for a negative answer: we show that any singleround twoprover commitment scheme can be broken by a nonsignaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) 1 in case of a perfectly sound scheme. In the case of multiround schemes, our impossibility result is restricted to perfectly hiding schemes.
On the positive side, we show that the impossibility result can be circumvented by considering three provers instead: there exists a threeprover commitment scheme that is secure against arbitrary nonsignaling attacks.
Ronald Cramer, Ivan Damgård, Nico Döttling, Serge Fehr, and Gabriele Spini
Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions
In Advances in Cryptology  EUROCRYPT 2015, volume 9057 of Lecture Notes in Computer Science, pages 313363. SpringerVerlag, 2015.
Abstract:
We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient listdecoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems:
(1) A linear nearthreshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size Ω(n)). Thus, the computational overhead per shared bit in this scheme is constant.
(2) An efficiently reconstructible robust secret sharing scheme for n/3 ≤ t ≤ (1ε) n/2 corrupted players (for any constant ε > 0) with shares of optimal size O(1+λ/n) and secrets of size Ω(n+λ), where λ is the security parameter.
Available files:


Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
Secure Identification and QKD in the BoundedQuantumStorage Model
In Theoretical Computer Science, volume 560, part 1, pages 1226, Theoretical Aspects of Quantum Cryptography  30 Years of BB84. Elsevier, 2014.
A preliminary version of this paper appeared in CRYPTO 2007.
Abstract:
We consider the problem of secure identification: user U proves to server S that he knows an agreed (possibly lowentropy) password w, while giving away as little information on w as possible  the adversary can exclude at most one possible password for each execution. We propose a solution in the boundedquantumstorage 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 maninthemiddle attack, but requires U and S to additionally share a highentropy key k. However, security is still guaranteed if one party loses k to the attacker but notices the loss. In both versions, 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 reused. A small modification to the identification scheme results in a quantumkey
distribution (QKD) scheme, secure in the boundedquantumstorage model, with the same reusability 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.
Available files:


Serge Fehr, and Stefan Berens,
On the Conditional Rényi Entropy
In IEEE Transactions on Information Theory, volume 60, number 11, pages 68016810. IEEE, 2014.
Abstract:
The Rényi entropy of general order unifies the wellknown Shannon entropy with several other entropy notions, like the minentropy or the collision entropy. In contrast to the Shannon entropy, there seems to be no commonly accepted definition for the conditional Rényi entropy: several versions have been proposed and used in the literature.
In this work, we reconsider the definition for the conditional Rényi entropy of general order as proposed by Arimoto in 1975.
We show that this particular notion satisfies several natural properties. In particular, we show that it satisfies monotonicity under conditioning, meaning that conditioning can only reduce the entropy, and (a weak form of) chain rule, which implies that the decrease in entropy due to conditioning is bounded by the number of bits one conditions on. None of the other suggestions for the conditional Rényi entropy satisfies both these properties.
Finally, we show a natural interpretation of the conditional Rényi entropy in terms of (unconditional) Rényi divergence, and we show consistency with a recently proposed notion of conditional Rényi entropy in the quantum setting.
Available files:


Harry Buhrman, Serge Fehr, and Christian Schaffner
On the Parallel Repetition of MultiPlayer Games: The NoSignaling Case
In Theory of Quantum Computation, Communication, and Cryptography  TQC 2014, LIPICS, pages 2435. Schloss Dagstuhl, 2014.
Abstract:
We consider the natural extension of twoplayer nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For twoplayer nonlocal games, it is known that both the classical and the nonsignaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is nontrivial to start with (i.e., has classical/nonsignaling value <1). Very recent results show similar behavior for the quantum value of a twoplayer game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the nonsignaling value.
In this work, we show a parallel repetition theorem for the nonsignaling value of a large class of multiplayer games, for an arbitrary number of players. Our result applies to all multiplayer games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game has a nonsignaling value smaller than 1, then the nonsignaling value of the nfold parallel repetition is exponentially small in n.
Our parallel repetition theorem for multiplayer games is weaker than the known parallel repetition results for twoplayer games in that the rate at which the nonsignaling value of the game decreases not only depends on the nonsignaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.
Available files:


Martin MüllerLennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, Marco Tomamichel
On quantum Rényi Entropies: A New Generalization and Some Properties
In Journal of Mathematical Physics, volume 54, 122203. AIP Publishing, 2013.
Abstract:
The Rényi entropies constitute a family of information measures that generalizes the wellknown Shannon entropy, inheriting many of its properties. They appear in the form of unconditional and conditional entropies, relative entropies, or mutual information, and have found many applications in information theory and beyond. Various generalizations of Rényi entropies to the quantum setting have been proposed, most prominently Petz's quasientropies and Renner's conditional min, max, and collision entropy. However, these quantum extensions are incompatible and thus unsatisfactory. We propose a new quantum generalization of the family of Rényi entropies that contains the von Neumann entropy, minentropy, collision entropy, and the maxentropy as special cases, thus encompassing most quantum entropies in use today. We show several natural properties for this definition, including dataprocessing inequalities, a duality relation, and an entropic uncertainty relation.
Available files:


Ronald Cramer, Serge Fehr, Carles Padró
Algebraic Manipulation Detection Codes
In SCIENCE CHINA Mathematics, volume 56, issue 7, pages 13491358. Science China Press, 2013.
Abstract:
Algebraic manipulation detection codes are a cryptographic primitive that was introduced by Cramer et al. (Eurocrypt 2008). It encompasses several methods that were previously used in cheater detection in secret sharing. Since its introduction, a number of additional applications have been found. This paper contains a detailed exposition of the known results about algebraic manipulation detection codes as well as some new results.
Available files:


Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, Stephanie Wehner
OneSided Device Independent QKD and PositionBased Cryptography from Monogamy Games
In Advances in Cryptology  EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 609625. SpringerVerlag, 2013.
Also (under a slightly different title): In New J. Phys. 15 (2013) 103002.
Abstract:
A serious concern with quantum key distribution (QKD) schemes is that, when under attack, the quantum devices in a reallife implementation may behave differently than modeled in the security proof. This can lead to reallife attacks against provably secure QKD schemes.
In this work, we show that the standard BB84 QKD scheme is onesided deviceindependent. This means that security holds even if Bob's quantum device is arbitrarily malicious, as long as Alice's device behaves as it should.
Thus, we can completely remove the trust into Bob's quantum device for free, without the need for changing the scheme, and without the need for hardtoimplement loopholefree violations of Bell inequality, as is required for fully (meaning twosided) deviceindependent QKD.
For our analysis, we introduce a new quantum game, called amonogamyofentanglement game, and we show a strong parallel repetition theorem for this game.
This new notion is likely to be of independent interest and to find additional applications. Indeed, besides the application to QKD, we also show a direct application to positionbased quantum cryptography: we give the first security proof for a oneround positionverification scheme that requires only singlequbit operations.
Serge Fehr, Ran Gelles, Christian Schaffner
Security and Composability of Randomness Expansion from Bell Inequalities
In Physical Review A, volume 87, issue 1, pages 012335. APS, 2013.
Abstract:
The nonlocal behavior of quantum mechanics can be used to generate guaranteed fresh randomness from an untrusted device that consists of two nonsignalling components; since the generation process requires some initial fresh randomness to act as a catalyst, one also speaks of randomness expansion.
Colbeck and Kent proposed the first method for generating randomness from untrusted devices, however, without providing a rigorous analysis. This was addressed subsequently by Pironio et al. [Nature 464 (2010)], who aimed at deriving a lower bound on the minentropy of the data extracted from an untrusted device, based only on the observed nonlocal behavior of the device.
Although that article succeeded in developing important tools towards the acquired goal, it failed in putting the tools together in a rigorous and correct way, and the given formal claim on the guaranteed amount of minentropy needs to be revisited.
In this paper we show how to combine the tools provided by Pironio et al., as to obtain a meaningful and correct lower bound on the minentropy of the data produced by an untrusted device, based on the observed nonlocal behavior of the device. Our main result confirms the essence of the improperly formulated claims of Pironio et al., and puts them on solid ground.
We also address the question of composability and show that different untrusted devices can be composed in an alternating manner under the assumption that they are not entangled. This enables for superpolynomial randomness expansion based on two untrusted yet unentangled devices.
Available files:


Serge Fehr, Jonathan Katz, Fang Song, HongSheng Zhou, Vassilis Zikas
Feasibility and Completeness of Cryptographic Tasks in the Quantum World
In Theory of Cryptography Conference  TCC 2013, volume 7785 of Lecture Notes in Computer Science, pages 281296. Springer Verlag, 2013.
Abstract:
It is known that cryptographic feasibility results can change by moving from the classical to the quantum world. With this in mind, we study the feasibility of realizing functionalities in the framework of universal composability, with respect to both computational and informationtheoretic security. With respect to computational security, we show that existing feasibility results carry over unchanged from the classical to the quantum world; a functionality is "trivial" (i.e., can be realized without setup) in the quantum world if and only if it is trivial in the classical world. The same holds with regard to functionalities that are complete (i.e., can be used to realize arbitrary other functionalities).
In the informationtheoretic setting, the quantum and classical worlds differ. In the quantum world, functionalities in the class we consider are either complete, trivial, or belong to a family of simultaneousexchange functionalities (e.g., XOR). However, other results in the informationtheoretic setting remain roughly unchanged.
Harry Buhrman,
Serge Fehr,
Christian Schaffner, and
Florian Speelman
The GardenHose Model
In Innovations in Theoretical Computer Science  ITCS 2013, pages 145158. ACM, 2013.
Also: Accepted to QIP 2012.
Abstract:
We define a new model of communication complexity, called the gardenhose model. Informally, the gardenhose complexity of a function f: {0,1}^{n} × {0,1}^{n} > {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}^{n} and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}^{n}. Alice turns on the water tap that she also connected to one of the pipes. Then,
the water comes out on Alice's or Bob's side depending on the function value f(x,y).
We prove almostlinear lower bounds on the gardenhose complexity for concrete functions like inner product, majority, and equality, and we show the existence of functions with exponential gardenhose complexity. Furthermore, we show a connection to classical complexity theory by proving that all functions computable in logspace have polynomial gardenhose complexity.
We consider a randomized variant of the gardenhose complexity,
where Alice and Bob hold preshared randomness, and a quantum
variant, where Alice and Bob hold preshared quantum entanglement, and
we show that the randomized gardenhose complexity is within a
polynomial factor of the deterministic gardenhose
complexity. Examples of (partial) functions are given where the
quantum gardenhose complexity is logarithmic in n while the classical
gardenhose complexity can be lower bounded by n^{c} for constant c>0.
Finally, we show an interesting connection between the gardenhose model and the (in)security of a certain class of {\em quantum positionverification} schemes.
Eli BenSasson, Serge Fehr, and
Rafail Ostrovsky
NearLinear UnconditionallySecure Multiparty Computation with a Dishonest Minority
In Advances in Cryptology  CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 663680 . SpringerVerlag, 2012.
Abstract:
In the setting of unconditionallysecure MPC, where dishonest players are unbounded and no cryptographic assumptions are used, it was known since the 1980's that an honest majority of players is both necessary and sufficient to achieve privacy and correctness, assuming secure pointtopoint and broadcast channels. The main open question that was left is to establish the exact communication complexity.
We settle the above question by showing an unconditionallysecure MPC protocol, secure against a dishonest minority of malicious players, that matches the communication complexity of the best known MPC protocol in the honestbutcurious setting. More specifically, we present a new nplayer MPC protocol that is secure against a computationallyunbounded malicious adversary that can adaptively corrupt up to t < n/2 of the players. For polynomiallylarge binary circuits that are not too unshaped,
our protocol has an amortized communication complexity of O(n log n + k/n^c) bits per multiplication (i.e. AND) gate, where k denotes the security parameter and c is an arbitrary nonnegative constant. This improves on the previously most efficient protocol with the same security guarantee, which offers an amortized communication complexity of O(n^2 k) bits per multiplication gate. For any k polynomial in n, the amortized communication complexity of our protocol matches the O(n log n) bit communication complexity of the best known MPC protocol with passive security.
We introduce several novel techniques that are of independent interest and we believe will have wider applicability. One is a novel idea of computing authentication tags by means of a mini MPC, which allows us to avoid expensive doublesharings; the other is a batchwise multiplication verification that allows us to speedup Beaver's ``multiplication triples''.
Niek Bouman, Serge Fehr,
Carlos GonzalezGuillen,
and Christian Schaffner
An AllButOne Entropic Uncertainty Relation, and Application to Passwordbased Identification
In Theory of Quantum Computation, Communication, and Cryptography  TQC 2012. Lecture Notes in Computer Science. SpringerVerlag, 2012.
Also: Accepted to QCRYPT 2011.
Abstract:
Entropic uncertainty relations are quantitative characterizations of Heisenberg's uncertainty principle, which make use of an entropy measure to quantify uncertainty.
In quantum cryptography, they are often used as convenient tools in security proofs.
We propose a new entropic uncertainty relation. It is the first such uncertainty relation that lower bounds the uncertainty of all but one measurement outcome with respect to an arbitrary (and in particular an arbitrarily large) set of possible measurements, and, at the same time, uses the minentropy as entropy measure, rather than the Shannon entropy. This makes it especially suited for quantum cryptography.
As application, we propose a new quantum identification scheme
in the bounded quantum storage model. It makes use of our new
uncertainty relation at the core of its security proof. In contrast to
the original quantum identification scheme proposed by Damgård
etal., our new scheme also offers some security in case the
boundedquantumstorage assumption fails hold. Specifically, our
scheme remains secure against an adversary that has unbounded storage
capabilities but is restricted to singlequbit operations. The scheme
by Damgård etal., on the other hand, completely breaks down under
such an attack.
Alfonso Cevallos, Serge Fehr,
Rafail Ostrovsky, and
Yuval Rabani
UnconditionallySecure Robust Secret Sharing with Compact Shares
In Advances in Cryptology  EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 195208. SpringerVerlag, 2012.
Abstract:
We consider the problem of reconstructing a shared secret in the presence of faulty shares, with unconditional security. We require that any t shares give no information on the shared secret, and reconstruction is possible even if up to t out of the n shares are incorrect. The interesting setting is n/3 <= t < n/2, where reconstruction of a shared secret in the
presence of faulty shares is possible, but only with an increase in the share size, and only if one admits a small failure probability. The goal of this work is to minimize this overhead in the share size. Known schemes either have a Omega(k n)overhead in share size, where k is the security parameter, or they have a closetooptimal overhead of order O(k + n) but have an exponential running time (in n).
In this paper, we propose a new scheme that has a closetooptimal overhead in the share size of order O(k + n log(n)), and a polynomial running time. Interestingly, the shares in our new scheme are prepared in the very same way as in the wellknown scheme by Rabin and BenOr, which relies on message authentication, but we use a message authentication code with short tags and keys and with correspondingly weak security. The short tags and keys give us the required saving in the share size. Surprisingly, we can compensate for the weakened security of the authentication and achieve an exponentially small (in k) failure probability by means of a more sophisticated reconstruction procedure.
Harry Buhrman,
Nishanth Chandran,
Serge Fehr,
Ran Gelles,
Vipul Goyal,
Rafail Ostrovsky, and
Christian Schaffner
PositionBased Quantum Cryptography: Impossibility and Constructions
In Advances in Cryptology  CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 429446. SpringerVerlag, 2011.
Also: in SIAM Journal on Computing (SICOMP), volume 43, issue 1.
Also: Accepted to QIP 2011 as plenary talk.
Abstract:
In this work, we study positionbased cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure positionverification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any positionverification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure positionverification is achievable. Jointly, these results suggest the interesting question whether secure positionverification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where
the bound is set to zero.
In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure positionverification is achievable, other positionbased cryptographic schemes are possible as well, such as secure positionbased authentication and positionbased key agreement.
Serge Fehr (Ed.)
5th International Conference on Information Theoretic Security  ICITS 2011
Proceedings, volume 6673 of Lecture Notes in Computer Science. SpringerVerlag, 2011.
Available files:


Niek Bouman, and Serge Fehr
Secure Authentication from a Weak Key, Without Leaking Information
In Advances in Cryptology  EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 246265. SpringerVerlag, 2011.
Abstract:
We study the problem of authentication based on a weak key in the informationtheoretic setting. A key is weak if its minentropy is an arbitrary small fraction of its bit length. This problem has recently received considerable attention, with different solutions optimizing different parameters. We study the problem in an extended setting, where the weak key is as a onetime session key that is derived from a public source of randomness with the help of a (potentially also weak) longterm key. Our goal now is to authenticate a message by means of the weak session key in such a way that (nearly) no information on the longterm key is leaked. Ensuring privacy of the longterm key is vital for the longterm key to be reusable. Previous work has not considered such a privacy issue, and previous solutions do not seem to satisfy this requirement. We show the existence of a practical fourround protocol that provides message authentication from a weak session key and that avoids nonnegligible leakage on the long
term key. The security of our scheme also holds in the quantum setting where the adversary may have limited quantum side information on the weak session key. As an application of our scheme, we show the existence of an identification scheme in the bounded quantum storage model that is secure against a maninthemiddle attack and that is truly passwordbased: it does not need any high entropy key, in contrast to the scheme proposed by Damgaard et al.
Available files:


Niek Bouman, and Serge Fehr
Sampling in a Quantum Population, and Applications
In Advances in Cryptology  CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 724741. SpringerVerlag, 2010.
Abstract:
We propose a framework for analyzing classical sampling strategies for estimating the Hamming weight of a large string from a few sample positions, when applied to a multiqubit quantum system instead. The framework shows how to interpret the result of such a strategy and how to define its accuracy when applied to a quantum system. Furthermore, we show how the accuracy of any strategy relates to its accuracy in its classical usage, which is well understood for the important examples.
We show the usefulness of our framework by using it to obtain new and simple security proofs for the following quantumcryptographic schemes: BB84 quantumkeydistribution, and quantum oblivioustransfer from bitcommitment.
Serge Fehr, Dennis Hofheinz, Eike Kiltz, and Hoeteck Wee
Encryption Schemes Secure Against ChosenCiphertext Selective Opening Attacks
In Advances in Cryptology  EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 381402. SpringerVerlag, 2010.
Abstract:
Imagine many small devices send data to a single receiver, encrypted
using the receiver's public key. Assume an adversary that has the
power to adaptively corrupt a subset of these devices. Given the
information obtained from these corruptions, do the ciphertexts from
uncorrupted devices remain secure?
Recent results suggest that conventional security notions for
encryption schemes (like INDCCA security) do not
suffice in
this setting. To fill this gap, the notion of security against
selectiveopening attacks (SOA security) has been introduced. It
has been shown that lossy encryption implies SOA security against a
passive, i.e., only eavesdropping and corrupting, adversary
(SOCPA). However, the known results on SOA security against an
active adversary (SOCCA) are rather limited. Namely, while
there exist feasibility results, the (time and space) complexity of
currently known SOCCA secure schemes depends on the number of
devices in the setting above.
In this contribution, we devise a new solution to the selective
opening problem that does not build on lossy encryption. Instead, we
combine techniques from noncommitting encryption and hash proof
systems with a new technique (dubbed ``crossauthentication codes'')
to glue several ciphertext parts together. The result is a rather
practical
SOCCA secure publickey encryption scheme that does not suffer from
the efficiency drawbacks of known schemes. Since we build upon hash
proof systems, our scheme can be instantiated using standard
numbertheoretic assumptions such as decisional DiffieHellman
(DDH), decisional composite residuosity (DCR), and quadratic
residuosity (QR). Besides, we construct a conceptually very simple
and comparatively efficient SOCPA secure scheme from (slightly
enhanced) trapdoor oneway permutations.
We stress that our schemes are completely independent of the number
of challenge ciphertexts, and we do not make assumptions about the
underlying message distribution (beyond being efficiently
samplable). In particular, we do not assume efficient conditional
resamplability of the message distribution. Hence, our schemes are
secure in arbitrary settings, even if it is not known in
advance how many ciphertexts might be considered for corruptions.
Serge Fehr
Quantum Cryptography
In Foundations of Physics, volume 40, number 5, pages 494531. SpringerVerlag, 2010.
Abstract:
Quantum cryptography makes use of the quantummechanical behavior of nature for the design and analysis of cryptographic schemes. Optimally (but not always), quantum cryptography allows for the design of cryptographic schemes whose security is guaranteed solely by the laws of nature. This is in sharp contrast to standard cryptographic schemes, which can be broken in principle, i.e., when given sufficient computing power. From a theory point of view, quantum cryptography offers a beautiful interplay between the mathematics of adversarial behavior and quantum information theory.
In this review article, we discuss the traditional application of quantum cryptography, quantum key distribution (QKD), from a modern perspective, and we discuss some recent developments in the context of quantum twoparty cooperation (2PC). QKD allows two distant parties to communicate in a provablysecure way in the presence of
an outside eavesdropper, whereas 2PC is concerned with protecting information against possibly malicious insiders. We show the basic idea of constructing quantum cryptographic schemes, but we also show some connections to quantum information theory as needed for the rigorous security analyses, and we discuss some of the relevant quantuminformationtheoretic results.
Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner
Improving the Security of Quantum Protocols via CommitandOpen
In Advances in Cryptology  CRYPTO '09, volume 5677 of Lecture Notes in Computer Science, pages 408427. SpringerVerlag, 2009.
Also: Accepted to QIP 2010.
Abstract:
We consider twoparty 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 boundedquantumstorage model (BQSM), so if the original protocol was BQSMsecure, 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 BQSMsecure 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.
Serge Fehr, and Christian Schaffner
Composing Quantum Protocols in a Classical Environment
In Theory of Cryptography Conference  TCC '09, volume 5444 of Lecture Notes in Computer Science, pages 350367. SpringerVerlag, 2009.
Abstract:
We propose a general security definition for cryptographic quantum
protocols that implement classical nonreactive twoparty tasks. The
definition is expressed in terms of simple quantuminformation
theoretic conditions which must be satisfied by the protocol to be
secure. The conditions are uniquely determined by the ideal
functionality F defining the cryptographic task to be implemented.
We then show the following composition result. If quantum protocols
pi_1,...,pi_l securely implement ideal functionalities F_1,...,F_l
according to our security definition, then any purely classical
twoparty protocol, which makes sequential calls to F_1,...,F_l,
is equally secure as the protocol obtained by replacing the calls
to F_1,...,F_l with the respective quantum protocols pi_1,...,pi_l.
Hence, our approach yields the minimal security requirements which
are strong enough for the typical use of quantum protocols as
subroutines within larger classical schemes. Finally, we show that
recently proposed quantum protocols for secure identification and
oblivious transfer in the boundedquantumstorage model satisfy our
security definition, and thus compose in the above sense.
Alexandra Boldyreva, Serge Fehr, and Adam O'Neill
On Notions of Security for Deterministic Encryption, and Efficient Constructions Without Random Oracles
In Advances in Cryptology  CRYPTO '08, volume 5157 Lecture Notes in Computer Science, pages 335359. SpringerVerlag, 2008.
Abstract:
The study of deterministic publickey encryption was initiated by Bellare et al. (CRYPTO '07), who provided the "strongest possible" notion of security for this primitive (called PRIV) and constructions in the random oracle (RO) model. We focus on constructing efficient deterministic encryption schemes without random oracles. To do so, we propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is apriori hardtoguess given the others (while PRIV did not have the latter restriction). Nevertheless, we argue that this version seems adequate for many practical applications. We show equivalence of this definition to singlemessage and indistinguishabilitybased ones, which are easier to work with. Then we give general constructions of both chosenplaintext (CPA) and chosenciphertextattack (CCA) secure deterministic encryption schemes, as well as efficient instantiations of them under standard numbertheoretic assumptions. Our constructions build on the recentlyintroduced framework of Peikert and Waters (STOC '08) for constructing CCAsecure probabilistic encryption schemes, extending it to the deterministicencryption setting as well.
Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs
Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
In Advances in Cryptology  EUROCRYPT '08, volume 4965 of Lecture Notes in Computer Science, pages 471488. SpringerVerlag, 2008.
Abstract:
Consider an abstract storage device Σ(G) that can hold a single element
x from a fixed, publicly known finite group G. Storage is private in the
sense that an adversary does not have read access to Σ(G) at all. However, Σ(G)
is nonrobust in the sense that the adversary can modify its contents by adding
some offset Δ ∈ G. Due to the privacy of the storage device, the value Δ can only
depend on an adversary's a priori knowledge of x. We introduce a new primitive
called an algebraic manipulation detection (AMD) code, which encodes a source
s into a value x stored on Σ(G) so that any tampering by an adversary will be detected.
We give a nearly optimal construction of AMD codes, which can flexibly
accommodate arbitrary choices for the length of the source s and security level.
We use this construction in two applications:
 We show how to efficiently convert any linear secret sharing scheme into a
robust secret sharing scheme, which ensures that no unqualified subset of
players can modify their shares and cause the reconstruction of some value
s' ≠ s.
 We show how to build nearly optimal robust fuzzy extractors for several natural
metrics. Robust fuzzy extractors enable one to reliably extract and later
recover random keys from noisy and nonuniform secrets, such as biometrics,
by relying only on nonrobust public storage. In the past, such constructions
were known only in the random oracle model, or required the entropy
rate of the secret to be greater than half. Our construction relies on a randomly
chosen common reference string (CRS) available to all parties.
Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
Cryptography in the Bounded QuantumStorage Model
In SIAM Journal on Computing, 37(6): 18651890, 2008.
Abstract:
We initiate the study of twoparty cryptographic primitives with
unconditional security, assuming that the adversary's {\em quantum}
memory is of bounded size. We show that oblivious transfer and bit
commitment can be implemented in this model using protocols where
honest parties need no quantum memory, whereas an adversarial player
needs quantum memory of size at least $n/2$ in order to break the
protocol, where $n$ is the number of qubits transmitted. This is in
sharp contrast to the classical boundedmemory model, where we can
only tolerate adversaries with memory of size quadratic in honest
players' memory size. Our protocols are efficient, noninteractive
and can be implemented using today's technology. On the technical
side, a new entropic uncertainty relation involving minentropy is
established.
Serge Fehr, and Christian Schaffner
Randomness Extraction via DeltaBiased Masking in the Presence of a Quantum Attacker
In Theory of Cryptography Conference  TCC '08, volume 4948 of Lecture Notes in Computer Science, pages 465481. SpringerVerlag, 2008.
Abstract:
Randomness extraction is of fundamental importance for informationtheoretic
cryptography. It allows to transform a raw key about which an attacker has some
limited knowledge into a fully secure random key, on which the attacker has
essentially no information.
We show a new randomnessextraction technique which works also in case where the
attacker has quantum information on the raw key. Randomness extraction is done by
xor'ing a socalled $\delta$biased mask to the raw key. Up to date, only very
few techniques are known to work against a quantum attacker, much in contrast to
the classical (nonquantum) setting, which is much better understood and for which
a vast amount of different techniques for randomness extraction are known.
We show two applications of the new result. We first show how to encrypt a long
message with a short key, informationtheoretically secure against a quantum
attacker, provided that the attacker has enough quantum uncertainty on the message.
This generalizes the concept of entropicallysecure encryption to the case of a
quantum attacker.
And, as a second application, we show how the new randomnessextraction technique
allows to do errorcorrection without leaking partial information to a quantum
attacker. Such a technique is useful in settings where the raw key may contain
errors, since standard errorcorrection techniques may provide the attacker with
information on, say, a secret key that was used to obtain the raw key.
Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
Secure Identification and QKD in the BoundedQuantumStorage Model
In Advances in Cryptology  CRYPTO '07, volume 4622 of Lecture Notes in Computer Science, pages 342359. SpringerVerlag, 2007.
Also: Accepted to QIP 2008.
Abstract:
We consider the problem of secure identification: user U proves to
server S that he knows an agreed (possibly lowentropy) 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
quantumstorage 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 maninthemiddle attack, but requires U and S to
additionally share a highentropy 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 reused.
A small modification to the identification scheme results in a
quantumkeydistribution (QKD) scheme, secure in the bounded
quantumstorage model, with the same reusability 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.
Ivan Damgård, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner
A Tight HighOrder Entropic Quantum Uncertainty Relation With Applications
In Advances in Cryptology  CRYPTO '07, volume 4622 of Lecture Notes in Computer Science, pages 360378. SpringerVerlag, 2007.
Also: Accepted to QIP 2008.
Masayuki Abe, and Serge Fehr
Perfect NIZK with Adaptive Soundness
In Theory of Cryptography Conference  TCC '07, volume 4392 of Lecture Notes in Computer Science, pages 118136. SpringerVerlag, 2007.
Abstract:
This paper presents a very simple and efficient adaptivelysound
perfect NIZK argument system for any NPlanguage. In contrast to
recently proposed schemes by Groth, Ostrovsky and Sahai, our
scheme does not pose any restriction on the statements to be
proven. Besides, it enjoys a number of desirable properties: it
allows to reuse the common reference string (CRS), it can handle
arithmetic circuits, and the CRS can be setup very efficiently
without the need for an honest party. We then show an application
of our techniques in constructing efficient NIZK schemes for
proving arithmetic relations among committed secrets, whereas
previous methods required expensive generic NPreductions.
The security of the proposed schemes is based on a strong
nonstandard assumption, an extended version of the socalled
KnowledgeofExponent Assumption (KEA) over bilinear groups. We
give some justification for using such an assumption by showing
that the commonlyused approach for proving NIZK arguments sound
does not allow for adaptivelysound statistical NIZK arguments
(unless NP is in P/poly). Furthermore, we show that the assumption
used in our construction holds with respect to generic adversaries
that do not exploit the specific representation of the group
elements. We also discuss how to avoid the nonstandard assumption
in a preprocessing model.
Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
Oblivious Transfer and Linear Functions
In Advances in Cryptology  CRYPTO '06, volume 4117 of Lecture Notes in Computer Science, pages 427444. SpringerVerlag, 2006.
Abstract:
We study unconditionally secure 1outof2 Oblivious Transfer
(12 OT). We first point out that a standard security
requirement for 12 OT of bits, namely that the receiver only
learns one of the bits sent, holds if and only if the receiver
has no information on the XOR of the two bits. We then
generalize this to 12 OT of strings and show that the security
can be characterized in terms of binary linear functions.
More precisely, we show that the receiver learns only one of
the two strings sent if and only if he has no information on
the result of applying any binary linear function (which
nontrivially depends on both inputs) to the two strings.
We then argue that this result not only gives new insight into
the nature of 12 OT, but it in particular provides a very
powerful tool for analyzing 12 OT protocols. We demonstrate
this by showing that with our characterization at hand, the
reducibility of 12 OT (of strings) to a wide range of weaker
primitives follows by a very simple argument. This is in sharp
contrast to previous literature, where reductions of 12 OT to
weaker flavors have rather complicated and sometimes even
incorrect proofs.
Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
Cryptography in the Bounded QuantumStorage Model
In 46th Symposium on Foundations of Computer Science (FOCS), pages 449458, 2005.
Also: Invited talk at QIP 2006.
Abstract:
We initiate the study of twoparty cryptographic primitives with
unconditional security, assuming that the adversary's {\em quantum}
memory is of bounded size. We show that oblivious transfer and bit
commitment can be implemented in this model using protocols where
honest parties need no quantum memory, whereas an adversarial player
needs quantum memory of size at least $n/2$ in order to break the
protocol, where $n$ is the number of qubits transmitted. This is in
sharp contrast to the classical boundedmemory model, where we can
only tolerate adversaries with memory of size quadratic in honest
players' memory size. Our protocols are efficient, noninteractive
and can be implemented using today's technology. On the technical
side, a new entropic uncertainty relation involving minentropy is
established.
Ronald Cramer, Serge Fehr, and Martijn Stam
BlackBox Secret Sharing from Primitive Sets in Algebraic Number Fields
In Advances in Cryptology  CRYPTO '05, volume 3621 of Lecture Notes in Computer Science, pages 344360. SpringerVerlag, 2005.
Abstract:
A {\em blackbox} secret sharing scheme (BBSSS) for a given access
structure works in exactly the same way over any finite Abelian
group, as it only requires blackbox access to group operations and
to random group elements. In particular, there is no dependence on
e.g.\ the structure of the group or its order. The expansion factor
of a BBSSS is the length of a vector of shares (the number of group
elements in it) divided by the number of players $n$.
At CRYPTO 2002 Cramer and Fehr proposed a threshold BBSSS with an
asymptotically minimal expansion factor $\Theta(\log n)$.
In this paper we propose a BBSSS that is based on a new paradigm,
namely, {\em primitive sets in algebraic number fields}. This leads
to a new BBSSS with an expansion factor that is absolutely minimal
up to an additive term of at most~2, which is an improvement by a
constant additive factor.
We provide good evidence that our scheme is considerably more
efficient in terms of the computational resources it requires.
Indeed, the number of group operations to be performed is
$\tilde{O}(n^2)$ instead of $\tilde{O}(n^3)$ for sharing and
$\tilde{O}(n^{1.6})$ instead of $\tilde{O}(n^{2.6})$ for
reconstruction.
Finally, we show that our scheme, as well as that of Cramer and
Fehr, has asymptotically optimal randomness efficiency.
Masayuki Abe, and Serge Fehr
Adaptively Secure Feldman VSS and Applications to UniversallyComposable Threshold Cryptography
In Advances in Cryptology  CRYPTO '04, volume 3152 of Lecture Notes in Computer Science, pages 317334. SpringerVerlag, 2004.
Abstract:
We propose the first distributed discretelog key generation (DLKG) protocol from scratch which
is adaptivelysecure in the nonerasure model, and at the same time completely avoids the use
of interactive zeroknowledge proofs. As a consequence, the protocol can be proven secure in a
universallycomposable (UC) like framework which prohibits rewinding. We prove the security in
what we call the singleinconsistentplayer (SIP) UC model, which guarantees arbitrary
composition as long as all protocols are executed by the same players. As applications, we
propose a fully UC threshold Schnorr signature scheme, a fully UC threshold DSS signature
scheme, and a SIP UC threshold CramerShoup cryptosystem.
Our results are based on a new adaptivelysecure Feldman VSS scheme. Although adaptive security
was already addressed by Feldman in the original paper, the scheme requires secure communication,
secure erasure, and either a linear number of rounds or digital signatures to resolve disputes.
Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction
on the corruption behavior of the adversary, which however disappears in some applications
including our new DLKG protocol.
We also propose several new adaptivelysecure protocols, which may find other applications, like
a distributed trapdoorkey generation protocol for Pedersen's commitment scheme, an
adaptivelysecure Pedersen VSS scheme (as a {\em committed} VSS), or distributedverifier proofs
for proving relations among commitments or even any NP relations in general.
Ivan Damgård, Serge Fehr, and Louis Salvail
ZeroKnowledge Proofs and String Commitments Withstanding Quantum Attacks
In Advances in Cryptology  CRYPTO '04, volume 3152 of Lecture Notes in Computer Science, pages 254272. SpringerVerlag, 2004
Abstract:
The concept of zeroknowledge (ZK) has become of fundamental importance
in cryptography. However, in a setting where entities are modeled by
quantum computers, classical arguments for proving ZK fail to hold since,
in the quantum setting, the concept of rewinding is not generally
applicable. Moreover, known classical techniques that avoid rewinding
have various shortcomings in the quantum setting.
We propose new techniques for building {\em quantum} zeroknowledge (QZK)
protocols, which remain secure even under (active) quantum attacks. We
obtain computational QZK proofs and perfect QZK arguments for any NP
language in the common reference string model. This is based on a general
method converting an important class of classical honestverifier ZK (HVZK)
proofs into QZK proofs. This leads to quite practical protocols if the
underlying HVZK proof is efficient. These are the first proof protocols
enjoying these properties, in particular the first to achieve perfect QZK.
As part of our construction, we propose a general framework for building
unconditionally hiding (trapdoor) string commitment schemes, secure against
quantum attacks, as well as concrete instantiations based on specific
(believed to be) hard problems. This is of independent interest, as these
are the first unconditionally hiding string commitment schemes withstanding
quantum attacks.
Finally, we give a partial answer to the question whether QZK is possible
in the plain model. We propose a new notion of QZK, {\em nonoblivious
verifier} QZK, which is strictly stronger than honestverifier QZK but
weaker than full QZK, and we show that this notion can be achieved by means
of efficient (quantum) protocols.
Ivan Damgård, Serge Fehr, Kirill Morozov, and Louis Salvail
Unfair Noisy Channels and Oblivious Transfer
In Theory of Cryptography Conference  TCC '04, volume 2951 of Lecture Notes in Computer Science, pages 355373. SpringerVerlag, 2004.
Abstract:
In a paper from EuroCrypt'99, Damg{\aa}rd, Kilian and Salvail show
various positive and negative results on constructing Bit Commitment
(BC) and Oblivious Transfer (OT) from Unfair Noisy Channels (UNC),
i.e., binary symmetric channels where the error rate is only known
to be in a certain interval $[\gamma ..\delta]$ and can be chosen
adversarily. They also introduce a related primitive called
$PassiveUNC$.
We prove in this paper that any OT protocol that can be constructed
based on a $PassiveUNC$ and is secure against a passive adversary
can be transformed using a generic ``compiler'' into an OT protocol
based on a $UNC$ which is secure against an active adversary. Apart
from making positive results easier to prove in general, this also
allows correcting a problem in the EuroCrypt'99 paper: There, a
positive result was claimed on constructing from UNC an OT that is
secure against active cheating. We point out that the proof sketch
given for this was incomplete, and we show that a correct proof of a
much stronger result follows from our general compilation result and
a new technique for transforming between weaker versions of OT with
different parameters.
Serge Fehr
Secure MultiPlayer Protocols: Fundamentals, Generality, and Efficiency
PhD Dissertation, University of Aarhus, Denmark, 2003.
Available files:


Ronald Cramer, Serge Fehr, Yuval Ishai, and Eyal Kushilevitz
Efficient MultiParty Computation over Rings
In Advances in Cryptology  EUROCRYPT '03, volume 2656 of Lecture Notes in Computer Science, pages 596613. SpringerVerlag, 2003.
Abstract:
Secure multiparty computation (MPC) is an active research area, and a
wide range of literature can be found nowadays suggesting improvements
and generalizations of existing protocols in various directions.
However, all current techniques for secure MPC apply to functions that
are represented by (boolean or arithmetic) circuits over finite
{\em fields}. We are motivated by two limitations of these techniques:
 {\sc Generality.} Existing protocols do not apply to computation
over more general algebraic structures (except via a bruteforce
simulation of computation in these structures).
 {\sc Efficiency.} The best known {\em constantround} protocols
do not efficiently scale even to the case of large finite fields.
Our contribution goes in these two directions. First, we propose a basis
for unconditionally secure MPC over an arbitrary finite {\em ring}, an
algebraic object with a much less nice structure than a field, and obtain
efficient MPC protocols requiring only a {\em blackbox access} to the
ring operations and to random ring elements. Second, we extend these
results to the constantround setting, and suggest efficiency improvements
that are relevant also for the important special case of fields. We
demonstrate the usefulness of the above results by presenting a novel
application of MPC over (nonfield) rings to the roundefficient secure
computation of the maximum function.
Masayuki Abe, Ronald Cramer, and Serge Fehr
NonInteractive DistributedVerifier Proofs and Proving Relations
among Commitments
In Advances in Cryptology  ASIACRYPT '02, volume 2501 of Lecture Notes in Computer Science, pages 206223. SpringerVerlag, 2002.
Abstract:
A {\em commitment multiplication proof}, CMP for short, allows a player who is
committed to secrets $s$, $s'$ and $s'' = s \cdot s'$, to prove, without revealing
$s,s'$ or $s''$, that indeed $s'' = s s'$. CMP is an important building block for
secure general multiparty computation as well as threshold cryptography.
In the standard cryptographic model, a CMP is typically done interactively using
zeroknowledge protocols. In the random oracle model it can be done non
interactively by removing interaction using the FiatShamir heuristic. An
alternative noninteractive solution in the distributed setting, where at most a
certain fraction of the verifiers are malicious, was presented in [Abe99] for
Pedersen's discrete log based commitment scheme. This CMP essentially consists of a
few invocations of Pedersen's verifiable secret sharing scheme (VSS) and is secure
in the standard model.
In the first part of this paper, we improve that CMP by arguing that a building
block used in its construction in fact already constitutes a CMP. This not only
leads to a simplified exposition, but also saves on the required number of
invocations of Pedersen's VSS. Next we show how to construct noninteractive
proofs of partial knowledge [CDS94] in this distributed setting. This allows for
instance to prove noninteractively the knowledge of $\ell$ out of $m$ given secrets,
without revealing which ones. We also show how to construct efficient noninteractive
zeroknowledge proofs for circuit satisfiability in the distributed setting.
In the second part, we investigate generalizations to other homomorphic commitment
schemes, and show that on the negative side, Pedersen's VSS cannot be generalized
to arbitrary (blackbox) homomorphic commitment schemes, while on the positive side,
commitment schemes based on $q$onewaygrouphomomorphism [CD98], which cover wide
range of currently used schemes, suffice.
Serge Fehr, and Ueli Maurer
Linear VSS and Distributed Commitments Based on Secret Sharing and
Pairwise Checks
In Advances in Cryptology  CRYPTO '02, volume 2442 of Lecture Notes in Computer Science, pages 565580. SpringerVerlag, 2002.
Abstract:
We present a general treatment of all noncryptographic (i.e., information
theoretically secure) linear verifiablesecretsharing (VSS) and distributed
commitment (DC) schemes, based on an underlying secret sharing scheme, pairwise
checks between players, complaints, and accusations of the dealer. VSS and DC
are main building blocks for unconditional secure multiparty computation
protocols. This general approach covers all known linear VSS and DC schemes.
The main theorem states that the security of a scheme is equivalent to a pure
linearalgebra condition on the linear mappings (e.g.~described as matrices and
vectors) describing the scheme. The security of all known schemes follows as
corollaries whose proofs are pure linearalgebra arguments, in contrast to some
hybrid arguments used in the literature. Our approach is demonstrated for the
CDM DC scheme, which we generalize to be secure against mixed adversary settings
(some curious and some dishonest players), and for the classical BGW VSS scheme,
for which we show that some of the checks between players are superfluous, i.e.,
the scheme is not optimal. More generally, our approach, establishing the minimal
conditions for security (and hence the common denominator of the known schemes),
can lead to the design of more efficient VSS and DC schemes for general adversary
structures.
Ronald Cramer, and Serge Fehr
Optimal BlackBox Secret Sharing over Arbitrary Abelian Groups
In Advances in Cryptology  CRYPTO '02, volume 2442 of Lecture Notes in Computer Science, pages 272287. SpringerVerlag, 2002.
Abstract:
A {\em blackbox} secret sharing scheme for the threshold access structure
$T_{t,n}$ is one which works over any finite Abelian group $G$. Briefly, such
a scheme differs from an ordinary linear secret sharing scheme (over, say, a
given finite field) in that distribution matrix and reconstruction vectors
are defined over $\Z$ and are designed {\em independently} of the group $G$
from which the secret and the shares are sampled. This means that perfect
completeness and perfect privacy are guaranteed {\em regardless} of which
group $G$ is chosen. We define the blackbox secret sharing problem as the
problem of devising, foran arbitrary given $T_{t,n}$, a scheme with minimal
expansion factor, i.e., where the length of the full vector of shares divided
by the number of players $n$ is minimal.
Such schemes are relevant for instance in the context of distributed
cryptosystems based on groups with secret or hard to compute group order. A
recent example is secure general multiparty computation over blackbox rings.
In 1994 Desmedt and Frankel have proposed an elegant approach to the blackbox
secret sharing problem based in part on polynomial interpolation over
cyclotomic number fields. For arbitrary given $T_{t,n}$ with $0 < t < n1$, the
expansion factor of their scheme is $O(n)$. This is the best previous general
approach to the problem.
Using certain low degree integral extensions of $\Z$ over which there exist
pairs of sufficiently large Vandermonde matrices with coprime determinants,
we construct, for arbitrary given $T_{t,n}$ with $0 < t < n1$, a blackbox secret
sharing scheme with expansion factor $O(\log n)$, which we show is minimal.
Ronald Cramer, Ivan Damgård, and Serge Fehr
On the Cost of Reconstructing a Secret, or VSS with Optimal Reconstruction Phase
In Advances in Cryptology  CRYPTO '01, volume 2139 of Lecture Notes in Computer Science, pages 503523. SpringerVerlag, 2001.
Abstract:
Consider a scenario where an $l$bit secret has been distributed among $n$
players by an honest dealer using some secret sharing scheme. Then, if all
players behave honestly, the secret can be reconstructed in one round with zero
error probability, and by broadcasting $nl$ bits.
We ask the following question: how close to this ideal can we get if up to $t$
players (but not the dealer) are corrupted by an adaptive, active adversary with
unbounded computing power?  and where in addition we of course require that the
adversary does not learn the secret ahead of reconstruction time. It is easy to
see that $t= \lfloor (n1)/2 \rfloor$ is the maximal value of $t$ that can be
tolerated, and furthermore, we show that the best we can hope for is a oneround
reconstruction protocol where every honest player outputs the correct secret or
``failure''. For any such protocol with failure probability at most
$2^{\Omega(k)}$, we show a lower bound of $\Omega(nl + k n^2)$ bits on the
information communicated. We further show that this is tight up to a constant
factor.
The lower bound trivially applies as well to VSS schemes, where also the dealer
may be corrupt. Using generic methods, the scheme establishing the upper bound
can be turned into a VSS with efficient reconstruction. \linebreak However, the
distribution phase becomes very inefficient. Closing this gap, we present a new
VSS protocol where the distribution complexity matches that of the previously best
known VSS, but where the reconstruction phase meets our lower bound up to a
constant factor. The reconstruction is a factor of $n$ better than previous VSS
protocols. We show an application of this to multiparty computation with
preprocessing, improving the complexity of earlier similar protocols by a factor
of $n$.
Serge Fehr
Efficient Construction of the Dual Span Program
Manuscript, May 1999.
Abstract:
We consider monotone span programs as a tool for representing,
we will say {\em computing}, general access structures. It is
known that if an access structure is computed by a monotone span
program, then the dual access structure is computed by a monotone
span program of the same size. We will strengthen this result by
proving that such an span program not only exists, but can be
efficiently computed.
 