## CryptoDB

### Chunming Tang

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Efficient Explicit Constructions of Multipartite Secret Sharing Schemes
Abstract

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing.This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, and the constructions for compartmented access structures with upper bounds and compartmented access structures with lower bounds, two families of compartmented access structures.On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to the three families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of the three families of access structures, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing the three families of multipartite access structures by efficient methods.

2014

EPRINT

2014

EPRINT

2008

EPRINT

Perfectly Hiding Commitment Scheme with Two-Round from Any One-Way Permutation
Abstract

Commitment schemes are arguably among the most important and
useful primitives in cryptography. According to the computational
power of receivers, commitments can be classified into three
possible types: {\it computational hiding commitments,
statistically hiding commitments} and {\it perfect computational
commitments}. The fist commitment with constant rounds had been
constructed from any one-way functions in last centuries, and the
second with non-constant rounds were constructed from any one-way
functions in FOCS2006, STOC2006 and STOC2007 respectively,
furthermore, the lower bound of round complexity of statistically
hiding commitments has been proven to be $\frac{n}{logn}$ rounds
under the existence of one-way function.
Perfectly hiding commitments implies statistically hiding, hence,
it is also infeasible to construct a practically perfectly hiding
commitments with constant rounds under the existence of one-way
function. In order to construct a perfectly hiding commitments
with constant rounds, we have to relax the assumption that one-way
functions exist. In this paper, we will construct a practically
perfectly hiding commitment with two-round from any one-way
permutation. To the best of our knowledge, these are the best
results so far.

2008

EPRINT

Divisible On-line/Off-line Signatures
Abstract

On-line/Off-line signatures are used in a particular scenario where the signer must respond quickly once the message to be signed is presented. The idea is to split the signing procedure into two phases: the off-line and on-line phases. The signer can do some pre-computations in off-line phase before he sees the message to be signed.
In most of these schemes, when signing a message $m$, a partial signature of $m$ is computed in the off-line phase. We call this part of signature the off-line signature token of message $m$. In some special applications, the off-line signature tokens might be exposed in the off-line phase. For example, some signers might want to transmit off-line signature tokens in the off-line phase in order to save the on-line transmission bandwidth. Another example is in the case of on-line/off-line threshold signature schemes, where off-line signature tokens are unavoidably exposed to all the players in the off-line phase.
This paper discusses this exposure problem and introduces a new notion: divisible on-line/off-line signatures, in which exposure of off-line signature tokens in off-line phase is allowed. An efficient construction of this type of signatures is also proposed. Furthermore, we show an important application of divisible on-line/off-line signatures in the area of on-line/off-line threshold signatures.

2004

EPRINT

Non-Interactive and Information-Theoretic Secure Publicly Verifiable Secret Sharing
Abstract

A publicly verifiable secret sharing scheme is more applicable
than a verifiable secret sharing because of the property that the
validity of the shares distributed by the dealer can be verified
by any party. In this paper, we construct a non-interactive and
information-theoretic publicly verifiable secret sharing by a
computationally binding and unconditionally hiding commitment
scheme and zero-knowledge proof of knowledge.

2004

EPRINT

Delegateable Signature Using Witness Indistinguishable and Witness Hiding Proofs
Abstract

A delegateable signature scheme is a signature scheme where the
owner of the signing key(Alice) can securely delegate to another
party(Bob) the ability to sign on Alice's behalf on a restricted
subset $S$ of the message space. Barak first defined and
constructed this signature scheme using non-interactive
zero-knowledge proof of knowledge(NIZKPK)\cite{Barak}. In his
delegateable signature scheme, the function of NIZKPK is to
prevent the signing verifier from tell which witness(i.e.
restricted subset) is being used.
Witness indistinguishable(WI) and witness hiding(WH) proof systems
are weaker proof model than zero-knowledge proof and were proposed
by Feige and Shamir in \cite{FS}, however, the verifier cannot
also distinguish the witness which is being used in these two
protocols. In this paper, we construct delegateable signature
scheme using WI and WH proof protocols.

2003

EPRINT

A Verifiable Secret Sharing Scheme with Statistical zero-knowledge
Abstract

In this paper, we first propose a protocol in which the prover can
show that a=b holds for two committed integers a and b;
also, we present a protocol in which the prover can prove that
a\neq 0 holds for committed integer a; then, we construct a
protocol to prove that the degree of a polynomial f(x) equals to
t-1 exactly, which has been as an open problem(see[21]);
finally, we provide a protocol in which the prover proves that a
pair (x,y) is generated by a polynomial f(x), i.e., y=f(x)(mod m), where m is a prime.
Based on above four protocols, we put forward a verifiable
(t,n)-secret sharing scheme, which can avoid all known the
dealer's cheats.
In particular, all above protocols are statistical zero-knowledge.

2003

EPRINT

The Statistical Zero-knowledge Proof for Blum Integer Based on Discrete Logarithm
Abstract

Blum integers (BL), which has extensively been used in the domain
of cryptography, are integers with form $p^{k_1}q^{k_2}$, where
$p$ and $q$ are different primes both $\equiv
3\hspace{4pt}mod\hspace{4pt}4$ and $k_1$ and $k_2$ are odd
integers. These integers can be divided two types: 1) $M=pq$, 2)
$M=p^{k_1}q^{k_2}$, where at least one of $k_1$ and $k_2$ is
greater than 1.\par
In \cite{dbk3}, Bruce Schneier has already proposed an open
problem: {\it it is unknown whether there exists a truly practical
zero-knowledge proof for $M(=pq)\in BL$}. In this paper, we
construct two statistical zero-knowledge proofs based on discrete
logarithm, which satisfies the two following properties: 1) the
prover can convince the verifier $M\in BL$ ; 2) the prover can
convince the verifier $M=pq$ or $M=p^{k_1}q^{k_2}$, where at least
one of $k_1$ and $k_2$ is more than 1.\par
In addition, we propose a statistical zero-knowledge proof in
which the prover proves that a committed integer $a$ is not equal
to 0.\par

#### Coauthors

- Yuenai Chen (1)
- Qi Chen (1)
- Chong-zhi Gao (1)
- Yong He (1)
- Xing Hu (1)
- Zhiqiang Lin (1)
- Zhuojun Liu (5)
- Jinwang Liu (1)
- Dingyi Pei (3)
- Yanfeng Qi (1)
- Mingsheng Wang (2)
- Baodian Wei (1)
- Can Xiang (1)
- Dongqing Xie (1)
- Zheng-an Yao (1)