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.     

Quadratic BSDEs with convex generators and unbounded terminal conditions

In Briand and Hu (Probab Theory Relat Fields 136(4):604–618, 2006), the authors proved an existence result for BSDEs with quadratic generators with respect to the variable z and with unbounded terminal conditions. However, no uniqueness result was stated in that work. The main goal of this paper is to fill this gap. In order to obtain a comparison theorem for this kind of BSDEs, we assume that the generator is convex with respect to the variable z. Under this assumption of convexity, we are also able to prove a stability result in the spirit of the a priori estimates stated in Karoui et al. (Math Finance 7(1):1–71, 1997). With these tools in hands, we can derive the nonlinear Feynman–Kac formula in this context.     

Notions and relations for RKA-secure permutation and function families

The theory of designing block ciphers is mature, having seen significant progress since the early 1990s for over two decades, especially during the AES development effort. Nevertheless, interesting directions exist, in particular in the study of the provable security of block ciphers along similar veins as public-key primitives, i.e. the notion of pseudorandomness (PRP) and indistinguishability (IND). Furthermore, recent cryptanalytic progress has shown that block ciphers well designed against known cryptanalysis techniques including related-key attacks (RKA) may turn out to be less secure against RKA than expected. The notion of provable security of block ciphers against RKA was initiated by Bellare and Kohno, and subsequently treated by Lucks. Concrete block cipher constructions were proposed therein with provable security guarantees. In this paper, we are interested in the security notions for RKA-secure block ciphers. In the first part of the paper, we show that secure tweakable permutation families in the sense of strong pseudorandom permutation (SPRP) can be transformed into secure permutation families in the sense of SPRP against some classes of RKA (SPRP–RKA). This fact allows us to construct a secure SPRP–RKA cipher which is faster than the Bellare–Kohno PRP–RKA cipher. We also show that function families of a certain form secure in the sense of a pseudorandom function (PRF) can be transformed into secure permutation families in the sense of PRP against some classes of RKA (PRP–RKA). We can exploit it to get various constructions secure against some classes of RKA from known MAC algorithms. Furthermore, we discuss how the key recovery (KR) security of the Bellare–Kohno PRP–RKA, the Lucks PRP–RKA and our SPRP–RKA ciphers relates to existing types of attacks on block ciphers like meet-in-the-middle and slide attacks. In the second part of the paper, we define other security notions for RKA-secure block ciphers, namely in the sense of indistinguishability (IND) and non-malleability, and show the relations between these security notions. In particular, we show that secure tweakable permutation families in the sense of IND (resp. non-malleability) can be transformed into RKA-secure permutation families in the sense of IND (resp. non-malleability).     

Operator–valued Fourier multiplier theorems and maximal $L_p$-regularity

We prove a Mihlin–type multiplier theorem for operator–valued multiplier functions on UMD–spaces. The essential assumption is R–boundedness of the multiplier function. As an application we give a characterization of maximal –regularity for the generator of an analytic semigroup in terms of the R–boundedness of the resolvent of A or the semigroup . Received July 19, 1999 / Revised July 13, 2000 / Published online February 5, 2001     

Über Die Konvergenz Operatorwertiger Cosinusfunktionen mit Gestörtem Infinitesimalen Erzeuger

On convergence of operator cosine functions with perturbed infinitesimal generator. The question under what kind of perturbations a closed linear operatorA remains of the class of infinitesimal generators of operator cosine functions seems to be a rather difficult one and is unsolved in general. In this note we give bounds for the perturbation of operator cosine functions caused byA-bounded perturbationsT ofA under the assumption thatT + A is also a generator.

     

A note on Jensen’s inequality for BSDEs

Under the Lipschitz assumption and square integrable assumption on g, Jiang proved that Jensen＇s inequality for BSDEs with generator g holds in general if and only if g is independent of y, g is super homogenous in z and g（t, 0） = 0, a.s., a.e.. In this paper, based on Jiang＇s results, under the same assumptions as Jiang＇s, we investigate the necessary and sufficient condition on g under which Jensen＇s inequality for BSDEs with generator g holds for some specific convex functions, which generalizes some known results on Jensen＇s inequality for BSDEs.     

A new variant of the Schwarz–Pick–Ahlfors Lemma

We prove a “general shrinking lemma” that resembles the Schwarz–Pick–Ahlfors Lemma and its many generalizations, but differs in applying to maps of a finite disk into a disk, rather than requiring the domain of the map to be complete. The conclusion is that distances to the origin are all shrunk, and by a limiting procedure we can recover the original Ahlfors Lemma, that all distances are shrunk. The method of proof is also different in that it relates the shrinking of the Schwarz–Pick–Ahlfors-type lemmas to the comparison theorems of Riemannian geometry. Received: 26 May 1998 / Revised version: 4 May 1999     

An Existential Divisibility Lemma for Global Fields

We generalize the Existential Divisibility Lemma by Th. Pheidas [7] to all global fields K of characteristic not 2, and for all sets of primes that are inert in a quadratic extension L of K. We also remove the conditions in real and ramifying primes, which were present in Pheidas’ version. As a Corollary, we recover the known fact that the set of integral elements at a prime in a global field is existentially definable. The first author is a Research Assistant of the Research Foundation – Flanders (FWO – Vlaanderen). Work partially supported by the European Community’s Human Potential Programme under contract HPRN-CT-2002-00287.     

On the Average Discrepancy of Successive Tuples of Pseudo-Random Numbers over Parts of the Period

 In the present paper we give an upper and a lower bound for the average value of the discrepancy of non-overlapping s-tuples of successive elements of a first order congruential pseudo-random-number generator (with prime modulus and maximal period). The estimates are – up to logarithmic factors – sharp also for short parts of the period. Received 30 January 1997; in revised form 2 May 1997     

On Lai–Massey and quasi-Feistel ciphers

We introduce a new notion called a quasi-Feistel cipher, which is a generalization of the Feistel cipher, and contains the Lai–Massey cipher as an instance. We show that most of the works on the Feistel cipher can be naturally extended to the quasi-Feistel cipher. From this, we give a new proof for Vaudenay’s theorems on the security of the Lai–Massey cipher, and also we introduce for Lai–Massey a new construction of pseudorandom permutation, analoguous to the construction of Naor–Reingold using pairwise independent permutations. Also, we prove the birthday security of (2b−1)- and (3b−2)-round unbalanced quasi-Feistel ciphers with b branches against CPA and CPCA attacks, respectively.     

σ-Extensions of discrete multivalued groups

The paper is devoted to the theory of singly generated multivalued groups. We construct new classes of such groups and find criteria that allow to check whether such a group is a coset group. For this purpose, we introduce the construction of a σ-extension of a singly generated multivalued group with Hermitian generator. This construction is based on the relation of the theory of such groups with the theory of symmetric graphs. The main result of the paper is as follows: the suggested construction of σ-extensions of singly generated bicoset multivalued groups with Hermitian generators is equivariant with respect to morphisms of graph-theoretic nature. Bibliography: 11 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 325, 2005, pp. 225–242.     

The class of groups all of whose subgroups with lesser number of generators are free is generic

It is shown that, in a certain statistical sense, in almost every group withm generators andn relations (withm andn chosen), any subgroup generated by less thanm elements (which need not belong to the system of generators of the whole group) is free. In particular, this solves Problem 11.75 from the Kourov Notebook. In the proof we introduce a new assumption on the defining relations stated in terms of finite marked groups. Translated fromMatematicheskie Zametki, Vol. 59, No. 4, pp. 489–496, April, 1996. The research of the second author was partially supported by the Russian Foundation for Basic Research under grant No. 94-0101541 and by the International Science Foundation under grant No. MID000.     

Luby–Rackoff Revisited: On the Use of Permutations as Inner Functions of a Feistel Scheme

In this paper we are dealing with the security of the Feistel structure in the Luby–Rackoff model when the round functions are replaced by permutations. There is a priori no reason to think that the security bounds remain the same in this case, as illustrated by Knudsen’s attack [5]. It is why we revisit Luby–Rackoff’s proofs [6] in this specific case. The conclusion is that when the inner functions are random permutations, a 3-round (resp. 4-round) Feistel scheme remains secure against pseudorandom (resp. superpseudorandom) distinguishers as long as m 2^n/2 (with m the number of queries and 2n the block size). The main part of this work was carried out when the author was a member of the UCL Crypto Group (http://www.uclcrypto.org).     

One-point extensions of Markov processes by darning

This paper is a continuation of the works by Fukushima–Tanaka (Ann Inst Henri Poincaré Probab Stat 41: 419–459, 2005) and Chen–Fukushima–Ying (Stochastic Analysis and Application, p.153–196. The Abel Symposium, Springer, Heidelberg) on the study of one-point extendability of a pair of standard Markov processes in weak duality. In this paper, general conditions to ensure such an extension are given. In the symmetric case, characterizations of the one-point extensions are given in terms of their Dirichlet forms and in terms of their L ²-infinitesimal generators. In particular, a generalized notion of flux is introduced and is used to characterize functions in the domain of the L ²-infinitesimal generator of the extended process. An important role in our investigation is played by the α-order approaching probability u _α . The research of Z.-Q. Chen is supported in part by NSF Grant DMS-0600206. The research of M. Fukushima is supported in part by Grant-in-Aid for Scientific Research of MEXT No.19540125.     

Jensen’s Inequality for Backward Stochastic Differential Equations

Abstract Under the Lipschitz assumption and square integrable assumption on g, the author proves that Jensen’s inequality holds for backward stochastic differential equations with generator g if and only if g is independent of y, g(t, 0) ≡ 0 and g is super homogeneous with respect to z. This result generalizes the known results on Jensen’s inequality for g- expectation in [4, 7–9]. *Project supported by the National Natural Science Foundation of China (No.10325101) and the Science Foundation of China University of Mining and Technology.     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

Derived Azumaya algebras and generators for twisted derived categories

We introduce a notion of derived Azumaya algebras over ring and schemes generalizing the notion of Azumaya algebras of Grothendieck (Le groupe de Brauer. I. Algèbres d’Azumaya et interprétations diverses. Dix Exposés sur la Cohomologie des Schémas, pp. 46–66, North-Holland, Amsterdam, 1968). We prove that any such algebra B on a scheme X provides a class ϕ(B) in . We prove that for X a quasi-compact and quasi-separated scheme ϕ defines a bijective correspondence, and in particular that any class in , torsion or not, can be represented by a derived Azumaya algebra on X. Our result is a consequence of a more general theorem about the existence of compact generators in twisted derived categories, with coefficients in any local system of reasonable dg-categories, generalizing the well known existence of compact generators in derived categories of quasi-coherent sheaves of Bondal and Van Den Bergh (Mosc. Math. J. 3(1):1–36, 2003). A huge part of this paper concerns the treatment of twisted derived categories, as well as the proof that the existence of compact generator locally for the fppf topology implies the existence of a global compact generator. We present explicit examples of derived Azumaya algebras that are not represented by classical Azumaya algebras, as well as applications of our main result to the localization for twisted algebraic K-theory and to the stability of saturated dg-categories by direct push-forwards along smooth and proper maps.     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant subspace S(Φ) of L ₂ (R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a ψ (necessarily unique) satisfying . The technical condition is satisfied, e.g., when the generators are at infinity for some ρ>k+d . In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19. 1996. Date revised: September 6, 1996.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

The Diffie–Hellman problem and generalization of Verheul’s theorem

Bilinear pairings on elliptic curves have been of much interest in cryptography recently. Most of the protocols involving pairings rely on the hardness of the bilinear Diffie–Hellman problem. In contrast to the discrete log (or Diffie–Hellman) problem in a finite field, the difficulty of this problem has not yet been much studied. In 2001, Verheul (Advances in Cryptology—EUROCRYPT 2001, LNCS 2045, pp. 195–210, 2001) proved that on a certain class of curves, the discrete log and Diffie–Hellman problems are unlikely to be provably equivalent to the same problems in a corresponding finite field unless both Diffie–Hellman problems are easy. In this paper we generalize Verheul’s theorem and discuss the implications on the security of pairing based systems.