We have realized a design automation platform of hardware accelerator for pairing operation over multiple elliptic curve parameters. Pairing operation is one of the fundamental operations to realize functional encryption. However, known as a computational complexity-heavy algorithm. Also because there have been not yet identified standard parameters, we need to choose curve parameters based on the required security level and affordable hardware resources. To explore this design optimization for each curve parameter is essential. In this research, we have realized an automated design platform for pairing hardware for such purposes. Optimization results show almost equivalent to those prior-art designs by hand.

A group signature scheme allows us to anonymously sign a message on behalf of a group. One of important issues in the group signatures is user revocation, and thus lots of revocable group signature (RGS) schemes have been proposed so far. One of the applications suitable to the group signature is privacy-enhancing crowdsensing, where the group signature allows mobile sensing users to be anonymously authenticated to hide the location. In the mobile environment, verifier-local revocation (VLR) type of RGS schemes are suitable, since revocation list (RL) is not needed in the user side. However, in the conventional VLR-RGS schemes, the revocation check in the verifier needs O(R) cryptographic operations for the number R of revoked users. On this background, VLR-RGS schemes with efficient revocation check have been recently proposed, where the revocation check is just (bit-string) matching. However, in the existing schemes, signatures are linkable in the same interval or in the same application-independent task with a public index. The linkability is useful in some scenarios, but users want the unlinkability for the stronger anonymity. In this paper, by introducing a property that at most K unlinkable signatures can be issued by a signer during each interval for a fixed integer K, we propose a VLR-RGS scheme with the revocation token matching. In our scheme, even the signatures during the same interval are unlinkable. Furthermore, since used indexes are hidden, the strong anonymity remains. The overheads are the computational costs of the revocation algorithm and the RL size. We show that the overheads are practical in use cases of crowdsensing.

BLS signature is an elliptic curve cryptography with an attractive feature that signatures can be aggregated and shortened. We have designed two ASIC architectures for hashing to the elliptic curve and pairing to minimize the latency. Also, the designs are optimized for BLS12-381, a relatively new and safe curve.

The prosperous Internet communication technologies have led to e-commerce in mobile computing and made Web of Things become popular. Electronic payment is the most important part of e-commerce, so many electronic payment schemes have been proposed. However, most of proposed schemes cannot give change. Based on proxy blind signatures, an e-cash payment system is proposed in this paper to solve this problem. This system can not only provide change divisibility through Web of Things, but also provide anonymity, verifiability, unforgeability and double-spending owner track.

The final exponentiation affects the efficiency of pairing computations especially on pairing-friendly curves with high embedding degree. We propose an efficient method for computing the hard part of the final exponentiation on the KSS18 curve at the 192-bit security level. Implementations indicate that the computation of the final exponentiation is 8.74% faster than the previously fastest result.

Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: BW13-P310 and BW19-P286, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the BW13-P310 curve. We first extend the technique of lazy reduction into the finite field arithmetic. Then, we present a new method to execute Miller's algorithm. Compared with the standard Miller iteration formulas, the new ones provide a more efficient software implementation of pairing computations. At last, we also give a fast formula to perform the final exponentiation. Our implementation results indicate that it can be computed efficiently, while it is slower than that over the (BLS12-P446) curve at the same security level.

To prove the graph relations such as the connectivity and isolation for a certified graph, a system of a graph signature and proofs has been proposed. In this system, an issuer generates a signature certifying the topology of an undirected graph, and issues the signature to a prover. The prover can prove the knowledge of the signature and the graph in the zero-knowledge, i.e., the signature and the signed graph are hidden. In addition, the prover can prove relations on the certified graph such as the connectivity and isolation between two vertexes. In the previous system, using integer commitments on RSA modulus, the graph relations are proved. However, the RSA modulus needs a longer size for each element. Furthermore, the proof size and verification cost depend on the total numbers of vertexes and edges. In this paper, we propose a graph signature and proof system, where these are computed on bilinear groups without the RSA modulus. Moreover, using a bilinear map accumulator, the prover can prove the connectivity and isolation on a graph, where the proof size and verification cost become independent from the total numbers of vertexes and edges.

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.

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.

This paper proposes an id-eCK secure identity-based authenticated key exchange (ID-AKE) scheme, where the id-eCK security implies that a scheme resists against leakage of all combinations of master, static, and ephemeral secret keys except ones trivially break the security. Most existing id-eCK secure ID-AKE schemes require two symmetric pairing operations or a greater number of asymmetric pairing, which is faster than symmetric one, operations to establish a session key. However, our scheme is realized with a single asymmetric pairing operation for each party, and this is an advantage in efficiency. The proposed scheme is based on the ID-AKE scheme by McCullagh and Barreto, which is vulnerable to an active attack. To achieve id-eCK security, we apply the HMQV construction and the NAXOS technique to the McCullagh-Barreto scheme. The id-eCK security is proved under the external Diffie-Hellman for target group assumption and the q-gap-bilinear collision attack assumption.

To enhance the user's privacy in electronic ID, anonymous credential systems have been researched. In the anonymous credential system, a trusted issuing organization first issues a certificate certifying the user's attributes to a user. Then, in addition to the possession of the certificate, the user can anonymously prove only the necessary attributes. Previously, an anonymous credential system was proposed, where CNF (Conjunctive Normal Form) formulas on attributes can be proved. The advantage is that the attribute proof in the authentication has the constant size for the number of attributes that the user owns and the size of the proved formula. Thus, various expressive logical relations on attributes can be efficiently verified. However, the previous system has a limitation: The proved CNF formulas cannot include any negation. Therefore, in this paper, we propose an anonymous credential system with constant-size attribute proofs such that the user can prove CNF formulas with negations. For the proposed system, we extend the previous accumulator for the limited CNF formulas to verify CNF formulas with negations.

This paper presents a two-dimensional (2D) DOA algorithm for double L-shaped arrays. The algorithm is applied to the underwater environment for eliminating the performance error caused by the sound speed uncertainty factor. By introducing the third dimensional array, the algorithm eliminates the sound velocity variable in the depression angle expression, so that the DOA estimation no longer considering the true value of unknown sound velocity. In order to determine the parameters of a three-dimensional array, a parameter matching method with the double L-shaped array is also proposed. Simulations show that the proposed algorithm outperforms the conventional 2D-DOA estimation algorithm in unknown sound velocity environment.

Inner product functional encryption (IPFE) is a subclass of functional encryption (FE), whose function class is limited to inner product. We construct an efficient private-key IPFE scheme with full-hiding security, where confidentiality is assured for not only encrypted data but also functions associated with secret keys. Recently, Datta et al. presented such a scheme in PKC 2016 and this is the only scheme that achieves full-hiding security. Our scheme has an advantage over their scheme for the two aspects. More efficient: keys and ciphertexts of our scheme are almost half the size of those of their scheme. Weaker assumption: our scheme is secure under the k-linear (k-Lin) assumption, while their scheme is secure under a stronger assumption, namely, the symmetric external Diffie-Hellman (SXDH) assumption. It is well-known that the k-Lin assumption is equivalent to the SXDH assumption when k=1 and becomes weak as k increases.

In conventional ID-based user authentications, privacy issues may occur, since users' behavior histories are collected in Service Providers (SPs). Although anonymous authentications such as group signatures have been proposed, these schemes rely on a Trusted Third Party (TTP) capable of tracing misbehaving users. Thus, the privacy is not high, because the TTP of tracing authority can always trace users. Therefore, the anonymous credential system using a blacklist without the TTP of tracing authority has been proposed, where blacklisted anonymous users can be blocked. Recently, an RSA-based blacklistable anonymous credential system with efficiency improvement has been proposed. However, this system still has an efficiency problem: The data size in the authentication is O(K'), where K' is the maximum number of sessions in which the user can conduct. Furthermore, the O(K')-size data causes the user the computational cost of O(K') exponentiations. In this paper, a blacklistable anonymous credential system using a pairing-based accumulator is proposed. In the proposed system, the data size in the authentication is constant for parameters. Although the user's computational cost depends on parameters, the dependent cost is O(δBL·K) multiplications, instead of exponentiations, where δBL is the number of sessions added to the blacklist after the last authentication of the user, and K is the number of past sessions of the user. The demerit of the proposed system is O(n)-size public key, where n corresponds to the total number of all sessions of all users in the system. But, the user only has to download the public key once.

In ID-based user authentications, a privacy problem can occur, since the service provider (SP) can accumulate the user's access history from the user ID. As a solution to that problem, group signatures have been researched. One of important issues in the group signatures is the user revocation. Previously, an efficient revocable scheme with signing/verification of constant complexity was proposed by Libert et al. In this scheme, users are managed by a binary tree, and a list of data for revoked users, called a revocation list (RL), is used for revocation. However, the scheme suffers from the large RL. Recently, an extended scheme has been proposed by Sadiah and Nakanishi, where the RL size is reduced by compressing RL. On the other hand, there is a problem that some overhead occurs in the authentication as a price for reducing the size of RL. In this paper, we propose an extended scheme where the authentication is speeded up by reducing the number of Groth-Sahai (GS) proofs. Furthermore, we implemented it on a PC to show the effectiveness. The verification time is about 30% shorter than that of the previous scheme by Sadiah and Nakanishi.

We propose a simple framework for evaluating the performance of pairing-based cryptographic schemes for various types of curves and parameter settings. The framework, which we call ‘Opcount’, enables the selection of an appropriate curve and parameters by estimating the performance of a cryptographic scheme from a pseudo-code describing the cryptographic scheme and an implementation-information database that records the performance of basic operations in curves targeted for evaluation. We apply Opcount to evaluate and compare the computational efficiency of several structure-preserving signature schemes that involve tens of pairing products in their signature verification. In addition to showing the usefulness of Opcount, our experiments also reveal the overlooked importance of taking account of the properties of underlying curves when optimizing computations and demonstrate the impact of tight security reductions.

We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a mark, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. A mark-embedded function must be functionally equivalent to the original function. It must be difficult for adversaries to remove the embedded mark without damaging the original functionality. In spite of its importance and usefulness, there have only been a few theoretical works on watermarking for functions (or programs). Furthermore, we do not have rigorous definitions of watermarking for cryptographic functions and concrete constructions. To solve the problem above, we introduce a notion of watermarking for cryptographic functions and define its security. Furthermore, we present a lossy trapdoor function (LTF) based on the decisional bilinear Diffie-Hellman problem problem and a watermarking scheme for the LTF. Our watermarking scheme is secure under the symmetric external Diffie-Hellman assumption in the standard model. We use techniques of dual system encryption and dual pairing vector spaces (DPVS) to construct our watermarking scheme. This is a new application of DPVS.

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.

An ASIC crypto processor optimized for the 254-bit prime-field optimal-ate pairing over Barreto-Naehrig (BN) curve is proposed. The data path of the proposed crypto processor is designed to compute five Fp2 operations, a multiplication, three addition/subtractions, and an inversion, simultaneously. We further propose a design methodology to automate the instruction scheduling by using a combinatorial optimization solver, with which the total cycle count is reduced to 1/2 compared with ever reported. The proposed crypto processor is designed and fabricated by using a 65nm silicon-on-thin-box (SOTB) CMOS process. The chip measurement result shows that the fabricated chip successfully computes a pairing in 0.185ms when a typical operating voltage of 1.20V is applied, which corresponds to 2.8× speed up compared to the current state-of-the-art pairing implementation on ASIC platform.

This paper proposes a novel method for two-dimensional (2-D) direction-of-arrival (DOA) estimation of multiple signals employing a sparse L-shaped array structured by a sparse linear array (SLA), a sparse uniform linear array (SULA) and an auxiliary sensor. In this method, the elevation angles are estimated by using the SLA and an efficient search approach, while the azimuth angle estimation is performed in two stages. In the first stage, the rough azimuth angle estimates are obtained by utilizing a noise-free cross-covariance matrix (CCM), the estimated elevation angles and data from three sensors including the auxiliary sensor. In the second stage, the fine azimuth angle estimates can be achieved by using the shift-invariance property of the SULA and the rough azimuth angle estimates. Without extra pair-matching process, the proposed method can achieve automatic pairing of the 2-D DOA estimates. Simulation results show that our approach outperforms the compared methods, especially in the cases of low SNR, snapshot deficiency and multiple sources.