## CryptoDB

### Wen-Guey Tzeng

#### Affiliation: National Chiao Tung University

#### Publications

**Year**

**Venue**

**Title**

2007

EPRINT

Public Key Broadcast Encryption with Low Number of Keys and Constant Decryption Time
Abstract

In this paper we propose two public-key BE schemes that have
efficient complexity measures.
The first scheme, called the BE-PI scheme, has $O(r)$
header size, $O(1)$ public keys and $O(\log N)$ private
keys, where $r$ is the number of revoked users.
This is the first public-key BE scheme that has both public
and private keys under $O(\log N)$ while the header size is
$O(r)$.
These complexity measures of the header size and private keys
also match those of efficient secret-key broadcast encryption
schemes.
\par
Our second scheme, called the PK-SD-PI scheme, has $O(r)$
header size, $O(1)$ public key and $O(\log^2 N)$ private
keys.
They are the same as those of the SD scheme. %
Nevertheless, the decryption time is remarkably $O(1)$. %
This is the first public-key BE scheme that has $O(1)$
decryption time while other complexity measures are kept
low.
The PK-LSD-PI scheme can be constructed in the same way. %
It has $O(r/\epsilon)$ ciphertext size and
$O(\log^{1+\epsilon} N)$ private keys, where $0<\epsilon<1$.
The decryption time is also $O(1)$.
\par
Our basic schemes are one-way secure against {\em full
collusion of revoked users}.
With a slight modification, we make both schemes
indistinguishably secure against the adaptive
chosen ciphertext attack.
The BE-PI scheme has the capability of {\em tracing
traitors}.
It is able to find out what private keys are used in a
confiscated decoding box.

2007

EPRINT

Identity-Committable Signatures and Their Extension to Group-Oriented Ring Signatures
Abstract

The identity of "Deep Throat", a pseudonym of the information source in the Watergate scandal, remained mysterious for more than three decades. In 2005, an ex-FBI official claimed that he was the anonymous source. Nevertheless, some are still inconvinced. In this paper, we introduce a new notion of identity-committable signatures (ICS) to ensure the anonymity of "Deep Throat" inside a group. A member of an organization can sign a message on behalf of himself (regular signature) or the organization (identity-committed signature). In the latter case, the signer's identity is hidden from anyone, and can be opened by himself only. We describe the requirements of ICS and give the formal definition of it.
Then we extend the notion of ICS to group-oriented ring signatures (GRS) which further allow the signer to hide his identity behind multiple groups. We believe a GRS scheme is more efficient and practical than a ring signature scheme for leaking secrets. Finally, we provide concrete constructions of ICS and GRS with information-theoretic anonymity, that is, the identity of the signer is fully-protected.

2005

PKC

2005

EPRINT

An Efficient Solution to The Millionaires' Problem Based on Homomorphic Encryption
Abstract

We proposed a two-round protocol for solving the
Millionaires' Problem in the setting of semi-honest
parties.
Our protocol uses either multiplicative or additive
homomorphic encryptions.
Previously proposed protocols used additive or XOR
homomorphic encryption schemes only.
The computation and communication costs of our protocol
are in the same asymptotic order as those of
the other efficient protocols.
Nevertheless, since multiplicative homomorphic encryption
scheme is more efficient than an additive one practically,
our construction saves computation time and communication
bandwidth in practicality.

2004

EPRINT

Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and Non-Adaptive Queries
Abstract

In this paper we propose a very efficient two-round k-out-of-n oblivious transfer scheme, in which R sends O(k) messages to S, and S sends O(n) messages back to R. The computation cost of R and S is reasonable as R needs O(k) operations and S needs O(n)operations. The choices of R are unconditionally secure and the secrecy of unchosen messages is guaranteed as well if the decisional bilinear Diffie-Hellman problem is hard. When k=1, our scheme is as efficient as the most efficient 1-out-of-n oblivious transfer scheme up to now. Our scheme has the nice property of universal parameters.
That is, each pair of R and S need neither hold any secret key nor perform any prior setup. The system parameters can be used by all senders and receivers without any trapdoor specification. Our k-out-of-n oblivious transfer scheme is the most efficient one in terms of the communication cost, in both rounds and the number of messages.
Moreover, our scheme can be extended in a straightforward way to an adaptive k-out-of-n oblivious transfer scheme, which allows the receiver R to choose the secrets one by one adaptively. In our scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, only O(1) messages are exchanged and O(1) operations (in elliptic curves) are performed. In fact, the number k of queries need not be pre-fixed or known beforehand. This makes our scheme highly flexible.

2003

EPRINT

A Threshold GQ Signature Scheme
Abstract

We proposed the first threshold GQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Our scheme achieve optimal resilience, that is, the adversary can corrupt up to a half of the players. As an extension of our work, we proposed a threshold forward-secure signature scheme, which is the threshold version of the most efficient forward-secure signature scheme up to now.

2001

EPRINT

Robust key-evolving public key encryption schemes
Abstract

We propose a key-evolving paradigm to deal with the key
exposure problem of public key encryption schemes.
The key evolving paradigm is like the one used for
forward-secure digital signature schemes.
Let time be divided into time periods such that
at time period $j$, the decryptor holds the secret key
$SK_j$, while the public key PK is fixed during its
lifetime.
At time period $j$, a sender encrypts a message $m$ as
$\langle j, c\rangle$, which can be decrypted only
with the private key $SK_j$.
When the time makes a transit from period $j$ to $j+1$, the
decryptor updates its private key from $SK_j$ to $SK_{j+1}$
and deletes $SK_j$ immediately.
The key-evolving paradigm assures that compromise of the
private key $SK_j$ does not jeopardize the message encrypted
at the other time periods.
\par
We propose two key-evolving public key encryption schemes
with $z$-resilience such that compromise of $z$ private keys
does not affect confidentiality of messages encrypted in
other time periods.
Assuming that the DDH problem is hard,
we show one scheme semantically secure against passive
adversaries and the other scheme semantically secure against
the adaptive chosen ciphertext attack under the random
oracle.

2001

EPRINT

Efficient oblivious transfer schemes
Abstract

In this paper we propose a very efficient
(string) $OT_n^1$ scheme
for any $n\geq 2$.
We build our $OT_n^1$ scheme from fundamental cryptographic
techniques directly.
It achieves optimal efficiency in the number of rounds
and the total number of exchanged messages for the case
that the receiver's
choice is unconditionally secure.
The computation time of our $OT_n^1$ scheme is very
efficient, too.
The receiver need compute 2 modular
exponentiations only no matter how large $n$ is,
and the sender need compute $2n$ modular exponentiations.
Furthermore, the system-wide parameters need not change
during the lifetime of the system and are {\em universally
usable}.
That is, all possible receivers and senders use the same
parameters and need no trapdoors specific to each of them.
For our $OT_n^1$ scheme, the privacy of the receiver's choice
is unconditionally secure and the privacy of
the un-chosen secrets is at least as strong as the hardness
of the decisional Diffie-Hellman problem.
\par
We extend our $OT_n^1$ scheme to distributed oblivious
transfer schemes.
Our distributed $OT_n^1$ scheme takes full advantage of
the research results of secret sharing and is conceptually
simple.
It achieves better security than
Noar and Pinkas's scheme does in many aspects.
For example, our scheme is secure against collusion of $R$
and $t$-$1$ servers
and it need not restrict $R$ to contact at most $t$ servers,
which is difficult to enforce.
\par
For applications, we present a method of transforming any
single-database PIR
protocol into a symmetric PIR protocol with only one extra
unit of communication cost.

#### Program Committees

- PKC 2016
- PKC 2012
- PKC 2006

#### Coauthors

- Yi-Ruei Chen (1)
- Cheng-Kang Chu (5)
- Hsiao-Ying Lin (1)
- Yi-Ru Liu (2)
- Li-Shan Liu (1)
- Amir Rezapour (1)
- Shiuan-Tzuo Shen (2)
- Zhi-Jia Tzeng (4)