We present a forward-secure public-key encryption (PKE) scheme without key update, i.e. both public and private keys are immutable. In contrast, prior forward-secure PKE schemes achieve forward security by constantly updating the secret keys. Our scheme is based on witness encryption by Garg et al. (STOC 2013) and a proof-of-stake blockchain with the distinguishable forking property introduced by Goyal et al. (TCC 2017), and ensures a ciphertext cannot be decrypted more than once, thereby rendering a compromised secret key useless with respect to decryption of past ciphertext the legitimate user has already decrypted. In this work, we formalize the notion of blockchain-based forward-secure PKE, show the feasibility of constructing a forward-secure PKE scheme without key update, and discuss interesting properties of our scheme such as post-compromise security.

The Internet of Things (IoT) implicates an infrastructure that creates new value by connecting everything with communication networks, and its construction is rapidly progressing in anticipation of its great potential. Enhancing the security of IoT is an essential requirement for supporting IoT. For ensuring IoT security, it is desirable to create a situation that even a terminal component device with many restrictions in computing power and energy capacity can easily verify other devices and data and communicate securely by the use of public key cryptography. To concretely achieve the big goal of penetrating public key cryptographic technology to most IoT end devices, we elaborated the secure cryptographic unit (SCU) built in a low-end microcontroller chip. The SCU comprises a hardware cryptographic engine and a built-in access controlling functionality consisting of a software gate and hardware gate. This paper describes the outline of our SCU construction technology's research and development and prospects.

Replayable chosen ciphertext (RCCA) security was introduced by Canetti, Krawczyk, and Nielsen (CRYPTO'03) in order to handle an encryption scheme that is “non-malleable except tampering which preserves the plaintext.” RCCA security is a relaxation of CCA security and a useful security notion for many practical applications such as authentication and key exchange. Canetti et al. defined non-malleability against RCCA (NM-RCCA), indistinguishability against RCCA (IND-RCCA), and universal composability against RCCA (UC-RCCA). Moreover, they proved that these three security notions are equivalent when considering a PKE scheme whose plaintext space is super-polynomially large. Among these three security notions, NM-RCCA seems to play the central role since RCCA security was introduced in order to capture “non-malleability except tampering which preserves the plaintext.” However, their definition of NM-RCCA is not a natural extension of that of original non-malleability, and it is not clear whether their NM-RCCA captures the requirement of original non-malleability. In this paper, we propose definitions of indistinguishability-based and simulation-based non-malleability against RCCA by extending definitions of original non-malleability. We then prove that these two notions of non-malleability and IND-RCCA are equivalent regardless of the size of plaintext space of PKE schemes.

Public-key encryption with keyword search (PEKS) is a cryptographic primitive that allows us to search for particular keywords over ciphertexts without recovering plaintexts. By using PEKS in cloud services, users can outsource their data in encrypted form without sacrificing search functionality. Concerning PEKS that can specify logical disjunctions and logical conjunctions as a search condition, it is known that such PEKS can be (generically) constructed from anonymous attribute-based encryption (ABE). However, it is not clear whether it is possible to construct this types of PEKS without using ABE which may require large computational/communication costs and strong mathematical assumptions. In this paper, we show that ABE is crucial for constructing PEKS with the above functionality. More specifically, we give a generic construction of anonymous key-policy ABE from PEKS whose search condition is specified by logical disjunctions and logical conjunctions. Our result implies such PEKS always requires large computational/communication costs and strong mathematical assumptions corresponding to those of ABE.

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.

In a large-scale information-sharing platform, such as a cloud storage, it is often required to not only securely protect sensitive information but also recover it in a reliable manner. Public-key encryption with non-interactive opening (PKENO) is considered as a suitable cryptographic tool for this requirement. This primitive is an extension of public-key encryption which enables a receiver to provide a non-interactive proof which confirms that a given ciphertext is decrypted to some public plaintext. In this paper, we present a Tag-KEM/DEM framework for PKENO. In particular, we define a new cryptographic primitive called a Tag-KEM with non-interactive opening (Tag-KEMNO), and prove the KEM/DEM composition theorem for this primitives, which ensures a key encapsulation mechanism (KEM) and a data encapsulation mechanism (DEM) can be, under certain conditions, combined to form a secure PKENO scheme. This theorem provides a secure way of combining a Tag-KEMNO scheme with a DEM scheme to construct a secure PKENO scheme. Using this framework, we explain the essence of existing constructions of PKENO. Furthermore, we present four constructions of Tag-KEMNO, which yields four PKENO constructions. These PKENO constructions coincide with the existing constructions, thereby we explain the essence of these existing constructions. In addition, our Tag-KEMNO framework enables us to expand the plaintext space of a PKENO scheme. Some of the previous PKENO schemes are only able to encrypt a plaintext of restricted length, and there has been no known way to expand this restricted plaintext space to the space of arbitrary-length plaintexts. Using our framework, we can obtain a PKENO scheme with the unbounded-length plaintext space by modifying and adapting such a PKENO scheme with a bounded-length plaintext space.

One of major ideas to design a multivariate public key cryptosystem (MPKC) is to generate its quadratic forms by a polynomial map over an extension field. In fact, Matsumoto-Imai's scheme (1988), HFE (Patarin, 1996), MFE (Wang et al., 2006) and multi-HFE (Chen et al., 2008) are constructed in this way and Sflash (Akkar et al., 2003), Quartz (Patarin et al., 2001), Gui (Petzoldt et al, 2015) are variants of these schemes. An advantage of such extension field type MPKCs is to reduce the numbers of variables and equations to be solved in the decryption process. In the present paper, we study the security of MPKCs whose quadratic forms are derived from a “quadratic” map over an extension field and propose a new attack on such MPKCs. Our attack recovers partial information of the secret affine maps in polynomial time when the field is of odd characteristic. Once such partial information is recovered, the attacker can find the plain-text for a given cipher-text by solving a system of quadratic equations over the extension field whose numbers of variables and equations are same to those of the system of quadratic equations used in the decryption process.

We present a new notion of public-key encryption, called multi-divisible on-line/off-line encryptions, in which partial ciphertexts can be computed and made publicly available for the recipients before the recipients' public key and/or the plaintexts are determined. We formalize its syntax and define several security notions with regard to the level of divisibility, the number of users, and the number of encryption (challenge) queries per user. Furthermore, we show implications and separations between these security notions and classify them into three categories. We also present concrete multi-divisible on-line/off-line encryption schemes. The schemes allow the computationally-restricted and/or bandwidth-restricted devices to transmit ciphertexts with low computational overhead and/or low-bandwidth network.

In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. In this work, we characterize such lazy parties, who are regarded as honest parties, but are unwilling to perform a costly task when they are not concerned about the security. Specifically, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either perfect randomness or a fixed string. We model lazy parties as rational players who behave rationally to maximize their utilities, and define a security game between the parties and an adversary. Since a standard secure encryption scheme does not work in this setting, we provide constructions of secure encryption schemes in various settings.

Rainbow is one of signature schemes based on the problem solving a set of multivariate quadratic equations. While its signature generation and verification are fast and the security is presently sufficient under suitable parameter selections, the key size is relatively large. Recently, Quaternion Rainbow — Rainbow over a quaternion ring — was proposed by Yasuda, Sakurai and Takagi (CT-RSA'12) to reduce the key size of Rainbow without impairing the security. However, a new vulnerability emerges from the structure of quaternion ring; in fact, Thomae (SCN'12) found that Quaternion Rainbow is less secure than the same-size original Rainbow. In the present paper, we further study the structure of Quaternion Rainbow and show that Quaternion Rainbow is one of sparse versions of the Rainbow. Its sparse structure causes a vulnerability of Quaternion Rainbow. Especially, we find that Quaternion Rainbow over even characteristic field, whose security level is estimated as about the original Rainbow of at most 3/4 by Thomae's analysis, is almost as secure as the original Rainbow of at most 1/4-size.

We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.

Recently, there have been many studies on constructing cryptographic primitives that are secure even if some secret information leaks. In this paper, we consider the problem of constructing public-key encryption schemes that are resilient to leaking the randomness used in the encryption algorithm. In particular, we consider the case in which public-key encryption schemes are constructed from the KEM/DEM framework, and the leakage of randomness in the encryption algorithms of KEM and DEM occurs independently. For this purpose, we define a new security notion for KEM. Then we provide a generic construction of a public-key encryption scheme that is resilient to randomness leakage from any KEM scheme satisfying this security. Also we construct a KEM scheme that satisfies the security from hash proof systems.

This paper proposes methods for “restricting the message space” of public-key encryption, by allowing a third party to verify whether a given ciphertext does not encrypt some message which is previously specified as a “bad” (or “problematic”) message. Public-key encryption schemes are normally designed not to leak even partial information of encrypted plaintexts, but it would be problematic in some circumstances. This higher level of confidentiality could be abused, as some malicious parties could communicate with each other, or could talk about some illegal topics, using an ordinary public key encryption scheme with help of the public-key infrastructure. It would be undesirable considering the public nature of PKI. The primitive of restrictive public key encryption will help this situation, by allowing a trusted authority to specify a set of “bad” plaintexts, and allowing every third party to detect ciphertexts that encrypts some of the specified “bad” plaintext. The primitive also provides strong confidentiality (of indistinguishability type) of the plaintext when it is not specified as “bad.” In this way, a third party (possible a gateway node of the network) can examine a ciphertext (which comes from the network) includes an allowable content or not, and only when the ciphertext does not contain forbidden message, the gateway transfers the ciphertext to a next node. In this paper, we formalize the above requirements and provide two constructions that satisfied the formalization. The first construction is based on the techniques of Teranishi et al. (IEICE Trans. Fundamentals E92-A, 2009), Boudot (EUROCRYPT 2000), and Nakanishi et al. (IEICE Trans. Fundamentals E93-A, 2010), which are developed in the context of (revocation of) group signature. The other construction is based on the OR-proof technique. The first construction has better performance when very few messages are specified as bad, while the other does when almost all of messages are specified as bad (and only very few messages are allowed to encrypt).

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.

The multivariate public key cryptosystem (MPKC), which is based on the problem of solving a set of multivariate systems of quadratic equations over a finite field, is expected to be secure against quantum attacks. Although there are several existing schemes in MPKC that survived known attacks and are much faster than RSA and ECC, there have been few discussions on security against physical attacks, aside from the work of Okeya et al. (2005) on side-channel attacks against Sflash. In this study, we describe general fault attacks on MPKCs including Big Field type (e.g. Matsumoto-Imai, HFE and Sflash) and Stepwise Triangular System (STS) type (e.g. UOV, Rainbow and TTM/TTS). For both types, recovering (parts of) the secret keys S,T with our fault attacks becomes more efficient than doing without them. Especially, on the Big Field type, only single fault is sufficient to recover the secret keys.

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.

In [1], Bellare, Boldyreva, and Micali addressed the security of public-key encryptions (PKEs) in a multi-user setting (called the BBM model in this paper). They showed that although the indistinguishability in the BBM model is induced from that in the conventional model, its reduction is far from tight in general, and this brings a serious key length problem. In this paper, we discuss PKE schemes in which the IND-CCA security in the BBM model can be obtained tightly from the IND-CCA security. We call such PKE schemes IND-CCA secure in the BBM model with invariant security reductions (briefly, SR-invariant IND-CCABBM secure). These schemes never suffer from the underlying key length problem in the BBM model. We present three instances of an SR-invariant IND-CCABBM secure PKE scheme: the first is based on the Fujisaki-Okamoto PKE scheme [7], the second is based on the Bellare-Rogaway PKE scheme [3], and the last is based on the Cramer-Shoup PKE scheme [5].

We propose an anonymous Hierarchical Identity-Based Encryption (anonymous HIBE) scheme with short ciphertexts. Prior to our work, most anonymous HIBE schemes have long ciphertexts increased according to the hierarchical depth of recipient. The size of the ciphertext in our scheme does not depend on the depth of the hierarchy. Moreover, our scheme achieves the lowest computational cost because during the decryption phase the computational cost of decryption is constant. The security can be proven under reasonable assumptions without using random oracles. Our scheme achieves selective-ID security notion.

The linear Piece In Hand (PH, for short) matrix method with random variables was proposed in our former work. It is a general prescription which can be applicable to any type of multivariate public-key cryptosystems for the purpose of enhancing their security. Actually, we showed, in an experimental manner, that the linear PH matrix method with random variables can certainly enhance the security of HFE against the Grobner basis attack, where HFE is one of the major variants of multivariate public-key cryptosystems. In 1998 Patarin, Goubin, and Courtois introduced the plus method as a general prescription which aims to enhance the security of any given MPKC, just like the linear PH matrix method with random variables. In this paper we prove the equivalence between the plus method and the primitive linear PH matrix method, which is introduced by our previous work to explain the notion of the PH matrix method in general in an illustrative manner and not for a practical use to enhance the security of any given MPKC. Based on this equivalence, we show that the linear PH matrix method with random variables has the substantial advantage over the plus method with respect to the security enhancement. In the linear PH matrix method with random variables, the three matrices, including the PH matrix, play a central role in the secret-key and public-key. In this paper, we clarify how to generate these matrices and thus present two probabilistic polynomial-time algorithms to generate these matrices. In particular, the second one has a concise form, and is obtained as a byproduct of the proof of the equivalence between the plus method and the primitive linear PH matrix method.

So far, in almost all of the practical public key encryption schemes, hash functions which are dependent on underlying cyclic groups are necessary, e.g., H:{0,1}* → Zp where p is the order of the underlying cyclic group, and it could be required to construct a dedicated hash function for each public key. The motivation of this note is derived from the following two facts: 1). there is an important technical gap between hashing to a specific prime-order group and hashing to a certain length bit sequence, and this could cause a security hole; 2). surprisingly, to our best knowledge, there is no explicit induction that one could use the simple construction, instead of tailor-made hash functions. In this note, we investigate this issue and provide the first rigorous discussion that in many existing schemes, it is possible to replace such hash functions with a target collision resistant hash function H:{0,1}* → {0,1}k, where k is the security parameter. We think that it is very useful and could drastically save the cost for the hash function implementation in many practical cryptographic schemes.