9th event on March 9th 2020

The next Tokyo Crypto Day will be held on March 9th (Mon) at the University of Tokyo.

Canceled

Due to the COVID19 issue, this event was canceled.

Place: room #63 in Bldg. #6, Faculty of Engineering, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656

Program

  1. 10:30 - 11:30 Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions (Junichi Tomida)
  2. 13:00 - 14:00 New Approaches for CCA-Secure Encryption (Venkata Koppula)
  3. 14:15 - 15:15 Cryptography from Information Loss (Prashant Nalini Vasudevan)
  4. 15:30 - 16:30 Uprooting the FALCON tree? How to recover secret keys from Gram-Schmidt norm (Alexandre Wallet)

This event is held with the help of Atsushi Takayasu

Abstracts

Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

Junichi Tomida (NTT Secure Platform Laboratories)

Abstract: At Eurocrypt'19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner (including those that resolved some open problems at the time). However, his approach heavily relies on so-called $q$-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem. In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung. Our framework significantly expands an area of ABEs that are realizable from standard assumptions. This includes the following adaptively secure large-universe ABEs for Boolean formulae under MDDH.

New Approaches for CCA-Secure Encryption

Venkata Koppula (Weizmann Insititute of Science)

Abstract: In this talk, I will present a generic and black box transformation from any encryption scheme secure against chosen plaintext attacks (CPA) to a chosen ciphertext attack (CCA) secure system. Furthermore, this transformation also works for advanced encryption schemes such as broadcast encryption, attribute based encryption, one-sided predicate encryption etc. Our transformation requires only the IND-CPA security of the original scheme coupled with a pseudorandom generator (PRG) with a special security property, which we call ‘hinting property’.

Given a PRG that maps n bits to n strings, consider the following distribution: choose a random seed s, compute PRG(s) = (z1, …, zn). Choose random strings (y1, …, yn). For each index i, if the ith bit of s is 1, output (yi, zi), else output (zi, yi). A PRG is a ‘hinting PRG’ if the output of this distribution is indistinguishable from n pairs of random strings.

We show constructions for hinting PRGs based on standard assumptions such as Learning with Errors (LWE) and Computational Diffie Hellman (CDH).

Cryptography from Information Loss

Prashant Nalini Vasudevan (UC Berkeley)

Abstract: Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is “lossy” reductions, where the reduction loses some information about the input instance. Such reductions are closely related to prevalent concepts in various areas of computer science, such as parametrized complexity and cryptography. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into “useful” hardness, namely cryptography.

We show various sufficient conditions in terms of such reductions that, together with worst-case or average-case hardness of the underlying language, imply one-way functions and collision-resistant hash functions.

Joint work with Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, and Vinod Vaikuntanathan.

Uprooting the FALCON tree? How to recover secret keys from Gram-Schmidt norm

Alexandre Wallet (NTT SC Labs)

Abstract: The so-called GPV framework allows for theoretically secure “Hash-and-sign”-style signatures schemes over lattices. Moreover, efficient instantiations using NTRU lattices are known, showcased by the NIST round 2 candidate Falcon as well as its IBE ancestor (Ducas, Lyubashevsky and Prest, ASIACRYPT 2014). As opposed to the series of concrete results on the “Fiat-Shamir with aborts” lattice signature paradigm, no particular side-channel leakage were identified before for GPV-style schemes.

Our work is the first step in this direction. First, we identify a specific source of side-channel leakage in most implementations of those schemes, namely, the one-dimensional Gaussian sampling steps within lattice Gaussian sampling. It turns out that the implementations of these steps often leak the Gram–Schmidt norms of the secret lattice basis. Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram–Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field. Third, we concretely demonstrate the side-channel attack against DLP (but not Falcon due to the different structures of the two schemes).

The challenge is that timing information only provides an approximation of the Gram–Schmidt norms, so our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximate values. Experimentally, we show that around 2^35 DLP traces are enough to reconstruct the entire key with good probability.