## CryptoDB

### Kaoru Kurosawa

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

How to Correct Errors in Multi-server PIR
Abstract

Suppose that there exist a user and $$\ell $$ servers $$S_1,\ldots ,S_{\ell }$$. Each server $$S_j$$ holds a copy of a database $$\mathbf {x}=(x_1, \ldots , x_n) \in \{0,1\}^n$$, and the user holds a secret index $$i_0 \in \{1, \ldots , n\}$$. A b error correcting $$\ell $$ server PIR (Private Information Retrieval) scheme allows a user to retrieve $$x_{i_0}$$ correctly even if and b or less servers return false answers while each server learns no information on $$i_0$$ in the information theoretic sense. Although there exists such a scheme with the total communication cost $$ O(n^{1/(2k-1)} \times k\ell \log {\ell } ) $$ where $$k=\ell -2b$$, the decoding algorithm is very inefficient.In this paper, we show an efficient decoding algorithm for this b error correcting $$\ell $$ server PIR scheme. It runs in time $$O(\ell ^3)$$.

2010

EPRINT

Between Hashed DH and Computational DH: Compact Encryption from Weaker Assumption
Abstract

In this paper, we introduce
the intermediate hashed Diffie-Hellman (IHDH) assumption
which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH
assumption),
and is stronger than the computational DH assumption.
We then present two public key encryption schemes with short ciphertexts
which are both chosen-ciphertext secure under this assumption.
The short-message scheme has smaller size of ciphertexts
than Kurosawa-Desmedt (KD) scheme,
and
the long-message scheme is a KD-size scheme with arbitrary plaintext length
which is based on a weaker assumption
than the HDH assumption.

2010

EPRINT

Efficiency-Improved Fully Simulatable Adaptive OT under the DDH Assumption
Abstract

At Asiacrypt 2009, Kurosawa and Nojima showed a fully simulatable adaptive oblivious transfer (OT) protocol under the DDH assumption in the standard model. However, Green and Hohenberger pointed out
that the communication cost of each transfer phase is O(n), where n is the number of the sender's messages. In this paper, we show that the cost can be reduced to O(1) by utilizing a verifiable shuffle protocol.

2010

EPRINT

Round-Efficient Perfectly Secure Message Transmission Scheme Against General Adversary
Abstract

In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are $n$ channels between a sender and a receiver,
and they share no key. An infinitely powerful adversary $A$ can corrupt (observe and forge) the messages sent through
some subset of $n$ channels. For non-threshold adversaries called $Q^2$, Kumar et al. showed a many round PSMT \cite{KGSR}.
In this paper, we show round efficient PSMTs against $Q^2$-adevrsaries. We first give a $3$-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a $2$-round PSMT which is inefficient in general. (However, it is efficient for some special case.)

2008

EPRINT

Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme
Abstract

In the model of perfectly secure message transmission schemes (PSMTs), there are $n$ channels between a sender and a receiver. An infinitely powerful adversary $\A$ may corrupt (observe and forge)the messages sent through $t$ out of $n$ channels. The sender wishes to send a secret $s$ to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver.
In this paper, we show the first $2$-round PSMT for $n=2t+1$ such that not only the transmission rate is $O(n)$ but also the computational costs of the sender and the receiver are both polynomial in $n$. This means that we solve the open problem raised by
Agarwal, Cramer and de Haan at CRYPTO 2006.

2008

ASIACRYPT

2008

EPRINT

Universally Composable Undeniable Signature
Abstract

How to define the security of undeniable signature schemes is a challenging task. This paper presents two security definitions of undeniable signature schemes which are more useful or natural than the existing definition. It then proves their equivalence.
We first define the UC-security, where UC means universal composability. We next show that there exists a UC-secure undeniable signature scheme which does not satisfy the standard definition of security that has been believed to be adequate so far. More precisely, it does not satisfy the invisibility defined by \cite{DP96}. We then show a more adequate definition of invisibility which captures a wider class of (naturally secure) undeniable signature schemes.
We finally prove that the UC-security against non-adaptive adversaries is equivalent to this definition of invisibility and the strong unforgeability in $\cF_{ZK}$-hybrid model, where $\cF_{ZK}$ is the ideal ZK functionality. Our result of equivalence implies that all the known proven secure undeniable signature schemes (including Chaum's scheme) are UC-secure if the confirmation/disavowal protocols are both UC zero-knowledge.

2008

EPRINT

Efficient Chosen Ciphertext Secure Public Key Encryption under the Computational Diffie-Hellman Assumption
Abstract

Recently Cash, Kiltz, and Shoup showed a variant of the Cramer-Shoup (CS) public key encryption (PKE) scheme whose chosen-ciphertext (CCA) security relies on the computational Diffie-Hellman (CDH) assumption. The cost for this high security is that the size of ciphertexts is much longer than the CS scheme. In this paper, we show how to achieve CCAsecurity under the CDH assumption without increasing the size of ciphertexts. We further show a more efficient scheme under the hashed Diffie-Hellman (HDH) assumption such that the size of ciphertexts is the same as that of the Kurosawa-Desmedt (KD) scheme. Note that the CDH and HDH assumptions are weaker than the decisional Diffie-Hellman assumption which the CS and KD schemes rely on. Both of our schemes are based on a certain broadcast encryption (BE) scheme while the Cash-Kiltz-Shoup scheme is based on a different paradigm which is called the Twin DH problem.
As an independent interest, we also show a generic method of constructing CCA-secure PKE schemes from BE schemes such that the existing CCA-secure constructions can be viewed as special cases.

2007

PKC

2007

EPRINT

Direct Reduction of String (1,2)-OT to Rabin's OT
Abstract

It is known that string (1,2)-OT and Rabin's OT are equivalent. However,
two steps are required to construct a string $(1,2)$-OT from Rabin's OT.
The first step is a construction of a bit (1,2)-OT from Rabin's OT, and
the second step is a construction of a string $(1,2)$-OT from the bit (1,2)-OT. No direct reduction is known. In this paper, we show a direct reduction of string (1,2)-OT to Rabin's OT by using a deterministic randomness extractor. Our reduction is much more efficient than the previous two-step reduction.

2007

EPRINT

How to Derive Lower Bound on Oblivious Transfer Reduction
Abstract

Suppose that we are given an ideal oblivious transfer protocol (OT). We wish to construct a larger OT by using the above OT as a blackbox. Then how many instances of the given ideal OT should be invoked ? For this problem, some lower bounds were derived using entropy. In this paper, we show more tight lower bounds
by using combinatorial techniques. Roughly speaking, our lower bounds are two times larger than the previous bounds.

2007

EPRINT

Almost Secure (1-Round, n-Channel) Message Transmission Scheme
Abstract

It is known that perfectly secure ($1$-round, $n$-channel) message transmission (MT) schemes exist if and only if $n \geq 3t+1$,
where $t$ is the number of channels that the adversary can corrupt.
Then does there exist an {\it almost} secure MT scheme for $n=2t+1$ ? In this paper, we first sum up a number flaws of the previous {\it almost} secure MT scheme presented at Crypto 2004. (The authors already noted in thier presentation at Crypto'2004 that their scheme was flawed.) We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity
of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure ($1$-round, $n$-channel) MT schemes for $n=2t+1$.

2007

EPRINT

How To Find Many Collisions of 3-Pass HAVAL
Abstract

The hash function HAVAL is an Australian extension
of well known Merkle-Damg\r{a}rd hash functions such as MD4 and MD5.
It has three variants, $3$-, $4$- and $5$-pass HAVAL.
On $3$-pass HAVAL,
the best known attack finds a collision pair
with $2^{7}$ computations of the compression function.
To find $k$ collision pairs,
it requires $2^{7}k$ computations.
In this paper,
we present a better collision attack on $3$-pass HAVAL,
which can find $k$ collision pairs with only $2k+33$ computations.
Further,
our message differential is different from the previous ones.
(It is important to find collisions for different message differentials.)

2005

EUROCRYPT

2005

EPRINT

A Provably Secure and Efficient Verifiable Shuffle based on a Variant of the Paillier Cryptosystem
Abstract

We propose a variant of the Paillier cryptosystem that
improves efficiency in encryption, re-encryption and decryption
while preserving the homomorphic property. We then use this
variant to construct a new verifiable shuffle system and prove its
security. We show that the new shuffle scheme has the least number
of rounds and exponentiations compared to all known shuffle
schemes. Finally, we show how to construct a publicly verifiable
mix-net using the shuffle system.

2005

EPRINT

Primal-Dual Distance Bounds of Linear Codes with Application to Cryptography
Abstract

Let $N(d,d^\perp)$ denote the minimum
length $n$ of a linear code $C$ with $d$ and $d^{\bot}$,
where $d$ is the minimum Hamming distance of $C$
and
$d^{\bot}$ is the minimum Hamming distance of $C^{\bot}$.
In this paper,
we show a lower bound and an upper bound on $N(d,d^\perp)$.
Further,
for small values of $d$ and $d^\perp$, we determine
$N(d,d^\perp)$ and give a
generator matrix of the optimum linear code.
This problem is directly related to the design method of cryptographic
Boolean functions suggested by Kurosawa et al.

2005

EPRINT

Verifiable Shuffles: A Formal Model and a Paillier-based 3-Round Construction with Provable Security
Abstract

We propose a formal model for security of verifiable
shuffles and a new verifiable shuffle system based on the Paillier
encryption scheme, and prove its security in the proposed model.
The model is general, so it can be extended to verifiable shuffle
decryption and provides a direction for provable security of
mix-nets.

2005

EPRINT

One-Wayness Equivalent to General Factoring
Abstract

This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent to
{\it general} factoring in the {\it standard} model (in the sense of IND-CPA).
Next our proof technique is applied to Rabin-Paillier encryption scheme and a variant of RSA-Paillier encryption scheme to prove their exactly tight one-wayness.

2005

EPRINT

Tag-KEM/DEM: A New Framework for Hybrid Encryption
Abstract

This paper presents a novel framework for the generic construction of hybrid encryption schemes which produces more efficient schemes than the ones known before. A previous framework introduced by Shoup combines a key encapsulation mechanism (KEM) and a data encryption mechanism (DEM). While it is sufficient to require both components to be secure against chosen ciphertext attacks (CCA-secure), Kurosawa and Desmedt showed a particular example of KEM that is not CCA-secure but can be securely combined with a specific type of CCA-secure DEM to
obtain a more efficient, CCA-secure hybrid encryption scheme. There are also many other efficient hybrid encryption schemes in the literature that do not fit Shoup's framework. These facts serve as motivation to seek another framework.
The framework we propose yields more efficient hybrid scheme, and in addition provides insightful explanation about existing schemes that do not fit into the previous framework. Moreover, it allows immediate
conversion from a class of threshold public-key encryption to a hybrid one without considerable overhead, which may not be possible in the previous approach.

2004

EPRINT

Almost Ideal Contrast Visual Cryptography with Reversing
Abstract

A drawback of visual cryptography schemes (VCS) is much loss of contrast in the reconstructed image. This paper shows a new paradigm of VCS in which the original image is almost perfectly reconstructed. A very simple non-cryptographic operation is assumed, reversing black and white, which many copy machines have these days. We first show a $(k,n)$-VCS with {\it reversing} such that white pixels are almost perfectly reconstructed in addition to the perfect reconstruction of black pixels. The proposed scheme is fully compatible with traditional VCS in the following sense: Even if we do not have a copy machine as described above, we can reconstruct the secret image $I$ exactly in the same way as in
the underlying VCS. In other words, we use a copy machine as a hedge to obtain better contrast.
We next show how to convert a perfect {\it black} $(k,n)$-VCS (with reversing) into a perfect {\it white} $(k,n)$-VCS with reversing. Thirdly, we show a perfect black VCS for any monotone access structure. Finally, we show applications of our idea to colored VCS and grey level VCS, respectively.

2004

EPRINT

The Security of the FDH Variant of Chaum's Undeniable Signature Scheme
Abstract

In this paper,
we first introduce a new kind of adversarial goal
called {\em forge-and-impersonate} in
undeniable signature schemes.
Note that
forgeability does not necessarily imply impersonation ability.
We then classify the security of the FDH
variant of Chaum's undeniable signature scheme
according to three dimensions,
the goal of adversaries, the attacks
and the ZK level of confirmation and disavowal protocols.
We finally relate each security to some
well-known computational problem.
In particular,
we prove that the security of the FDH variant of Chaum's scheme with
NIZK confirmation and disavowal protocols
is equivalent to the CDH problem,
as opposed to the GDH problem
as claimed by Okamoto and Pointcheval.

2003

EPRINT

Almost Security of Cryptographic Boolean Functions
Abstract

$PC(l)$ of order $k$
is one of the most general cryptographic criteria
of secure Boolean functions.
In this paper, we introduce
its $\epsilon$-almost version.
The new definition requires {\it only} that
$f(X)+f(X+\Delta)$
is {\it almost} uniformly distiributed
(while the original definition of $PC(l)$ of order $k$
requires that
it is {\it strictly} uniformly distiributed).
We next show its construciton.
Better parameters are then obtained than
normal $PC(l)$ of order $k$ functions.

2003

EPRINT

Stronger Security Bounds for OMAC, TMAC and XCBC
Abstract

OMAC, TMAC and XCBC are CBC-type MAC schemes which are provably secure for arbitrary message length. In this paper, we present a more tight upper bound on ${\tt Adv}^{\sf mac}$ for each scheme,
where ${\tt Adv}^{\sf mac}$ denotes the maximum success (forgery) probability of adversaries. Our bounds are expressed in terms of
the \textit{total length} of all queries of an adversary to the MAC generation oracle while the previous bounds are expressed in terms of the \textit{maximum length} of each query. In particular, a significant improvement occurs if the lengths of queries are heavily unbalanced.

2003

EPRINT

On the Pseudorandomness of KASUMI Type Permutations
Abstract

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that
the four round version is pseudorandom and the six round version is super-pseudorandom.

2003

EPRINT

Some RSA-based Encryption Schemes with Tight Security Reduction
Abstract

In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model.
We first derive the exactly tight one-wayness
of Rabin-Paillier encryption scheme
which assumes that factoring Blum integers is hard.
We next propose the first IND-CPA scheme
whose one-wayness is equivalent to factoring {\it general} $n=pq$
(not factoring Blum integers).
Our reductions of one-wayness are very tight
because they require only one decryption-oracle query.

2003

EPRINT

Efficient Public Key Steganography Secure Against Adaptively Chosen Stegotext Attacks
Abstract

We define the notion of adative chosen stegotext security. We then construct \emph{efficient} public key
steganographic schemes secure against adaptively chosen stegotext attacks, without resort to any special
existence assumption such as unbiased functions. This is the first time such a construction is
obtained. Not only our constructions are \emph{secure}, but also are essentially optimal and have
\emph{no error} decoding. We achieve this by applying a primitive called $\ch{P}$-codes.

2002

EPRINT

TMAC: Two-Key CBC MAC
Abstract

In this paper, we propose TMAC, Two-Key CBC Message Authentication Code. TMAC is a refinement of XCBC (which is a variant of CBC MAC) shown by Black and Rogaway. We use only $(k+n)$-bit key for TMAC while XCBC uses $(k+2n)$-bit key, where $k$ is the key length of the underlying block cipher and $n$ is its block length. The cost for reducing the size of secret keys is almost negligible; only one shift and one conditional XOR. Similarly to XCBC, our algorithm correctly and efficiently handles messages of arbitrary bit length.

2002

EPRINT

New covering radius of Reed-Muller codes for $t$-resilient functions
Abstract

From a view point of cryptography,
we define a new covering radius
of Reed-Muller codes as the maximum distance between
$t$-{\it resilient} functions
and the $r$-th order Reed-Muller code $RM(r,n)$.
We next derive its lower and upper bounds.
We also present a table of numerical data
of our bounds.

2002

EPRINT

Power of a Public Random Permutation and its Application to Authenticated-Encryption
Abstract

In this paper,
we first show that many independent pseudorandom permutations
over $\{0,1\}^n$
can be obtained
from a single public random permutation
and secret $n$ bits.
We next prove that a slightly modified IAPM is secure even if
the underlying block cipher $F$
is publicly accessible (as a blackbox).
We derive a similar result for OCB mode, too.
We finally prove that
our security bound is tight within a constant factor.

2002

EPRINT

OMAC: One-Key CBC MAC
Abstract

In this paper, we present One-key CBC MAC (OMAC) and prove its security for arbitrary length messages. OMAC takes only one key, $K$ ($k$ bits) of a block cipher $E$. Previously, XCBC requires three keys, $(k+2n)$ bits in total, and TMAC requires two keys, $(k+n)$ bits in total, where $n$ denotes the block length of $E$.
The saving of the key length makes the security proof of OMAC substantially harder than those of XCBC and TMAC.

2002

EPRINT

Oblivious Keyword Search
Abstract

In this paper,
we introduce a notion of Oblivious Keyword Search ($OKS$).
Let $W$ be the set of possible keywords.
In the commit phase, a database supplier $T$ commits $n$ data.
In each transfer subphase,
a user $U$ can choose a keyword $w \in W$ adaptively
and find $Search(w)$ without revealing $w$ to $T$,
where $Search(w)$ is the set of all data which includes $w$ as a keyword.
We then show two efficient protocols
such that the size of the commitments is only $(nB)$
regardless of the size of $W$, where $B$ is the size of each data.
It is formally proved that $U$ learns nothing more and
$T$ gains no information on the keywords which $U$ searched.
We further present a more efficient adaptive $OT_k^n$ protocol
than the previous one as an application of our first $OKS$ protocol.

2002

EPRINT

Bit-Slice Auction Circuit
Abstract

In this paper, we introduce a bit-slice approach for auctions and present a more efficient circuit than the normal approach for the highest-price auction. Our circuit can be combined with any auction protocol based on general circuit evaluation. Especially, if we combine with the mix and match technique, then we can obtain a highest-price auction protocol which is at least seven times faster. A second-price auction protocol is also easily constructed from our circuit.

2001

EPRINT

Multi-Recipient Public-Key Encryption with Shortened Ciphertext
Abstract

In the trivial
$n$-recipient public-key encryption scheme,
a ciphertext is a concatenation
of independently encrypted messages for $n$ recipients.
In this paper,
we say that an $n$-recipient scheme
has a ``{\it shortened ciphertext}'' property
if
the length of the ciphertext is almost
a half (or less) of the trivial scheme
and the security is still almost the same
as the underlying single-recipient scheme.
We first present
(multi-plaintext, multi-recipient) schemes
with the ``{\it shortened ciphertext}'' property
for ElGamal scheme and Cramer-Shoup scheme.
We next show
(single-plaintext, multi-recipient)
hybrid encryption schemes
with the ``{\it shortened ciphertext}'' property.

2001

EPRINT

Linear Code Implies Public-Key Traitor Tracing
Abstract

In this paper, we first show that three public-key $(k,n)$-traceability schemes can be derived from an $[n,u,d]$-linear code ${\cal C}$ such that $d \geq 2k+1$. The previous schemes are obtained as special cases. This observation gives a more freedom and a new insight to this field. For example, we show that Boneh-Franklin scheme is equivalent to a slight modification of the corrected Kurosawa-Desmedt scheme. This means that BF scheme is redundant or overdesigned because the modified KD scheme is much simpler. It is also shown that the corrected KD scheme is the best among them.

2000

EPRINT

How to Encrypt Long Messages without Large Size Symmetric/Asymmetric Encryption Schemes
Abstract

Suppose that we wish to encrypt long messages
with small overhead by a public key encryption scheme
which is secure against adaptive chosen ciphertext attack (IND-CCA2).
Then the previous schemes require either
a large size one-way trapdoor permutation (OAEP)
or both a large size symmetric encryption scheme
and a small size asymmetric encryption scheme (hybrid encryption).
In this paper,
we show a scheme which requires only a small size
asymmetric encryption scheme satisfying IND-CCA2
for our purpose.
Therefore, the proposed scheme is very efficient.
A hash function and
a psuedorandom bit generator are used as random oracles.

1997

EUROCRYPT

#### Program Committees

- Asiacrypt 2018
- Asiacrypt 2015
- TCC 2015
- PKC 2014
- Crypto 2014
- PKC 2013 (Program chair)
- PKC 2012
- Crypto 2012
- PKC 2011
- Asiacrypt 2010
- Eurocrypt 2009
- Crypto 2009
- Asiacrypt 2008
- PKC 2008
- Crypto 2007
- Asiacrypt 2007 (Program chair)
- Asiacrypt 2006
- PKC 2005
- FSE 2004
- PKC 2003
- Eurocrypt 2001
- Eurocrypt 1993

#### Coauthors

- Masayuki Abe (3)
- Carlo Blundo (1)
- Mike Burmester (1)
- Yvo Desmedt (5)
- Jun Furukawa (1)
- Rosario Gennaro (4)
- Goichiro Hanaoka (3)
- Swee-Huay Heng (5)
- Toshiya Itoh (1)
- Kazutomo Itoh (1)
- Tetsu Iwata (12)
- Thomas Johansson (2)
- Yutaka Katayama (1)
- Wataru Kishimoto (1)
- Toshimitsu Konno (1)
- Takeshi Koshiba (3)
- Noboru Kunihiro (1)
- Tri Van Le (1)
- Shuichi Makishima (1)
- Ryutaroh Matsumoto (1)
- Toshihiki Matsuo (1)
- Masashi Mitomo (2)
- Lan Nguyen (2)
- Ryo Nojima (2)
- Koji Nuida (1)
- Satoshi Obana (2)
- Wakaha Ogata (14)
- Yasuhiro Ohtaki (1)
- Koji Okada (5)
- Tatsuaki Okamoto (1)
- Choonsik Park (2)
- Le Trieu Phong (1)
- Reihaneh Safavi-Naini (2)
- Takeshi Saito (1)
- Keiichi Sakano (2)
- Kouichi Sakurai (1)
- Alfredo De Santis (1)
- Takashi Satoh (4)
- Katja Schmidt-Samoa (2)
- Victor Shoup (2)
- Douglas R. Stinson (2)
- Kazuhiro Suzuki (4)
- Tsuyoshi Takagi (5)
- Shigeo Tsujii (7)
- Tomohiko Uyematsu (1)
- Duong Quang Viet (1)
- Tohru Yagi (1)
- Takuya Yoshida (3)
- Tomonobu Yoshino (2)
- Takayuki Yoshiwara (1)
- Tomohiro Yuasa (1)