International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Junji Shikata

Affiliation: Yokohama National University, Japan

Publications

Year
Venue
Title
2018
CRYPTO
Lower Bounds on Lattice Enumeration with Extreme Pruning 📺
At Eurocrypt ’10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.
2016
PKC
2015
EPRINT
2015
EPRINT
2005
ASIACRYPT
2004
PKC
2004
EPRINT
Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application
In this paper, we discuss non-interactive updating of decryption keys in identity-based encryption (IBE). IBE is a public key cryptosystem where a public key is an arbitrary string. In practice, key revocation is a necessary and inevitable process and IBE is no exception when it comes to having to manage revocation of decryption keys without losing its merits in efficiency. Our main contribution of this paper is to propose novel constructions of IBE where the decryption key can be renewed without having to make changes to its public key, i.e. user's identity. We achieve this by tactfully extending the hierarchical IBE (HIBE). Regarding security, we address semantic security against adaptive chosen cipher-text attack for a very strong attack environment that models all possible types of key exposures in the random oracle model. Straightforward extension of the HIBE, however, does not achieve our goal and such scheme is completely insecure under our attack model. In addition to this, we show method of constructing (partially collusion resistant) HIBE from arbitrary IBE in the random oracle model. By combining these results, we can construct an IBE with non-interactive key update from only an arbitrary IBE.
2003
PKC
2003
EPRINT
Relation among simulator-based and comparison-based definitions of semantic security
Yodai Watanabe Junji Shikata
This paper studies the relation among simulator-based and comparison-based definitions of semantic security. The definitions are considered in a more general framework than the ordinal one; namely, an adversary is assumed to have access to prior information of a plaintext. If the framework is restricted to the ordinal one, then all the security notions considered in this paper, including indistinguishability, are shown to be equivalent. On the other hand, the equivalence is not necessarily valid in the general framework. In fact, it is shown that no encryption scheme is secure in the sense of comparison-based semantic security in the strongest forms. Furthermore, a sufficient condition for the equivalence between semantic security and indistinguishability is derived.
2003
EPRINT
On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?
In a practical system, a message is often encrypted more than once by different encryptions, here called multiple encryption, to enhance its security. Additionally, new features may be achieved by multiple encrypting a message for a scheme, such as the key-insulated cryptosystems \cite{DKXY02} and anonymous channels \cite{Cha81}. Intuitively, a multiple encryption should remain ``secure'', whenever there is one component cipher unbreakable in it. In NESSIE's latest Portfolio of recommended cryptographic primitives (Feb. 2003), it is suggested to use multiple encryption with component ciphers based on different assumptions to acquire long term security. However, in this paper we show this needs careful discussion. Especially, this may \emph{not} be true according to (adaptive) chosen ciphertext attack ({\sf CCA}), even with all component ciphers {\sf CCA} secure. We define an extended version of {\sf CCA} called \emph{chosen ciphertext attack for multiple encryption} ({\sf ME-CCA}) to emulate real world partial breaking of assumptions, and give constructions of multiple encryption satisfying {\sf ME-CCA} security. Since {\sf CCA} security seems so stringent, we further relax it by introducing \emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf IND-ME-wCCA} secure multiple encryption can be acquired from {\sf IND-gCCA} secure component ciphers. We also study the relation of various security notions for multiple encryption. We then apply these results to key-insulated cryptosystem. It is only previously known in \cite{DKXY02} that a generic construction exists provably secure against {\sf CPA} attack, however, we prove that this generic construction is in fact secure against {\sf ME-wCCA} by choosing all components {\sf IND-CCA} secure. We also give an efficient generic construction of key-insulated cryptosystem, which is so far the \emph{first} generic construction provably secure against {\sf CCA} (in the random oracle model).
2002
ASIACRYPT
2002
EUROCRYPT
2002
PKC
2002
EPRINT
Equivalence between semantic security and indistinguishability against chosen ciphertext attacks
Yodai Watanabe Junji Shikata Hideki Imai
The aim of this work is to examine the relation between the notions of semantic security and indistinguishability against chosen ciphertext attacks. For this purpose, a new security notion called non-dividability is introduced independent of attack models, and is shown to be equivalent to both of the two notions. This result is expected to provide a clearer understanding of the equivalence between semantic security and indistinguishability under any form of attack.
2000
ASIACRYPT
1999
ASIACRYPT
1999
EUROCRYPT

Program Committees

Asiacrypt 2019
PKC 2002