CryptoDB

Markus Jakobsson

Publications

Year
Venue
Title
2006
JOFC
2005
EPRINT
We identify and describe a new type of phishing attack that circumvents what is probably today's most efficient defense mechanism in the war against phishing, namely the shutting down of sites run by the phisher. This attack is carried out using what we call a distributed phishing attack (DPA). The attack works by a per-victim personalization of the location of sites collecting credentials and a covert transmission of credentials to a hidden coordination center run by the phisher. We show how our attack can be simply and efficiently implemented and how it can increase the success rate of attacks while at the same time concealing the tracks of the phisher. We briefly describe a technique that may be helpful to combat DPAs.
2005
EPRINT
We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted network nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for RSA-PSS and DSA signature schemes and how the same technique can be applied to Feige-Fiat-Shamir (FFS) and Schnorr signature schemes. Our technique does not modify the distribution of the generated signature transcripts, and has only a minimal overhead in terms of computation, communication, and storage. Keywords. covert channel, malware, observer, subliminal channel, tamper-evident, undercover
2005
EPRINT
Visualizing protocols is not only useful as a step towards understanding and ensuring security properties, but is also a beneficial tool to communicate notions of security to decision makers and technical people outside the field of cryptography. We present a simple card game that is a visualization for a secure protocol for private polling where it is simple to see that individual responses cannot be traced back to a respondent, and cheating is irrational. We use visualization tricks to illustrate a somewhat complex protocol, namely the Cryptographic Randomized Response Technique protocol of Lipmaa et al. While our tools --- commitments and cut-and-choose --- are well known, our construction for oblivious transfer using playing cards is new. As part of visualizing the protocol, we have been able to show that, while cut-and-choose protocols normally get more secure with an increasing number of choices, the protocol we consider --- surprisingly --- does not. This is true for our visualization of the protocol and for the real protocol.
2004
PKC
2003
EPRINT
We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.
2003
EPRINT
We consider how to avoid unsolicited e-mail -- so called spam -- in a stronger adversarial model than has previously been considered. Our primary concern is the proposal of an architecture and of protocols preventing against successful spamming attacks launched by a strong attacker. This attacker is assumed to control the communication media and to be capable of corrupting large numbers of protocol participants. Additionally, the same architecture can be used as a basis to support message integrity and privacy, though this is not a primary goal of our work. This results in a simple and efficient solution that is largely backwards-compatible, and which addresses many of the concerns surrounding e-mail communication.
2002
ASIACRYPT
2002
CRYPTO
2002
EPRINT
We introduce a novel amortization technique for computation of consecutive preimages of hash chains, given knowledge of the seed. While all previously known techniques have a memory-times-computational complexity of $O(n)$ per chain element, the complexity of our technique can be upper bounded at $O(log^2 n)$, making it a useful primitive for low-cost applications such as authentication, signatures and micro-payments. Our technique uses a logarithmic number of {\em pebbles} associated with points on the hash chain. The locations of these pebbles are modified over time. Like fractals, where images can be found within images, the pebbles move within intervals and sub-intervals according to a highly symmetric pattern.
2002
EPRINT
We introduce a novel technique for computation of consecutive preimages of hash chains. Whereas traditional techniques have a memory-times-computation complexity of $O(n)$ per output generated, the complexity of our technique is only $O(log^2 \, n)$, where $n$ is the length of the chain. Our solution is based on the same principal amortization principle as \cite{J01}, and has the same asymptotic behavior as this solution. However, our solution decreases the real complexity by approximately a factor of two. Thus, the computational costs of our solution are approximately ${1 \over 2} log_2 \, n$ hash function applications, using only a little more than $log_2 \, n$ storage cells. A result of independent interest is the lower bounds we provide for the optimal (but to us unknown) solution to the problem we study. The bounds show that our proposed solution is very close to optimal. In particular, we show that there exists no improvement on our scheme that reduces the complexity by more than an approximate factor of two.
2002
EPRINT
In this paper we investigate the timed release of standard digital signatures, and demonstrate how to do it for RSA, Schnorr and DSA signatures. Such signatures, once released, cannot be distinguished from signatures of the same type obtained without a timed release, making it transparent to an observer of the end result. While previous work has allowed timed release of signatures, these have not been standard, but special-purpose signatures. Building on the recent work by Boneh and Naor on timed commitments, we introduce the notion of a reusable time-line, which, besides allowing the release of standard signatures, lowers the session costs of existing timed applications.
2002
EPRINT
We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server provides strong evidence of its correct operation by revealing a pseudo-randomly selected subset of its input/output relations. Randomized partial checking is exceptionally efficient compared to previous proposals for providing robustness; the evidence provided at each layer is shorter than the output of that layer, and producing the evidence is easier than doing the mixing. It works with mix nets based on any encryption scheme (i.e., on public-key alone, and on hybrid schemes using public-key/symmetric-key combinations). It also works both with Chaumian mix nets where the messages are successively encrypted with each servers' key, and with mix nets based on a single public key with randomized re-encryption at each layer. Randomized partial checking is particularly well suited for voting systems, as it ensures voter privacy and provides assurance of correct operation. Voter privacy is ensured (either probabilistically or cryptographically) with appropriate design and parameter selection. Unlike previous work, our work provides voter privacy as a global property of the mix net rather than as a property ensured by a single honest server. RPC-based mix nets also provide very high assurance of a correct election result, since a corrupt server is very likely to be caught if it attempts to tamper with even a couple of ballots.
2002
EPRINT
We introduce a model for electronic election schemes that involves a more powerful adversary than in previous work. In particular, we allow the adversary to demand of coerced voters that they vote in a particular manner, abstain from voting, or even disclose their secret keys. We define a scheme to be _coercion-resistant_ if it is infeasible for the adversary to determine whether a coerced voter complies with the demands. A first contribution of this paper is to describe and characterize a new and strengthened adversary for coercion in elections. (In doing so, we additionally present what we believe to be the first formal security definitions for electronic elections of _any_ type.) A second contribution is to demonstrate a protocol that is secure against this adversary. While it is clear that a strengthening of attack models is of theoretical relevance, it is important to note that our results lie close to practicality. This is true both in that we model real-life threats (such as vote-buying and vote-cancelling), and in that our proposed protocol combines a fair degree of efficiency with an unusual lack of structural complexity. Furthermore, while previous schemes have required use of an untappable channel, ours only carries the much more practical requirement of an anonymous channel.
2001
PKC
2000
ASIACRYPT
2000
ASIACRYPT
2000
ASIACRYPT
2000
PKC
1999
CRYPTO
1999
FSE
1999
PKC
1999
PKC
1998
EUROCRYPT
1997
EUROCRYPT
1997
EUROCRYPT
1997
EPRINT
We fill a gap in the theory of zero-knowledge protocols by presenting NP-arguments that achieve negligible error probability and computational zero-knowledge in four rounds of interaction, assuming only the existence of a one-way function. This result is optimal in the sense that four rounds and a one-way function are each individually necessary to achieve a negligible error zero-knowledge argument for NP.
1996
CRYPTO
1996
EUROCRYPT
1995
EUROCRYPT
1994
EUROCRYPT

Eurocrypt 2002
PKC 2002
Eurocrypt 2000
PKC 2000
PKC 1999
Asiacrypt 1999
Eurocrypt 1998