Program
- A Unified Approach to Constructing Black-box UC Protocols in Trusted Setup Models (Susumu Kiyoshima)
- Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques (Shota Yamada)
- Side-Channel Attacks on BLISS Lattice-Based Signatures (Mehdi Tibouchi)
- Secure AES computation comparable to local AES computation (Ryo Kikuchi)
Abstracts
A Unified Approach to Constructing Black-box UC Protocols in Trusted Setup Models
Susumu Kiyoshima (NTT Secure Platform Laboratories)
We present a unified framework for obtaining black-box constructions of Universal Composable (UC) protocol in trusted setup models. Our result is analogous to the unified framework of Lin, Pass, and Venkitasubramaniam [STOC'09, Asiacrypt'12] that, however, only yields non-black-box constructions of UC protocols. Our unified framework shows that to obtain black-box constructions of UC protocols, it suffices to implement a special purpose commitment scheme that is, in particular, concurrently extractable using a given trusted setup. Using our framework, we improve black-box constructions in the common reference string and tamper-proof hardware token models by weakening the underlying computational and setup assumptions.
Joint work with Huijia Lin (UCSB) and Muthuramakrishnan Venkitasubramaniam (University of Rochester).
Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques
Shota Yamada (AIST)
In this talk, we focus on the constructions of adaptively secure identity-based encryption (IBE) from lattices and verifiable random function (VRF) with large input spaces. Existing constructions of these primitives suffer from low efficiency, whereas their counterparts with weaker guarantees (IBEs with selective security and VRFs with small input spaces) are reasonably efficient. We try to fill these gaps by developing new partitioning techniques that can be performed with compact parameters and proposing new schemes based on the idea.
We propose new lattice IBEs with poly-logarithmic master public key sizes, where we count the number of the basic matrices to measure the size. Our constructions are proven secure under the LWE assumption with polynomial approximation factors. They achieve the best asymptotic space efficiency among existing schemes that depend on the same assumption and achieve the same level of security.
We also propose several new VRFs on bilinear groups. In our first scheme, the size of the proofs is poly-logarithmic in the security parameter, which is the smallest among all the existing schemes with similar properties. On the other hand, the verification keys are long. In our second scheme, the size of the verification keys is poly-logarithmic, which is the smallest among all the existing schemes. The size of the proofs is sub-linear, which is larger than our first scheme, but still smaller than all the previous schemes.
Side-Channel Attacks on BLISS Lattice-Based Signatures
Mehdi Tibouchi (NTT Secure Platform Laboratores)
In this talk, we discuss recent results on the security of the BLISS lattice-based signature scheme, one of the most promising candidates for postquantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to microcontrollers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more traditional side-channel analysis, and describe several attacks that can yield a full key recovery.
We first identify a serious source of leakage in the rejection sampling algorithm used during signature generation. Existing implementations of that rejection sampling step, which is essential for security, actually leak the ``relative norm’’ of the secret key. We show how an extension of an algorithm due to Howgrave-Graham and Szydlo can be used to recover the key from that relative norm, at least when the absolute norm is easy to factor. We describe how this leakage can be exploited in practice both on an embedded device using e.g. power analysis, and on a desktop computer using a technique called branch tracing.
We also show that other parts of the BLISS signing algorithm can leak secrets. This includes the Gaussian sampling step used to obtain the randomness used in signatures, as well as the sparse polynomial multiplications carried out in BLISS. Overall, although we suggest possible countermeasures, protecting BLISS against side-channels appears to be a hard problem.
Joint work with Thomas Espitau, Pierre-Alain Fouque, and Benoit Gerard
Secure AES computation comparable to local AES computation
Ryo Kikuchi (NTT Secure Platform Laboratores)
Secure computation is a technique that enables parties with inputs to evaluate a function on the inputs while keeping them secret. Despite the advantage of secure computation, it has not been common due to its inefficiency; the performance is far from that of local computations. Therefore, the main challenge is to obtain better performance in secure computation. In general, obtaining the best performance for a function requires an optimization of an algorithm through deep understanding of the function itself and an architecture in which the computation is conducted. The same thing holds in secure computation; optimizations of a protocol and an algorithm through the understanding of both the function and the architecture can lead to great improvements.
We demonstrates the effect of this general approach and shows how fast secure computation can be by actually improving the performance through new protocols, algorithm optimization, and implementation techniques with regards to secure Advanced Encryption Standard (AES) computation. Secure AES computation is a quite appropriate example to be optimized since it has been widely investigated as a de facto standard performance benchmark on secure computation and it serves as a challenging test case. It is also important by itself as distributing shares of keys to prevent corrupted server from accessing the secret key. Furthermore, parts of the improvements are general and not specific to AES, and can be applied to secure computation of arbitrary functions.
On three 8-core PCs with a 10-Gigabit ring network in the model of passive security with an honest majority, our implementation including the all improvements achieved a throughput of 519 Mbps, which involved 4 million AES blocks per second in counter mode. This throughput is about 350 Mbps more than and three times faster than a throughput of 169 Mbps, which was achieved by Araki \etal in the same model at ACM CCS 2016. In addition, this throughput is comparable to those of local AES computation. The throughput of 519 Mbps is more than twice the throughput as a benchmark implementation of AES at the time of the AES competition. This indicates that, at least in the area of AES, highly optimized secure computation can be sufficiently practical and perform better than certain local computations used in the real world. Furthermore, the latency of our implementation is 1.7 ms, which is nearly optimal according to the number of rounds and network latency.
Joint work with Dai Ikarashi, Koki Hamada, and Koji Chida