Date: 2011/1/14 (Fri) 15F30`17F00

      Place: Collaboration Room #7 (Information Science Building, 5th floor)

      Name: Isamu Teranishi
          NEC Corporation, Internet Systems Research Laboratories.

      Title: Signatures Resilient to Continual Leakage on Memory and Computation

      Abstract: Cryptographic schemes have traditionally been modeled under the assumption that the secret key is hidden completely within a device. However, cryptographic engineering has taught us that devices are not perfect and can leak information about the key, via ''side channels'', such as timing, radiation, or power consumption associated with computations. We propose a signature scheme which is secure even if a large fraction of the secret keys is leaked. The fraction of information that our scheme allows to leak is optimal in the sense that no signature scheme can be secure against more leakage than ours. Moreover, our scheme is secure even when leaked information is related with the randomness used in signing. Known schemes satisfied this property only in the random oracle model, or only when the fraction of leakage was not optimal while our scheme does not require such an assumption or condition. Our scheme also has a key update procedure, by which one can get new key without leakage. Our scheme is secure under SXDH assumption in the standard model.