International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Dominik Raub

Publications

Year
Venue
Title
2009
TCC
2009
EPRINT
Combining Computational and Information-Theoretic Security in Multi-Party Computation
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
Jörn Müller-Quade Dominik Raub
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
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
Ueli Maurer Dominik Raub
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
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.