International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Neal Koblitz

Affiliation: Univ. of Washington

Publications

Year
Venue
Title
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2010
EPRINT
A Security Weakness in Composite-Order Pairing-Based Protocols with Imbedding Degree $k>2$
Neal Koblitz
In this note we describe a security weakness in pairing-based protocols when the group order is composite and the imbedding degree $k$ is greater than $2$.
2010
EPRINT
Intractable Problems in Cryptography
Neal Koblitz Alfred Menezes
We examine several variants of the Diffie-Hellman and Discrete Log problems that are connected to the security of cryptographic protocols. We discuss the reductions that are known between them and the challenges in trying to assess the true level of difficulty of these problems, particularly if they are interactive or have complicated input.
2008
EPRINT
Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift
Over a period of sixteen years elliptic curve cryptography went from being an approach that many people mistrusted or misunderstood to being a public key technology that enjoys almost unquestioned acceptance. We describe the sometimes surprising twists and turns in this paradigm shift, and compare this story with the commonly accepted Ideal Model of how research and development function in cryptography. We also discuss to what extent the ideas in the literature on "social construction of technology" can contribute to a better understanding of this history.
2007
EPRINT
Another Look at Automated Theorem-Proving
Neal Koblitz
I examine the use of automated theorem-proving for reductionist security arguments in cryptography and discuss three papers that purport to show the potential of computer-assisted proof-writing and proof-checking. I look at the proofs that the authors give to illustrate the "game-hopping" technique -- for Full-Domain Hash signatures, ElGamal encryption, and Cramer-Shoup encryption -- and ask whether there is evidence that automated theorem-proving can contribute anything of value to the security analysis of cryptographic protocols.
2007
EPRINT
Another Look at Non-Standard Discrete Log and Diffie-Hellman Problems
Neal Koblitz Alfred Menezes
We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these non-standard problems.
2007
JOFC
2006
EPRINT
Another Look at "Provable Security". II
Neal Koblitz Alfred Menezes
We discuss the question of how to interpret reduction arguments in cryptography. We give some examples to show the subtlety and difficulty of this question.
2006
EPRINT
Another Look at Generic Groups
Neal Koblitz Alfred Menezes
Starting with Shoup's seminal paper [24], the generic group model has been an important tool in reductionist security arguments. After an informal explanation of this model and Shoup's theorem, we discuss the danger of flaws in proofs. We next describe an ontological difference between the generic group assumption and the random oracle model for hash functions. We then examine some criticisms that have been leveled at the generic group model and raise some questions of our own.
2005
EPRINT
Pairing-Based Cryptography at High Security Levels
Neal Koblitz Alfred Menezes
In recent years cryptographic protocols based on the Weil and Tate pairings on elliptic curves have attracted much attention. A notable success in this area was the elegant solution by Boneh and Franklin of the problem of efficient identity-based encryption. At the same time, the security standards for public key cryptosystems are expected to increase, so that in the future they will be capable of providing security equivalent to 128-, 192-, or 256-bit AES keys. In this paper we examine the implications of heightened security needs for pairing-based cryptosystems. We first describe three different reasons why high-security users might have concerns about the long-term viability of these systems. However, in our view none of the risks inherent in pairing-based systems are sufficiently serious to warrant pulling them from the shelves. We next discuss two families of elliptic curves E for use in pairing-based cryptosystems. The first has the property that the pairing takes values in the prime field F_p over which the curve is defined; the second family consists of supersingular curves with embedding degree k=2. Finally, we examine the efficiency of the Weil pairing as opposed to the Tate pairing and compare a range of choices of embedding degree k, including k=1 and k=24.
2004
EPRINT
Another Look at ``Provable Security''
Neal Koblitz Alfred Menezes
We give an informal analysis and critique of several typical ``provable security'' results. In some cases there are intuitive but convincing arguments for rejecting the conclusions suggested by the formal terminology and ``proofs,'' whereas in other cases the formalism seems to be consistent with common sense. We discuss the reasons why the search for mathematically convincing theoretical evidence to support the security of public-key systems has been an important theme of researchers. But we argue that the theorem-proof paradigm of theoretical mathematics is of limited relevance here and often leads to papers that are confusing and misleading. Because our paper is aimed at the general mathematical public, it is self-contained and as jargon-free as possible.
1998
CRYPTO
1998
JOFC
1992
CRYPTO
Kid Krypto
Michael R. Fellows Neal Koblitz
1991
CRYPTO
1991
JOFC
1990
CRYPTO
1989
JOFC
1988
CRYPTO

Program Committees

Crypto 2007
Eurocrypt 2001
Crypto 1996
Crypto 1992