## CryptoDB

### Serge Fehr

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
Abstract

We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis.
Our main technical contribution is a framework that simplifies the use of (the parallel-query generalization of) the compressed oracle technique for proving query complexity results. With our framework in place, whenever applicable, it is possible to prove quantum query complexity lower bounds by means of purely classical reasoning. More than that, for typical examples the crucial classical observations that give rise to the classical bounds are sufficient to conclude the corresponding quantum bounds.
We demonstrate this on a few examples, recovering known results but also obtaining new results. Our main target is the hardness of finding a q-chain with fewer than q parallel queries, i.e., a sequence x_0, x_1, ..., x_q with x_i = H(x_{i-1}) for all 1 \leq i \leq q.
The above problem of finding a hash chain is of fundamental importance in the context of proofs of sequential work. Indeed, as a concrete cryptographic application of our techniques, we prove quantum security of the ``Simple Proofs of Sequential Work'' by Cohen and Pietrzak.

2021

CRYPTO

Compressing Proofs of k-Out-Of-n Partial Knowledge
Abstract

In a proof of partial knowledge, introduced by Cramer, Damg{\aa}rd and Schoenmakers (CRYPTO 1994), a prover knowing witnesses for some $k$-subset of $n$ given public statements can convince the verifier of this claim without revealing which $k$-subset.
Their solution combines $\Sigma$-protocol theory and linear secret sharing, and achieves linear communication complexity for general $k,n$.
Especially the ``one-out-of-$n$'' case $k=1$ has seen myriad applications during the last decades, e.g., in electronic voting, ring signatures, and confidential transaction systems.
In this paper we focus on the discrete logarithm (DL) setting, where the prover claims knowledge of DLs of $k$-out-of-$n$ given elements.
Groth and Kohlweiss (EUROCRYPT 2015) have shown how to solve the special case $k=1$ %, yet arbitrary~$n$,
with {\em logarithmic} (in $n$) communication, instead of linear as prior work. However, their method takes explicit advantage of $k=1$ and does not generalize to $k>1$.
Alternatively, an {\em indirect} approach for solving the considered problem is by translating the $k$-out-of-$n$ relation into a circuit and then applying communication-efficient circuit ZK. Indeed, for the $k=1$ case this approach has been highly optimized, e.g., in ZCash.
Our main contribution is a new, simple honest-verifier zero-knowledge proof protocol for proving knowledge of $k$ out of $n$ DLs with {\em logarithmic} communication and {\em for general $k$ and $n$}, without requiring any generic circuit ZK machinery.
Our solution puts forward a novel extension of the {\em compressed} $\Sigma$-protocol theory (CRYPTO 2020), which we then utilize to compress a new $\Sigma$-protocol for proving knowledge of $k$-out-of-$n$ DL's down to logarithmic size. The latter $\Sigma$-protocol is inspired by the CRYPTO 1994 approach, but a careful re-design of the original protocol is necessary for the compression technique to apply.
Interestingly, {\em even for $k=1$ and general $n$} our approach improves prior {\em direct} approaches as it reduces prover complexity without increasing the communication complexity.
Besides the conceptual simplicity,
we also identify regimes of
practical relevance where our approach achieves asymptotic and concrete improvements,
e.g., in proof size and prover complexity, over the generic approach based on circuit-ZK.
Finally, we show various extensions and generalizations of our core result. For instance, we extend our protocol to proofs of partial knowledge of Pedersen (vector) commitment openings, and/or to include a proof that the witness satisfies some additional constraint, and we show how to extend our results to non-threshold access structures.

2020

TCC

Robust Secret Sharing with Almost Optimal Share Size and Security Against Rushing Adversaries
📺
Abstract

We show a robust secret sharing scheme for a maximal threshold $t < n/2$ that features an optimal overhead in share size, offers security against a rushing adversary, and runs in polynomial time. Previous robust secret sharing schemes for $t < n/2$ either suffered from a suboptimal overhead, offered no (provable) security against a rushing adversary, or ran in superpolynomial time.

2020

EUROCRYPT

On the Quantum Complexity of the Continuous Hidden Subgroup Problem
📺
Abstract

The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor's celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms.
The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m, even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices.
The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits.
This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.

2020

CRYPTO

The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More
📺
Abstract

We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and Zhandry on the security of the Fiat-Shamir transformation of sigma-protocols in the quantum random oracle model (QROM). Two natural questions that arise in this context are: (1) whether the results extend to the Fiat-Shamir transformation of {\em multi-round} interactive proofs, and (2) whether Don et al.'s O(q^2) loss in security is optimal.
Firstly, we answer question (1) in the affirmative. As a byproduct of solving a technical difficulty in proving this result, we slightly improve the result of Don et al., equipping it with a cleaner bound and an even simpler proof. We apply our result to digital signature schemes showing that it can be used to prove strong security for schemes like MQDSS in the QROM. As another application we prove QROM-security of a non-interactive OR proof by Liu, Wei and Wong.
As for question (2), we show via a Grover-search based attack that Don et al.'s quadratic security loss for the Fiat-Shamir transformation of sigma-protocols is optimal up to a small constant factor. This extends to our new multi-round result, proving it tight up to a factor that depends on the number of rounds only, i.e. is constant for any constant-round interactive proof.

2019

EUROCRYPT

Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary
📺
Abstract

Robust secret sharing enables the reconstruction of a secret-shared 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^{-\kappa }$$ and with some overhead in the share size.Recently, Bishop, Pastro, Rajaraman and Wichs [3] proposed a scheme with an (almost) optimal overhead of $$\widetilde{O}(\kappa )$$. This seems to answer the open question posed by Cevallos et al. [6] who proposed a scheme with overhead of $$\widetilde{O}(n+\kappa )$$ 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 non-rushing 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(\kappa n^\varepsilon )$$, where $$\varepsilon > 0$$ is arbitrary but fixed. This $$n^\varepsilon $$-factor is obviously worse than the $$\mathrm {polylog}(n)$$-factor hidden in the $$\widetilde{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 $$\kappa $$ is substantially smaller than n).A small variation of our scheme has the same $$\widetilde{O}(\kappa )$$ overhead as the scheme of Bishop et al. and achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.

2019

CRYPTO

Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model
📺
Abstract

The famous Fiat-Shamir transformation turns any public-coin three-round interactive proof, i.e., any so-called
$$\Sigma {\text {-protocol}}$$
, into a non-interactive proof in the random-oracle 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 Fiat-Shamir transformation in the quantum random-oracle model into a similarly successful quantum dishonest prover attacking the underlying
$$\Sigma {\text {-protocol}}$$
(in the standard model). Applied to the standard soundness and proof-of-knowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the Fiat-Shamir 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 post-quantum secure signature schemes, our results imply that for any
$$\Sigma {\text {-protocol}}$$
that is a proof-of-knowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding Fiat-Shamir signature scheme is secure in the quantum random-oracle model. For example, we can conclude that the non-optimized version of Fish, which is the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.

2018

TOSC

Short Non-Malleable Codes from Related-Key Secure Block Ciphers
Abstract

A non-malleable 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 split-state model, which simply encodes a message m as k||Ek(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 related-key attacks on E. In this work, we prove this construction to be a strong non-malleable code as long as E is (i) a pseudorandom permutation under leakage and (ii) related-key secure with respect to an arbitrary but fixed key relation. Both properties are believed to hold for “good” block ciphers, such as AES-128, making this non-malleable code very efficient with short codewords of length |m|+2τ (where τ is the security parameter, e.g., 128 bits), without significant security penalty.

2018

TCC

Secure Certification of Mixed Quantum States with Application to Two-Party Randomness Generation
Abstract

We investigate sampling procedures that certify that an arbitrary quantum state on n subsystems is close to an ideal mixed state $$\varphi ^{\otimes n}$$ for a given reference state $$\varphi $$, 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 mixed-state 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 two-party quantum coin-tossing. 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 high-entropy source, where the entropy is an arbitrarily small fraction below the maximum.

2018

TCC

Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions
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 quantum-security of hash functions; this is in contrast to previous proofs which are in terms of sophisticated quantum-information-theoretic and quantum-algorithmic reasoning.

2017

EUROCRYPT

2016

EUROCRYPT

2015

EUROCRYPT

2010

EPRINT

Position-Based Quantum Cryptography
Abstract

In this work, we initiate the study of position-based cryptography in the quantum setting. The aim of position-based cryptography is to use the geographical position of a party as its only credential. This has interesting applications, e.g., it enables two military bases to talk to each other over insecure (i.e. neither private nor authenticated) channels and without having any pre-shared key, with the guarantee that only parties within the bases learn the content of the conversation. We present schemes for several important position-based cryptographic tasks: positioning, authentication, and key exchange, and we prove them unconditionally secure, i.e., without assuming any restriction on the adversaries (beyond the laws of quantum mechanics). At the core of our security proofs lies the strong complementary information tradeoff recently introduced by Renes and Boileau. An attractive feature of all our schemes is that they only involve ``simple'' quantum operations, namely to prepare, communicate and measure-upon-arrival individual qubits. We stress that
the above position-based tasks are impossible in the classical setting without limiting the adversary. Therefore, our work shows that position-based quantum cryptography is one of the rare examples besides QKD for which there is such a strong separation between classical and quantum cryptography. Besides the schemes for which we give rigorous security proofs, we also present a couple of significantly more efficient schemes for which we can merely conjecture security; proving them secure remains an interesting challenge. Our results open a fascinating new direction for position-based security in cryptography where security of protocols is solely based on the laws of physics and proofs of security do not require any pre-existing infrastructure.

2008

TCC

2008

EUROCRYPT

2008

CRYPTO

2008

EPRINT

Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
Abstract

Consider an abstract storage device $\Sigma(\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 $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense
that the adversary can modify its contents by adding some offset $\Delta \in \G$.
Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We introduce a new primitive called an {\em
algebraic manipulation detection} (AMD) code, which encodes a source $s$ into a value $x$ stored on $\Sigma(\G)$ so that any tampering
by an adversary will be detected, except with a small error probability $\delta$. 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 $\delta$. We use this construction in two applications:
\begin{itemize}
\item We show how to efficiently convert any linear secret sharing
scheme into a {\em robust secret sharing scheme}, which ensures that
no \emph{unqualified subset} of players can modify their shares and cause
the reconstruction of some value $s'\neq s$.
\item
We show how how to build nearly optimal {\em robust fuzzy
extractors} for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets,
such as biometrics, by relying only on {\em non-robust 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.
\end{itemize}

2008

EPRINT

On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles
Abstract

The study of deterministic public-key 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
\emph{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
a-priori hard-to-guess \emph{given the others} (while PRIV did not
have the latter restriction). Nevertheless, we argue that this
version seems adequate for certain practical applications. We show
equivalence of this definition to single-message and
indistinguishability-based ones, which are easier to work with.
Then we give general constructions of both chosen-plaintext (CPA)
and chosen-ciphertext-attack (CCA) secure deterministic encryption
schemes, as well as efficient instantiations of them under standard
number-theoretic assumptions. Our constructions build on the
recently-introduced framework of Peikert and Waters (STOC '08) for
constructing CCA-secure \emph{probabilistic} encryption schemes,
extending it to the deterministic-encryption setting and yielding
some improvements to their original results as well.

2007

EPRINT

Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker
Abstract

Randomness extraction is of fundamental importance for information-theoretic 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 randomness-extraction technique which works also in case where the attacker has quantum information on the raw key. Randomness extraction is done by XORing a so-called 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 (non-quantum) 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, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker.
As a second application, we show how the new randomness-extraction technique allows to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key.

2007

EPRINT

Secure Identification and QKD in the Bounded-Quantum-Storage Model
Abstract

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.

2007

EPRINT

A Tight High-Order Entropic Quantum Uncertainty Relation With Applications
Abstract

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.

2006

EPRINT

Perfect NIZK with Adaptive Soundness
Abstract

This paper presents a very simple and efficient adaptively-sound perfect NIZK argument system for any NP-language. In contrust 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 re-use the common reference string (CRS), it can handle
arithmetic circuits, and the CRS can be set-up 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 NP-reductions.
The security of the proposed schemes is based on a strong non-standard assumption, an extended version of the so-called Knowledge-of-Exponent Assumption (KEA) over bilinear groups. We give some justification for using such an assumption by showing that the commonly-used approach for proving NIZK arguments sound does not allow for adaptively-sound 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 non-standard
assumption in a pre-processing model.

2005

EPRINT

Cryptography In the Bounded Quantum-Storage Model
Abstract

We initiate the study of two-party 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 bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

2005

EPRINT

Oblivious Transfer and Linear Functions
Abstract

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 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 1-2 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 non-trivially depends on both inputs) to the two strings.
We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 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 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.

2004

CRYPTO

2004

EPRINT

Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography
Abstract

We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the non-erasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the single-inconsistent-player (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 Cramer-Shoup cryptosystem.
Our results are based on a new adaptively-secure 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 adaptively-secure protocols, which may find other applications, like a distributed trapdoor-key generation protocol for Pedersen's commitment scheme, an adaptively-secure Pedersen VSS scheme (as a {\em committed} VSS), or distributed-verifier proofs for proving relations among commitments or even any NP relations in general.

2003

EPRINT

Efficient Multi-Party Computation over Rings
Abstract

Secure multi-party 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 brute-force simulation of computation in these structures).
{\sc Efficiency.} The best known {\em constant-round} 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 black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round 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 (non-field) rings to the round-efficient secure computation of the maximum function.

2002

EPRINT

Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
Abstract

A {\em black-box} 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 the integers 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 black-box secret sharing problem as the problem of devising, for
an 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 multi-party computation over
black-box rings.
In 1994 Desmedt and Frankel have proposed an
elegant approach to the black-box secret sharing problem
based in part on polynomial interpolation over
cyclotomic number fields. For arbitrary given $T_{t,n}$ with
$0<t<n-1$, the expansion factor of their scheme is $O(n)$. This is
the best previous general approach to the problem.
Using low degree integral extensions of the integers over which there exists a
pair of sufficiently large Vandermonde matrices with co-prime
determinants, we construct, for arbitrary given $T_{t,n}$ with
$0<t<n-1$ , a black-box secret sharing scheme with expansion factor
$O(\log n)$, which we show is minimal.

#### Program Committees

- Eurocrypt 2019
- Eurocrypt 2018
- TCC 2017
- PKC 2017 (Program chair)
- TCC 2015
- Crypto 2014
- Eurocrypt 2014
- Crypto 2012
- Crypto 2011
- Crypto 2010
- Eurocrypt 2009
- Asiacrypt 2009
- Eurocrypt 2008
- Asiacrypt 2008
- TCC 2007
- Eurocrypt 2007
- Asiacrypt 2007
- PKC 2006

#### Coauthors

- Masayuki Abe (5)
- Thomas Attema (1)
- Eli Ben-Sasson (1)
- Alexandra Boldyreva (2)
- Niek J. Bouman (2)
- Harry Buhrman (1)
- Alfonso Cevallos (1)
- Nishanth Chandran (2)
- Kai-Min Chung (1)
- Ronald Cramer (11)
- Ivan Damgård (12)
- Koen de Boer (1)
- Yevgeniy Dodis (2)
- Jelle Don (2)
- Nico Döttling (1)
- Léo Ducas (1)
- Frédéric Dupuis (2)
- Max Fillinger (3)
- Ran Gelles (2)
- Vipul Goyal (2)
- Dennis Hofheinz (1)
- Yu-Hsuan Huang (1)
- Yuval Ishai (2)
- Jedrzej Kaniewski (2)
- Pierre Karpman (1)
- Jonathan Katz (2)
- Eike Kiltz (1)
- Eyal Kushilevitz (2)
- Philippe Lamontagne (2)
- Tai-Ning Liao (1)
- Carolin Lunemann (1)
- Christian Majenz (2)
- Ueli Maurer (1)
- Bart Mennink (1)
- Kirill Morozov (1)
- Adam O'Neill (2)
- Rafail Ostrovsky (4)
- Carles Padró (2)
- Yuval Rabani (1)
- Renato Renner (2)
- Louis Salvail (13)
- Christian Schaffner (13)
- Fang Song (2)
- Gabriele Spini (1)
- Martijn Stam (1)
- Marco Tomamichel (2)
- Hoeteck Wee (1)
- Stephanie Wehner (2)
- Daniel Wichs (2)
- Chen Yuan (2)
- Hong-Sheng Zhou (2)
- Vassilis Zikas (2)