In recent years, blockchain has been widely applied in the Internet of Things (IoT). Blockchain oracle, as a bridge for data communication between blockchain and off-chain, has also received significant attention. However, the numerous and heterogeneous devices in the IoT pose great challenges to the efficiency and security of data acquisition for oracles. We find that the matching relationship between data sources and oracle nodes greatly affects the efficiency and service quality of the entire oracle system. To address these issues, this paper proposes a distributed and efficient oracle solution tailored for the IoT, enabling fast acquisition of real-time off-chain data. Specifically, we first design a distributed oracle architecture that combines both Trusted Execution Environment (TEE) devices and ordinary devices to improve system scalability, considering the heterogeneity of IoT devices. Secondly, based on the trusted node information provided by TEE, we determine the matching relationship between nodes and data sources, assigning appropriate nodes for tasks to enhance system efficiency. Through simulation experiments, our proposed solution has been shown to effectively improve the efficiency and service quality of the system, reducing the average response time by approximately 9.92% compared to conventional approaches.

In 2005, Nandi introduced a class of double-block-length compression functions hπ(x) := (h(x), h(π(x))), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damgård hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry’s compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.

The Schnorr signature is one of the representative signature schemes and its security was widely discussed. In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schröder showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.

Aggregate signature (AS) schemes enable anyone to compress signatures under different keys into one. In sequential aggregate signature (SAS) schemes, the aggregate signature is computed incrementally by the sighers. Several trapdoor-permutation-based SAS have been proposed. In this paper, we give a constructions of SAS based on the first SAS scheme with lazy verification proposed by Brogle et al. in ASIACRYPT 2012. In Brogle et al.'s scheme, the size of the aggregate signature is linear of the number of the signers. In our scheme, the aggregate signature has constant length which satisfies the original ideal of compressing the size of signatures.

IGE mode used in Telegram's customized protocol has not been fully investigated in terms of post-quantum security. In this letter, we show that IGE mode is IND-qCPA insecure by Simon's algorithm, assuming that the underlying block cipher is a standard-secure pseudorandom function (sPRF). Under a stronger assumption that the block cipher is a quantum-secure pseudorandom function (qPRF), IND-qCPA security of IGE mode is proved using one-way to hiding lemma.

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.

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 recent years, Fischlin and Fleischhacker showed the impossibility of proving the security of specific types of FS-type signatures, the signatures constructed by the Fiat-Shamir transformation, via a single-instance reduction in the non-programmable random oracle model (NPROM, for short). In this paper, we pose a question whether or not the impossibility of proving the security of any FS-type signature can be shown in the NPROM. For this question, we show that each FS-type signature cannot be proven to be secure via a key-preserving reduction in the NPROM from the security against the impersonation of the underlying identification scheme under the passive attack, as long as the identification scheme is secure against the impersonation under the active attack. We also show the security incompatibility between the security of some FS-type signatures in the NPROM via a single-instance key-preserving reduction and the underlying cryptographic assumptions. By applying this result to the Schnorr signature, one can prove the incompatibility between the security of the Schnorr signature in this situation and the discrete logarithm assumption, whereas Fischlin and Fleischhacker showed that such an incompatibility cannot be proven via a non-key-preserving reduction.

Rational proofs, introduced by Azar and Micali (STOC 2012), are a variant of interactive proofs in which the prover is rational, and may deviate from the protocol for increasing his reward. Guo et al. (ITCS 2014) demonstrated that rational proofs are relevant to delegation of computation. By restricting the prover to be computationally bounded, they presented a one-round delegation scheme with sublinear verification for functions computable by log-space uniform circuits with logarithmic depth. In this work, we study rational proofs in which the verifier is also rational, and may deviate from the protocol for decreasing the prover's reward. We construct a three-message delegation scheme with sublinear verification for functions computable by log-space uniform circuits with polylogarithmic depth in the random oracle model.

Structured signatures are digital signatures where relationship between signers is guaranteed in addition to the validity of individually generated data for each signer, and have been expected for the digital right management. Nevertheless, we mention that there is no scheme with a tight security reduction, to the best of our knowledge. Loosely speaking, it means that the security is downgraded against an adversary who obtains a large amount of signatures. Since contents are widely utilized in general, achieving a tighter reduction is desirable. Based on this background, we propose the first structured signature scheme with a tight security reduction in the conventional public key cryptography and the one with a rigorous reduction proof in the ID-based cryptography via our new proof method. Moreover, the security of our schemes can be proven under the CDH assumption which is the most standard. Our schemes are also based on bilinear maps whose implementation can be provided via well-known cryptographic libraries.

Two new authenticated key agreement protocols in the certificateless setting are presented in this paper. Both are proved secure in the extended Canetti-Krawczyk model, under the BDH assumption. The first one is more efficient than the Lippold et al.'s (LBG) protocol, and is proved secure in the same security model. The second protocol is proved secure under the Swanson et al.'s security model, a weaker model. As far as we know, our second proposed protocol is the first one proved secure in the Swanson et al.'s security model. If no pre-computations are done, the first protocol is about 26% faster than LBG, and the second protocol is about 49% faster than LBG, and about 31% faster than the first one. If pre-computations of some operations are done, our two protocols remain faster.

In this paper, we propose an identity-based authenticated key exchange (ID-AKE) protocol that is secure in the identity-based extended Canetti-Krawczyk (id-eCK) model in the random oracle model under the gap Bilinear Diffie-Hellman assumption. The proposed ID-AKE protocol is the most efficient among the existing ID-AKE protocols that is id-eCK secure, and it can be extended to use in asymmetric pairing.

This paper provides a sufficient condition to construct timed-release public-key encryption (TRPKE), where the constructed TRPKE scheme guarantees strong security against malicious time servers, proposed by Chow et al., and strong security against malicious receivers, defined by Cathalo et al., in the random oracle model if the component IBE scheme is IND-ID-CPA secure, the component PKE scheme is IND-ID-CPA secure, and the PKE scheme satisfies negligible γ-uniformity for every public key. Although Chow et al. proposed a strongly secure TRPKE scheme, which is concrete in the standard model, to the best of our knowledge, the proposed construction is the first generic one for TRPKE that guarantees strong security even in the random oracle model.

We propose a security model, referred as g-eCK model, for group key exchange that captures essentially all non-trivial leakage of static and ephemeral secret keys of participants, i.e., group key exchange version of extended Canetti-Krawczyk (eCK) model. Moreover, we propose the first one-round tripartite key exchange (3KE) protocol secure in the g-eCK model under the gap Bilinear Diffie-Hellman (gap BDH) assumption and in the random oracle model.

This paper analyzes security of sequential multiple encryptions based on asymmetric key encryptions, and shows that a sequential construction of secure multiple encryptions exists. The sequential multiple encryption scheme can be proved to be indistinguishable against chosen ciphertext attacks for multiple encryptions (IND-ME-CCA), where the adversary can access to the decryption oracle of the multiple encryption, even when all the underlying encryptions of the multiple encryption are indistinguishable against chosen plaintext attacks (IND-CPA). We provide an extended security notion of sequential multiple encryptions, in which the adversary is allowed to access decryption oracles of the underlying encryptions in addition to the multiple encryption, and show that our constructed scheme satisfies the security notion when all the underlying encryptions are indistinguishable against chosen ciphertext attacks (IND-CCA).

We analyze the security notion of information-theoretic secrecy against an adversary who can make adaptive queries to the decryption oracle, and show that it is equivalent to requiring that the encryption scheme can perfectly encrypt +1 different messages. This immediately yields a lower bound on the key length and an optimal construction, namely (+1)-wise independent permutations. This also gives an operational interpretation to the notion of decryption oracles in information-theoretic security.

Verifying the signing order is sometimes very important in multisignature schemes. A multisignature scheme in which the signing order can be verified is called structured multisignature scheme and many such schemes have been proposed so far. However, there are not many structured multisignature schemes utilizing an algebraic structure of underlying algebraic operation. Ohmori, Chida, Shizuya and Nishizeki have proposed a structured multisignature scheme by utilizing a non-commutative ring homomorphism. Since their scheme does not fully reflect the structure of signers and its rigorous security analysis is not provided, we construct an improved structured multisignature scheme overcoming these problems by utilizing the non-commutative ring homomorphism in a different way and discuss its rigorous security against various attacks, including signer structure forgery, rogue key attack and attack-0 under the discrete logarithm assumption. As far as we know, the scheme in [30], which does not use non-commutative ring homomorphism, guarantees the most rigorous security but the number of signers is restricted in order to prevent attack-0. In contrast, our scheme overcomes attack-0 by virtue of a ring homomorphism and no restriction is imposed on the number of signers.

In this paper, we present a new methodology, called a random oracle (RO) transformation, for designing IND-CCA secure PKE schemes in the standard model from schemes in the RO model. Unlike the RO methodology [3], [19], the security of the original scheme in the RO model does not necessarily have to be identical with that of the scheme resulting from the RO transformation. We then introduce a new notion, IND-INS-CCA security, and show how to obtain IND-CCA secure PKE schemes by instantiating ROs in IND-INS-CCA secure PKE schemes. Furthermore, we introduce another new notion, a strong pseudorandom function (PRF) family associated with a trapdoor one-way permutation generator (briefly, -SPRF family), which can be regarded as an enhanced PRF family, so that the resulting PKE scheme becomes quite practical.

Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can easily confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks just the value needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

This work focuses on a vulnerability of hash functions due to sloppy usages or implementations in the real world. If our cryptographic research community succeeded in the development of a perfectly secure random function as the random oracle, it might be broken in some sense by invalid uses. In this paper, we propose a new variant of the random oracle model in order to analyze the security of cryptographic protocols under the situation of an invalid use of hash functions. Our model allows adversaries to obtain contents of the hash list of input and output pairs arbitrarily. Also, we analyze the security of several prevailing protocols (FDH, OAEP, Cramer-Shoup cryptosystem, Kurosawa-Desmedt cryptosystem, NAXOS) in our model. As the result of analyses, we clarify that FDH and Cramer-Shoup cryptosystem are still secure but others are insecure in our model. This result shows the separation between our model and the standard model.