The existing discrete-logarithm-based two-round multi-signature schemes without using the idealized model, i.e., the Algebraic Group Model (AGM), have quite large reduction loss. This means that an implementation of these schemes requires an elliptic curve (EC) with a very large order for the standard 128-bit security when we consider concrete security. Indeed, the existing standardized ECs have orders too small to ensure 128-bit security of such schemes. Recently, Pan and Wagner proposed two two-round schemes based on the Decisional Diffie-Hellman (DDH) assumption (EUROCRYPT 2023). For 128-bit security in concrete security, the first scheme can use the NIST-standardized EC P-256 and the second can use P-384. However, with these parameter choices, they do not improve the signature size and the communication complexity over the existing non-tight schemes. Therefore, there is no two-round scheme that (i) can use a standardized EC for 128-bit security and (ii) has high efficiency. In this paper, we construct a two-round multi-signature scheme achieving both of them from the DDH assumption. We prove that an EC with at least a 321-bit order is sufficient for our scheme to ensure 128-bit security. Thus, we can use the NIST-standardized EC P-384 for 128-bit security. Moreover, the signature size and the communication complexity per one signer of our proposed scheme under P-384 are 1152 bits and 1535 bits, respectively. These are most efficient among the existing two-round schemes without using the AGM including Pan-Wagner’s schemes and non-tight schemes which do not use the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.

As one of privacy-enhancing authentications suitable for decentralized environments, ring signatures have intensively been researched. In ring signatures, each user can choose any ad-hoc set of users (specified by public keys) called a ring, and anonymously sign a message as one of the users. However, in applications of anonymous authentications, users may misbehave the service due to the anonymity, and thus a mechanism to exclude the anonymous misbehaving users is required. However, in the existing ring signature scheme, a trusted entity to open the identity of the user is needed, but it is not suitable for the decentralized environments. On the other hand, as another type of anonymous authentications, a decentralized blacklistable anonymous credential system is proposed, where anonymous misbehaving users can be detected and excluded by a blacklist. However, the DL-based instantiation needs O(N) proof size for the ring size N. In the research line of the DL-based ring signatures, an efficient scheme with O(log N) signature size, called DualRing, is proposed. In this paper, we propose a DL-based blacklistable ring signature scheme extended from DualRing, where in addition to the short O(log N) signature size for N, the blacklisting mechanism is realized to exclude misbehaving users. Since the blacklisting mechanism causes additional costs in our scheme, the signature size is O(log N+l), where l is the blacklist size.

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.

The proliferation of coronavirus disease (COVID-19) has prompted changes in business models. To ensure a successful transition to non-face-to-face and electronic communication, the authenticity of data and the trustworthiness of communication partners are essential. Trust services provide a mechanism for preventing data falsification and spoofing. To develop a trust service, the characteristics of the service and the scope of its use need to be determined, and the relevant legal systems must be investigated. Preparing a document to meet trust service provider requirements may incur significant expenses. This study focuses on electronic signatures, proposes criteria for classification, classifies actual documents based on these criteria, and opens a discussion. A case study illustrates how trusted service providers search a document highlighting areas that require approval. The classification table in this paper may prove advantageous at the outset when business decisions are uncertain, and there is no clear starting point.

The BGPsec protocol, which is an extension of the border gateway protocol (BGP) for Internet routing known as BGPsec, uses digital signatures to guarantee the validity of routing information. However, the use of digital signatures in routing information on BGPsec causes a lack of memory in BGP routers, creating a gaping security hole in today's Internet. This problem hinders the practical realization and implementation of BGPsec. In this paper, we present APVAS (AS path validation based on aggregate signatures), a new protocol that reduces the memory consumption of routers running BGPsec when validating paths in routing information. APVAS relies on a novel aggregate signature scheme that compresses individually generated signatures into a single signature. Furthermore, we implement a prototype of APVAS on BIRD Internet Routing Daemon and demonstrate its efficiency on actual BGP connections. Our results show that the routing tables of the routers running BGPsec with APVAS have 20% lower memory consumption than those running the conventional BGPsec. We also confirm the effectiveness of APVAS in the real world by using 800,000 routes, which are equivalent to the full route information on a global scale.

We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme generates tags from messages by constructing a scheme under a mild security condition that is existentially unforgeable against random message attack with auxiliary information. Thus our scheme can reduce the signature size since it does not need to send tags with the signatures. Our scheme has short signature sizes of O(1) and achieves tighter reduction loss than that of Ducas et al.'s scheme. Our proposed scheme has two variants. Our scheme with one property has tighter reduction and the same verification key size of O(log n) as that of Ducas et al.'s scheme, where n is the security parameter. Our scheme with the other property achieves much tighter reduction loss of O(Q/n) and verification key size of O(n), where Q is the number of signing queries.

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.

We propose a new lattice-based digital signature scheme MLWRSign by modifying Dilithium, which is one of the second-round candidates of NIST's call for post-quantum cryptographic standards. To the best of our knowledge, our scheme MLWRSign is the first signature scheme whose security is based on the (module) learning with rounding (LWR) problem. Due to the simplicity of the LWR, the secret key size is reduced by approximately 30% in our scheme compared to Dilithium, while achieving the same level of security. Moreover, we implemented MLWRSign and observed that the running time of our scheme is comparable to that of Dilithium.

Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional pre-communication stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value before deciding messages to be signed. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the standard DL problem. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

SPHINCS+ is a state-of-the-art post-quantum hash-based signature that is a candidate for the NIST post-quantum cryptography standard. For a target bit security, SPHINCS+ supports many different tradeoffs between the signature size and the signing speed. SPHINCS+ provides 6 parameter sets: 3 parameter sets for size optimization and 3 parameter sets for speed optimization. We propose new parameter sets with better performance. Specifically, SPHINCS+ implementations with our parameter sets are up to 26.5% faster with slightly shorter signature sizes.

This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP's, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP's, which themselves are of unbounded size and input length.

We propose a key-policy attribute-based encryption (KP-ABE) scheme with constant-size ciphertexts, whose almost tightly semi-adaptive security is proven under the decisional linear (DLIN) assumption in the standard model. The access structure is expressive, that is given by non-monotone span programs. It also has fast decryption, i.e., a decryption includes only a constant number of pairing operations. As an application of our KP-ABE construction, we also propose an efficient, fully secure attribute-based signatures with constant-size secret (signing) keys from the DLIN. For achieving the above results, we extend the sparse matrix technique on dual pairing vector spaces. In particular, several algebraic properties of an elaborately chosen sparse matrix group are applied to the dual system security proofs.

This paper presents decentralized multi-authority attribute-based encryption and signature (DMA-ABE and DMA-ABS) schemes, in which no central authority exists and no global coordination is required except for the setting of a parameter for a prime order bilinear group and a hash function, which can be available from public documents, e.g., ISO and FIPS official documents. In the proposed DMA-ABE and DMA-ABS schemes, every process can be executed in a fully decentralized manner; any party can become an authority and issue a piece for a secret key to a user without interacting with any other party, and each user obtains a piece of his/her secret key from the associated authority without interacting with any other party. While enjoying such fully decentralized processes, the proposed schemes are still secure against collusion attacks, i.e., multiple pieces issued to a user by different authorities can form a collusion resistant secret key, composed of these pieces, of the user. The proposed ABE scheme is the first DMA-ABE for non-monotone relations (and more general relations), which is adaptively secure under the decisional linear (DLIN) assumption in the random oracle model. This paper also proposes the first DMA-ABS scheme for non-monotone relations (and more general relations), which is fully secure, adaptive-predicate unforgeable and perfect private, under the DLIN assumption in the random oracle model. DMA-ABS is a generalized notion of ring signatures. The efficiency of the proposed DMA-ABE and DMA-ABS schemes is comparable to those of the existing practical ABE and ABS schemes with comparable relations and security.

Group signatures are signatures providing signer anonymity where signers can produce signatures on behalf of the group that they belong to. Although such anonymity is quite attractive considering privacy issues, it is not trivial to check whether a signer has been revoked or not. Thus, how to revoke the rights of signers is one of the major topics in the research on group signatures. In particular, scalability, where the signing and verification costs and the signature size are constant in terms of the number of signers N, and other costs regarding signers are at most logarithmic in N, is quite important. In this paper, we propose a revocable group signature scheme which is currently more efficient compared to previous all scalable schemes. Moreover, our revocable group signature scheme is secure under simple assumptions (in the random oracle model), whereas all scalable schemes are secure under q-type assumptions. We implemented our scheme by employing a Barreto-Lynn-Scott curve of embedding degree 12 over a 455-bit prime field (BLS-12-455), and a Barreto-Naehrig curve of embedding degree 12 over a 382-bit prime field (BN-12-382), respectively, by using the RELIC library. We showed that the online running times of our signing algorithm were approximately 14msec (BLS-12-455) and 11msec (BN-12-382), and those of our verification algorithm were approximately 20msec (BLS-12-455) and 16msec (BN-12-382), respectively. Finally, we showed that our scheme (with a slight extension) is applied to an identity management system proposed by Isshiki et al.

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.

SPHINCS+, an updated version of SPHINCS, is a post-quantum hash-based signature scheme submitted to the NIST post-quantum cryptography standardization project. To evaluate its performance, SPHINCS+ gives the theoretical number of function calls and the actual runtime of a reference implementation. We show that the theoretical number of function calls for SPHINCS+ verification is inconsistent with the runtime and then present the correct number of function calls.

Multisignatures are digital signatures for a group consisting of multiple signers where each signer signs common documents via interaction with its co-signers and the data size of the resultant signatures for the group is independent of the number of signers. In this work, we propose a multisignature scheme, whose security can be tightly reduced to the CDH problem in bilinear groups, in the strongest security model where nothing more is required than that each signer has a public key, i.e., the plain public key model. Loosely speaking, our main idea for a tight reduction is to utilize a three-round interaction in a full-domain hash construction. Namely, we surmise that a full-domain hash construction with three-round interaction will become tightly secure under the CDH problem. In addition, we show that the existing scheme by Zhou et al. (ISC 2011) can be improved to a construction with a tight security reduction as an application of our proof framework.

Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. In 2009, it was shown that hardware advances do not favor just “traditional” alternatives such as ECC and RSA, but also makes MPKCs faster and keeps them competitive at 80-bit security when properly implemented. These techniques became outdated due to emergence of new instruction sets and higher requirements on security. In this paper, we review how MPKC signatures changes from 2009 including new parameters (from a newer security level at 128-bit), crypto-safe implementations, and the impact of new AVX2 and AESNI instructions. We also present new techniques on evaluating multivariate polynomials, multiplications of large finite fields by additive Fast Fourier Transforms, and constant time linear solvers.

Deterministic ID-based signatures are digital signatures where secret keys are probabilistically generated by a key generation center while the signatures are generated deterministically. Although the deterministic ID-based signatures are useful for both systematic and cryptographic applications, to the best of our knowledge, there is no scheme with a tight reduction proof. Loosely speaking, since the security is downgraded through dependence on the number of queries by an adversary, a tighter reduction for the security of a scheme is desirable, and this reduction must be as close to the difficulty of its underlying hard problem as possible. In this work, we discuss mathematical features for a tight reduction of deterministic ID-based signatures, and show that the scheme by Selvi et al. (IWSEC 2011) is tightly secure by our new proof framework under a selective security model where a target identity is designated in advance. Our proof technique is versatile, and hence a reduction cost becomes tighter than the original proof even under an adaptive security model. We furthermore improve the scheme by Herranz (The Comp. Jour., 2006) to prove tight security in the same manner as described above. We furthermore construct an aggregate signature scheme with partial aggregation, which is a key application of deterministic ID-based signatures, from the improved scheme.

In this paper, we propose a new generic construction of signatures from trapdoor commitments with strong openings in the random oracle model. Our construction is very efficient in the sense that signatures consist of just a single decommitment of the underlying commitment scheme, and verification corresponds to verifying this decommitment against a commitment derived via a hash function. Furthermore, assuming the commitment scheme provides sufficiently strong statistical hiding and trapdoor opening properties, the reduction of the security of the signature scheme to the binding property of the commitment scheme is tight. To instantiate our construction, we propose two new commitment schemes with strong openings. Both of these are statistically hiding, and have binding properties based on a Diffie-Hellman inversion problem and factoring, respectively. The signature schemes obtained from these are very efficient; the first matches the performance of BLS signatures, which currently provides the shortest signatures, and the second provides signatures of similar length to the shortest version of Rabin-Williams signatures while still being tightly related to factoring.