Kyushu University Academic Staff Educational and Research Activities Database
List of Papers
Masaya Yasuda Last modified date:2019.06.13

Associate Professor / Laboratory of Mathematical Design for Advanced Cryptography / Institute of Mathematics for Industry


Papers
1. Masaya Yasuda, Self-dual DeepBKZ for finding short lattice vectors, to appear in a MathCrypt special issue of Journal of Mathematical Cryptology, 2019.06.
2. Huy Quoc Le, Pradeep Kumar Mishra, Dung Hoang Duong, Masaya Yasuda, Solving LWR via BDD strategy
Modulus switching approach, 17th International Conference on Cryptology and Network Security, CANS 2018 Cryptology and Network Security - 17th International Conference, CANS 2018, Proceedings, 10.1007/978-3-030-00434-7_18, 357-376, 2018.01, The typical approach in attacking an LWR
m,n,q,p(χs)
instance parameterized by four integers m, n, q, p (Formula Presented) and a probability distribution χs is just by simply regarding it as a Learning with Errors (LWE) modulo q instance and then trying to adapt known LWE attacks to this LWE instance. In this paper, we show that for an LWR
m,n,q,p(χs)
instance whose parameters satisfy a certain sufficient condition, one can use the BDD strategy to recover the secret with higher advantages if one transforms the LWR instance to an LWE modulo (Formula Presented) instance with (Formula Presented) chosen appropriately instead of an LWE modulo q instance. The optimal modulus q used in our BDD attack is quite close to p as well as typically smaller than q. Especially, our experiments confirm that our BDD attack is much better in solving search-LWR in terms of root Hermite factor, success probability and even running time either in case the ratio log (q)/log (p) is big or/and the dimension n is sufficiently large..
3. Momonari Kudo, Yuki Yokota, Yasushi Takahashi, Masaya Yasuda, Acceleration of index calculus for solving ECDLP over prime fields and its limitation, 17th International Conference on Cryptology and Network Security, CANS 2018 Cryptology and Network Security - 17th International Conference, CANS 2018, Proceedings, 10.1007/978-3-030-00434-7_19, 377-393, 2018.01, In 2018, Amadori et al. proposed a new variant of index calculus to solve the elliptic curve discrete logarithm problem (ECDLP), using Semaev’s summation polynomials. The variant drastically decreases the number of required Gröbner basis computations, and it outperforms other index calculus algorithms for the ECDLP over prime fields. In this paper, we provide several improvements to accelerate to solve systems of multivariate equations arising in the variant. A main improvement is to apply the hybrid method, which mixes exhaustive search and Gröbner bases techniques to solve multivariate systems over finite fields. We also make use of symmetries of summation polynomials. We show experimental results of our improvements, and give their complexity analysis to discuss a limitation of our acceleration in both theory and practice..
4. Deevashwer Rathee, Pradeep Kumar Mishra, Masaya Yasuda, Faster PCA and linear regression through hypercubes in HElib, 17th ACM Workshop on Privacy in the Electronic Society, WPES 2018, held in conjunction with the 25th ACM Conference on Computer and Communications Security, CCS 2018 WPES 2018 - Proceedings of the 2018 Workshop on Privacy in the Electronic Society, co-located with CCS 2018, 10.1145/3267323.3268952, 42-53, 2018.10, The significant advancements in the field of homomorphic encryption have led to a grown interest in securely outsourcing data and computation for privacy critical applications. In this paper, we focus on the problem of performing secure predictive analysis, such as principal component analysis (PCA) and linear regression, through exact arithmetic over encrypted data. We improve the plaintext structure of Lu et al.'s protocols (from NDSS 2017), by switching over from linear array arrangement to a two-dimensional hypercube. This enables us to utilize the SIMD (Single Instruction Multiple Data) operations to a larger extent, which results in improving the space and time complexity by a factor of matrix dimension. We implement both Lu et al.'s method and ours for PCA and linear regression over HElib, a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme. In particular, we show how to choose optimal parameters of the BGV scheme for both methods. For example, our experiments show that our method takes 45 seconds to train a linear regression model over a dataset with 32k records and 6 numerical attributes, while Lu et al.'s method takes 206 seconds..
5. Masaya Yasuda, Junpei Yamaguchi, A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths, Designs, Codes, and Cryptography, 10.1007/s10623-019-00634-9, 2019.01, Lattice basis reduction algorithms have been used in cryptanalysis. The most famous algorithm is LLL, proposed by Lenstra, Lenstra, Lovász, and one of its typical improvements is LLL with deep insertions (DeepLLL). A DeepLLL-reduced basis is LLL-reduced, and hence its quality is at least as good as LLL. In practice, DeepLLL often outputs a more reduced basis than LLL, but no theoretical result is known. First, we show provable output quality of DeepLLL, strictly better than that of LLL. Second, as a main work of this paper, we propose a new variant of DeepLLL. The squared-sum of Gram–Schmidt lengths of a basis is related with the computational hardness of lattice problems such as the shortest vector problem (SVP). Given an input basis, our variant monotonically decreases the squared-sum by a given factor at every deep insertion. This guarantees that our variant runs in polynomial-time..
6. Shinya Okumura, Shingo Sugiyama, Masaya Yasuda, Tsuyoshi Takagi, Security analysis of cryptosystems using short generators over ideal lattices, Japan Journal of Industrial and Applied Mathematics, 10.1007/s13160-018-0306-z, 1-33, 2018.05, In this paper, we analyze the security of cryptosystems using short generators over ideal lattices. Our approach is based on a recent work by Cramer et al. on analysis of the recovering short generators problem on q-th cyclotomic fields with prime powers q. In their analysis, implicit lower bounds of the special values of Dirichlet L-functions at 1 are essentially used for estimating some sizes of the dual bases of the log-unit lattices of the q-th cyclotomic fields. Our contribution is to improve Cramer et al.’s analysis by giving explicit lower and upper bounds of the special values of Dirichlet L-functions at 1. Our improvement allows one to analyze the RSG attack not only asymptotically but also explicitly for fixed practical parameters. Moreover, we give experimental evidence that recovering short generators over (Formula presented.)-th cyclotomic fields for (Formula presented.) is succeeded with high probability..
7. 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..
8. 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..
9. Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba, Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors, Journal of Mathematical Cryptology, 10.1515/jmc-2016-0008, 11, 1, 1-24, 2017.03, In 2015, Fukase and Kashiwabara proposed an efficient method to find a very short lattice vector. Their method has been applied to solve Darmstadt shortest vector problems of dimensions 134 to 150. Their method is based on Schnorr's random sampling, but their preprocessing is different from others. It aims to decrease the sum of the squared lengths of the Gram-Schmidt vectors of a lattice basis, before executing random sampling of short lattice vectors. The effect is substantiated from their statistical analysis, and it implies that the smaller the sum becomes, the shorter sampled vectors can be. However, no guarantee is known to strictly decrease the sum. In this paper, we study Fukase-Kashiwabara's method in both theory and practice, and give a heuristic but practical condition that the sum is strictly decreased. We believe that our condition would enable one to monotonically decrease the sum and to find a very short lattice vector in fewer steps..
10. 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..
11. Dung Hoang Duong, Masaya Yasuda, Tsuyoshi Takagi, Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU, 20th International Conference on Information Security, ISC 2017 Information Security - 20th International Conference, ISC 2017, Proceedings, 10.1007/978-3-319-69659-1_5, 10599 LNCS, 79-91, 2017.01, Albrecht et al. [1] at Crypto 2016 and Cheon et al. [4] at ANTS 2016 independently presented a subfield attack on overstretched NTRU problem. Their idea is to map the public key down to the subfield (by norm and trace map respectively) and hence obtain a lattice of smaller dimension for which a lattice reduction algorithm is efficiently applicable. At Eurocrypt 2017, Kirchner and Fouque proposed another variant attack which exploits the presence of orthogonal bases within the cyclotomic number rings and instead of using the matrix of the public key in the subfield, they use the multiplication matrix by the public key in the full field and apply a lattice reduction algorithm to a suitable projected lattice of smaller dimension. They also showed a tight estimation of the parameters broken by lattice reduction and implementation results that their attack is better than the subfield attack. In this paper, we exploit technical results from Kirchner and Fouque [12] for the relative norm of field elements in the subfield and we use Hermite factor for estimating the output of a lattice basis reduction algorithm in order to analyze general choice of parameters for the subfield attack by Albrecht et al. [1]. As a result, we obtain the estimation for better choices of the subfields for which the attack works with smaller modulus. Our experiment results show that we can attack overstretched NTRU with modulus smaller than that of Albrecht et al. and of Kirchner and Fouque..
12. Pradeep Kumar Mishra, Dung Hoang Duong, Masaya Yasuda, Enhancement for secure multiple matrix multiplications over ring-LWE homomorphic encryption, 13th International Conference on Information Security Practice and Experience, ISPEC 2017 Information Security Practice and Experience - 13th International Conference, ISPEC 2017, Proceedings, 10.1007/978-3-319-72359-4_18, 320-330, 2017.01, Homomorphic encryption allows to perform various calculations on encrypted data without decryption. In this paper, we propose an efficient method for secure multiple matrix multiplications over the somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan. Our method is a generalization of Duong et al.’s method, which computes only one multiplication between two matrices. In order to minimize both the ciphertext size and the computation cost, our method packs every matrix into a single ciphertext so that it enables efficient matrix multiplications over the packed ciphertexts. We also propose several modifications to obtain practical performance of secure multiplications among matrices with larger size and entries. We show implementation results of our packing method with modifications for secure multiplications among two and three matrices with 32 × 32 and 64 × 64 sizes and entries from 16-bit to 64-bit..
13. Masaya Yasuda, Takeshi Shimoyama, Masahiko Takenaka, Narishige Abe, Shigefumi Yamada, Junpei Yamaguchi, Recovering attacks against linear sketch in fuzzy signature schemes of ACNS 2015 and 2016, 13th International Conference on Information Security Practice and Experience, ISPEC 2017 Information Security Practice and Experience - 13th International Conference, ISPEC 2017, Proceedings, 10.1007/978-3-319-72359-4_24, 10701 LNCS, 409-421, 2017.01, In biometrics, template protection aims to protect the confidentiality of templates (i.e., enrolled biometric data) by certain conversion. At ACNS 2015, as a new approach of template protection, Takahashi et al. proposed a new concept of digital signature, called “fuzzy signature”, that uses biometric data as a private key for securely generating a signature. After that, at ACNS 2016, Matsuda et al. modified the original scheme with several relaxing requirements. A main ingredient of fuzzy signature is “linear sketch”, which incorporates a kind of linear encoding and error correction process to securely output only the difference of signing keys without revealing any biometric data. In this paper, we give recovering attacks against the linear sketch schemes proposed at ACNS 2015 and 2016. Specifically, given encoded data by linear sketch (called a “sketch”), our attacks can directly recover both the signing key and the biometric data embedded in the sketch. Our attacks make use of the special structure that a sketch has the form of a sum of an integral part and a decimal part, and biometric data is embedded in the decimal part. On the other hand, we give a simple countermeasure against our attacks and discuss the effect in both theory and practice..
14. Yutaro Kiyomura, Akiko Inoue, Yuto Kawahara, Masaya Yasuda, Tsuyoshi Takagi, Tetsutaro Kobayashi, Secure and efficient pairing at 256-Bit security level, 15th International Conference on Applied Cryptography and Network Security, ACNS 2017 Applied Cryptography and Network Security - 15th International Conference, ACNS 2017, Proceedings, 10.1007/978-3-319-61204-1_4, 10355 LNCS, 59-79, 2017.01, At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve (NFS) algorithm for the discrete logarithm problem (DLP) in a finite field. The security of pairing-based cryptography (PBC) is based on the difficulty in solving the DLP. Hence, it has become necessary to revise the bitlength that the DLP is computationally infeasible against the efficient NFS algorithms. The timing of the main operations of PBC (i.e. pairing, scalar multiplication on the elliptic curves, and exponentiation on the finite field) generally becomes slower as the bitlength becomes longer, so it has become increasingly important to compute the main operations of PBC more efficiently. To choose a suitable pairing-friendly curve from among various pairing-friendly curves is one of the factors that affect the efficiency of computing the main operations of PBC. We should implement the main operations of PBC and compare the timing among some pairing-friendly curves in order to choose the suitable pairing-friendly curve precisely. In this paper, we focus on the five candidate pairing-friendly curves from the Barreto- Lynn-Scott (BLS) and Kachisa-Schaefer-Scott (KSS) families as the 256- bit secure pairing-friendly curves and show the following two results; (1) the revised bitlength that the DLP is computationally infeasible against the efficient NFS algorithms for each candidate pairing-friendly curve, (2) the suitable pairing-friendly curve by comparing the timing of the main operations of PBC among the candidate pairing-friendly curves using the revised bitlength..
15. Keiji Kimura, Hayato Waki, Masaya Yasuda, Application of mixed integer quadratic program to shortest vector problems, JSIAM Letters, 2017.
16. Masaya Yasuda, Applications of fully homomorphic encryption, Journal of the Institute of Electronics, Information and Communication Engineers, 99, 12, 1167-1175, 2016.12.
17. 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..
18. 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..
19. Dung Hoang Duong, Pradeep Kumar Mishra, Masaya Yasuda, Efficient Secure Matrix Multiplication over LWE-Based Homomorphic Encryption, Tatra Mountains Mathematical Publications, 10.1515/tmmp-2016-0031, 67, 1, 69-83, 2016.09, Homomorphic encryption enables various calculations while preserving the data confidentiality. In this paper, we apply the somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011) to secure matrix multiplication between two matrices. To reduce both the ciphertext size and the computation cost, we propose a new method to pack a matrix into a single ciphertexts so that it also enables efficient matrix multiplication over the packed ciphertexts. Our packing method generalizes Yasuda et al.'s methods (Security Comm. Networks 2015 and ACISP 2015), which are for secure inner product. We also implement our methods and give a comparison with previous packing methods..
20. Avradip Mandal, Arnab Roy, Masaya Yasuda, Comprehensive and improved secure biometric system using homomorphic encryption, 10th International Workshop on Data Privacy Management, and Security Assurance, DPM 2015 and 4th International Workshop on Quantitative Aspects in Security Assurance, QASA 2015 Data Privacy Management, and Security Assurance - 10th International Workshop, DPM 2015 and 4th International Workshop, QASA 2015, Revised Selected Papers, 10.1007/978-3-319-29883-2_12, 9481, 183-198, 2016.01, With the widespread development of biometric systems, concerns about security and privacy are increasing. An active area of research is template protection technology, which aims to protect registered biometric data. We focus on a homomorphic encryption approach, which enables building a “cryptographically-secure” system. In DPM 2013, Yasuda et al. proposed an efficient template protection system, using the homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan. In this work, we improve and fortify their system to withstand impersonation attacks such as replay and spoofing attacks. We introduce a challenge-response authentication mechanism in their system and design a practical distributed architecture where computation and authentication are segregated. Our comprehensive system would be useful to build a large-scale and secure biometric system such as secure remote authentication over public networks..
21. Momonari Kudo, Junpei Yamaguchi, Yang Guo, Masaya Yasuda, Practical analysis of key recovery attack against search-LWE problem, 11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016 Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings, 10.1007/978-3-319-44524-3_10, 9836 LNCS, 164-181, 2016.01, The security of a number of modern cryptographic schemes relies on the computational hardness of the learning with errors (LWE) problem. In 2015, Laine and Lauter analyzed a key recovery (or decoding) attack against the search variant of LWE. Their analysis is based on a generalization of the Boneh-Venkatesan method for the hidden number problem to LWE. They adopted the LLL algorithm and Babai’s nearest plane method in the attack against LWE, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give an alternative analysis of the key recovery attack.While Laine and Lauter’s analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai’s nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack. Furthermore, our analysis enables one to determine a successful range of the attack with practical lattice reduction such as the BKZ algorithm..
22. 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..
23. Masaya Yasuda, Torsion points and reduction of elliptic curves, Acta Arithmetica, 10.4064/aa8425-6-2016, 176, 1, 89-100, 2016.01.
24. Masaya Yasuda, Yuka Sugimura, Biometric key-binding using lattice masking, Security and Communication Networks, 10.1002/sec.1267, 8, 18, 3405-3414, 2015.12, In biometrics, template protection technology aims to protect the confidentiality of a biometric template (i.e., enrolled biometric information) by certain conversion. Here, we focus on the key-binding approach for template protection. This approach generates a secure template from joint data of a user's specific key with a user's template, and the key can be correctly extracted from the secure template only when a queried biometric feature is close to the plain template. While almost all conventional schemes use the error correcting code technique, we present a new technique based on lattices to give a new key-binding scheme. Our proposed scheme can provide several requirements (e.g., diversity and revocability) for template protection, which cannot be provided by error correcting code based typical schemes such as the fuzzy commitment and the fuzzy vault..
25. Masaya Yasuda, Ramification of the Kummer extension generated from torsion points of elliptic curves, International Journal of Number Theory, 10.1142/S1793042115500736, 11, 6, 1725-1734, 2015.09, For a prime p, let p denote a fixed primitive pth root of unity. Let E be an elliptic curve over a number field k with a p-torsion point. Then the p-torsion subgroup of E gives a Kummer extension over k(p). In this paper, for p = 5 and 7, we study the ramification of such Kummer extensions using explicit Kummer generators directly computed by Verdure in 2006..
26. 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
CPU..
27. Masaya Yasuda, Takeshi Koshiba, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Secure data devolution: Practical re-encryption with auxiliary data in LWE-based homomorphic encryption, Proceedings of the 3rd International Workshop on Security in Cloud Computing (SCC@AsiaCCS 2015), ACM , 53-61, 2015.04.
28. Masaya Yasuda, Takeshi Koshiba, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Secure data devolution
Practical re-encryption with auxiliary data in LWE-based somewhat homomorphic encryption, 3rd ACM International Workshop on Security in Cloud Computing, SCC 2015 SCC 2015 - Proceedings of the 3rd ACM International Workshop on Security in Cloud Computing, part of ASIACCS 2015, 10.1145/2732516.2732521, 53-61, 2015.04, Homomorphic encryption can support meaningful operations on encrypted data, and hence it enables users to outsource their data in encrypted format to cloud services. However, homomorphic encryption cannot operate on ciphertexts with different keys in general. To resolve the problem, re-encryption allows operations on such ciphertexts by unifying the different keys into a new one. In this paper, we focus on the scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011), and give a practical re-encryption method. Our strategy for efficient re-encryption is to simply rewrite the decryption circuit and then to evaluate the circuit homomorphically with auxiliary information. In particular, our method requires only a few homomorphic operations for re-encryption, and it can be applied to various applications such as secure key exchange for collaboratively computing multiple users' data in the cloud..
29. 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.
30. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, New packing method in somewhat homomorphic encryption and its applications, Security and Communication Networks, 10.1002/sec.1164, 8, 13, 2194-2213, 2015.01, Somewhat homomorphic encryption is public key encryption supporting a limited number of additions and multiplications on encrypted data. This encryption gives a powerful tool in performing meaningful computations with protecting data confidentiality, whose property is suitable mainly in cloud computing. In this paper, we focus on the scheme proposed by Brakerski and Vaikuntanathan, and present two types of packed ciphertexts in order to improve performance and reduce size of the encrypted data. One type of our packed ciphertexts is based on the message encoding technique proposed by Lauter, Naehrig and Vaikuntanathan. While their technique empowers efficient secure computation of sums and products over the integers, our second type of packed ciphertexts enables efficient secure computation of more complex functionalities such as multiple inner products and multiple Hamming distances. We apply our packing method to construct several protocols for secure biometric authentication and secure pattern matching computations. Our implementation shows that our method gives faster performance than the state-of-the-art work in such applications..
31. Jun Kogure, Takeshi Shimoyama, Masaya Yasuda, Searchable encryption
A technology that enables searches on encrypted data, Journal of the Institute of Electronics, Information and Communication Engineers, 98, 3, 202-206, 2015.01.
32. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Secure statistical analysis using RLWE-based homomorphic encryption, 20th Australasian Conference on Information Security and Privacy, ACISP 2015 Information Security and Privacy - 20th Australasian Conference, ACISP 2015, Proceedings, 10.1007/978-3-319-19962-7_27, 9144, 471-487, 2015.01, 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 CPU..
33. Masaya Yasuda, Ramification of the Kummer extensions generated from torsion points of elliptic curves, International Journal of Number Theory, 1-10, 2014.12.
34. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Secure computation of purchase histry data using somewhat homomorphic encryption , Pacific Journal of Mathematics for Industry, 1-9, 2014.12.
35. Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba, On the exact decryption range for Gentry-Halevi's implementation of fully homomorphic encryption , Journal of Mathematical Cryptology, 8, 3, 305-329, 2014.09.
36. Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba, On the exact decryption range for Gentry-Halevi's implementation of fully homomorphic encryption, Journal of Mathematical Cryptology, 10.1515/jmc-2013-0024, 8, 3, 305-329, 2014.01, In this paper, we revisit the fully homomorphic encryption (FHE) scheme implemented by Gentry and Halevi, which is just an instantiation of Gentry's original scheme based on ideal lattices. Their FHE scheme starts from a somewhat homomorphic encryption (SHE) scheme, and its decryption range is deeply related with the FHE construction. Gentry and Halevi gave an experimental evaluation of the decryption range, but theoretical evaluations have not been given so far. Moreover, we give a theoretical upper bound, and reconsider suitable parameters for theoretically obtaining an FHE scheme. In particular, while Gentry and Halevi use the Euclidean norm evaluation in the noise management of ciphertexts, our theoretical bound enables us to use the ∞-norm evaluation, and hence it helps to lower the difficulty of controlling the noise density of ciphertexts..
37. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Practical packing method in somewhat homomorphic encryption, 8th International Workshop on Data Privacy Management, DPM 2013 and 6th International Workshop on Autonomous and Spontaneous Security, SETOP 2013 Data Privacy Management and Autonomous Spontaneous Security - 8th International Workshop, DPM 2013, and 6th International Workshop, SETOP 2013, Revised Selected Papers, 10.1007/978-3-642-54568-9_3, 8247 LNCS, 34-50, 2014.01, Somewhat homomorphic encryption is public key encryption supporting a limited number of both additions and multiplications on encrypted data, which is useful for performing fundamental computations with protecting the data confidentiality. In this paper, we focus on the scheme proposed by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), and present two types of packed ciphertexts based on their packing technique. Combinations of two types of our packing method give practical size and performance for wider computations such as statistical analysis and distances. To demonstrate its efficiency, we implemented the scheme with our packing method for secure Hamming distance, which is often used in privacy-preserving biometrics. For secure Hamming distance between two binary vekoshiba@mail.saitama-u.ac.jpctors of 2048-bit, it takes 5.31 ms on an Intel Xeon X3480 at 3.07 GHz. This gives the best performance in the state-of-the-art work using homomorphic encryption..
38. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Privacy-preserving wildcards pattern matching using symmetric somewhat homomorphic encryption, 19th Australasian Conference on Information Security and Privacy, ACISP 2014 Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings, 10.1007/978-3-319-08344-5_22, 8544 LNCS, 338-353, 2014.01, The basic pattern matching problem is to find the locations where a pattern occurs in a text. We give several computations enabling a client to obtain matching results from a database so that the database can not learn any information about client's queried pattern. For such computations, we apply the symmetric-key variant scheme of somewhat homomorphic encryption proposed by Brakerski and Vaikuntanathan (CRYPTO 2011), which can support a limited number of both polynomial additions and multiplications on encrypted data. We also utilize the packing method introduced by Yasuda et al. (CCSW 2013) for efficiency. While they deal with only basic problems for binary vectors, we address more complex problems such as the approximate and wildcards pattern matching for non-binary vectors. To demonstrate the efficiency of our method, we implemented the encryption scheme for secure wildcards pattern matching of DNA sequences. Our implementation shows that a client can privately search real-world genomes of length 16,500 in under one second on a general-purpose PC..
39. Yuka Sugimura, Masaya Yasuda, Shigefumi Yamada, Narishige Abe, Takashi Shinzaki, A Biometric Key-binding scheme using lattice masking, 13th International Conference of the Biometrics Special Interest Group, BIOSIG 2014 BIOSIG 2014 - Proceedings of the 13th International Conference of the Biometrics Special Interest Group, P-230, 211-218, 2014, Template protection technology can protect the confidentiality of a biometric template by certain conversion. We focus on the key-binding approach for template protection. This approach generates a secure template (or a conversion template) from joint data of a user's specific key with a user's template, and the key can be correctly extracted from the secure template only when a queried biometric feature is sufficiently close to the original template. While almost all conventional schemes use the error correcting code (ECC) technique, we present a new technique based on lattices to give a new key-binding scheme. Our proposed scheme can provide several requirements (e.g., diversity and revocability) for template protection, which cannot be provided by ECC-based schemes such as the fuzzy commitment and the fuzzy vault..
40. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Packed homomorphic encryption based on ideal lattices and its application to biometrics, CD-ARES 2013 Workshops: 2nd International Workshop on Modern Cryptography and Security Engineering, MoCrySEn 2013 and 3rd International Workshop on Security and Cognitive Informatics for Homeland Defense, SeCIHD 2013 Security Engineering and Intelligence Informatics - CD-ARES 2013 Workshops MoCrySEn and SeCIHD, Proceedings, 10.1007/978-3-642-40588-4_5, 8128 LNCS, 55-74, 2013.12, Among many approaches for privacy-preserving biometric authentication, we focus on the approach with homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In biometric authentication, the Hamming distance is often used as a metric to compare two biometric feature vectors. In this paper, we propose an efficient method to compute the Hamming distance on encrypted data using the homomorphic encryption based on ideal lattices. In our implementation of secure Hamming distance of 2048-bit binary vectors with a lattice of 4096 dimension, encryption of a vector, secure Hamming distance, and decryption respectively take about 19.89, 18.10, and 9.08 milliseconds (ms) on an Intel Xeon X3480 at 3.07 GHz. We also propose a privacy-preserving biometric authentication protocol using our method, and compare it with related protocols. Our protocol has faster performance and shorter ciphertext size than the state-of-the-art prior work using homomorphic encryption..
41. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba, Secure pattern matching using somewhat homomorphic encryption, 2013 ACM Cloud Computing Security Workshop, CCSW 2013 - Co-located with the 20th ACM Conference on Computer and Communications Security, CCS 2013 CCSW 2013 - Proceedings of the 2013 ACM Cloud Computing Security Workshop, Co-located with CCS 2013, 10.1145/2517488.2517497, 65-76, 2013.12, The basic pattern matching problem is to find the locations where a pattern occurs in a text. Recently, secure pattern matching has been received much attention in various areas, including privacy-preserving DNA matching and secure biometric authentication. The aim of this paper is to give a practical solution for this problem using homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In this paper, we make use of the somewhat homomorphic encryption scheme presented by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), which supports a limited number of both additions and multiplications on encrypted data. In their work, some message encoding techniques are also presented for enabling us to efficiently compute sums and products over the integers. Based on their techniques, we propose a new packing method suitable for an efficient computation of multiple Hamming distance values on encrypted data. Our main extension gives two types of packed ciphertexts, and a linear computation over packed ciphertexts gives our desired results. We implemented the scheme with our packing method. Our experiments ran in an Intel Xeon at 3.07 GHz with our software library using inline assembly language in C programs. Our optimized implementation shows that the packed encryption of a text or a pattern, the computation of multiple Hamming distance values over packed ciphertexts, and the decryption respectively take about 3.65 milliseconds (ms), 5.31 ms, and 3.47 ms for secure exact and approximate pattern matching of a binary text of length 2048. The total time is about 12.43 ms, which would give the practical performance in real life. Our method gives both faster performance and lower communication than the state-of-the-art work for a binary text of several thousand bits in length..
42. 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.
43. Masaya Yasuda, Kummer generators and torsion points of elliptic curves with bad reduction at some primes, International Journal of Number Theory, 10.1142/S1793042113500541, 9, 7, 1743-1752, 2013.11, For a prime p, let ζp denote a fixed primitive pth root of unity. Let E be an elliptic curve over a number field K with a p-torsion point. Then the p-torsion subgroup of E gives a Kummer extension over K(ζp), and in this paper, we study the ramification of such Kummer extensions using the Kummer generators directly computed by Verdure in 2006. For quadratic fields K, we also give unramified Kummer extensions over K(ζp) generated from elliptic curves over K having a p-torsion point with bad reduction at certain primes. Many of these unramified Kummer extensions have not appeared in the previous work using fundamental units of quadratic fields..
44. Masaya Yasuda, Jun Yajima, Takeshi Shimoyama, Jun Kogure, Analysis of lattice reduction attack against the somewhat homomorphic encryption based on ideal lattices, 9th European Workshop on Public Key Infrastructures, Services and Applications, EuroPKI 2012 Public Key Infrastructures, Services and Applications - 9th European Workshop, EuroPKI 2012, Revised Selected Papers, 10.1007/978-3-642-40012-4_1, 7868 LNCS, 1-16, 2013, In 2009, Gentry first proposed a concrete method for constructing a fully homomorphic encryption (FHE) scheme, which supports arbitrary operations on encrypted data. The construction of the FHE scheme starts from a somewhat homomorphic encryption (SHE) scheme, which only supports limited operations but can be much faster than the FHE scheme. The Gentry's scheme is based on ideal lattices, and Chen and Nguyen estimated that it needs at least 10,000 lattice dimension to make the FHE scheme secure. In contrast, the security of the SHE scheme can be guaranteed for lower lattice dimensions, depending on the possible operations which are determined by key parameters. The aim of this paper is to classify which key parameters are feasible to be solved. We attack the lattice problem of lower dimensions by practical lattice reduction algorithms, and estimate the key parameters which can be solved in practice..
45. Masaya Yasuda, Torsion points of elliptic curves with bad reduction at some primes II, Bulletin of the Korean Mathematical Society, 10.4134/BKMS.2013.50.1.083, 50, 1, 83-96, 2013, Let K be a number field and fix a prime number p. For any set S of primes of K, we here say that an elliptic curve E over K has S-reduction if E has bad reduction only at the primes of S. There exists the set BK,p of primes of K satisfying that any elliptic curve over K with BK,p-reduction has no p-torsion points under certain conditions. The first aim of this paper is to construct elliptic curves over K with BK,p reduction and a p-torsion point. The action of the absolute Galois group on the p-torsion subgroup of E gives its associated Galois representation PE,p modulo p. We also study the irreducibility and surjectivity of ρE,p for semistable elliptic curves with BK,p-reduction..
46. Takanori Yasuda, Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, On the number of the pairing-friendly curves, International Journal of Pure and Applied Mathematics, 77, 1, 11-15, 2012.05, In pairing-based cryptography, it is necessary to choose an elliptic curve with a small embedding degree and a large prime-order subgroup, which is called a pairing-friendly curve. In this paper, we study the number of the pairing-friendly curves with a given large prime-order subgroup..
47. Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Solving a DLP with auxiliary input with the ρ-algorithm, 12th International Workshop on Information Security Applications, WISA 2011 Information Security Applications - 12th International Workshop, WISA 2011, Revised Selected Papers, 10.1007/978-3-642-27890-7_8, 7115 LNCS, 98-108, 2012.03, The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find a positive integer α from elements G, αG, α d G in an additive cyclic group generated by G of prime order r and a positive integer d dividing r -1. In 2011, Sakemi et al. implemented Cheon's algorithm for solving DLPwAI, and solved a DLPwAI in a group with 128-bit order r in about 131 hours with a single core on an elliptic curve defined over a prime finite field which is used in the TinyTate library for embedded cryptographic devices. However, since their implementation was based on Shanks' Baby-step Giant-step (BSGS) algorithm as a sub-algorithm, it required a large amount of memory (246 GByte) so that it was concluded that applying other DLPwAIs with larger parameter is infeasible. In this paper, we implemented Cheon's algorithm based on Pollard's ρ-algorithm in order to reduce the required memory. As a result, we have succeeded solving the same DLPwAI in about 136 hours by a single core with less memory (0.5 MByte)..
48. Masaya Yasuda, A generalization of the anomalous attack for the ECDLP over Q p, International Journal of Pure and Applied Mathematics, 77, 1, 1-9, 2012, The elliptic curve discrete logarithm problem (ECDLP) over a field K is as follows: given an elliptic curve E over K, a point S ∈ E(K), and a point T ∈ E(K) with T ∈ hSi, find the integer d such that T = dS. The hardness of the ECDLP over a finite field is essential for the security of all elliptic curve cryptographic schemes. Semaev, Smart, and Satoh and Araki independently proposed an efficient attack for the ECDLP over F p in the anomalous case, which is called the anomalous attack. In this paper, we generalize the method of the anomalous attack and give an algorithm for solving the ECDLP over the p-adic field Q p..
49. Masaya Yasuda, On elliptic curves whose 3-torsion subgroup splits as μ3 ⊕ ℤ/3ℤ, Communications of the Korean Mathematical Society, 10.4134/CKMS.2012.27.3.497, 27, 3, 497-503, 2012, In this paper, we study elliptic curves E over ( such thatthe 3-torsion subgroup E[3] is split as μ3 ⊕ ℤ/3ℤ. For a non-zero integer m, let Cm denote the curve x3 + y3 = m. We consider the relation between the set of integral points of Cm and the elliptic curves E with E[3] ≃ μ3 ⊕ ℤ/3ℤ..
50. Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu, On the strength comparison of the ECDLP and the IFP, 8th International Conference on Security and Cryptography for Networks, SCN 2012 Security and Cryptography for Networks - 8th International Conference, SCN 2012, Proceedings, 10.1007/978-3-642-32928-9_17, 7485 LNCS, 302-325, 2012, At present, the RSA cryptosystem is most widely used in public key cryptography. On the other hand, elliptic curve cryptography (ECC) has recently received much attention since smaller ECC key sizes provide the same security level as RSA. Although there are a lot of previous works that analyze the security of ECC and RSA, the comparison of strengths varies depending on analysis. The aim of this paper is once again to compare the security strengths, considering state-of-the-art of theory and experiments. The security of RSA is closely related to the hardness of the integer factorization problem (IFP), while the security of ECC is closely related to the elliptic curve discrete logarithm problem (ECDLP). In this paper, we compare the computing power required to solve the ECDLP and the IFP, respectively, and estimate the sizes of the problems that provide the same level of security..
51. Yumi Sakemi, Goichiro Hanaoka, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Solving a discrete logarithm problem with auxiliary input on a 160-bit elliptic curve, 15th International Conference on Practice and Theory in Public Key Cryptography, PKC 2012 Public Key Cryptography, PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Proceedings, 10.1007/978-3-642-30057-8_35, 7293 LNCS, 595-608, 2012, A discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, α dG in an additive cyclic group generated by an element G of prime order r, and a positive integer d satisfying d|(r - 1). The infeasibility of this problem assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI (Cheon's algorithm). This paper reports our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we have succeeded to solve DLPwAI on a pairing-friendly elliptic curve of 160-bit order in 1314 core days. Implications of our experiments on cryptographic schemes are also discussed..
52. Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Solving DLP with auxiliary input over an elliptic curve used in TinyTate library, 5th Workshop in Information Security Theory and Practice, WISTP 2011 Information Security Theory and Practice Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings, 10.1007/978-3-642-21040-2_8, 6633 LNCS, 116-127, 2011.06, The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, α dG in an additive cyclic group generated by G of prime order r and a positive integer d dividing r-1. The infeasibility of DLPwAI assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI. This paper shows our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we succeeded to solve DLPwAI in a group with 128-bit order in 45 hours with a single PC on an elliptic curve defined over a prime finite field with 256-bit elements which is used in the TinyTate library..
53. Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Experimantal analysis of cheon's algorithm against pairing-friendly curves, 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011 Proceedings - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011, 10.1109/AINA.2011.37, 90-96, 2011, The discrete logarithm problem (DLP) is one of the familiar problem on which some cryptographic schemes rely. In 2006, Cheon proposed an algorithm for solving DLP with auxiliary input which works better than conventional algorithms. In this paper, we show our experimental results of Cheon's algorithm on a pairing-friendly elliptic curve defined over GF(3127). It is shown that the algorithm combined with the kangaroo method has an advantage over that combined with the baby-step giant-step method in the sense that the required time and space are smaller. Then, for the algorithm combined with the kangaroo-method, speeding-up techniques are introduced. Based on our experimental results and the speeding-up techniques, we evaluate the required time and space for some pairing-friendly elliptic curves curves. As results, a portion of pairing-friendly elliptic curves can be analyzed by Cheon's algorithm at reasonable cost..
54. Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Experimental analysis of cheon’s algorithm against pairing-friendly curves, Journal of Information Processing, 10.2197/ipsjjip.19.441, 19, 441-450, 2011, Let G be an additive group generated by an element G of prime order r. The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α on inputs G, αG, αdG ∈ G for a positive integer d dividing r − 1. The infeasibility of DLPwAI ensures the security of some pairing-based cryptographic schemes. In 2006, Cheon proposed an algorithm for solving DLPwAI which works better than conventional algorithms. In this paper, we report our experimental results of Cheon’s algorithm on a pairing-friendly elliptic curve defined over GF(3127). Moreover, based on our experimental results, we estimate the required cost of Cheon’s algorithm to solve DLPwAI on some pairing-friendly elliptic curves over a finite field of characteristic 3. Our estimation implies that DLPwAI on a part of pairing-friendly curves can be solved at reasonable cost when the optimal parameter d is chosen..
55. Masaya Yasuda, On the canonical bundle formula for abelian fiber spaces in positive characteristic, Kodai Mathematical Journal, 10.2996/kmj/1301576761, 34, 1, 55-70, 2011, Let X be a non-singular projective (n + 1)-fold defined over an algebraically closed field k of characteristic p ≥ 0, and B be a non-singular complete curve defined over k. A surjective morphism f: X → B is said to be an n-abelian fiber space if almost all fibers are n-dimensional abelian varieties. We examine the canonical bundle formula for n-abelian fiber spaces..
56. Masaya Yasuda, The lifting problem for the ECDLP and the Selmer rank, International Journal of Pure and Applied Mathematics, 71, 2, 193-205, 2011, The hardness of the elliptic curve discrete logarithm problem (ECDLP) on a finite field is essential for the security of all elliptic curve cryptographic schemes. A number of ways of approaching the solution to the ECDLP on a finite field is known, for example, the MOV attack [7], and the anomalous attack (see [9], [13]). In their paper [2], Cheon et al. proposed an algorithm to solve the ECDLP on prime fields, which is very efficient if we could lift two points to an elliptic curve over ℚ with rank one. In this paper, we investigate the success probability of their method by estimating the Selmer rank of lifted elliptic curves. We note that the Selmer rank means the upper bound of the rank given by the Selmer group (see [11])..
57. Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Time estimation of Cheon's algorithm over elliptic curves on finite fields with characteristic 3, 2011 5th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, IMIS 2011 Proceedings - 2011 5th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, IMIS 2011, 10.1109/IMIS.2011.113, 594-596, 2011, Cheon introduced a novel algorithm for solving the discrete logarithm problems with auxiliary input (DLPwAI). Since the infeasibility of DLPwAI assures the security of some cryptographic schemes, some implementational results have been reported. This paper estimates the required time for solving DLPwAI on elliptic curves over finite fields with characteristics 3 by extrapolating previous results..
58. Masaya Yasuda, The elliptic curve discrete logarithm problems over the p-adic field and formal groups, 6th International Conference on Information Security Practice and Experience, ISPEC 2010 Information Security Practice and Experience - 6th International Conference, ISPEC 2010, Proceedings, 10.1007/978-3-642-12827-1_9, 6047 LNCS, 110-122, 2010.12, The hardness of the elliptic curve discrete logarithm problem (ECDLP) on a finite field is essential for the security of all elliptic curve cryptographic schemes. The ECDLP on a field K is as follows: given an elliptic curve E over K, a point S ∈ E(K), and a point T ∈ E(K) with T ∈ (S), find the integer d such that T = dS. A number of ways of approaching the solution to the ECDLP on a finite field is known, for example, the MOV attack [5], and the anomalous attack [7,10]. In this paper, we propose an algorithm to solve the ECDLP on the p-adic field Qp. Our method is to use the theory of formal groups associated to elliptic curves, which is used for the anomalous attack proposed by Smart [10], and Satoh and Araki [7]..
59. Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda, Experimental results on Cheon's algorithm, 5th International Conference on Availability, Reliability, and Security, ARES 2010 ARES 2010 - 5th International Conference on Availability, Reliability, and Security, 10.1109/ARES.2010.55, 625-628, 2010, The discrete logarithm problem (DLP) is one of the familiar problem on which cryptographic schemes rely. In 2006, Cheon proposed an algorithm for solving DLP with auxiliary input which works better than conventional algorithms. This paper firstly reports experimental results on Cheon's algorithm for DLP on a supersingular elliptic curve defined over GF(3127), which is used for efficient pairing computation in practice. About 8 hours and 34 MByte database are required for the 1st step of Cheon's algorithm, and about 6 hours and 23 MByte data-base for the 2nd step. In total, about 14 hours are required for solving the problem. Our results imply that the security evaluation from a viewpoint of Cheon's algorithm is crucial..
60. Masaya Yasuda, Torsion points of elliptic curves with good reduction, Kodai Mathematical Journal, 10.2996/kmj/1225980443, 31, 3, 385-403, 2008, We consider the torsion points of elliptc curves over certain number fields with good reduction everywhere..