Miodrag J. MIHALJEVIC Marc P. C. FOSSORIER Hideki IMAI
In this paper, important methods for cryptanalysis of the stream cipher based on a class of keystream generators are discussed. These methods employ an approach called the fast correlation attack. This cryptographic problem is treated by considering its equivalent channel coding approach, namely decoding of certain very low rate codes in presence of very high noise. A novel family of algorithms for the fast correlation attack is presented. The algorithms are based on the iterative decoding principle in conjunction with a novel method for constructing the parity-checks. A goal of this paper is to summarize reported results and to compare some of the recent ones. Accordingly, the family is compared with recently proposed improved fast correlation attacks based on iterative decoding methods. An analysis of the algorithms performances and complexities is presented. The corresponding trade-offs between performance, complexity and required inputs are pointed out.
Goichiro HANAOKA Junji SHIKATA Yuliang ZHENG Hideki IMAI
Digital signatures whose security does not rely on any unproven computational assumption have recently received considerable attention. While these unconditionally secure digital signatures provide a foundation for long term integrity and non-repudiation of data, currently known schemes generally require a far greater amount of memory space for the storage of secret and public keys than a traditional digital signature. The focus of this paper is on methods for reducing memory requirements of unconditionally secure digital signatures. A major contribution of this paper is to propose two novel unconditionally secure digital signature schemes, one called a symmetric construction and other an asymmetric construction, which require a significantly smaller amount of memory. As a specific example, with a typical parameter setting the required memory size for a user is reduced to be approximately of that in a previously known scheme. Another contribution of the paper is to show an attack on a multireceiver authentication code which was proposed by Safavi-Naini and Wang. A simple method to fix the problem of the multireceiver authentication code is also proposed.
Goichiro HANAOKA Kazuto OGAWA Itsuro MUROTA Go OHTAKE Keigo MAJIMA Seiichi GOHSHI Kimiyuki OYAMADA Seiichi NAMBA Hideki IMAI
Secure distribution of digital goods is now a significantly important issue for protecting publishers' copyrights. In this paper, we study a useful primitive for constructing a secure and efficient digital rights management system (DRM) where a server which encrypts digital content and one which issues the corresponding decryption key works independently, and existing schemes lack this property. We first argue the desired property necessary of an encryption scheme for constructing an efficient DRM, and formally define an encryption scheme as split encryption scheme containing such property. Also, we show that an efficient split encryption scheme can be constructed from any identity-based scheme. More precisely, we show an equivalence result implying that a split encryption scheme for some system parameter setting and an identity-based encryption scheme have the same primitives but for different uses. Since currently there is no identity-based encryption scheme which is based on well-known computational assumption and/or provably secure in the standard model (i.e. without the random oracle model), by reasonably tuning the system parameter, we show another construction of split encryption which is secure against chosen ciphertext attacks in the standard model assuming that decision Diffie-Hellman problem is hard to solve.
SeongHan SHIN Kazukuni KOBARA Hideki IMAI
An anonymous password-authenticated key exchange (PAKE) protocol is designed to provide both password-only authentication and client anonymity against a semi-honest server, who honestly follows the protocol. In INDOCRYPT2008, Yang and Zhang [26] proposed a new anonymous PAKE (NAPAKE) protocol and its threshold (D-NAPAKE) which they claimed to be secure against insider attacks. In this paper, we first show that the D-NAPAKE protocol [26] is completely insecure against insider attacks unlike their claim. Specifically, only one legitimate client can freely impersonate any subgroup of clients (the threshold t > 1) to the server. After giving a security model that captures insider attacks, we propose a threshold anonymous PAKE (called, TAP+) protocol which provides security against insider attacks. Moreover, we prove that the TAP+ protocol has semantic security of session keys against active attacks as well as insider attacks under the computational Diffie-Hellman problem, and provides client anonymity against a semi-honest server, who honestly follows the protocol. Finally, several discussions are followed: 1) We also show another threshold anonymous PAKE protocol by applying our RATIONALE to the non-threshold anonymous PAKE (VEAP) protocol [23]; and 2) We give the efficiency comparison, security consideration and implementation issue of the TAP+ protocol.
Masakazu YOSHIDA Manabu HAGIWARA Takayuki MIYADERA Hideki IMAI
Entangled states play crucial roles in quantum information theory and its applied technologies. In various protocols such as quantum teleportation and quantum key distribution, a good entangled state shared by a pair of distant players is indispensable. In this paper, we numerically examine entanglement sharing protocols using quantum LDPC CSS codes. The sum-product decoding method enables us to detect uncorrectable errors, and thus, two protocols, Detection and Resending (DR) protocol and Non-Detection (ND) protocol are considered. In DR protocol, the players abort the protocol and repeat it if they detect the uncorrectable errors, whereas in ND protocol they do not abort the protocol. We show that DR protocol yields smaller error rate than ND protocol. In addition, it is shown that rather high reliability can be achieved by DR protocol with quantum LDPC CSS codes.
Nuttapong ATTRAPADUNG Jun FURUKAWA Takeshi GOMI Goichiro HANAOKA Hideki IMAI Rui ZHANG
In this paper, we present an efficient variant of the Boneh-Franklin scheme that achieves a tight security reduction. Our scheme is basically an IBE scheme under two keys, one of which is randomly chosen and given to the user. It can be viewed as a continuation of an idea introduced by Katz and Wang; however, unlike the Katz-Wang variant, our scheme is quite efficient, as its ciphertext size is roughly comparable to that of the original full Boneh-Franklin scheme. The security of our scheme can be based on either the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) assumptions.
Kazuto OGAWA Goichiro HANAOKA Hideki IMAI
In the current broadcasting system or Internet content distribution system, content providers distribute decoders (STB) that contain secret keys for content decryption, prior to content distribution. A content provider sends encrypted content to each user, who then decodes it with his or her STB. While users can get the services at their houses if they have an STB, it is hard for them to get the services outside their houses. A system that allowed users to carry around their secret keys would improve usability, but it would require countermeasures against secret key exposure. In this paper, we propose such an extended broadcasting system using tokens and group signature. The content providers can control the number of keys that users can use outside their houses. The system enables the broadcasters to minimize the damage caused by group signature key exposures and the user to get services outside his or her home.
SeongHan SHIN Kazukuni KOBARA Hideki IMAI
In this paper, we propose a leakage-resilient and proactive authenticated key exchange (called LRP-AKE) protocol for credential services which provides not only a higher level of security against leakage of stored secrets but also secrecy of private key with respect to the involving server. And we show that the LRP-AKE protocol is provably secure in the random oracle model with the reduction to the computational Diffie-Hellman problem. In addition, we discuss about some possible applications of the LRP-AKE protocol.
Huanfei MA Haibin KAN Hideki IMAI
Construction of quaternion design for Space-Time-Polarization Block Codes (STPBCs) is a hot but difficult topic. This letter introduces a novel way to construct high dimensional quaternion designs based on any existing low dimensional quaternion orthogonal designs(QODs) for STPBC, while preserving the merits of the original QODs such as full diversity and simple decoding. Furthermore, it also provides a specific schema to reach full diversity and maximized code gain by signal constellation rotation on the polarization plane.
Miodrag J. MIHALJEVI Marc P.C. FOSSORIER Hideki IMAI
This letter yields a security evaluation of certain broadcast encryption (BE) schemes regarding the generic vulnerability of the textbook BE schemes. The considered vulnerability can be effectively explored assuming known plaintext attacks which in a realistic scenario, corresponding to a legitimate user being the attacker, appears as a ciphertext only attack. Employing the birthday paradox, a dedicated time-data trade-off based algorithm for cryptanalysis is proposed. The developed algorithm is applied to cryptanalysis of particular recently reported class of BE schemes, implying additional insights regarding motivations for their security improvements.
Kunihiko MIYAZAKI Goichiro HANAOKA Hideki IMAI
A digital signature does not allow any alteration of the document to which it is attached. Appropriate alteration of some signed documents, however, should be allowed because there are security requirements other than the integrity of the document. In the disclosure of official information, for example, sensitive information such as personal information or national secrets is masked when an official document is sanitized so that its nonsensitive information can be disclosed when it is requested by a citizen. If this disclosure is done digitally by using the current digital signature schemes, the citizen cannot verify the disclosed information because it has been altered to prevent the leakage of sensitive information. The confidentiality of official information is thus incompatible with the integrity of that information, and this is called the digital document sanitizing problem. Conventional solutions such as content extraction signatures and digitally signed document sanitizing schemes with disclosure condition control can either let the sanitizer assign disclosure conditions or hide the number of sanitized portions. The digitally signed document sanitizing scheme we propose here is based on the aggregate signature derived from bilinear maps and can do both. Moreover, the proposed scheme can sanitize a signed document invisibly, that is, no one can distinguish whether the signed document has been sanitized or not.
This paper describes some representations of a mapping and their simplification. Any mapping from a finite set into another can be represented by a sequence of Boolean functinos if we encode its domain and range to finite binary sequences. The complexity of the representation depends on the encoding. We present a problem of finding an algorithm that derives one of the simplest representations of a given mapping, and solve it in a case where the complexity measure is determined according to the number of literals in disjunctive forms.
Goichiro HANAOKA Yuliang ZHENG Hideki IMAI
In the past few years, we have seen the emergence of a large number of proposals for electronic payments over open networks. Among these proposals is the Secure Electronic Transaction (SET) protocol promoted by MasterCard and VISA which is currently being deployed world-widely. While SET has a number of advantages over other proposals in terms of simplicity and openness, there seems to be a consensus regarding the relative inefficiency of the protocol. This paper proposes a light-weight version of the SET protocol, called "LITESET. " For the same level of security as recommended in the latest version of SET specifications, LITESET yields a 56.2/51.4% reduction in the computational time in message generation/verification and a 79.9% reduction in communication overhead. This has been achieved by the use of a new cryptographic primitive called signcryption. We hope that our proposal can contribute to the practical and engineering side of real-world electronic payments.
JaeGwi CHOI Goichiro HANAOKA KyungHyune RHEE Hideki IMAI
Digital fingerprinting schemes are cryptographic methods deterring buyers from illegally redistributing digital contents. It enables sellers to identify the traitor by providing each buyer with a slight different version. What is important in designing fingerprinting scheme is to make it more practical and efficient. Recently, two oblivious transfer protocol-based schemes to consider practicality were proposed. These are significant in the sense that they are completely specified from a computation point of view and are thus readily implementable. But these schemes cannot offer the security of sellers and buyers. In this paper, we show how to break the existing oblivious transfer-based fingerprinting schemes and then suggest how to make secure fingerprinting schemes against the dishonesty of sellers and buyers. We use oblivious transfer protocol with two-lock cryptosystem to make it practical and secure. All computations are performed efficiently and the security degree is strengthened in our proposal.
Thi Lan Anh PHAN Goichiro HANAOKA Kanta MATSUURA Hideki IMAI
To deal with the problem of secret key exposure, Dodis, Katz, Xu and Yung [6] proposed a key-insulated public key encryption (KIE), which uses the secure helper key to update the secret key more often and helps to minimize the damage overall. We take this idea further in improving the helper key security by introducing an auxiliary helper key besides of the main helper key. The auxiliary helper key is used less than the main helper key and can help the system to reduce the damage even in case of helper key exposure. This paper give two different schemes of KIE with auxiliary helper key. There are trade-offs between public key length and ciphertext size, as well as between encryption algorithms and decryption algorithms in these two schemes. With these trade-offs, it is flexible to choose an efficient one to implement in reality. We also show concrete constructions with chosen-ciphertext security. The formal security proofs for all schemes are given in this paper, based on the CBDH assumption [2] in the random oracle model.
Jose CARRIJO Rafael TONICELLI Hideki IMAI Anderson C.A. NASCIMENTO
We present a very simple probabilistic, passive attack against the protocols HB and HB+. Our attack presents some interesting features: it requires less captured transcripts of protocol executions when compared to previous results; It makes possible to trade the amount of required transcripts for computational complexity; the value of noise used in the protocols HB and HB+ need not be known.
Mira KIM Junji SHIKATA Hirofumi MURATANI Hideki IMAI
In this paper, we deal with c-secure codes in a fingerprinting scheme, which encode user ID to be embedded into the contents. If a pirate copy appears, c-secure codes allow the owner of the contents to trace the source of the illegal redistribution under collusion attacks. However, when dealing in practical applications, most past proposed codes are failed to obtain a good efficiency, i.e. their codeword length are too large to be embedded into digital contents. In this paper, we propose a construction method of c-secure CRT codes based on polynomials over finite fields and it is shown that the codeword length in our construction is shorter than that of Muratani's scheme. We compare the codeword length of our construction and that of Muratani's scheme by numerical experiments and present some theoretical results which supports the results obtained by numerical experiments. As a result, we show that our construction is especially efficient in respect to a large size of any coalition c. Furthermore, we discuss the influence of the random error on the traceability and formally define the Weak IDs in respect to our construction.
Goichiro HANAOKA Junji SHIKATA Yumiko HANAOKA Hideki IMAI
Authentication codes (A-codes, for short) are considered as important building blocks for constructing unconditionally secure authentication schemes. Since in the conventional A-codes, two communicating parties, transmitter and receiver, utilized a common secret key, and such A-codes do not provide non-repudiation. With the aim of enhancing with non-repudiation property, Simmons introduced A2-codes. Later, Johansson formally defined an improved version of A2-codes called, the A3-codes. Unlike A2-codes, A3-codes do not require an arbiter to be fully trusted. In this paper, we clarify the security definition of A3-codes which may be misdefined. We show a concrete attack against an A3-code and conclude that concrete constructions of A3-codes implicitly assumes a trusted arbiter. We also show that there is no significant difference between A2-codes and A3-codes in a practical sense and further argue that it is impossible to construct an "ideal" A3-codes, that is, without any trusted arbiter. Finally, we introduce a novel model of asymmetric A-codes with an arbiter but do not have to be fully trusted, and also show a concrete construction of the asymmetric A-codes for the model. Since our proposed A-code does not require fully trusted arbiters, it is more secure than A2-codes or A3-codes.
Arisa FUJII Go OHTAKE Goichiro HANAOKA Nuttapong ATTRAPADUNG Hajime WATANABE Kazuto OGAWA Hideki IMAI
Broadcasters transmit TV programs and often need to transmit an individual message, e.g. an individual contract, to each user. The programs have to be encrypted in order to protect the copyright and the individual messages have to be encrypted to preserve the privacy of users. For these purposes, broadcasters transmit not only encrypted content but also encrypted personalized messages to individual users. Current broadcasting services employ an inefficient encryption scheme based on a symmetric key. Recently, several broadcast encryption schemes using a public key have been proposed in which the broadcaster encrypts a message for some subset S of users with a public key and any user in S can decrypt the broadcast with his/her private key. However, it is difficult to encrypt a personalized message and transmit it to every user efficiently. In this paper, we propose a broadcast encryption scheme that has a personalized message encryption function. We show that our scheme is efficient in terms of the ciphertext size.
Tatsuyuki MATSUSHITA Hideki IMAI
We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that (i) any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and (ii) both each subscriber's storage and the transmission overhead are independent of n, while (i) the maximum number of revoked ones cannot be changed or (ii) they depend on n in previous schemes, where n is the total number of subscribers. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that (i) the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and (ii) the tracing algorithm runs in O(log n) time, while the previous ones cannot satisfy both of these properties, where k is the maximum number of traitors in a coalition.