1-17hit |
The membership check of a group is an important operation to implement discrete logarithm-based cryptography in practice securely. Since this check requires costly scalar multiplication or exponentiation operation, several efficient methods have been investigated. In the case of pairing-based cryptography, this is an extended research area of discrete logarithm-based cryptography, Barreto et al. (LATINCRYPT 2015) proposed a parameter choice called subgroup-secure elliptic curves. They also claimed that, in some schemes, if an elliptic curve is subgroup-secure, costly scalar multiplication or exponentiation operation can be omitted from the membership check of bilinear groups, which results in faster schemes than the original ones. They also noticed that some schemes would not maintain security with this omission. However, they did not show the explicit condition of what schemes become insecure with the omission. In this paper, we show a concrete example of insecurity in the sense of subgroup security to help developers understand what subgroup security is and what properties are preserved. In our conclusion, we recommend that the developers use the original membership check because it is a general and straightforward method to implement schemes securely. If the developers want to use the subgroup-secure elliptic curves and to omit the costly operation in a scheme for performance reasons, it is critical to carefully analyze again that correctness and security are preserved with the omission.
Yuki NANJO Masaaki SHIRASE Takuya KUSAKA Yasuyuki NOGAMI
To be suitable in practice, pairings are typically carried out by two steps, which consist of the Miller loop and final exponentiation. To improve the final exponentiation step of a pairing on the BLS family of pairing-friendly elliptic curves with embedding degree 15, the authors provide a new representation of the exponent. The proposal can achieve a more reduction of the calculation cost of the final exponentiation than the previous method by Fouotsa et al.
Zule XU Anugerah FIRDAUZI Masaya MIYAHARA Kenichi OKADA Akira MATSUZAWA
This paper presents a type-I digital ring-based PLL with wide loop bandwidth to lower the ring oscillator's noise contribution. The loop delay due to the D flip-flops at filter's output is compensated in order to lower the noise peak and stably achieve wide loop bandwidth. The input-referred jitter is lowered by using a successive-approximated-register analog-to-digital converter (SAR-ADC)-based sampling phase detector (SPD). A stacked reference buffer is introduced to reduce the transient short-circuit current for low power and low reference spur. The locking issue due to the steady-state phase error in a type-I PLL and the limited range of the phase detector is addressed using a TDC-assisted loop. The loop stability and phase noise are analyzed, suggesting a trade-off for the minimum jitter. The solutions in detail are described. The prototype PLL fabricated in 65 nm CMOS demonstrates 2.0 ps RMS jitter, 3.1 mW power consumption, and 0.067 mm2 area, with 50 MHz reference frequency and 2.0 GHz output frequency.
Masayuki ABE Fumitaka HOSHINO Miyako OHKUBO
Bilinear-type conversion is to translate a cryptographic scheme designed over symmetric bilinear groups into one that works over asymmetric bilinear groups with small overhead regarding the size of objects concerned in the target scheme. In this paper, we address scalability for converting complex cryptographic schemes. Our contribution is threefold. Investigating complexity of bilinear-type conversion. We show that there exists no polynomial-time algorithm for worst-case inputs under standard complexity assumption. It means that bilinear-type conversion in general is an inherently difficult problem. Presenting a new scalable conversion method. Nevertheless, we show that large-scale conversion is indeed possible in practice when the target schemes are built from smaller building blocks with some structure. We present a novel conversion method, called IPConv, that uses 0-1 Integer Programming instantiated with a widely available IP solver. It instantly converts schemes containing more than a thousand of variables and hundreds of pairings. Application to computer-aided design. Our conversion method is also useful in modular design of middle to large scale cryptographic applications; first construct over simpler symmetric bilinear groups and run over efficient asymmetric groups. Thus one can avoid complication of manually allocating variables over asymmetric bilinear groups. We demonstrate its usefulness by somewhat counter-intuitive examples where converted DLIN-based Groth-Sahai proofs are more compact than manually built SXDH-based proofs. Though the early purpose of bilinear-type conversion is to save existing schemes from attacks against symmetric bilinear groups, our new scalable conversion method will find more applications beyond the original goal. Indeed, the above computer-aided design can be seen as a step toward automated modular design of cryptographic schemes.
A new method is proposed for the construction of pairing-friendly elliptic curves. For any fixed embedding degree, it can transform the problem to solving equation systems instead of exhaustive searching, thus it's more targeted and efficient. Via this method, we obtain various families including complete families, complete families with variable discriminant and sparse families. Specifically, we generate a complete family with important application prospects which has never been given before as far as we know.
Yasuyuki NOGAMI Hiroto KAGOTANI Kengo IOKIBE Hiroyuki MIYATAKE Takashi NARITA
Pairing-based cryptography has realized a lot of innovative cryptographic applications such as attribute-based cryptography and semi homomorphic encryption. Pairing is a bilinear map constructed on a torsion group structure that is defined on a special class of elliptic curves, namely pairing-friendly curve. Pairing-friendly curves are roughly classified into supersingular and non supersingular curves. In these years, non supersingular pairing-friendly curves have been focused on from a security reason. Although non supersingular pairing-friendly curves have an ability to bridge various security levels with various parameter settings, most of software and hardware implementations tightly restrict them to achieve calculation efficiencies and avoid implementation difficulties. This paper shows an FPGA implementation that supports various parameter settings of pairings on non supersingular pairing-friendly curves for which Montgomery reduction, cyclic vector multiplication algorithm, projective coordinates, and Tate pairing have been combinatorially applied. Then, some experimental results with resource usages are shown.
Naoyuki SHINOHARA Takeshi SHIMOYAMA Takuya HAYASHI Tsuyoshi TAKAGI
The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 3. Indeed many high-speed implementations of this pairing have been reported, and it is an attractive candidate for practical deployment of pairing-based cryptosystems. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), where the function field sieve (FFS) is known as the asymptotically fastest algorithm of solving it. Moreover, several efficient algorithms are employed for implementation of the FFS, such as the large prime variation. In this paper, we estimate the time complexity of solving the DLP for the extension degrees n=97, 163, 193, 239, 313, 353, and 509, when we use the improved FFS. To accomplish our aim, we present several new computable estimation formulas to compute the explicit number of special polynomials used in the improved FFS. Our estimation contributes to the evaluation for the key length of pairing-based cryptosystems using the ηT pairing.
Mitsuhiro HATTORI Takato HIRANO Takashi ITO Nori MATSUDA Takumi MORI Yusuke SAKAI Kazuo OHTA
We propose a new hidden vector encryption (HVE) scheme that we call a ciphertext-policy delegatable hidden vector encryption (CP-dHVE) scheme. Several HVE schemes have been proposed and their properties have been analyzed extensively. Nonetheless, the definition of the HVE has been left unchanged. We therefore reconsider it, and point out that the conventional HVE should be categorized as the key-policy HVE, because the vectors corresponding to the secret keys can contain wildcards (which specify an access policy) whereas those corresponding to the ciphertexts cannot contain them. We then formalize its dual concept, the ciphertext-policy HVE, and propose a concrete scheme. Then, as an application of our scheme, we propose a public-key encryption with conjunctive keyword search scheme that can be used in the hierarchical user systems. Our scheme is novel in that the ciphertext size grows logarithmically to the number of uses in the system, while that of a conventional scheme grows linearly.
Takuya HAYASHI Naoyuki SHINOHARA Lihua WANG Shin'ichiro MATSUO Masaaki SHIRASE Tsuyoshi TAKAGI
Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The ηT pairing on supersingular curves over GF(3n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone attack, the discrete logarithm problem (DLP) in GF(36n) becomes a concern for the security of cryptosystems using ηT pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over GF(36n). Therefore, we first fulfill such an implementation and we successfully set a new record for solving the DLP in GF(36n), the DLP in GF(36·71) of 676-bit size. In addition, we also compare JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.
Aya COMUTA Mitsuru KAWAZOE Tetsuya TAKAHASHI Isamu YOSHIZAWA
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D. Freeman for the genus two case. In this paper, we give an explicit construction of pairing-friendly hyperelliptic curves of genus two and four with ordinary Jacobians based on the closed formulae for the order of the Jacobian of special hyperelliptic curves. For the case of genus two, we prove the closed formula for curves of type y2=x5+c. By using the formula, we develop an analogue of the Cocks-Pinch method for curves of type y2=x5+c. For the case of genus four, we also develop an analogue of the Cocks-Pinch method for curves of type y2=x9+cx. In particular, we construct the first examples of pairing-friendly hyperelliptic curves of genus four with ordinary Jacobians.
In the proposed scheme, every sensor establishes communications keys with its neighbors after deployment. They are selectively employed for intra-cluster communications, and the employed keys are determined by local topology of clusters. Thus, our scheme periodically changes the local topology of clusters so as to renew the intra-cluster communication keys. Besides, new Cluster Heads (CHs) easily share a key with the Base Station (BS) by informing the BS of their member information without sending key materials. Simulation results prove that our approach has strong resiliency against the increase of compromised sensors. It also achieves a performance gain in terms of energy.
Chang-An ZHAO Fangguo ZHANG Jiwu HUANG
In this paper, we suggest that all pairings are in a group from an abstract angle. Based on the results, some new pairings with the short Miller loop are constructed for great efficiency. It is possible that our observation can be applied into other aspects of pairing-based cryptosystems.
Tein-Yaw CHUNG Kuan-Chun LEE Hsiao-Chih LEE
This paper derived a closed-form expression for inter-flow capacity of a backhaul wireless mesh network (WMN) with centralized scheduling by employing a ring-based approach. Through the definition of an interference area, we are able to accurately describe a bottleneck collision area for a WMN and calculate the upper bound of inter-flow capacity. The closed-form expression shows that the upper bound is a function of the ratio between transmission range and network radius. Simulations and numerical analysis show that our analytic solution can better estimate the inter-flow capacity of WMNs than that of previous approach.
Taiichi SAITO Fumitaka HOSHINO Shigenori UCHIYAMA Tetsutaro KOBAYASHI
This paper proposes new candidate one-way functions constructed with a certain type of endomorphisms on non-supersingular elliptic curves. We can show that the one-wayness of our proposed functions is equivalent to some special cases of the co-Diffie-Hellman assumption. Also a digital signature scheme is explicitly described using our proposed functions.
Shi CUI Pu DUAN ChoongWah CHAN
Non-supersingular elliptic curves are important for the security of pairing-based cryptosystems. But there are few suitable non-supersingular elliptic curves for pairing-based cryptosystems. This letter introduces a method which allows the existing method to generate more non-supersingular elliptic curves suitable for pairing-based cryptosystems when the embedding degree is 6.
Taiichi SAITO Fumitaka HOSHINO Shigenori UCHIYAMA Tetsutaro KOBAYASHI
This paper provides methods for construction of pairing-based cryptosystems based on non-supersingular elliptic curves.
Somsak WALAIRACHT Masahiro ISHII Yasuharu KOIKE Makoto SATO
We have proposed a new string-based haptic interface device in this paper. It is a kind of device that allows a user to use both hands and multi-fingers to direct manipulate the virtual objects in the computer simulated virtual environment. One of the advantages of the device is to allow the user to use both hands to perform the cooperative works of hands, such as holding a large object that cannot be grasped or held by single hand. In addition, the haptic feedback sensation provided by the device at the fingertips makes possible for the user to perform dexterous manipulation, such as manipulating small size of objects. We have discussed about the design of the proposed device and have elaborated the methods of fingertip positions measurement and force feedback generation. The experiments had been carried out to verify the capabilities of the proposed device.