International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Yasuhiko Ikematsu

Publications

Year
Venue
Title
2022
TCHES
Side-Channel Masking with Common Shares
To counter side-channel attacks, a masking scheme randomly encodes key-dependent variables into several {\it shares}, and transforms operations into the masked correspondence (called {\it gadget}) operating on shares. This provably achieves the de facto standard notion of {\it probing security}. We continue the long line of works seeking to reduce the overhead of masking. Our main contribution is a new masking scheme over finite fields in which shares of different variables have a part in common. This enables the reuse of randomness / variables across different gadgets, and reduces the total cost of masked implementation. For security order $d$ and circuit size $\ell$, the randomness requirement and computational complexity of our scheme are $\tilde{O}(d^2)$ and $\tilde{O}(\ell d^2)$ respectively, strictly improving upon the state-of-the-art $\tilde{O}(d^2)$ and $\tilde{O}(\ell d^3)$ of Coron et al. at Eurocrypt 2020. A notable feature of our scheme is that it enables a new paradigm in which many intermediates can be precomputed before executing the masked function. The precomputation consumes $\tilde{O}(\ell d^2)$ and produces $\tilde{O}(\ell d)$ variables to be stored in RAM. The cost of subsequent (online) computation is reduced to $\tilde{O}(\ell d)$, effectively speeding up e.g., challenge-response authentication protocols. We showcase our method on the AES on ARM Cortex M architecture. Our results show a speed-up during the online phase compared with state-of-the-art implementations, at the cost of acceptable RAM consumption and precomputation time. To prove security for our scheme, we propose a new security notion intrinsically supporting randomness / variables reusing across gadgets, and bridging the security of {\it parallel} compositions of gadgets to {\it general} compositions, which may be of independent interest.
2021
ASIACRYPT
A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV 📺
The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key; thus, various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with a public key represented by block matrices whose components correspond to an element of a quotient ring. We discuss how it affects the security of our proposed scheme whether or not the quotient ring is a field. Furthermore, we discuss their security against currently known and newly possible attacks and propose parameters for our scheme. We demonstrate that our proposed scheme can achieve a small public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 85.8 KB for NIST's Post-Quantum Cryptography Project (security level 3), whereas that of compressed Rainbow is 252.3 KB, where Rainbow is a variant of UOV and is one of the third-round finalists of the NIST PQC project.