## CryptoDB

### Victor K. Wei

#### Publications

**Year**

**Venue**

**Title**

2006

EPRINT

Invisible Designated Confirmer Signatures without Random Oracles
Abstract

We construct the first $O(1)$-size designated confirmer signatures (DCS) with security in the state-of-the-art model of Camenisch and Michels, Eurocrypt 2000, without random oracles. In particular, we achieve the security notion called the "invisibility of signature" therein.

2006

EPRINT

(Hierarchical Identity-Based) Threshold Ring Signatures
Abstract

We construct the first several efficient threshold ring signatures (TRS) without random oracles. Specializing to a threshold of one, they are the first several efficient ring signatures without random oracles after the only earlier instantiation of Chow, Liu, Wei, and Yuen. Further specializing to a ring of just one user, they are the short (ordinary) signatures without random oracles summarized in Wei and Yuen.
We also construct the first hierarchical identity-based threshold ring signature without random oracles. The signature size is $O(n\lambda_s)$ bits, where $\lambda_s$ is the security parameter and $n$ is the number of users in the ring. Specializing to a threshold of one, it is the first hierarchical identity-based ring signature without random oracles. Further specializing to a ring of one user, it is the constant-size hierarchical identity-based signature (HIBS) without random oracles in Yuen-Wei - the signature size is $O(\lambda_s)$ bits which is independent of the number of levels in the hierarchy.

2006

EPRINT

Chosen Ciphertext Secure Broadcast Threshold Encryption (resp. Threshold-Traitor Tracing)
Abstract

Recently, Boneh, Gentry, and Waters '05 presented an efficient broadcast encryption, and Boneh, Sahai, and Waters '06 presented an efficient traitor tracing scheme. The former broadcast encryption result contains both a simpler chosen plaintext secure version and a more complicated but chosen ciphertext secure version. The latter traitor tracing scheme is only chosen plaintext secure. In this paper, we use the twin encryption technique of Naor and Yung '90 to add chosen ciphertext security to both papers. By``twinning", we extend the simpler chosen plaintext secure broadcast encryption to achieve chosen ciphertext security, and we extend the chosen plaintext secure traitor tracing to achieve chosen ciphertext security. We also extend both schemes to versions corresponding to threshold encryption which we call "broadcast threshold encryption" and "threshold-traitor tracing", i.e. tracing of threshold traitors. In these schemes, any $\theta$ un-revoked users can decrypt while $\theta-1$ users cannot. The tracing is to a set of $\theta$ users. We call this set a "threshold-traitor". Our broadcast threshold encryption is collusion resistant. Our threshold-traitor tracing is collusion resistant in its traceability.

2005

EPRINT

Tight Reductions among Strong Die-Hellman Assumptions
Abstract

We derive some tight equivalence reductions between several Strong Die-Hellman (SDH) assumptions.

2005

EPRINT

Ring Signatures without Random Oracles
Abstract

Since the formalization of ring signature by Rivest, Shamir and Tauman in 2001, there are lots of variations appeared in the literature. Almost all of the variations rely on the random oracle model for security proof.
In this paper, we propose a ring signature scheme based on bilinear pairings, which is proven to be secure against chosen message attack without using the random oracle model. It is one of the first in the literature to achieve this security level.

2005

EPRINT

Constant-Size Hierarchical Identity-Based Signature/Signcryption without Random Oracles
Abstract

We construct the first constant-size hierarchical identity-based signature (HIBS) without random oracles - the signature size is $O(\lambda_s)$ bits, where $\lambda_s$ is the security parameter, and it is independent of the number of levels in the hierarchy.
We observe that an efficient hierarchical identity-based signcryption (HIBSC) scheme without random oracles can be compositioned from our HIBS and Boneh, Boyen, and Goh's hierarchical identity-based encryption (HIBE). We further optimize it to a constant-factor efficiency improvement. This is the first constant-size HIBSC without random oracles.

2005

EPRINT

Signature from a New Subgroup Assumption
Abstract

We present a new signature whose security is reducible to a new assumptions about subgroups, the {\em Computational Conjugate Subgroup Members (CCSM) Assumption}, in the random oracle model.

2005

EPRINT

Group Signature where Group Manager, Members and Open Authority are Identity-Based
Abstract

We present the first group signature scheme with provable security
and signature size $O(\lambda)$ bits where the group manager, the group
members, and the Open Authority (OA) are all identity-based. We use the security model of Bellare, Shi, and Zhang, except to add three identity managers for manager, members, and OA respectively, and we discard the Open Oracle. Our construction uses identity-based signatures summarized in Bellare, Namprempre, and Neven for manager, Boneh and Franklin's IBE for OA, and we extend Bellare et al.'s group signature construction by verifiably encrypt an image of the member public key, instead of the public key itself. The last innovation is crucial in our efficiency; otherwise, Camenisch and Damgard's verifiable encryption would have to be used resulting in lower efficiency.

2005

EPRINT

Short (resp. Fast) CCA2-Fully-Anonymous Group Signatures using IND-CPA-Encrypted Escrows
Abstract

In the newest and strongest security models for group signatures \cite{BMW03,BellareShZh05,KiayiasYu04}, attackers are given the capability to query an Open Oracle, $\oo$, in order to obtain the signer identity of the queried signature. This oracle mirrors the Decryption Oracle in security experiments involving encryption schemes, and the security notion of CCA2-full-anonymity for group signatures mirrors the security notion of IND-CCA2-security for encryption schemes. Most group signatures escrows the signer identity to a TTP called the {\em Open Authority (OA)} by encrypting the signer identity to OA. Methods to efficiently instantiate $O(1)$-sized CCA2-fully-anonymous group signatures using IND-CCA2-secure encryptions, such as the Cramer-Shoup scheme or the twin encryption scheme, exist \cite{BMW03,BellareShZh05,KiayiasYu04,NguyenSN04}. However, it has long been suspected that IND-CCA2-secure encryption
to OA is an overkill, and that CCA2-fully-anonymous group signature can be constructed using only IND-CPA-secure encryptions. Here, we settle this issue in the positive by constructing CCA2-fully-anonymous group signatures from IND-CPA-secure encryptions for the OA, without ever using IND-CCA2-secure encryptions. Our technique uses a single ElGamal or similar encryption plus Dodis and Yampolskiy \cite{DodisYa05}'s VRF (Verifiable Random Function). The VRF provides a sound signature with zero-knowledge in both the signer secret and the signer identity, while it simultaneously defends active $\oo$-query attacks. The benefits of our theoretical advance is improved efficiency. Instantiations in pairings result in the shortest CCA2-fully-anonymous group signature at 11 rational points or $\approx 1870$ bits for 170-bit curves. It is 27\% shorter (and slightly faster) than the previous fastest \cite{BBS04,KiayiasYu04} at 15 rational points. Instantiations in the strong RSA framework result in the fastest CCA2-fully-anonymous group signature at 4 multi-base exponentiations for 1024-bit RSA. It is 25\% faster than the previous fastest at 5 multi-base exponentiations \cite{ACJT00,CL02,KiayiasYu04}.

2005

EPRINT

More Compact E-Cash with Efficient Coin Tracing
Abstract

In 1982, Chaum \cite{Chaum82} pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands \cite{Brands93apr,Brands93,Brands93tm} and Ferguson \cite Ferguson93c,Ferguson93} published on single-term offline anonymous e-cash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya
\cite{CaHoLy05} gave the first compact $2^\ell$-spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of $O(1)$-unit wallet size and efficient coin tracing. The latter property is needed to revoke {\em bad} coins from over-spenders. In this paper, we solve \cite{CaHoLy05}'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability Assumption: the {\em Decisional Harmonic-Relationed Diffie-Hellman (DHRDH) Assumption}.

2005

EPRINT

More short signatures without random oracles
Abstract

We construct three new signatures and prove their securities without random oracles. They are motivated, respectively, by Boneh and Boyen's, Zhang, et al.'s, and Camenisch and Lysyanskaya's signatures without random oracles. The first two of our signatures are as short as Boneh and Boyen's (resp. Zhang, et al.'s} state-of-the-art short signatures. Our third signature is reducible to a modified LRSW Assumption but without their hypothesized external signing oracle. New and interesting variants of the q-SDH Assumption, the q-SR (Square Root) Assumption are also presented. New and independently interesting proof techniques extending the two-mode technique of Boneh and Boyen are used, including a combined three-mode simulation and rewinding in the standard model.

2004

EPRINT

Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups
Abstract

We present a linkable spontaneously
anonymous group (LSAG) signature scheme
(alternatively known as linkable ring signature scheme)
satisfying the following three properties.
(1) Anonymity, or signer indistinguishability.
(2) Linkability: That two signatures by the same signer can be linked.
(3) Spontaneity: No group secret, therefore no group manager or
group secret sharing setup.
We reduce the security of our scheme to well-known problems
under the random oracle model.
Using the scheme, we construct a new efficient one-round e-voting system
which does not have a registration phase.
We also present a new efficient
reduction of famous
rewind simulation lemma which
only relies on elementary probability theory.
Threshold extensions of our scheme are also presented.

2004

EPRINT

Custodian-Hiding Verifiable Encryption
Abstract

In a verifiable encryption, an asymmetrically encrypted ciphertext
can be publicly verified to be decipherable by a designated receiver
while maintaining the semantic security of the message
\cite{AsokanShWa98,CamenischDa00,CamenischSh03}.
In this paper, we introduce {\em Custodian-Hiding Verifiable Encryption},
where it can be publicly verified that there exists at least
one custodian (user), out of a designated group of $n$ custodians (users),
who can decrypt the message, while the semantic security of the message
and the anonymity of the actual decryptor
are maintained.
Our scheme is proven secure in the random oracle model.
We also introduce two extensions to decryption by a subset of more
than one user.

2004

EPRINT

A Bilinear Spontaneous Anonymous Threshold Signature for Ad Hoc Groups
Abstract

We present an adaptive chosen-plaintext cryptanalysis of Boneh, et al.'s bilinear spontaneous anonymous ad hoc group signature. Then we present a patch, and an extension to a threshold version complete with a security proof in the random oracle model (ROM).

2004

EPRINT

Cryptanalyzing Bresson, et al.'s Spontaneous Anonymous Threshold Signature for Ad Hoc Groups and Patching via Updating Cramer, et al.'s Threshold Proof-of-Knowledge
Abstract

We present an algebraic
cryptanalysis of Bresson, et al.'s
spontaneous anonymous threshold signature for ad hoc groups.
The technique is to reduce a degenerate condition
in Lagrange interpolation to an algebraically solvable high-density
knapsack problem over $GF(2^\ell)$.
We repair their protocol by revisiting and updating
Cramer, et al.'s
result on spontaneous anonymous threshold proof-of-knowledge (partial
proof-of-knowledge).
We generalize their proof by removing two assumptions,
and reduce its security to a new candidate hard problem, PoK-Collision,
in the random oracle model.
To add to the urgency of our update,
we present major versions of major PoK schemes
that do not satisfy their special soundness assumption.

2004

EPRINT

Fast and Proven Secure Blind Identity-Based Signcryption from Pairings
Abstract

We present the first blind identity-based signcryption (BIBSC).
We formulate its security model and define the security notions of blindness and parallel one-more unforgeability (p1m-uf). We present an efficient construction from pairings, then prove a security theorem that reduces its p1m-uf to Schnorr??s ROS Problem in the random oracle model plus the generic group and pairing model. The latter model is an extension of the generic group model to add support for pairings, which we introduce in this paper. In the process, we also introduce a new security model for (non-blind) identity-based signcryption (IBSC) which is a strengthening of Boyen??s. We construct the first IBSC scheme proven secure in the strenghened model which is also the fastest (resp. shortest) IBSC in this model or Boyen??s model. The shortcomings of several existing IBSC schemes in the strenghened model are shown.

2004

EPRINT

ID-based Cryptography from Composite Degree Residuosity
Abstract

We present identity-based identification (resp. encryption, signature, blind signature,ring signature) from composite degree residuosity (CDR). Constructions of identifications and signatures
motivated by several existing CDR-based bandwidth-efficient
encryption schemes are presented. Their securities are proven equivalent to famous hard problems, in the random oracle model.
Motivated by Cocks,we construct an identity-based encryption from CDR. Its security is proven equivalent to a new problem, the JSR (Jacobi Symbol of Roots of two quadratic polynomials) Problem. We prove JSR is at least as hard as QRP (Quadratic Residuosity Problem). Furthermore, we present the first two-way equivalence reduction of the security of Cocks' IBE, to the JSR Problem.

2004

EPRINT

Separable Linkable Threshold Ring Signatures
Abstract

A ring signature scheme is a group signature scheme with no group
manager to setup a group or revoke a signer. A linkable ring
signature, introduced by Liu, et al. \cite{LWW04}, additionally
allows anyone to determine if two ring signatures are signed by
the same group member (a.k.a. they are \emph{linked}). In this
paper, we present the first separable linkable ring signature
scheme, which also supports an efficient thresholding option. We
also present the security model and reduce the security of our
scheme to well-known hardness assumptions. In particular, we
introduce the security notions of {\em accusatory linkability} and
{\em non-slanderability} to linkable ring signatures. Our scheme
supports ``event-oriented'' linking. Applications to such linking
criterion is discussed.

2004

EPRINT

Short Linkable Ring Signatures for E-Voting, E-Cash and Attestation
Abstract

A ring signature scheme can be viewed as a group signature scheme
with no anonymity revocation and with simple group setup. A
\emph{linkable} ring signature (LRS) scheme additionally allows
anyone to determine if two ring signatures have been signed by the
same group member. Recently, Dodis et al. \cite{DKNS04} gave a
short (constant-sized) ring signature scheme. We extend it to the
first short LRS scheme, and reduce its security to a new hardness
assumption, the Link Decisional RSA (LD-RSA) Assumption. We also
extend \cite{DKNS04}'s other schemes to a generic LRS scheme and a
generic linkable group signature scheme. We discuss three
applications of our schemes. Kiayias and Yung \cite{KY04}
constructed the first e-voting scheme which simultaneously
achieves efficient tallying, public verifiability, and write-in
capability for a typical voter distribution under which only a
small portion writes in. We construct an e-voting scheme based on
our short LRS scheme which achieves the same even for all
worst-case voter distribution. Direct Anonymous Attestation (DAA)
\cite{BCC04} is essentially a ring signature scheme with certain
linking properties that can be naturally implemented using LRS
schemes. The construction of an offline anonymous e-cash scheme
using LRS schemes is also discussed.

2004

EPRINT

Tracing-by-Linking Group Signautres
Abstract

In a group signature \cite{CvH91}, any group member can sign on behalf of the group while remaining anonymous, but its identity can be traced in an future dispute investigation. Essentially all state-of-the-art group signatures implement the tracing mechnism by requiring the signer to escrow its identity to an Open Authority (OA) \cite{ACJT00,CL02scn,BMW03,KiayiasYu04,BSZ05,BBS04,KiayiasTsYu04}. We call them {\em Tracing-by-Escrowing (TbE)} group signatures. One drawback is that the OA also has the unnecessary power to trace without proper cause.
In this paper we introduce {\em Tracing-by-Linking (TbL)} group signatures. The signer's anonymity is irrevocable by any authority if the group member signs only once (per event). But if a member signs twice, its identity can be traced by a public algorithm without needing any trapdoor. We initiate the formal study of TbL group signatures by introducing its security model, constructing the first examples, and give several applications. Our core construction technique is the successful transplant of the TbL technique from single-term offline e-cash from the blind signature framework \cite{Brands93,Ferguson93,Ferguson93c} to the group signature framework. Our signatures have size $O(1)$.

#### Coauthors

- Man Ho Au (2)
- Tony K. Chan (1)
- Sherman S. M. Chow (1)
- Joseph K. Liu (5)
- Patrick P. Tsang (2)
- Duncan S. Wong (4)
- Tsz Hon Yuen (6)
- Fangguo Zhang (2)