## CryptoDB

### Douglas R. Stinson

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Short One-Time Signatures
Abstract

We present a new one-time signature scheme having short signatures. Our new scheme supports aggregation, batch verification, and admits efficient proofs of knowledge. It has a fast signing algorithm, requiring only modular additions, and its verification cost is comparable to ECDSA verification. These properties make our scheme suitable for applications on resource-constrained devices such as smart cards and sensor nodes. Along the way, we give a unified description of five previous one-time signature schemes and improve parameter selection for these schemes, and as a corollary we give a fail-stop signature scheme with short signatures.

2010

EPRINT

On the Complexity of the Herding Attack and Some Related Attacks on Hash Functions
Abstract

In this paper, we analyze the complexity of the construction of the 2^k-diamond structure proposed by Kelsey and Kohno. We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory, which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine.
Precisely, our results shows the following:
1. The message complexity for the construction of a diamond structure is \sqrt{k} times more than what was previously stated in literature.
2. The time complexity is n times the message complexity, where n is the size of hash value.
Due to above two results, the complexity of the herding attack and the second preimage attack on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on "hash twice'' is n times the claimed complexity, by giving a more detailed analysis of the attack.

2009

EPRINT

Anonymity in Shared Symmetric Key Primitives
Abstract

We provide a stronger definition of anonymity in the context of shared symmetric key primitives, and show that
existing schemes do not provide this level of anonymity. A new scheme is presented to share symmetric key operations
amongst a set of participants according to a $(t,n)$-threshold access structure.
We quantify the amount of information the output of the shared operation provides about the group of
participants which collaborated to produce it.

2008

EPRINT

How To Ensure Forward and Backward Untraceability of RFID Identification Schemes By Using A Robust PRBG
Abstract

In this paper, we analyze an RFID identification scheme which is designed to provide forward untraceability and backward untraceability. We show that if a standard cryptographic pseudorandom bit generator (PRBG) is used in the scheme, then the scheme may fail to provide
forward untraceability and backward untraceability. To achieve the desired untraceability features, the scheme can use a robust PRBG which provides forward security and backward security. We also note that the backward security is stronger than necessary for the backward untraceability of the scheme.

2008

EPRINT

Two attacks on a sensor network key distribution scheme of Cheng and Agrawal
Abstract

A sensor network key distribution scheme
for hierarchical sensor networks was recently proposed by
Cheng and Agrawal. A feature of their scheme is that
pairwise keys exist between any pair of high-level nodes
(which are called cluster heads) and between any (low-level)
sensor node and the nearest cluster head. We present two attacks on their scheme.
The first attack can be applied for certain
parameter sets. If it is applicable, then this attack can result in the
compromise of most if not all of
the sensor node keys after a small number of cluster heads are compromised.
The second attack can always be applied, though it is weaker.

2008

EPRINT

On The Security of The ElGamal Encryption Scheme and Damgards Variant
Abstract

In this paper, we discuss the security of the ElGamal encryption scheme and its variant by Damgard. For the ElGamal encryption, we show that (1) under the generalized knowledge-of-exponent assumption and the one-more discrete log assumption, ElGamal encryption is one-way under nonadaptive chosen cipher attacks; (2) one-wayness of ElGamal encryption under non-adaptive chosen cipher attacks is equivalent to the hardness of one-more computational Diffie-Hellman problem. For
a variant of ElGamal encryption proposed by Damgard (DEG), we give a new proof that DEG is semantically secure against non-adaptive chosen ciphertext attacks under the one-more decisional Diffie-Hellman assumption (although the same result for DEG security has been presented in the literature before, our proof is simpler). We also give a new security proof for DEG based on the decisional Diffie-
Hellman assumption (DDHA) and a weaker version of the knowledge-of-exponent assumption (KEA), and note that KEA is stronger than necessary in the security proof of DEG, for which KEA was originally proposed.

2008

EPRINT

Recognition in Ad Hoc Pervasive Networks
Abstract

We examine the problem of message and entity recognition in the context of ad hoc networks. We review the definitions and the security model described in the literature and examine previous recognition protocols described in ABCLMN98, HWGW05, LZWW05, M03, and WW03. We prove that there is a one to one correspondence
between non-interactive message recognition protocols and digital
signature schemes. Hence, we concentrate on designing interactive recognition protocols.
We look at LZWW05 in more detail and suggest a variant to overcome a certain shortcoming. In particular, in case of communication failure or adversarial disruption, this protocol is not equipped with a practical resynchronization process and can fail to resume. We propose a variant of this protocol which is equipped with a resynchronization technique that allows users to resynchronize whenever they wish or when they suspect an intrusion.

2008

EPRINT

A New Message Recognition Protocol for Ad Hoc Pervasive Networks
Abstract

We propose a message recognition protocol which is suitable for ad hoc pervasive networks without the use of hash chains. Hence, we no longer require the sensor motes to save values of a hash chain in their memories. This relaxes the memory requirements. Moreover, we do not need to fix the total number of times the protocol can be executed which implies a desired flexibility in this regard. Furthermore, our protocol is secure without having to consider families of assumptions that depend on the number of sessions the protocol is executed. Hence, the security does not weaken as the protocol is executed over time. Last but not least, we provide a practical procedure for resynchronization in case of any adversarial disruption or communication failure.

2008

EPRINT

Combinatorial batch codes
Abstract

In this paper, we study batch codes, which were
introduced by Ishai, Kushilevitz, Ostrovsky and Sahai.
A batch code specifies a method to distribute a
database of n items among m devices (servers)
in such a way that any k items
can be retrieved by reading at most t items from each of the servers. It is of interest to devise batch codes that
minimize the total storage, denoted by N, over all m servers.
In this paper, we study the special case t=1, under
the assumption that every server stores a subset of
the items. This is purely a combinatorial problem, so
we call this kind of batch code a "combinatorial batch code''.
For various parameter situations, we are able to present
batch codes that are optimal with respect to the storage
requirement, N. We also study uniform codes, where every item is
stored in precisely c of the m servers (such a code
is said to have rate 1/c). Interesting new results
are presented in the cases c = 2, k-2 and k-1. In addition,
we obtain improved existence results for arbitrary
fixed c using the probabilistic method.

2007

EPRINT

Authorship Proof for Textual Document
Abstract

In this paper, we investigate the problem of how to prove the authorship of textual documents. First we define the basic functionalities of an authorship proof scheme (APS) based on natural language watermarking, and identify two essential security requirements for an APS to be secure against various attacks. We review existing natural language watermarking schemes, and we propose two new schemes with improved security.

2007

EPRINT

A Zero-Knowledge Identification and Key Agreement Protocol
Abstract

In this paper, we propose a zero-knowledge authenticated key agreement protocol with key confirmation (AKC) in asymmetric setting. The protocol has several desirable security attributes like some classical AKCs such as STS and MQV. One highlight of our protocol is its zero-knowledge property, which enables succinct proofs of the claimed security attributes, while the overhead in communication and computation resulting from the special design to achieve zero-knowledge is insignificant.

2007

EPRINT

A Bound on the Size of Separating Hash Families
Abstract

The paper provides an upper bound on the size of a (generalised)
separating hash family, a notion introduced by Stinson, Wei and
Chen. The upper bound generalises and unifies several previously known
bounds which apply in special cases, namely bounds on perfect hash
families, frameproof codes, secure frameproof codes and separating
hash families of small type.

2007

EPRINT

Interactive two-channel message authentication based on interactive-collision Resistant hash functions
Abstract

We propose an interactive message authentication protocol (IMAP)
using two channels: an insecure broadband channel and an
authenticated narrow-band channel. We consider the problem in the
context of ad hoc networks, where it is assumed that there is
neither a secret key shared among the two parties, nor a public-key
infrastructure in place. The security of our IMAP is based on the
existence of Interactive-Collision Resistant (ICR) hash functions, a
new notion of hash function security.
Our IMAP is based on the computational assumption that ICR hash
functions exist. It performs better than message authentication
protocols that are based on computational assumptions. That is,
while achieving the same level of security, the amount of
information sent over the authenticated channel in our IMAP is
smaller than the most secure IMAP and Non-interactive Message
Authentication Protocol (NIMAP) in the literature. In other words,
if we send the same amount of information over the authenticated
channel, we can allow much stronger adversaries compared to the
existing protocols in the literature.
Moreover, our IMAP benefits from a simple structure and works under
fewer security assumptions compared to other IMAPs in the
literature. The efficient and easy-to-use structure of our IMAP
makes it very practical in real world ad hoc network scenarios.

2007

EPRINT

Generalized mix functions and orthogonal equitable rectangles
Abstract

Ristenpart and Rogaway defined "mix" functions, which are used to
mix inputs from two sets of equal size, and produce outputs
from the same two sets, in an optimal way. These functions have
a cryptographic application in the context of extending the domain
of a block cipher. It was observed that mix functions could be
constructed from orthogonal latin squares.
In this paper, we give a simple, scalable construction for mix functions.
We also consider a generalization of mix functions, in which the
two sets need not be of equal size. These generalized mix functions
turn out to be equivalent to an interesting type of combinatorial
design which has not previously been studied. We term these
"orthogonal equitable rectangles" and we construct them
for all possible parameter situations, with a small
number of exceptions and possible exceptions.

2007

EPRINT

The Effectiveness of Receipt-Based Attacks on ThreeBallot
Abstract

The ThreeBallot voting system is an end-to-end (E2E) voter-verifiable voting system. Each voter fills out three ballots according to a few simple rules and takes a copy of one of them home as a receipt for verification purposes. All ballots are posted on a public bulletin board so that any voter may verify the result. In this paper we investigate the effectiveness of attacks using the voter's receipt and the bulletin board. We determine thresholds for when the voter's vote can be reconstructed from a receipt, and when a coercer can effectively verify if a voter followed instructions by looking for prespecified patterns on the bulletin board. Combining these two results allows us to determine safe ballot sizes that resist known attacks. We also generalize a previous observation that an individual receipt can leak information about a voter's choices.

2007

EPRINT

A Critical Analysis and Improvement of AACS Drive-Host Authentication
Abstract

This paper presents a critical analysis of the AACS drive-host authentication scheme. A few weaknesses are identified which could lead to various attacks on the scheme. In particular, we observe that the scheme is susceptible to unknown key-share and man-in-the-middle attacks. Modifications of the scheme are suggested in order to provide better security. A proof of security of the modified scheme is also presented. The modified scheme achieves better efficiency than the original scheme.

2006

EPRINT

Multicollision Attacks on some Generalized Sequential Hash Functions
Abstract

A multicollision for a function
is a set of inputs whose outputs are all identical.
A. Joux showed multicollision
attacks on the classical iterated hash function. He also showed how
these multicollision attacks can be used to get a collision attack
on a concatenated hash function. In this paper,
we study multicollision attacks in a more general class of hash functions which
we term ``generalized sequential hash functions''.
We show that multicollision attacks exist for this class of hash functions provided that
every message block is used at most twice in the computation
of the message digest.

2006

EPRINT

Noninteractive two-channel message authentication based on hybrid-collision resistant hash functions
Abstract

We consider the problem of non-interactive message authentication
using two channels: an insecure broadband channel and an
authenticated narrow-band channel. This problem has been considered
in the context of ad hoc networks, where it is assumed that there is
neither a secret key shared among the two parties, nor a public-key
infrastructure in place. We present a formal model for protocols of
this type, along with a new protocol which is as efficient as the
best previous protocols. The security of our protocol is based on a
new property of hash functions that we introduce, which we name
``hybrid-collision resistance''.

2006

EPRINT

An Efficient and Secure Two-flow Zero-Knowledge Identification Protocol
Abstract

In this paper, we propose a new zero-knowledge identification
protocol. While the protocol consists of only two message flows, it does
not rely on any underlying signature or encryption scheme. Its zero-knowledge
property is preserved under concurrent composition and reset
settings. It is secure under the strongest attack model which
incorporates concurrent attacks, active-intruder attacks and reset
attacks. Meanwhile its performance in computation and communication
is close to that of the most efficient identification protocols not
based on signature or encryption systems, most of which are insecure in this
strong
attack model.

2006

EPRINT

Unconditionally secure chaffing and winnowing with short authentication tags
Abstract

Rivest proposed the idea of a chaffing-and-winnowing scheme, in which confidentiality is achieved through the use of an authentication code. Thus it would still be possible to have confidential communications even if conventional encryption schemes were outlawed. Hanaoka et al. constructed unconditionally secure chaffing-and-winnowing schemes which achieve perfect secrecy in the sense of Shannon. Their schemes are constructed from unconditionally secure authentication codes.
In this paper, we construct unconditionally secure chaffing-and-winnowing schemes from unconditionally secure authentication codes in which the authentication tags are very short. This could be a desirable feature, because certain types of unconditionally secure authentication codes can provide perfect secrecy if the length of an authentication tag is at least as long as the length of the plaintext. The use of such a code might be prohibited if encryption schemes are made illegal, so it is of interest to construct chaffing-and-winnowing schemes based on "short'' authentication tags.

2004

EPRINT

Multicollision Attacks on Generalized Hash Functions
Abstract

In a recent paper in crypto-04, A. Joux showed a
multicollision attacks on the classical iterated hash function. He
also showed how the multicollision attack can be used to get a
collision attack on the concatenated hash function. In this paper
we have shown that the multicollision attacks exist in a general
class of sequential or tree based hash functions even if message
blocks are used twice unlike the classical hash function.

2001

EPRINT

Some observations on the theory of cryptographic hash functions
Abstract

In this paper, we study several issues related to the notion of
``secure'' hash functions. Several necessary conditions
are considered, as well as a popular sufficient condition
(the so-called random oracle model). We study the security of
various problems that are motivated by the notion of a secure
hash function.
These problems are analyzed in the random oracle model,
and we prove that
the obvious trivial algorithms are optimal.
As well, we look closely at
reductions between various problems. In particular,
we consider the important question ``does preimage resistance imply
collision resistance?''. Finally, we study the relationship
of the security of
hash functions built using the Merkle-Damgard construction
to the security of the underlying compression function.

2001

EPRINT

Slope packings and coverings, and generic algorithms for the discrete logarithm problem
Abstract

We consider the set of slopes of lines formed by
joining all pairs of points in some subset S of a
Desarguesian affine plane of prime order, p.
If all the slopes are distinct and non-infinite, we have a
slope packing;
if every possible non-infinite slope occurs, then we have
a slope covering. We review and unify some results on these problems
that can be derived from the study of Sidon sets and sum covers.
Then we report some
computational results we have obtained for small values of p.
Finally, we
point out some connections between slope packings and coverings
and generic algorithms for the discrete logarithm problem in prime
order (sub)groups. Our results provide a combinatorial
characterization
of such algorithms, in the sense that any generic algorithm
implies the
existence of a certain slope packing or covering, and conversely.

2000

EPRINT

Combinatorial Properties of Frameproof and Traceability Codes
Abstract

In order to protect copyrighted material, codes may be
embedded in the content or codes may be associated with the
keys used to recover the content. Codes can offer protection
by providing some form of traceability for pirated
data. Several researchers have studied different notions of
traceability and related concepts in recent years. "Strong"
versions of traceability allow at least one member of a
coalition that constructs a "pirate decoder" to be
traced. Weaker versions of this concept ensure that no
coalition can "frame" a disjoint user or group of users. All
these concepts can be formulated as codes having certain
combinatorial properties.
In this paper, we study the relationships between the various
notions, and we discuss equivalent formulations using
structures such as perfect hash families. We use methods from
combinatorics and coding theory to provide bounds (necessary
conditions) and constructions (sufficient conditions) for the
objects of interest.

2000

EPRINT

Constructions and Bounds for Unconditionally Secure Commitment Schemes
Abstract

Commitment schemes have been extensively studied since they
were introduced by Blum in 1982. Rivest recently
showed how to construct unconditionally secure commitment schemes,
assuming the existence of a trusted initializer. In this paper, we present a
formal mathematical model for such schemes, and analyze their
binding and concealing properties. In particular, we
show that such schemes cannot be perfectly concealing: there is necessarily
a small probability that Alice can cheat Bob by committing to one value
but later revealing a different value. We prove several
bounds on Alice's cheating probability, and present constructions
of schemes that achieve optimal cheating probabilities. We also
show a close link between commitment schemes and the classical
``affine resolvable designs''.

1996

EPRINT

On the Contrast in Visual Cryptography Schemes
Abstract

A visual cryptography scheme is a method to encode a secret image SI into
shadow images called shares such that certain qualified subsets of shares
enable the ``visual'' recovery of the secret image.
The ``visual'' recovery consists of xeroxing the shares onto transparencies,
and then stacking them. The shares of a qualified set will reveal the secret
image without any cryptographic computation.
In this paper we analyze the contrast of the reconstructed image
in k out of n visual cryptography schemes. (In such a scheme
any k shares will reveal the image, but no set of k-1 shares
gives any information about the image.)
In the case of 2 out of n threshold schemes we give a complete
characterization of schemes having optimal contrast and minimum
pixel expansion in terms of certain balanced incomplete block designs.
In the case of k out of n threshold schemes with k>2 we obtain
upper and lower bounds on the optimal contrast.

1995

JOFC

#### Program Committees

- Eurocrypt 2011
- Asiacrypt 2005
- Eurocrypt 2005
- Eurocrypt 2003
- Crypto 2001
- Crypto 2000
- Crypto 1997
- Eurocrypt 1995
- Crypto 1993 (Program chair)
- Crypto 1990

#### Coauthors

- Mustafa Atici (1)
- Jürgen Bierbrauer (1)
- Simon R. Blackburn (1)
- Carlo Blundo (8)
- Ernest F. Brickell (4)
- M. Chateauneuf (1)
- Paolo D'Arco (3)
- Navid Nasr Esfahani (1)
- Tuvi Etzion (1)
- Antonio Giorgio Gaggia (1)
- K. Gopalakrishnan (1)
- Kevin J. Henry (1)
- Kevin Henry (1)
- Thomas Johansson (2)
- Kaoru Kurosawa (2)
- Thalia M. Laing (1)
- A.C.H. Ling (1)
- Spyros S. Magliveras (1)
- Keith M. Martin (1)
- Atefeh Mashatan (4)
- James L. Massey (1)
- Barbara Masucci (1)
- Luiz A. Frota Mattos (1)
- Mridul Nandi (2)
- Mehrdad Nojoumian (1)
- Maura B. Paterson (2)
- M. B. Paterson (2)
- Alfredo De Santis (5)
- Jessica Staddon (1)
- Jiayuan Sui (2)
- Tran van Trung (1)
- J. Upadhyay (1)
- Ugo Vaccaro (2)
- Scott A. Vanstone (1)
- Ruizhong Wei (3)
- J. Wu (5)
- Gregory M. Zaverucha (3)