This paper proposes a new side channel attack to RSA cryptography. Our target is an implementation with a combination of countermeasures. These are an SPA countermeasure by m-ary method and a DPA countermeasure by randomizing exponent techniques. Here, randomizing exponent techniques shows two DPA countermeasures to randomize the secret exponent d. One is an exponent randomizing technique using d'i = d+ riφ(N) to calculate cd'i (mod N), and another is a technique using di,1 = d/ri and di,2 =(d (mod ri)) to calculate (cdi,1)ri cdi,2 (mod N). Using the combination of countermeasures, it was supposed that the implementation is secure against power attack. However, we firstly show the result to successfully attack the implementation of the combination of these countermeasures. We performed the experiment of this search on a PC, and complete d has been successfully revealed less than 10 hours for both attacks.

This paper studies a privacy-preserving decision tree learning protocol (PPDT) for vertically partitioned datasets. In vertically partitioned datasets, a single class (target) attribute is shared by both parities or carefully treated by either party in existing studies. The proposed scheme allows both parties to have independent class attributes in a secure way and to combine multiple class attributes in arbitrary boolean function, which gives parties some flexibility in data-mining. Our proposed PPDT protocol reduces the CPU-intensive computation of logarithms by approximating with a piecewise linear function defined by light-weight fundamental operations of addition and constant multiplication so that information gain for attributes can be evaluated in a secure function evaluation scheme. Using the UCI Machine Learning dataset and a synthesized dataset, the proposed protocol is evaluated in terms of its accuracy and the sizes of trees*.

Compact design is very important for embedded systems such as wireless sensor nodes, RFID tags and mobile devices because of their limited hardware (H/W) resources. This paper proposes a compact H/W implementation for the KASUMI block cipher, which is the 3GPP standard encryption algorithm. In [8] and [9], Yamamoto et al. proposed a method of reducing the register size for the MISTY1 FO function (YYI-08), and implemented very compact MISTY1 H/W. In this paper we aim to implement the smallest KASUMI H/W to date by applying a YYI-08 configuration to KASUMI, whose FO function has a similar structure to that of MISTY1. However, we discovered that straightforward application of YYI-08 raises problems. We therefore propose a new YYI-08 configuration improved for KASUMI and the compact H/W architecture. The new YYI-08 configuration consists of new FL function calculation schemes and a suitable calculation order. According to our logic synthesis on a 0.11-µm ASIC process, the gate size is 2.99 K gates, which, to our knowledge, is the smallest to date.

This paper studies two types of documents in which an adversary can forge a signature on a chosen document. One type is that a nonce is padded on an input document. The time-stamp protocol is a good example of this type. Another is a structured document (such as PS or PDF) whose contents are described in a body part and information (such as generated time and a generator) are in a meta part. In fact, this paper shows how to forge a time-stamp, a signature on a PDF and an X.509 certificate by the extended forgery attack and numerical examples. Forged signature by the original or the extended attacks is only accepted by the clients whose length check of zero-field is loosely implemented. As a result, we found that the latest versions of Adobe's Acrobat and Acrobat Reader accept the forged time-stamp and the forged signature on a PDF document. Target of this attack is RSASSA-PKCS1-v1_5, which does not have provable security. We also show the expanded attack might forge the signature of RSASSA-PSS, which has provable security, when the length check of zero-field is omitted or loosely implemented.

This paper proposes a compact hardware (H/W) implementation for the MISTY1 block cipher, which is one of the ISO/IEC 18033-3 standard encryption algorithms. In designing the compact H/W, we focused on optimizing the implementation of FO/FI/FL functions, which are the main components of MISTY1. For this optimization, we propose three new methods; reducing temporary registers for the FO function, shortening the critical path for the FI function, and merging the FL/FL-1 functions. According to our logic synthesis on a 0.18-µm CMOS standard cell library based on our proposed methods, the gate size is 3.4 Kgates, which is the smallest as far as we know.

For a variant of RSA with modulus N=prq and ed ≡ 1 (mod(p-1)(q-1)), we show that d is to be recovered if d < N(2-)/(r+1). (Note that φ(N) (p-1)(q-1).) Boneh-Durfee's result for the standard RSA is obtained as a special case for r=1. Technically, we develop a method for finding a small root of a trivariate polynomial equation f(x, y,z)=x(y-1)(z-1)+1 ≡ 0 (mod e) under the condition that yrz=N. Our result cannot be obtained from the generic method of Jochemsz-May.

PPDP (Privacy-Preserving Data Publishing) is technology that discloses personal information while protecting individual privacy. k-anonymity is a privacy model that should be achieved in PPDP. However, k-anonymity does not guarantee privacy against adversaries who have knowledge of even a few uncommon individuals in a population. In this paper, we propose a new model, called k-presence-secrecy, that prevents such adversaries from inferring whether an arbitrary individual is included in a personal data table. We also propose an algorithm that satisfies the model. k-presence-secrecy is a practical model because an algorithm that satisfies it requires only a PPDP target table as personal information, whereas previous models require a PPDP target table and almost all the background knowledge of adversaries. Our experiments show that, whereas an algorithm satisfying only k-anonymity cannot protect privacy, even against adversaries who have knowledge for one uncommon individual in a population, our algorithm can do so with less information loss and shorter execution time.