In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime c by just using additions, subtractions and multiplications ...on the ring. If the characteristic of an underlying ring is public and coprime to c, then it is easy to compute the inverse of c by using the extended Euclidean algorithm. On the other hand, if the characteristic is hidden, it seems difficult to compute it. For discussing the generic hardness of the inversion problem, we first extend existing generic ring models to capture a ring of an unknown characteristic. Then we prove that there is no generic algorithm to solve the inversion problem in our model when the underlying ring is isomorphic to Zp for a randomly chosen prime p assuming the hardness of factorization of an unbalanced modulus. We also study a relation between the inversion problem on a ring and a self-bilinear map. Namely, we give a construction of a self-bilinear map based on a ring on which the inversion problem is hard, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t. the resulting sef-bilinear map.
Chosen-ciphertext security is a central goal in designing a secure public-key encryption scheme, and it is also important that the chosen-ciphertext security is tightly reduced to some ...well-established hard problem. Moreover, it is more important to have a tight reduction in the multi-user multi-challenge setting, since a tight security reduction in the single-user single-challenge setting generally does not imply a tight reduction to the multi-user multi-challenge setting. We propose the first fully tightly secure and practical public-key encryption scheme which is chosen-ciphertext secure in the multi-user multi-challenge setting in the random oracle model. The scheme is proven secure under the decisional Diffie-Hellman assumption in a pairing-free group. The ciphertext overhead of our scheme is two group elements and two exponents.
It is an important research area to construct a cryptosystem that satisfies the security for multi-user setting. In addition, it is desirable that such a cryptosystem is tightly secure and the ...ciphertext size is small. For IND-CCA public key encryption schemes for multi-user setting with constant-size ciphertexts tightly secure under the DH assumptions, in 2020, Y. Sakai and G. Hanaoka firstly proposed such a scheme (implicitly based on hybrid encryption paradigm) under the DDH assumption. More recently, Y. Lee et al. proposed such a hybrid encryption scheme (with slightly stronger security) where the assumption for the KEM part is weakened to the CDH assumption. In this paper, we revisit the twin-DH hashed ElGamal KEM with even shorter ciphertexts than those schemes, and prove that its IND-CCA security for multi-user setting is in fact tightly reducible to the CDH assumption.
Multi-signatures have seen renewed interest due to their application to blockchains, e.g., BIP 340 (one of the Bitcoin improvement proposals), which has triggered the proposals of several new schemes ...with improved efficiency. However, many previous works have a “loose” security reduction (a large gap between the difficulty of the security assumption and breaking the scheme) or depend on strong idealized assumptions such as the algebraic group model (AGM). This makes the achieved level of security uncertain when instantiated in groups typically used in practice, and it becomes unclear for developers how secure a given scheme is for a given choice of security parameters. Thus, this leads to the question “what kind of schemes can we construct that achieves tight security based on standard assumptions?”. In this paper, we show a simple two-round tightly-secure pairing-based multi-signature scheme based on the computation Diffie-Hellman problem in the random oracle model. This proposal is the first two-round multi-signature scheme that achieves tight security based on a computational assumption and supports key aggregation. Furthermore, our scheme reduce the signature bit size by 19% compared with the shortest existing tightly-secure DDH-based multi-signature scheme. Moreover, we implemented our scheme in C++ and confirmed that it is efficient in practice; to complete the verification takes less than 1ms with a total (computational) signing time of 13ms for under 100 signers. The source code of the implementation is published as OSS.
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.
Deniable ring authentication enables a prover in some group (called a
ring
) to authenticate a message to a verifier using its secret key while at the same time allowing the prover to deny ever ...having interacted with the verifier. This primitive furthermore guarantees the anonymity of the prover in the sense that the verifier will learn nothing about the prover’s identity except that it is included in the ring. In this work, we propose a new generic construction of two-round concurrently deniable ring authentication in the random oracle model. Our generic construction is based on any
IND-CPA
secure broadcast encryption (BE) scheme. Instantiating the underlying
IND-CPA
secure BE scheme with the schemes proposed by Agrawal and Yamada (EUROCRYPT 2020) or Agrawal, Wichs, and Yamada (TCC 2020), we obtain the first two-round concurrently deniable ring authentication scheme with optimal efficiency in an asymptotic sense. Here, by optimal efficiency, we mean that all of the sizes of a public parameter and secret keys, the communication costs, and the number of pairing operations are independent of
n
, where
n
is the number of users in a ring. In addition to these main instantiations, through our generic construction, we further obtain various two-round concurrently deniable ring authentication schemes.
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.
In this paper, we construct multi-key homomorphic and fully homomorphic encryption (resp. MKHE and MKFHE) schemes with malicious circuit privacy. Our schemes are based on learning with errors (LWE) ...besides appropriate circular security assumptions. In contrast, the previous maliciously circuit-private MKFHE scheme by Chongchitmate and Ostrovsky (PKC, 2017) is based on the non-standard decisional small polynomial ratio (DSPR) assumption with a super-polynomial modulus, besides ring learning with errors and circular security assumptions. We note that it was shown by Albrecht et al. (CRYPTO, 2016) that there exists a sub-exponential time attack against this type of DSPR assumption. The main building block of our maliciously circuit-private MKFHE scheme is a (plain) MKFHE scheme by Brakerski et al. (TCC, 2017), and the security of our schemes is proven under the hardness of LWE with sub-exponential modulus-to-noise ratio and circular security assumptions related to the Brakerski et al. scheme. Furthermore, based on our MKFHE schemes, we construct four-round multi-party computation (MPC) protocols with circuit privacy against a semi-honest server and malicious clients in the plain model. The protocols are obtained by combining our schemes with a maliciously sender-private oblivious transfer protocol and a circuit garbling scheme, all of which can be instantiated only assuming LWE.
Fault-tolerant aggregate signature (FT-AS) is a special type of aggregate signature that is equipped with the functionality for tracing signers who generated invalid signatures in the case an ...aggregate signature is detected as invalid. In existing FT-AS schemes (whose tracing functionality requires multi-rounds), a verifier needs to send a feedback to an aggregator for efficiently tracing the invalid signer(s). However, in practice, if this feedback is not responded to the aggregator in a sufficiently fast and timely manner, the tracing process will fail. Therefore, it is important to estimate whether this feedback can be responded and received in time on a real system. In this work, we measure the total processing time required for the feedback by implementing an existing FT-AS scheme, and evaluate whether the scheme works without problems in real systems. Our experimental results show that the time required for the feedback is 605.3ms for a typical parameter setting, which indicates that if the acceptable feedback time is significantly larger than a few hundred ms, the existing FT-AS scheme would effectively work in such systems. However, there are situations where such feedback time is not acceptable, in which case the existing FT-AS scheme cannot be used. Therefore, we further propose a novel FT-AS scheme that does not require any feedback. We also implement our new scheme and show that a feedback in this scheme is completely eliminated but the size of its aggregate signature (affecting the communication cost from the aggregator to the verifier) is 144.9 times larger than that of the existing FT-AS scheme (with feedbacks) for a typical parameter setting, and thus has a trade-off between the feedback waiting time and the communication cost from the verifier to the aggregator with the existing FT-AS scheme.
PDF
