||Masaya Yasuda, Junpei Yamaguchi, Michiko Ooka, Satoshi Nakamura, Development of a dual version of DeepBKZ and its application to solving the LWE challenge, 10th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2018
Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Proceedings, 10.1007/978-3-319-89339-6_10, 162-182, 2018.01, Lattice basis reduction is a strong tool in cryptanalysis. In 2017, DeepBKZ was proposed as a new variant of BKZ, and it calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. In this paper, we develop a dual version of DeepBKZ (which we call “Dual-DeepBKZ”), to reduce the dual basis of an input basis. For Dual-DeepBKZ, we develop a dual version of DeepLLL, and then combine it with the dual enumeration by Micciancio and Walter. It never computes the dual basis of an input basis, and it is as efficient as the primal DeepBKZ. We also demonstrate that Dual-DeepBKZ solves several instances in the TU Darmstadt LWE challenge. We use Dual-DeepBKZ in the bounded distance decoding (BDD) approach for solving an LWE instance. Our experiments show that Dual-DeepBKZ reduces the cost of Liu-Nguyen’s BDD enumeration more effectively than BKZ. For the LWE instance of (n, α) = (40, 0.015) (resp., (n, α) = (60, 0.005)), our results are about 2.2 times (resp., 4.0 times) faster than Xu et al.’s results, for which they used BKZ in the fplll library and the BDD enumeration with extreme pruning while we used linear pruning in our experiments..
||Junpei Yamaguchi, Masaya Yasuda, Explicit formula for gram-schmidt vectors in LLL with deep insertions and its applications, 1st International Conference on Number-Theoretic Methods in Cryptology, NuTMiC 2017
Number-Theoretic Methods in Cryptology - 1st International Conference, NuTMiC 2017, Revised Selected Papers, 10.1007/978-3-319-76620-1_9, 142-160, 2018.01, Lattice basis reduction algorithms have been used as a strong tool for cryptanalysis. The most famous one is LLL, and its typical improvements are BKZ and LLL with deep insertions (DeepLLL). In LLL and DeepLLL, at every time to replace a lattice basis, we need to recompute the Gram-Schmidt orthogonalization (GSO) for the new basis. Compared with LLL, the form of the new GSO vectors is complicated in DeepLLL, and no formula has been known. In this paper, we give an explicit formula for GSO in DeepLLL, and also propose an efficient method to update GSO in DeepLLL. As another work, we embed DeepLLL into BKZ as a subroutine instead of LLL, which we call “DeepBKZ”, in order to find a more reduced basis. By using our DeepBKZ with blocksizes up to β = 50, we have found a number of new solutions for the Darmstadt SVP challenge in dimensions from 102 to 123..
||Masaya Yasuda, Secure Hamming distance computation for biometrics using ideal-lattice and ring-LWE homomorphic encryption, Information Security Journal, 10.1080/19393555.2017.1293199, 26, 2, 85-103, 2017.03, With widespread development of biometrics, concerns about security and privacy are rapidly increasing. Homomorphic encryption enables us to operate on encrypted data without decryption, and it can be applied to construct a privacy-preserving biometric system. In this article, we apply two homomorphic encryption schemes based on ideal-lattice and ring-LWE (Learning with Errors), which both have homomorphic correctness over the ring of integers of a cyclotomic field. We compare the two schemes in applying them to privacy-preserving biometrics. In biometrics, the Hamming distance is used as a metric to compare two biometric feature vectors for authentication. We propose an efficient method for secure Hamming distance. Our method can pack a biometric feature vector into a single ciphertext, and it enables efficient computation of secure Hamming distance over our packed ciphertexts..
||Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu, Computational hardness of IFP and ECDLP, Applicable Algebra in Engineering, Communications and Computing, 10.1007/s00200-016-0291-x, 27, 6, 493-521, 2016.12, The RSA cryptosystem and elliptic curve cryptography (ECC) have been used practically and widely in public key cryptography. The security of RSA and ECC respectively relies on the computational hardness of the integer factorization problem (IFP) and the elliptic curve discrete logarithm problem (ECDLP). In this paper, we give an estimate of computing power required to solve each problem by state-of-the-art of theory and experiments. By comparing computing power required to solve the IFP and the ECDLP, we also estimate bit sizes of the two problems that can provide the same security level..
||Masaya Yasuda, Torsion points and reduction of elliptic curves, Acta Arithmetica, 2016.09, Let $E$ be an elliptic curve over a number field $K$. Given a prime $p$, the $K$-rational $p$-torsion points of $E$ are the points of exact order $p$ in the Mordell-Weil group $E(K)$. In this paper, we study relation between torsion points and reduction of elliptic curves. Specifically, we give a condition of the pair $(K, p)$ for which there do not exist $K$-rational $p$-torsion points of any elliptic curve over $K$ with bad reduction only at certain primes..
||Masaya Yasuda, Takeshi Shimoyama, Narishige Abe, Shigefumi Yamada, Takashi Shinzaki, Takeshi Koshiba, Privacy-preserving fuzzy commitment for biometrics via layered error-correcting codes, 8th International Symposium on Foundations and Practice of Security, FPS 2015
Foundations and Practice of Security - 8th International Symposium, FPS 2015, Revised Selected Papers, 10.1007/978-3-319-30303-1_8, 9482, 117-133, 2016.01, With the widespread development of biometrics, concerns about security and privacy are increasing. In biometrics, template protection technology aims to protect the confidentiality of biometric templates (i.e., enrolled biometric data) by certain conversion. The fuzzy commitment scheme gives a practical way to protect biometric templates using a conventional error-correcting code. The scheme has both concealing and binding of templates, but it has some privacy problems. Specifically, in case of successful matching, stored biometric templates can be revealed. To address such problems, we improve the scheme. Our improvement is to coat with two error-correcting codes. In particular, our scheme can conceal stored biometric templates even in successful matching. Our improved scheme requires just conventional error-correcting codes as in the original scheme, and hence it gives a practical solution for both template security and privacy of biometric templates..
||Masaya Yasuda, Torsion points and reduction of elliptic curves, Acta Arithmetica, 10.4064/aa8425-6-2016, 176, 1, 89-100, 2016.01.
||Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Secure statistical analysis using RLWE-based homomorphic encryption, ACISP 2015, 10.1007/978-3-319-19962-7-27, 471-487, 2015.07, Homomorphic encryption enables various calculations while preserving the data confidentiality. Here we apply the homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011) to secure statistical analysis between two variables. For reduction of ciphertext size and practical performance, we propose a method to pack multiple integers into a few ciphertexts so that it enables efficient computation over the packed ciphertexts. Our packing method is based on Yasuda et al.’s one (DPM 2013). While their method gives efficient secure computation only for small integers, our modification is effective for larger integers. Our implementation shows that our method is faster than the state-of-the-art work. Specifically, for one million integers of 16 bits (resp. 128 bits), it takes about 20 minutes (resp. 3.6 hours) for secure covariance and correlation on an Intel Core i7-3770 3.40 GHz
||Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, New packing method in somewhat homomorphic encryption and its applications, Security and Communication Networks, 2015.01.
||Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Secure pattern matching using somewhat homomorphic encryption, Proceedings of the 2013 ACM workshop on Cloud computing security workshop (ACM CCSW 2013), 65-76, 2013.11.