## CryptoDB

### Joseph K. Liu

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications
📺
Abstract

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree $$k\ge 2$$, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree $$k\ge 2$$ have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case ($$k=1$$) and a very specific quadratic case ($$k=2$$), which are obtained as a special case of our technique.Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting “inter-slot” operations, and “NTT-friendly” tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

2014

EPRINT

2010

EPRINT

Practical ID-based Encryption for Wireless Sensor Network
Abstract

In this paper, we propose a new practical identity-based encryption scheme which is suitable for wireless sensor network (WSN). We call it \textit{Receiver-Bounded Online/Offline Identity-based Encryption}
(RB-OOIBE). It splits the encryption process into two parts -- the offline and the online part. In the offline part, all heavy computations are done without the knowledge of the receiver's identity and the plaintext message. In the online stage, only light computations such as modular operation and symmetric key encryption are required, together with the receiver's identity and the plaintext message. Moreover, since each offline ciphertext can be re-used for the same receiver, the number of offline ciphertexts
the encrypter holds only confines the number of receivers instead of the number of messages to be encrypted. In this way, a sensor node (with limited computation power and limited storage) in WSN can send encrypted data easily: A few offline ciphertexts can be computed in the manufacturing stage while the online part is light enough for the sensor to process.
We propose an efficient construction for this new notion. The scheme can be proven selective-ID CCA secure in the standard model. Compared to previous online/offline identity-based encryption schemes, our scheme is exempt from a high storage requirement,
which is proportional to the number of messages to be sent. The improvement is very significant if many messages are sent to few receivers.

2010

EPRINT

Efficient Online/Offline Identity-Based Signature for Wireless Sensor Network
Abstract

In this paper, we present an \emph{online/offline identity-based
signature} scheme for the wireless sensor network (WSN). We argue
that due to significant reduction in computational and storage costs,
our scheme is particularly suitable for the WSN environment with
severely constrained resources. One of the interesting features of our
scheme is that it provides \textit{multi-time} usage of the offline
storage, which allows the signer to re-use the offline pre-computed
information in polynomial time, in contrast to \textit{one-time} usage
in all previous online/offline signature schemes. As evidence of the
practicality and feasibility of our scheme to be used in the WSN
environment, we provide an actual implementation result of our
scheme on the MicaZ platform.

2010

EPRINT

Identity-Based Online/Offline Key Encapsulation and Encryption
Abstract

An identity-based online/offline encryption (IBOOE) scheme splits the encryption process into two phases. The first phase performs most of the heavy computations, such as modular exponentiation or pairing over points on elliptic curve. The knowledge of the plaintext or the receiver's identity is not required until the second phase, where the ciphertext is produced by only light computations, such as integer addition/multiplication or hashing. This division of computations makes encryption affordable by devices with limited computation power since the preparation works can be executed ``offline'' or possibly by some powerful devices.
Since efficiency is the main concern, smaller ciphertext size and less burden in the computation requirements of all phases (i.e., both phases of encryption and the decryption phase) are desirable. In this paper, we proposed new schemes with improved efficiency over previous schemes by assuming random oracles. Our first construction is a very efficient scheme which is secure against chosen-plaintext attack (CPA), This scheme is slightly modified from an existing scheme. In particular, the setup and the user private key remain the same. We then proceed to propose the notion of ID-based Online/Offline KEM (IBOOKEM) that allows the key encapsulation process to be split into offline and online stages, in the same way as IBOOE does. We also present a generic transformation to get security against chosen-ciphertext attack (CCA) for IBOOE from any IBOOKEM scheme with one-wayness only. Our schemes (both CPA and CCA) are the most efficient one in the state-of-the-art, in terms of online computation and ciphertext size, which are the two main focuses of online/offline schemes. Our schemes are very suitable to be deployed on embedded devices such as smartcard or wireless sensor which have very limited computation powers and the communication bandwidth is very expensive.

2010

EPRINT

Online/Offline Identity-Based Signcryption Re-visited
Abstract

In this paper, we re-define a cryptographic notion called
Online/Offline Identity-Based Signcryption. It is an ``online/offline'' version of identity-based signcryption, where most of the computations are carried out offline and the online part does not require any heavy computations such as pairings or multiplications on elliptic curve. It is particularly suitable for power-constrained devices such as smart cards.
We give a concrete implementation of online/offline identity-based
signcryption. The construction is very efficient and flexible. Unlike all previous schemes in the literature, our scheme does
not require the knowledge of receiver's information (either
public key or identity) in the offline stage. The receiver's identity and the message to be signcrypted are only needed in the online stage. This feature provides great flexibility to our scheme and makes it practical to use in real-world applications. We prove that the proposed scheme meets strong security requirements in the random oracle model, assuming the Strong Diffie-Hellman (SDH) and Bilinear Diffie-Hellman Inversion (BDHI) are computationally hard.

2008

EPRINT

Certificate-Based Signature Schemes without Pairings or Random Oracles
Abstract

In this paper, we propose two new certificate-based signature
(CBS) schemes with new features and advantages. The first one
is very efficient as it does not require any pairing
computation and its security can be proven using Discrete
Logarithm assumption in the random oracle model. We also
propose another scheme whose security can be proven in the
standard model without random oracles. To the best of our
knowledge, these are the \emph{first} CBS schemes in the
literature that have such kind of features.

2008

EPRINT

A New Variant of the Cramer-Shoup KEM Secure against Chosen Ciphertext Attack
Abstract

We propose a new variant of the Cramer-Shoup KEM (key
encapsulation mechanism). The proposed variant is more
efficient than the original Cramer-Shoup KEM scheme in terms of
public key size and encapsulation cost, but is proven to be
(still) secure against chosen ciphertext attack in the standard
model, relative to the Decisional Diffie-Hellman problem.

2007

EPRINT

(Convertible) Undeniable Signatures without Random Oracles
Abstract

We propose a convertible undeniable signature scheme without random oracles. Our construction is based on Waters' and Kurosawa and Heng's schemes that were proposed in Eurocrypt 2005. The security of our scheme is based on the CDH and the decision linear assumption. Comparing only the part of undeniable signatures, our scheme uses more standard assumptions than the existing undeniable signatures without random oracles due to Laguillamie and Vergnaud.

2007

EPRINT

Efficient Hierarchical Identity Based Signature in the Standard Model
Abstract

The only known constructions of Hierarchical Identity Based Signatures that are proven secure in the strongest model without random oracles are based on the approach of attaching certificate chains or hierarchical authentication tree with one-time signature. Both construction methods lead to schemes that are somewhat inefficient and leave open the problem of efficient direct construction. In this paper, we propose the first direct construction of Hierarchical Identity Based Signature scheme that is
proven under the strongest model without relying on random oracles and using more standard $q$-SDH assumption. It is computationally efficient and the signature size is constant.
When the number of hierarchical level is set to be one, our scheme is a normal identity based signature scheme. It enjoys the shortest size in public parameters and signatures when compare with others in the literature, with the same security level.

2007

EPRINT

Certificateless Public Key Encryption Secure against Malicious KGC Attacks in the Standard Model
Abstract

We introduce the first secure Certificateless Public Key
Encryption (CL-PKE) scheme against a malicious Key Generation
Center (KGC) in the standard model. Recently, Au \textit{et al.}
\cite{AuChLiMuWoYa07} pointed out that the previous security
models for CL-PKE schemes cannot guarantee the security against a
malicious KGC. They also showed that although some schemes are
secure against malicious KGC, they require the random oracle model
to prove the security. In this paper, we first show that previous
CL-PKE schemes in the standard model are not secure against
malicious KGC. And then, we construct a new CL-PKE scheme
with rigorous security proof against the
attacks of a malicious KGC in the standard model, which is the first in the literature.

2006

EPRINT

Self-Generated-Certificate Public Key Cryptosystem
Abstract

Certificateless Public Key Cryptography (CL-PKC) enjoys a number of features of Identity-Based
Cryptography (IBC) while without having the problem of key escrow. However, it \textit{does} suffer to
an attack where the adversary, Carol, replaces Alice's public key by someone's public key so that
Bob, who wants to send an encrypted message to Alice, uses Alice's identity and other's public
key as the inputs to the encryption function. As a result, Alice cannot decrypt the message
while Bob is unaware of this. We call it \textit{Denial-of-Decryption (DoD) Attack}
as its nature is similar to the well known Denial-of-Service (DoS) Attack. Based on CL-PKC,
we propose a new paradigm called \textit{Self-Generated-Certificate Public Key Cryptography (SGC-PKC)}
that captures the DoD Attack. We also provide a generic construction of
a self-generated-certificate public key encryption scheme
in the standard model. In addition, we further
propose a certificateless signature and a certificateless encryption scheme with concrete implementation.
They are all
provably secure in the standard model, which are
the first in the literature regardless of the generic
constructions by Yum and Lee which may contain security weaknesses as pointed out by others.
We believe these concrete implementations are of independent interest.

2006

EPRINT

ID-Based Ring Signature Scheme secure in the Standard Model
Abstract

The only known construction of ID-based ring signature schemes which
maybe secure in the standard model is to attach certificates to
non-ID-based ring signatures. This method leads to schemes that are
somewhat inefficient and it is an open problem to find more
efficient and direct constructions. In this paper, we propose two
such constructions. Our first scheme, with signature size linear in
the cardinality of the ring, is secure in the standard model under
the computational Diffie-Hellman assumption. The second scheme,
achieving constant signature size, is secure in a weaker attack
model (the selective ID and weak chosen message model), under the
Diffie-Hellman Inversion assumption.

2006

EPRINT

Malicious KGC Attacks in Certificateless Cryptography
Abstract

Identity-based cryptosystems have an inherent key escrow issue, that is, the Key Generation Center (KGC) always knows user secret key. If the KGC is malicious, it can always impersonate the user. Certificateless cryptography, introduced by Al-Riyami and Paterson in 2003, is intended to solve this problem. However, in all the previously proposed certificateless schemes, it is always assumed that the malicious KGC starts launching attacks (so-called Type II attacks) only after it has generated a master public/secret key pair honestly. In this paper, we propose new security models that remove this assumption for both certificateless signature and encryption schemes. Under the new models, we show that a class of certificateless encryption and signature schemes proposed previously are insecure. These schemes still suffer from the key escrow problem. On the other side, we also give new proofs to show that there are two generic constructions, one for certificateless signature and the other for certificateless encryption, proposed recently that are secure under our new models.

2006

EPRINT

Practical Hierarchical Identity Based Encryption and Signature schemes Without Random Oracles
Abstract

In this paper, we propose a Hierarchical Identity Based Encryption scheme that is
proven secure under the strongest model of \cite{BonehFr01} directly, without relying on random oracles.
The size of the ciphertext is a constant while the size of public parameters is independent
to the number of bit representing an identity. It is the first in the literature to achieve
such a high security level and space efficiency at the same time. In addition, we also propose
the first Hierarchical Identity Based Signature scheme that is proven under the strongest model
without relying on random oracles and using more standard $q$-SDH assumption. Similar to the
proposed encryption scheme, the space complexity of the signature and public parameters are as efficient
as the proposed encryption scheme.

2006

EPRINT

Self-Generated-Certificate Public Key Cryptography and Certificateless Signature / Encryption Scheme in the Standard Model
Abstract

Certificateless Public Key Cryptography (CL-PKC) enjoys a number of features of Identity-Based
Cryptography (IBC) while without having the problem of key escrow. However, it \textit{does} suffer to
an attack where the adversary, Carol, replaces Alice's public key by someone's public key so that
Bob, who wants to send an encrypted message to Alice, uses Alice's identity and other's public
key as the inputs to the encryption function. As a result, Alice cannot decrypt the message
while Bob is unaware of this. We call it \textit{Denial-of-Decryption (DoD) Attack}
as its nature is similar to the well known Denial-of-Service (DoS) Attack. Based on CL-PKC,
we propose a new paradigm called \textit{Self-Generated-Certificate Public Key Cryptography (SGC-PKC)}
that captures the DoD Attack. We also provide a generic construction of
a self-generated-certificate public key encryption scheme
in the standard model. Our generic construction uses certificateless signature
and certificateless encryption as the building block.
In addition, we further
propose a certificateless signature and a certificateless encryption scheme with concrete implementation that
are all
provably secure in the standard model, which are
the first in the literature regardless of the generic
constructions by Yum and Lee which may contain security weaknesses as pointed out by others.
We believe these concrete implementations are of independent interest.

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

A Suite of ID-Based Threshold Ring Signature Schemes with Different Levels of Anonymity
Abstract

Since the introduction of Identity-based (ID-based) cryptography
by Shamir in 1984, numerous ID-based signature schemes have been
proposed. In 2001, Rivest et al. introduced ring signature that
provides irrevocable signer anonymity and spontaneous group
formation. In recent years, ID-based ring signature schemes have
been proposed and all of them are based on bilinear pairings. In
this paper, we propose the first ID-based threshold ring signature
scheme that is not based on bilinear pairings. We also propose the
first ID-based threshold `linkable' ring signature scheme. We
emphasize that the anonymity of the actual signers is maintained
even against the private key generator (PKG) of the ID-based
system. Finally we show how to add identity escrow to the two
schemes. Due to the different levels of signer anonymity they
support, the schemes proposed in this paper actually form a suite
of ID-based threshold ring signature schemes which is applicable
to many real-world applications with varied anonymity
requirements.

2005

EPRINT

Solutions to Key Exposure Problem in Ring Signature
Abstract

In this paper, we suggest solutions to the key exposure problem in ring signature. In particular, we propose the first forward secure ring signature scheme and the first key-insulated ring signature schemes. Both constructions allow a $(t,n)$-threshold setting. That is, even $t$ secret keys are compromised, the validity of all forward secure ring signatures generated in the past is still preserved. In the other way, the compromise of up to all secret keys does not allow any adversary to generate a valid key-insulated ring signature for the remaining time periods.

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

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

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.

#### Coauthors

- Man Ho Au (9)
- Joonsang Baek (4)
- Feng Bao (1)
- Tony K. Chan (1)
- Jing Chen (1)
- Sherman S. M. Chow (2)
- Cheng-Kang Chu (1)
- Robert H. Deng (1)
- Muhammed F. Esgin (1)
- Yong Ho Hwang (1)
- Kaitai Liang (1)
- Dongxi Liu (1)
- Yi Mu (1)
- Ron Steinfeld (1)
- Willy Susilo (5)
- Patrick P. Tsang (2)
- Victor K. Wei (5)
- Duncan S. Wong (11)
- Jun Wen Wong (1)
- Guomin Yang (1)
- Yanjiang Yang (1)
- Y. H. Yuen (1)
- Tsz Hon Yuen (4)
- Jianying Zhou (6)