## CryptoDB

### Man Ho Au

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Collusion Resistant Watermarkable PRFs from Standard Assumptions
📺
Abstract

A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc.
A natural security requirement for watermarking schemes is collusion resistance, where the adversary’s goal is to remove the embedded messages given multiple marked versions of the same program. Currently, this strong security guarantee has been achieved by watermarking schemes for public key cryptographic primitives from standard assumptions (Goyal et al., CRYPTO 2019) and by watermarking schemes for PRFs from indistinguishability obfuscation (Yang et al., ASIACRYPT 2019). However, no collusion resistant watermarking scheme for PRF from standard assumption is known.
In this work, we solve this problem by presenting a generic construction that upgrades a watermarkable PRF without collusion resistance to a collusion resistant one. One appealing feature of our construction is that it can preserve the security properties of the original scheme. For example, if the original scheme has security with extraction queries, the new scheme is also secure with extraction queries. Besides, the new scheme can achieve unforgeability even if the original scheme does not provide this security property. Instantiating our construction with existing watermarking schemes for PRF, we obtain collusion resistant watermarkable PRFs from standard assumptions, offering various security properties.

2020

ASIACRYPT

Possibility and Impossibility Results for Receiver Selective Opening Secure PKE in the Multi-Challenge Setting
📺
Abstract

Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages.
In this work, we explore the possibility for achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the $k$-challenge setting (i.e., the adversary can obtain $k$ challenge ciphertexts for each public key) if its secret key contains less than $k$ bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the $k$-challenge setting, where the ratio of the secret key length to $k$ approaches the lower bound 1.

2019

CRYPTO

Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications
📺
Abstract

We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error $$(2/3)$$, or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that “approximates” the actual witness. Our systems do not suffer from these limitations.The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error $$(1/poly)$$, and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.

2019

ASIACRYPT

Strongly Secure Authenticated Key Exchange from Supersingular Isogenies
Abstract

This paper aims to address the open problem, namely, to find new techniques to design and prove security of supersingular isogeny-based authenticated key exchange (AKE) protocols against the widest possible adversarial attacks, raised by Galbraith in 2018. Concretely, we present two AKEs based on a double-key PKE in the supersingular isogeny setting secure in the sense of CK$$^+$$, one of the strongest security models for AKE. Our contributions are summarised as follows. Firstly, we propose a strong OW-CPA secure PKE, $$\mathsf {2PKE_{sidh}}$$, based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a [OW-CCA, OW-CPA] secure KEM, $$\mathsf {2KEM_{sidh}}$$. Secondly, we propose a two-pass AKE, $$\mathsf {SIAKE}_2$$, based on SI-DDH assumption, using $$\mathsf {2KEM_{sidh}}$$ as a building block. Thirdly, we present a modified version of $$\mathsf {2KEM_{sidh}}$$ that is secure against leakage under the 1-Oracle SI-DH assumption. Using the modified $$\mathsf {2KEM_{sidh}}$$ as a building block, we then propose a three-pass AKE, $$\mathsf {SIAKE}_3$$, based on 1-Oracle SI-DH assumption. Finally, we prove that both $$\mathsf {SIAKE}_2$$ and $$\mathsf {SIAKE}_3$$ are CK$$^+$$ secure in the random oracle model and supports arbitrary registration. We also provide an implementation to illustrate the efficiency of our schemes. Our schemes compare favourably against existing isogeny-based AKEs. To the best of our knowledge, they are the first of its kind to offer security against arbitrary registration, wPFS, KCI, and MEX simultaneously. Regarding efficiency, our schemes outperform existing schemes in terms of bandwidth as well as CPU cycle count.

2019

ASIACRYPT

Collusion Resistant Watermarking Schemes for Cryptographic Functionalities
Abstract

A cryptographic watermarking scheme embeds a message into a program while preserving its functionality. Recently, a number of watermarking schemes have been proposed, which are proven secure in the sense that given one marked program, any attempt to remove the embedded message will substantially change its functionality.In this paper, we formally initiate the study of collusion attacks for watermarking schemes, where the attacker’s goal is to remove the embedded messages given multiple copies of the same program, each with a different embedded message. This is motivated by practical scenarios, where a program may be marked multiple times with different messages.The results of this work are twofold. First, we examine existing cryptographic watermarking schemes and observe that all of them are vulnerable to collusion attacks. Second, we construct collusion resistant watermarking schemes for various cryptographic functionalities (e.g., pseudorandom function evaluation, decryption, etc.). To achieve our second result, we present a new primitive called puncturable functional encryption scheme, which may be of independent interest.

2018

PKC

Hedged Nonce-Based Public-Key Encryption: Adaptive Security Under Randomness Failures
Abstract

Nowadays it is well known that randomness may fail due to bugs or deliberate randomness subversion. As a result, the security of traditional public-key encryption (PKE) cannot be guaranteed any more. Currently there are mainly three approaches dealing with the problem of randomness failures: deterministic PKE, hedged PKE, and nonce-based PKE. However, these three approaches only apply to different application scenarios respectively. Since the situations in practice are dynamic and very complex, it’s almost impossible to predict the situation in which a scheme is deployed, and determine which approach should be used beforehand.In this paper, we initiate the study of hedged security for nonce-based PKE, which adaptively applies to the situations whenever randomness fails, and achieves the best-possible security. Specifically, we lift the hedged security to the setting of nonce-based PKE, and formalize the notion of chosen-ciphertext security against chosen-distribution attacks (IND-CDA2) for nonce-based PKE. By presenting two counterexamples, we show a separation between our IND-CDA2 security for nonce-based PKE and the original NBP1/NBP2 security defined by Bellare and Tackmann (EUROCRYPT 2016). We show two nonce-based PKE constructions meeting IND-CDA2, NBP1 and NBP2 security simultaneously. The first one is a concrete construction in the random oracle model, and the second one is a generic construction based on a nonce-based PKE scheme and a deterministic PKE scheme.

2008

EPRINT

Constant-Size Dynamic $k$-TAA
Abstract

$k$-times anonymous authentication ($k$-TAA) schemes allow members
of a group to be authenticated anonymously by application providers
for a bounded number of times. Dynamic $k$-TAA allows application
providers to independently grant or revoke users from their own
access group so as to provide better control over their clients. In
terms of time and space complexity, existing dynamic $k$-TAA schemes
are of complexities O($k$), where $k$ is the allowed number of
authentication. In this paper, we construct a dynamic $k$-TAA scheme
with space and time complexities of $O(log(k))$. We also outline how
to construct dynamic $k$-TAA scheme with a constant proving effort.
Public key size of this variant, however, is $O(k)$.
We then describe a trade-off between efficiency and setup freeness
of AP, in which AP does not need to hold any secret while
maintaining control over their clients.
To build our system, we modify the short group signature scheme into
a signature scheme and provide efficient protocols that allow one to
prove in zero-knowledge the knowledge of a signature and to obtain a
signature on a committed block of messages. We prove that the
signature scheme is secure in the standard model under the $q$-SDH
assumption.
Finally, we show that our dynamic $k$-TAA scheme, constructed from
bilinear pairing, is secure in the random oracle model.

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

Practical Compact E-Cash
Abstract

Compact e-cash schemes allow a user to withdraw a wallet
containing $k$ coins in a single operation, each of which the user
can spend unlinkably. One big open problem for compact e-cash is
to allow multiple denominations of coins to be spent efficiently
without executing the spend protocol a number of times. In this
paper, we give a (\emph{partial}) solution to this open problem by
introducing two additional protocols, namely, compact spending and
batch spending. Compact spending allows spending all the $k$ coins
in one operation while batch spending allows spending any number
of coins in the wallet in a single execution.
We modify the security model of compact e-cash to accommodate
these added protocols and present a generic construction. While
the spending and compact spending protocol are of constant time
and space complexities, complexities of batch spending is linear
in the number of coins to be spent together. Thus, we regard our
solution to the open problem as {\it partial}.
We provide two instantiations under the $q$-SDH assumption and the
LRSW assumption respectively and present security arguments for
both instantiations in the random oracle model.

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

Structural Identity-Based Encryption
Abstract

In this paper, we introduce the concept of structural identity-based
encryption (SIBE). Similar to hierarchical identity-based encryption
(HIBE), entities in the system are organized into hierarchy. An
entity in SIBE can decrypt ciphertext for all its ancestors. It can
be seen as an opposite of HIBE, where an entity can decrypt the
ciphertext for all its descendants.
We formalize the notion and security requirements, propose an
efficient construction and show that our construction is secure
under appropriate assumptions in the random oracle model.

2007

EPRINT

Practical Anonymous Divisible E-Cash From Bounded Accumulators
Abstract

We present an efficient off-line divisible e-cash scheme which is
\emph{truly anonymous} without a trusted third party. This is the
second scheme in the literature which achieves full unlinkability
and anonymity, after the seminal work proposed by Canard and Gouget.
The main trick of our scheme is the use of a bounded accumulator in
combination with the classical binary tree approach.
The aims of this paper are twofold. Firstly, we analyze Canard and
Gouget's seminal work on the efficient off-line divisible e-cash. We
point out some subtleties on the parameters generation of their
scheme. Moreover, spending a coin of small value requires
computation of several hundreds of multi-based exponentiations,
which is very costly. In short, although this seminal work provides
a new approach of achieving a truly anonymous divisible e-cash,
unfortunately it is rather impractical. Secondly, we present our
scheme that uses a novel approach of incorporating a bounded
accumulator. In terms of time and space complexities, our scheme is
$50$ to $100$ times more efficient than Canard and Gouget's work in
the spend protocol at the cost of an $10$ to $500$ (the large range
is due to whether pre-processing is taken into account and the
probabilistic nature of our withdrawal protocol) times less
efficient withdrawal protocol. We believe this trade-off between the
withdrawal protocol and the spend protocol is reasonable as the
former protocol is to be executed much less frequent than the
latter. Nonetheless, while their scheme provides an affirmative
answer to whether divisible e-cash can be \emph{truly anonymous},
our result puts it a step further and we show that truly anonymous
divisible e-cash can be \emph{practical}.

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

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

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

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.

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.

#### Coauthors

- Tony K. Chan (1)
- Jing Chen (1)
- Wenbin Chen (1)
- Hui Cui (1)
- Jinguang Han (1)
- Zhengan Huang (2)
- Junzuo Lai (3)
- Jin Li (1)
- Joseph K. Liu (9)
- Yi Mu (6)
- Zhen Peng (1)
- Willy Susilo (7)
- Song Tian (1)
- Patrick P. Tsang (2)
- Kunpeng Wang (1)
- Victor K. Wei (2)
- William Whyte (1)
- Duncan S. Wong (6)
- Qiuliang Xu (4)
- Xiu Xu (1)
- Haiyang Xue (1)
- Guomin Yang (1)
- Rupeng Yang (4)
- Siu Ming Yiu (1)
- Zuoxia Yu (3)
- Y. H. Yuen (1)
- Tsz Hon Yuen (3)
- Zhenfei Zhang (1)
- Jianying Zhou (1)