Reflections on the security proofs of Boneh-Franklin identity-based encryption scheme

In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.     

On the relations between non-interactive key distribution,identity-based encryption and trapdoor discrete log groups

This paper investigates the relationships between identity-based non-interactive key distribution (ID-NIKD) and identity-based encryption (IBE). It provides a new security model for ID-NIKD, and a construction that converts a secure ID-NIKD scheme satisfying certain conditions into a secure IBE scheme. This conversion is used to explain the relationship between the ID-NIKD scheme of Sakai, Ohgishi and Kasahara and the IBE scheme of Boneh and Franklin. The paper then explores the construction of ID-NIKD and IBE schemes from general trapdoor discrete log groups. Two different concrete instantiations for such groups provide new, provably secure ID-NIKD and IBE schemes. These schemes are suited to applications in which the Trusted Authority is computationally well-resourced, but clients performing encryption/decryption are highly constrained.      

Efficient revocable identity-based encryption via subset difference methods

Providing an efficient revocation mechanism for identity-based encryption (IBE) is very important since a user’s credential (or private key) can be expired or revealed. revocable IBE (RIBE) is an extension of IBE that provides an efficient revocation mechanism. Previous RIBE schemes essentially use the complete subtree (CS) scheme of Naor, Naor and Lotspiech (CRYPTO 2001) for key revocation. In this paper, we present a new technique for RIBE that uses the efficient subset difference (SD) scheme of Naor et al. instead of using the CS scheme to improve the size of update keys. Following our new technique, we first propose an efficient RIBE scheme in prime-order bilinear groups by combining the IBE scheme of Boneh and Boyen and the SD scheme and prove its selective security under the standard assumption. Our RIBE scheme is the first RIBE scheme in bilinear groups that has O(r) number of group elements in an update key where r is the number of revoked users. Next, we also propose another RIBE scheme in composite-order bilinear groups and prove its full security under static assumptions. Our RIBE schemes also can be integrated with the layered subset difference scheme of Halevy and Shamir (CRYPTO 2002) to reduce the size of a private key.     

Efficient identity-based encryption with Hierarchical key-insulation from HIBE

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth. In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (Des. Codes Cryptography 89(7):1535–1574, 2021). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters’ sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the k-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.’s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.’s scheme in the sense of the sizes of master public/secret keys.

     

Revocable hierarchical identity-based encryption with shorter private keys and update keys

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that supports the revocation of user’s private keys to manage the dynamic credentials of users in a system. Many different RHIBE schemes were proposed previously, but they are not efficient in terms of the private key size and the update key size since the depth of a hierarchical identity is included as a multiplicative factor. In this paper, we propose efficient RHIBE schemes with shorter private keys and update keys and small public parameters by removing this multiplicative factor. To achieve our goals, we first present a new HIBE scheme with the different generation of private keys such that a private key can be simply derived from a short intermediate private key. Next, we show that two efficient RHIBE schemes can be built by combining our HIBE scheme, an IBE scheme, and a tree based broadcast encryption scheme in a modular way.     

Efficient hybrid encryption from ID-based encryption

This paper deals with generic transformations from ID-based key encapsulation mechanisms (IBKEM) to hybrid public-key encryption (PKE). The best generic transformation known until now is by Boneh and Katz and requires roughly 704-bit overhead in the ciphertext. We present new generic transformations that are applicable to partitioned IBKEMs. A partitioned IBKEM is an IBKEM that provides some extra structure. Such IBKEMs are quite natural and in fact nearly all known IBKEMs have this additional property. Our first transformation yields chosen-ciphertext secure PKE schemes from selective-ID secure partitioned IBKEMs with a 256-bit overhead in ciphertext size plus one extra exponentiation in encryption/decryption. As the central tool a Chameleon Hash function is used to map the identities. We also propose other methods to remove the use of Chameleon Hash, which may be of independent technical interest. Applying our transformations to existing IBKEMs we propose a number of novel PKE schemes with different trade-offs. In some concrete instantiations the Chameleon Hash can be made “implicit” which results in improved efficiency by eliminating the additional exponentiation. Since our transformations preserve the public verifiability property of the IBE schemes it is possible to extend our results to build threshold hybrid PKE schemes. We show an analogue generic transformation in the threshold setting and present a concrete scheme which results in the most efficient threshold PKE scheme in the standard model.     

Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can “freely” perform the operation inevitably means that ciphertexts are malleable, and it is well-known that adaptive chosen ciphertext (CCA) security and the homomorphic property can never be achieved simultaneously. In this paper, we show that CCA security and the homomorphic property can be simultaneously handled in situations that the user(s) who can perform homomorphic operations on encrypted data should be controlled/limited, and propose a new concept of homomorphic public-key encryption, which we call keyed-homomorphic public-key encryption (KH-PKE). By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation. To construct KH-PKE schemes, we introduce a new concept, transitional universal property, and present a practical KH-PKE scheme with multiplicative homomorphic operations from the decisional Diffie-Hellman (DDH) assumption. For \(\ell \)-bit security, our DDH-based KH-PKE scheme yields only \(\ell \)-bit longer ciphertext size than that of the Cramer–Shoup PKE scheme. Finally, we consider an identity-based analogue of KH-PKE, called keyed-homomorphic identity-based encryption and give its concrete construction from the Gentry IBE scheme.     

Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Affine message authentication code (MAC) and delegatable affine MAC turn out to be useful tools for constructing identity-based encryption (IBE) and hierarchical IBE (HIBE), as shown in Blazy, Kiltz and Pan’s (BKP) creative work in CRYPTO (2014). An important result obtained by BKP is IBE of tight PR-ID-CPA security, i.e., tight IND-ID-CPA security together with ciphertext pseudorandomness (PR). However, the problem of designing tightly PR-ID-CCA2 secure IBE remains open. We note that the CHK transformation does not preserve ciphertext pseudorandomness when converting IND-ID-CPA secure 2-level HIBE to IND-ID-CCA2 secure IBE. In this paper, we solve this problem with a new approach. We introduce a new concept called De-randomized delegatable affine MAC and define for it weak APR-CMA security. We construct such a MAC with a tight security reduction to the Matrix DDH assumption, which includes the k-Linear and DDH assumptions. We present a paradigm for constructing PR-ID-CCA2 secure IBE, which enjoys both ciphertext pseudorandomness and IND-ID-CCA2 security, from De-randomized delegatable affine MAC and Chameleon hashing. The security reduction is tightness preserving. It provides another approach to IND-ID-CCA2 security besides the CHK transformation. By instantiating the paradigm with our specific De-randomized delegatable affine MAC, we obtain the first IBE of tight PR-ID-CCA2 security from the Matrix DDH assumption over pairing groups of prime order. Our IBE also serves as the first tightly IND-ID-CCA2 secure IBE with anonymous recipient (ANON-ID-CCA2) from the Matrix DDH assumption. Our IBE further implies the first tightly IND-ID-CCA2 secure extractable IBE based on the Matrix DDH assumption. The latter can be used to get IBE of simulation-based selective opening CCA2 (SIM-SO-CCA2) security (due to Lai et al. in EUROCRYPT, 2014). The tight security of our IBE leads to a tighter reduction of the SIM-SO-CCA2 security.     

Adjoint and Selfadjoint Lie-group Methods

In the past few years, a number of Lie-group methods based on Runge—Kutta schemes have been proposed. One might extrapolate that using a selfadjoint Runge—Kutta scheme yields a Lie-group selfadjoint scheme, but this is generally not the case: Lie-group methods depend on the choice of a coordinate chart which might fail to comply to selfadjointness.In this paper we discuss Lie-group methods and their dependence on centering coordinate charts. The definition of the adjoint of a numerical method is thus subordinate to the method itself and the choice of the chart. We study Lie-group numerical methods and their adjoints, and define selfadjoint numerical methods. The latter are defined in terms of classical selfadjoint Runge—Kutta schemes and symmetric coordinates, based on geodesic or on flow midpoint. As result, the proposed selfadjoint Lie-group numerical schemes obey time-symmetry both for linear and nonlinear problems.This revised version was published online in October 2005 with corrections to the Cover Date.     

One-sided stability and convergence of the Nessyahu–Tadmor scheme

Non-oscillatory schemes are widely used in numerical approximations of nonlinear conservation laws. The Nessyahu–Tadmor (NT) scheme is an example of a second order scheme that is both robust and simple. In this paper, we prove a new stability property of the NT scheme based on the standard minmod reconstruction in the case of a scalar strictly convex conservation law. This property is similar to the One-sided Lipschitz condition for first order schemes. Using this new stability, we derive the convergence of the NT scheme to the exact entropy solution without imposing any nonhomogeneous limitations on the method. We also derive an error estimate for monotone initial data.     

Second-order schemes for conservation laws with discontinuous flux modelling clarifier–thickener units

Continuously operated clarifier–thickener (CT) units can be modeled by a non-linear, scalar conservation law with a flux that involves two parameters that depend discontinuously on the space variable. This paper presents two numerical schemes for the solution of this equation that have formal second-order accuracy in both the time and space variable. One of the schemes is based on standard total variation diminishing (TVD) methods, and is addressed as a simple TVD (STVD) scheme, while the other scheme, the so-called flux-TVD (FTVD) scheme, is based on the property that due to the presence of the discontinuous parameters, the flux of the solution (rather than the solution itself) has the TVD property. The FTVD property is enforced by a new nonlocal limiter algorithm. We prove that the FTVD scheme converges to a BV _t solution of the conservation law with discontinuous flux. Numerical examples for both resulting schemes are presented. They produce comparable numerical errors, while the FTVD scheme is supported by convergence analysis. The accuracy of both schemes is superior to that of the monotone first-order scheme based on the adaptation of the Engquist–Osher scheme to the discontinuous flux setting of the CT model (Bürger, Karlsen and Towers in SIAM J Appl Math 65:882–940, 2005). In the CT application there is interest in modelling sediment compressibility by an additional strongly degenerate diffusion term. Second-order schemes for this extended equation are obtained by combining either the STVD or the FTVD scheme with a Crank–Nicolson discretization of the degenerate diffusion term in a Strang-type operator splitting procedure. Numerical examples illustrate the resulting schemes.     

A new hypothesis concerning children’s fractional knowledge

The basic hypothesis of the teaching experiment, The Child’s Construction of the Rational Numbers of Arithmetic (Steffe & Olive, 1990) was that children’s fractional schemes can emerge as accommodations in their numerical counting schemes. This hypothesis is referred to as the reorganization hypothesis because when a new scheme is established by using another scheme in a novel way, the new scheme can be regarded as a reorganization of the prior scheme. In that case where children’s fractional schemes do emerge as accommodations in their numerical counting schemes, I regard the fractional schemes as superseding their earlier numerical counting schemes. If one scheme supersedes another, that does not mean the earlier scheme is replaced by the superseding scheme. Rather, it means that the superseding scheme solves the problems the earlier scheme solved but solves them better, and it solves new problems the earlier scheme didn’t solve. It is in this sense that we hypothesized children’s fractional schemes can supersede their numerical counting schemes and it is the sense in which we regarded numerical schemes as constructive mechanisms in the production of fractional schemes (Kieren, 1980).     

Character Tables of Association Schemes Based on Attenuated Spaces

The set of subspaces of a given dimension in an attenuated space has a structure of a symmetric association scheme and this association scheme is called an association scheme based on an attenuated space. Association schemes based on attenuated spaces are generalizations of Grassmann schemes and bilinear forms schemes, and also q-analogues of nonbinary Johnson schemes. Wang, Guo, and Li computed the intersection numbers of association schemes based on attenuated spaces. The aim of this paper is to compute character tables of association schemes based on attenuated spaces using the method of Tarnanen, Aaltonen, and Goethals. Moreover, we also prove that association schemes based on attenuated spaces include as a special case the m-flat association scheme, which is defined on the set of cosets of subspaces of a constant dimension in a vector space over a finite field.     

A numerical scheme for highly oscillatory DAEs and its application to circuit simulation

A new numerical integration scheme for the simulation of differential–algebraic equations is presented. In the context of the computer-aided design of electronic circuits, the modeling of highly oscillatory circuits leads to oscillatory differential–algebraic equations mostly of index 1 or 2. Standard schemes can solve these equations neither efficiently nor reliably. The new discretiziation scheme is constructed in such a way as to overcome the problems of classical numerical methods. It uses the Principle of Coherence due to Hersch in combination with a multistep approach. A combined Maple and Fortran77 implementation of the presented integration scheme reduces the simulation time for a quartz-controlled oscillator to about 2% compared with standard methods. Therefore, it is a powerful tool for the design of highly oscillatory circuits. This revised version was published online in June 2006 with corrections to the Cover Date.     

Certificateless signature and proxy signature schemes from bilinear pairings

Due to avoiding the inherent escrow of identity-based cryptography and yet not requiring certificates to guarantee the authenticity of public keys, certificateless public key cryptography has received a significant attention. Due to various applications of bilinear pairings in cryptography, numerous pairing-based encryption schemes, signature schemes, and other cryptographic primitives have been proposed. In this paper, a new certificateless signature scheme based on bilinear pairings is presented. The signing algorithm of the proposed scheme is very simple and does not require any pairing computation. Combining our signature scheme with certificateless public key cryptography yields a complete solution of certificateless public key system. As an application of the proposed signature scheme, a certificateless proxy signature scheme is also presented. We analyze both schemes from security point of view.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 95–103, January–March, 2005.     

Imprimitive cometric association schemes: Constructions and analysis

Dualizing the “extended bipartite double” construction for distance-regular graphs, we construct a new family of cometric (or Q-polynomial) association schemes with four associate classes based on linked systems of symmetric designs. The analysis of these new schemes naturally leads to structural questions concerning imprimitive cometric association schemes, some of which we answer with others being left as open problems. In particular, we prove that any Q-antipodal association scheme is dismantlable: the configuration induced on any subset of the equivalence classes in the Q-antipodal imprimitivity system is again a cometric association scheme. Further examples are explored. Dedicated to the memory of Dom de Caen, 1956—2002.     

Discrete artificial boundary conditions for nonlinear Schrödinger equations

In this work we construct and analyze discrete artificial boundary conditions (ABCs) for different finite difference schemes to solve nonlinear Schrödinger equations. These new discrete boundary conditions are motivated by the continuous ABCs recently obtained by the potential strategy of Szeftel. Since these new nonlinear ABCs are based on the discrete ABCs for the linear problem we first review the well-known results for the linear Schrödinger equation. We present our approach for a couple of finite difference schemes, including the Crank–Nicholson scheme, the Dùran–Sanz-Serna scheme, the DuFort–Frankel method and several split-step (fractional-step) methods such as the Lie splitting, the Strang splitting and the relaxation scheme of Besse. Finally, several numerical tests illustrate the accuracy and stability of our new discrete approach for the considered finite difference schemes.     

A family of non-oscillatory 6-point interpolatory subdivision schemes

In this paper we propose and analyze a new family of nonlinear subdivision schemes which can be considered non-oscillatory versions of the 6-point Deslauries-Dubuc (DD) interpolatory scheme, just as the Power _p schemes are considered nonlinear non-oscillatory versions of the 4-point DD interpolatory scheme. Their design principle may be related to that of the Power _p schemes and it is based on a weighted analog of the Power _p mean. We prove that the new schemes reproduce exactly polynomials of degree three and stay ’close’ to the 6-point DD scheme in smooth regions. In addition, we prove that the first and second difference schemes are well defined for each member of the family, which allows us to give a simple proof of the uniform convergence of these schemes and also to study their stability as in [19, 22]. However our theoretical study of stability is not conclusive and we perform a series of numerical experiments that seem to point out that only a few members of the new family of schemes are stable. On the other hand, extensive numerical testing reveals that, for smooth data, the approximation order and the regularity of the limit function may be similar to that of the 6-point DD scheme and larger than what is obtained with the Power _p schemes.     

Shorter identity-based encryption via asymmetric pairings

We present efficient identity-based encryption (IBE) under the symmetric external Diffie–Hellman (SXDH) assumption in bilinear groups; our scheme also achieves anonymity. In our IBE scheme, all parameters have constant numbers of group elements, and are shorter than those of previous constructions based on decisional linear (DLIN) assumption. Our construction uses both dual system encryption (Waters, CRYPTO 2009) and dual pairing vector spaces (Okamoto and Takashima, Pairing 2008; ASIACRYPT 2009). Specifically, we show how to adapt the recent DLIN-based instantiation of Lewko (EUROCRYPT 2012) to the SXDH assumption. To our knowledge, this is the first work to instantiate either dual system encryption or dual pairing vector spaces under the SXDH assumption. Furthermore, our work could be extended to many other functional encryption. In Particular, we show how to instantiate our framework to inner product encryption and key-policy functional encryption. All parameters of our constructions are shorter than those of DLIN-based constructions.