## CryptoDB

### Dominik Raub

#### Publications

**Year**

**Venue**

**Title**

2009

EPRINT

Combining Computational and Information-Theoretic Security in Multi-Party Computation
Abstract

Most protocols for multi-party computation (MPC) are secure either
against information-theoretic (IT) or against computationally bounded
adversaries. In this work, we bring together the best of both worlds:
For any robustness parameter $\rob<\frac{n}{2}$ we obtain one MPC
protocol that is simultaneously IT secure with robustness for up to
$t\leq\rob$ actively corrupted parties, IT secure with fairness (no
robustness) for up to $t<\frac{n}{2}$ and computationally secure with
agreement on abort (no fairness) for up to $t<n-\rob$. Our
construction is secure in the universal composability (UC) framework,
and achieves the bounds of Ishai et al. [CRYPTO'06], Katz [STOC'07],
and Cleve [STOC'86] on trade-offs between robustness and privacy, and
on fairness.
For example, for the special case $\rob=0$ our protocol simultaneously
achieves non-robust MPC for up to $t<n$ corrupted parties in the
computational setting (like Goldreich et al. [STOC'87]) while
providing security with fairness in the IT setting for up to
$t<\frac{n}{2}$ corrupted parties (like Rabin and Ben-Or [STOC'89]
though without robustness).

2008

EPRINT

A Complete Treatment of 2-party SFE in the Information-Theoretic Setting with Applications to Long-Term Security
Abstract

It is well known that general secure function evaluation (SFE) with
information-theoretical (IT) security is infeasible in the secure
channels model in presence of a corrupted majority \cite{Cle86,Kil91,
Kus92, Kil00, IKLP06, Kat06}. In particular these results extend to
and are derived from the 2-party scenario, where any corrupted party
is already a corrupted majority. On the other hand \cite{BroTap07}
have recently demonstrated that a wealth of interesting functions can
be computed securely even in presence of a corrupted majority, at
least if one is willing to sacrifice robustness, thus raising
interest in a general description of these functions.
In this work we give a complete combinatorial classification of
2-party functions, by their secure computability under active,
semi-honest, passive and quantum adversaries. Our treatment is
constructive, in the sense that, if a function is computable in a
given setting, then we exhibit a protocol.
We then proceed to apply our results to gain insight into long-term
security, where we admit computational assumptions for the duration
of a computation, but require information-theoretical security
(privacy) once the computation is concluded.

2008

EPRINT

Secure Computability of Functions in the IT setting with Dishonest Majority and Applications to Long-Term Security
Abstract

It is well known that general secure function evaluation (SFE) with information-theoretical (IT) security is infeasible in presence of a corrupted majority in the standard model. On the other hand, there are SFE protocols (Goldreich et al.~[STOC'87]) that are computationally secure (without fairness) in presence of an actively corrupted majority of the participants. Now, the issue with computational assumptions is not so much that they might be unjustified at the time of protocol execution. Rather, we are usually worried about a potential violation of the privacy of sensitive data by an attacker whose power increases over time (e.g.~due to new technical developments). Therefore, we ask which functions can be computed with long-term security, where we admit computational assumptions for the duration of a computation, but require IT security (privacy) once the computation is concluded.
Toward this end we combinatorially characterize the classes of functions that can be computed IT securely in the authenticated channels model in presence of passive, semi-honest, active, and quantum adversaries (our results for quantum adversaries and in part for active adversaries are limited to the 2-party setting). In particular we obtain results on the fair computability of functions in the IT setting along the lines of the work of Gordon et al.~[STOC'08] for the computational setting. Our treatment is constructive in the sense that if a function is computable in a given setting, then we exhibit a protocol.
We show that the class of functions computable with long-term security in a very practical setting where the adversary may be active and insecure channels and a public-key infrastructure are provided is precisely the class of functions computable with IT security in the authenticated channels model in presence of a semi-honest adversary.
Finally, from our results and the work of Kushilevitz [SIAM Journal on Discrete Mathematics '92] and Kraschewski and Müller-Quade we can derive a complete combinatorial classification of functions, by secure computability and completeness under passive, semi-honest, active, and quantum adversaries.

2007

ASIACRYPT

2007

EPRINT

Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations
Abstract

The black-box field (BBF) extraction problem is, for a given field
$\F$, to determine a secret field element hidden in a black-box which
allows to add and multiply values in $\F$ in the box and which reports
only equalities of elements in the box. This problem is of
cryptographic interest for two reasons. First, for $\F=\F_p$ it
corresponds to the generic reduction of the discrete logarithm problem
to the computational Diffie-Hellman problem in a group of prime order
$p$. Second, an efficient solution to the BBF problem proves the
inexistence of certain field-homomorphic encryption schemes whose
realization is an interesting open problems in algebra-based
cryptography. BBFs are also of independent interest in computational
algebra.
In the previous literature, BBFs had only been considered for the
prime field case. In this paper we consider a generalization of the
extraction problem to BBFs that are extension fields. More precisely
we discuss the representation problem defined as follows: For given
generators $g_1,\ldots,g_d$ algebraically generating a BBF and an
additional element $x$, all hidden in a black-box, express $x$
algebraically in terms of $g_1,\ldots,g_d$. We give an efficient
algorithm for this representation problem and related problems for
fields with small characteristic (e.g. $\F=\F_{2^n}$ for some $n$). We
also consider extension fields of large characteristic and show how to
reduce the representation problem to the extraction problem for the
underlying prime field.
These results imply the inexistence of field-homomorphic (as opposed
to only group-homomorphic, like RSA) one-way permutations for fields
of small characteristic.

2004

EPRINT

On the Security and Composability of the One Time Pad
Abstract

Recent experimental results in quantum cryptography have renewed the interest in information-theoretically secure ciphers. In April 2004, in Vienna a bank transfer was secured by means of a one time pad encryption, with the key material being derived from a quantum key exchange. However, in this experiment the integrity of the transmitted message remained unprotected. This can have severe consequences, if the bank transfer form itself contains no authentication mechanism and there is a known position where the amount of money or the recipient is specified. Through flipping bits at the corresponding positions in the ciphertext, the amount of transfered money or the recipient of the money can be changed.
This concrete example illustrates the necessity for a thorough theoretical analysis of information-theoretically secure cryptographic techniques that are to be deployed in practice. In this work we show how to implement a statistically secure and composable system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in an asynchronous adversarially-controlled network using the framework put forward by Backes, Pfitzmann, and Waidner. The composition theorem offered by this framework enables the use of our scheme as a building block of more complex protocols as needed in practical applications.

#### Coauthors

- Robin Künzler (2)
- Christoph Lucas (1)
- Ueli Maurer (3)
- Jörn Müller-Quade (4)
- Rainer Steinwandt (1)