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.     

Carter subgroups and Fitting heights of finite groups

Let G be a finite group possessing a Carter subgroup K. Denote by \(\mathbf {h}(G)\) the Fitting height of G, by \(\mathbf {h}^*(G)\) the generalized Fitting height of G, and by \(\ell (K)\) the number of composition factors of K, that is, the number of prime divisors of the order of K with multiplicities. In 1969, E. C. Dade proved that if G is solvable, then \(\mathbf {h}(G)\) is bounded in terms of \(\ell (K)\). In this paper, we show that \(\mathbf {h}^*(G)\) is bounded in terms of \(\ell (K)\) as well.     

Asymptotic results for jump probabilities associated to the multiple scan statistic

The concept of pattern arises in many applications comprising experimental trials with two or more possible outcomes in each trial. A binary scan of type r / k is a special pattern referring to success–failure strings of fixed length k that contain at least r-successes, where r, k are positive integers with \(r\le k\). The multiple scan statistic \(W_{t,k,r}\) is defined as the enumerating random variable for the overlapping moving windows occurring until trial t which include a scan of type r / k. In the present work, we consider a sequence of independent binary trials with not necessarily equal probabilities of success and develop upper bounds for the probability of the event that the multiple scan statistic will perform a jump from \(\ell \) to \(\ell +1\) (where \(\ell \) is a nonnegative integer) in a finite time horizon.     

Demiquantifiers on $$\ell $$-groups

In this paper we introduce two kinds of unary operations on abelian \(\ell \)-groups with a positive distinguished element u. One of them, called demiquantifier of type I, behaves like an existential quantifier (in the sense of Cimadamore and Varela) in the negative cone, and like a universal quantifier in the positive cone. The other kind of unary operation we introduce, called demiquantifier of type II, satisfies analogous properties to demiquantifiers of type I via a translation of the negative cone, by means of the element u. These unary operations are interdefinable with the usual existential quantifiers, provided the distinguished element u is a strong unit. Moreover, if G is an abelian \(\ell \)-group, then the restriction of a demiquantifier of type II to the MV-algebra \(\Gamma (G,u)\) yields a different type of quantifier, where \(\Gamma \) is Mundici’s functor. These quantifiers are interdefinable with the usual existential quantifiers on MV-algebras given by Rutledge, provided that the involution of the corresponding MV-algebras have a fixed point.     

On pseudo-amenability of commutative semigroup algebras and their second duals

In this paper, we first characterize pseudo-amenability of semigroup algebras \(\ell ^1(S),\) for a certain class of commutative semigroups S,  the so-called archimedean semigroups. We show that for an archimedean semigroup S,  pseudo-amenability, amenability and approximate amenability of \(\ell ^1(S)\) are equivalent. Then for a commutative semigroup S,  we show that pseudo-amenability of \(\ell ^{1}(S)\) implies that S is a Clifford semigroup. Finally, we give some results on pseudo-amenability and approximate amenability of the second dual of a certain class of commutative semigroup algebras \(\ell ^1(S)\).     

Isometric multipliers of a vector valued Beurling algebra on a discrete semigroup

Let (S,ω) be a weighted abelian semigroup, let M _ω (S) be the semigroup of ω-bounded multipliers of S, and let \(\mathcal {A}\) be a strictly convex commutative Banach algebra with identity. It is shown that T is an onto isometric multiplier of \(\ell ^{1}(S,\omega , \mathcal {A})\) if and only if there exists an invertible σ ∈ M _ω (S), a unitary point \(a \in \mathcal {A}\), and a k>0 such that \(T(f)= ka{\sum }_{x \in S} f(x)\delta _{\sigma (x)}\) for each \(f={\sum }_{x \in S}f(x)\delta _{x} \in \ell ^{1}(S,\omega ,\mathcal {A})\). It is also shown that an isomorphism from \(\ell ^{1}(S_{1},\omega _{1},\mathcal {A})\) onto \(\ell ^{1}(S_{2},\omega _{2}, \mathcal {B})\) induces an isomorphism from \(M(\ell ^{1}(S_{1},\omega _{1},\mathcal {A}))\), the set of all multipliers of \(\ell ^{1}(S_{1},\omega _{1},\mathcal {A})\), onto \(M(\ell ^{1}(S_{2},\omega _{2},\mathcal {B}))\).     

CLT for Random Walks of Commuting Endomorphisms on Compact Abelian Groups

Let \(\mathcal S\) be an abelian group of automorphisms of a probability space \((X, {\mathcal A}, \mu )\) with a finite system of generators \((A_1, \ldots , A_d).\) Let \(A^{{\underline{\ell }}}\) denote \(A_1^{\ell _1} \ldots A_d^{\ell _d}\), for \({{\underline{\ell }}}= (\ell _1, \ldots , \ell _d).\) If \((Z_k)\) is a random walk on \({\mathbb {Z}}^d\), one can study the asymptotic distribution of the sums \(\sum _{k=0}^{n-1} \, f \circ A^{\,{Z_k(\omega )}}\) and \(\sum _{{\underline{\ell }}\in {\mathbb {Z}}^d} {\mathbb {P}}(Z_n= {\underline{\ell }}) \, A^{\underline{\ell }}f\), for a function f on X. In particular, given a random walk on commuting matrices in \(SL(\rho , {\mathbb {Z}})\) or in \({\mathcal M}^*(\rho , {\mathbb {Z}})\) acting on the torus \({\mathbb {T}}^\rho \), \(\rho \ge 1\), what is the asymptotic distribution of the associated ergodic sums along the random walk for a smooth function on \({\mathbb {T}}^\rho \) after normalization? In this paper, we prove a central limit theorem when X is a compact abelian connected group G endowed with its Haar measure (e.g., a torus or a connected extension of a torus), \(\mathcal S\) a totally ergodic d-dimensional group of commuting algebraic automorphisms of G and f a regular function on G. The proof is based on the cumulant method and on preliminary results on random walks.     

Triviality of Iwasawa module associated to some abelian fields of prime conductors

Let p be an odd prime number and \(\ell \) an odd prime number dividing \(p-1\). We denote by \(F=F_{p,\ell }\) the real abelian field of conductor p and degree \(\ell \), and by \(h_F\) the class number of F. For a prime number \(r \ne p,\,\ell \), let \(F_{\infty }\) be the cyclotomic \(\mathbb {Z}_r\)-extension over F, and \(M_{\infty }/F_{\infty }\) the maximal pro-r abelian extension unramified outside r. We prove that \(M_{\infty }\) coincides with \(F_{\infty }\) and consequently \(h_F\) is not divisible by r when r is a primitive root modulo \(\ell \) and r is smaller than an explicit constant depending on p.     

Congruences for $$\ell $$-regular overpartitions and Andrews’ singular overpartitions

Let \(\overline{A}_{\ell }(n)\) be the number of overpartitions of n into parts not divisible by \(\ell \). In a recent paper, Shen calls the overpartitions enumerated by the function \(\overline{A}_{\ell }(n)\) as \(\ell \)-regular overpartitions. In this paper, we find certain congruences for \(\overline{A}_{\ell }(n)\), when \(\ell =4, 8\), and 9. Recently, Andrews introduced the partition function \(\overline{C}_{k, i}(n)\), called singular overpartition, which counts the number of overpartitions of n in which no part is divisible by k and only parts \(\equiv \pm i\pmod {k}\) may be over-lined. He also proved that \(\overline{C}_{3, 1}(9n+3)\) and \(\overline{C}_{3, 1}(9n+6)\) are divisible by 3. In this paper, we prove that \(\overline{C}_{3, 1}(12n+11)\) is divisible by 144 which was conjectured to be true by Naika and Gireesh.     

Representation of normal bands as semigroups of <Emphasis Type="Italic">k</Emphasis>-bi-ideals of a semiring

Here we show that every normal band N can be embedded into the normal band \(\mathcal {B(S)}\) of all k-bi-ideals, the left part \(N/ \mathcal {R}\) of N into the left normal band \(\mathcal {R(S)}\) of all right k-ideals, the right part \(N/ \mathcal {L}\) of N into the right normal band \(\mathcal {L(S)}\) of all left k-ideals, and the greatest semilattice homomorphic image \(N/ \mathcal {J}\) of N into the semilattice of all k-ideals of a same k-regular and intra k-regular semiring S.     

Lengths of words in transformation semigroups generated by digraphs

Given a simple digraph D on n vertices (with \(n\ge 2\)), there is a natural construction of a semigroup of transformations \(\langle D\rangle \). For any edge (a, b) of D, let \(a\rightarrow b\) be the idempotent of rank \(n-1\) mapping a to b and fixing all vertices other than a; then, define \(\langle D\rangle \) to be the semigroup generated by \(a \rightarrow b\) for all \((a,b) \in E(D)\). For \(\alpha \in \langle D\rangle \), let \(\ell (D,\alpha )\) be the minimal length of a word in E(D) expressing \(\alpha \). It is well known that the semigroup \(\mathrm {Sing}_n\) of all transformations of rank at most \(n-1\) is generated by its idempotents of rank \(n-1\). When \(D=K_n\) is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate \(\ell (K_n,\alpha )\), for any \(\alpha \in \langle K_n\rangle = \mathrm {Sing}_n\); however, no analogous non-trivial results are known when \(D \ne K_n\). In this paper, we characterise all simple digraphs D such that either \(\ell (D,\alpha )\) is equal to Howie–Iwahori’s formula for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )\) for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )\) for all \(\alpha \in \langle D\rangle \). We also obtain bounds for \(\ell (D,\alpha )\) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank \(n-1\) of \(\mathrm {Sing}_n\)). We finish the paper with a list of conjectures and open problems.     

How to build time-lock encryption

Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. We propose a novel time-lock encryption scheme, whose main advantage over prior constructions is that even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party. We build our time-lock encryption on top of the new concept of computational reference clocks and an extractable witness encryption scheme. We explain how to construct a computational reference clock based on Bitcoin. We show how to achieve constant level of multilinearity for witness encryption by using SNARKs. We propose a new construction of a witness encryption scheme which is of independent interest: our scheme, based on Subset-Sum, achieves extractable security without relying on obfuscation. The scheme employs multilinear maps of arbitrary order and is independent of the implementations of multilinear maps.     

On color-preserving automorphisms of Cayley graphs of odd square-free order

An automorphism \(\alpha \) of a Cayley graph \(\mathrm{Cay}(G,S)\) of a group G with connection set S is color-preserving if \(\alpha (g,gs) = (h,hs)\) or \((h,hs^{-1})\) for every edge \((g,gs)\in E(\mathrm{Cay}(G,S))\). If every color-preserving automorphism of \(\mathrm{Cay}(G,S)\) is also affine, then \(\mathrm{Cay}(G,S)\) is a Cayley color automorphism (CCA) graph. If every Cayley graph \(\mathrm{Cay}(G,S)\) is a CCA graph, then G is a CCA group. Hujdurovi? et al. have shown that every non-CCA group G contains a section isomorphic to the non-abelian group \(F_{21}\) of order 21. We first show that there is a unique non-CCA Cayley graph \(\Gamma \) of \(F_{21}\). We then show that if \(\mathrm{Cay}(G,S)\) is a non-CCA graph of a group G of odd square-free order, then \(G = H\times F_{21}\) for some CCA group H, and \(\mathrm{Cay}(G,S) = \mathrm{Cay}(H,T)\mathbin {\square }\Gamma \).     

Normes cyclotomiques naïves et unités logarithmiques

We compute the \({\mathbb {Z}}\)-rank of the subgroup \(\widetilde{E}_K =\bigcap _{n\in {\mathbb {N}}} N_{K_n/K}(K_n^\times )\) of elements of the multiplicative group of a number field K that are norms from every finite level of the cyclotomic \({\mathbb {Z}}_\ell \)-extension \(K^c\) of K. Thus we compare its \(\ell \)-adification \({\mathbb {Z}}_\ell \otimes _{\mathbb {Z}}\widetilde{E}_K\) with the group of logarithmic units \(\widetilde{\varepsilon }_K\). By the way we point out an easy proof of the Gross–Kuz’min conjecture for \(\ell \)-undecomposed extensions of abelian fields.     

Super-strong RKA secure MAC,PKE and SE from tag-based hash proof system

\(\mathcal {F}\)-related-key attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say k, but also related keys f(k), with f adaptively chosen from \(\mathcal {F}\) by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called super-strong RKA securities, which stipulate minimal restrictions on the adversary’s forgery or oracle access, thus turn out to be the strongest ones among existing RKA security requirements. We present paradigms for constructing super-strong RKA secure MAC, PKE and SE from a common ingredient, namely Tag-based hash proof system (THPS). We also present constructions for THPS based on the k-linear and the DCR assumptions. When instantiating our paradigms with concrete THPS constructions, we obtain super-strong RKA secure MAC, PKE and SE schemes for the class of restricted affine functions \(\mathcal {F}_{\text {raff}}\), of which the class of linear functions \(\mathcal {F}_{\text {lin}}\) is a subset. To the best of our knowledge, our MACs, PKEs and SEs are the first ones possessing super-strong RKA securities for a non-claw-free function class \(\mathcal {F}_{\text {raff}}\) in the standard model and under standard assumptions. Our constructions are free of pairing and are as efficient as those proposed in previous works. In particular, the keys, tags of MAC and ciphertexts of PKE and SE all consist of only a constant number of group elements.     

System identification in dynamical sampling

We consider the problem of spatiotemporal sampling in a discrete infinite dimensional spatially invariant evolutionary process x ⁽ⁿ⁾ = A ⁿ x to recover an unknown convolution operator A given by a filter \(a \in \ell ^{1}(\mathbb {Z})\) and an unknown initial state x modeled as a vector in \(\ell ^{2}(\mathbb {Z})\). Traditionally, under appropriate hypotheses, any x can be recovered from its samples on \(\mathbb {Z}\) and A can be recovered by the classical techniques of deconvolution. In this paper, we will exploit the spatiotemporal correlation and propose a new sampling scheme to recover A and x that allows us to sample the evolving states x,A x,? ,A ^N?1 x on a sub-lattice of \(\mathbb {Z}\), and thus achieve a spatiotemporal trade off. The spatiotemporal trade off is motivated by several industrial applications (Lu and Vetterli, 2249–2252, 2009). Specifically, we show that

$$\{x(m\mathbb {Z}), Ax(m\mathbb {Z}), \cdots , A^{N-1}x(m\mathbb {Z}): N \geq 2m\}$$

contains enough information to recover a typical “low pass filter” a and x almost surely, thus generalizing the idea of the finite dimensional case in Aldroubi and Krishtal, arXiv:1412.1538 (2014). In particular, we provide an algorithm based on a generalized Prony method for the case when both a and x are of finite impulse response and an upper bound of their support is known. We also perform a perturbation analysis based on the spectral properties of the operator A and initial state x, and verify the results by several numerical experiments. Finally, we provide several other numerical techniques to stabilize the proposed method, with some examples to demonstrate the improvement.

     

Strong authenticated key exchange with auxiliary inputs

In the Russian cards problem, Alice, Bob and Cath draw a, b and c cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Alice and Bob’s exchanges do not allow Cath to know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card. We propose an intermediate notion, which we call \(\varepsilon \)-strong security, where the probabilities perceived by Cath may only change by a factor of \(\varepsilon \). We then show that strategies based on affine or projective geometries yield \(\varepsilon \)-strong safety for arbitrarily small \(\varepsilon \) and appropriately chosen values of a, b, c.     

Module derivations on semigroup algebras

We show that for an inverse semigroup S with the set idempotents E acting on S trivially from left and by multiplication from right, any bounded module derivation from \(\ell ^1(S)\) to \(({\ell ^1(S)}/{J})^*=J^{\perp }\) is inner, where J is the closed ideal generated by elements of the form \(\delta _{set}-\delta _{st}\) with \(s,t\in S\) and \(e\in E\).     

The shape of $$ \mathbb {Z}/\ell \mathbb {Z}$$-number fields

Let \(\ell \) be a prime and let \(L/ \mathbb {Q}\) be a Galois number field with Galois group isomorphic to \( \mathbb {Z}/\ell \mathbb {Z}\). We show that the shape of L, see Definition 1.2, is either \(\frac{1}{2}\mathbb {A}_{\ell -1}\) or a fixed sub-lattice depending only on \(\ell \); such a dichotomy in the value of the shape only depends on the type of ramification of L. This work is motivated by a result of Bhargava and Shnidman, and a previous work of the first named author, on the shape of \( \mathbb {Z}/3 \mathbb {Z}\) number fields.     

Stable Signal Recovery from Phaseless Measurements

The aim of this paper is to study the stability of the \(\ell _1\) minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that \(m={\mathcal {O}}(k\log (N/k))\) measurements are enough to guarantee the \(\ell _1\) minimization to recover k-sparse signals stably provided the measurement matrix A satisfies the strong RIP property. We second investigate the phaseless instance-optimality presenting a null space property of the measurement matrix A under which there exists a decoder \(\Delta \) so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the \(\ell _1\) norm. This builds a parallel for compressive phase retrieval with the classical compressive sensing.