Recent zbMATH articles in MSC 94https://zbmath.org/atom/cc/942022-11-17T18:59:28.764376ZUnknown authorWerkzeugBook review of: E. Brown and R. K. Guy, The unity of combinatoricshttps://zbmath.org/1496.000152022-11-17T18:59:28.764376Z"Pak, Igor"https://zbmath.org/authors/?q=ai:pak.igorReview of [Zbl 1458.05001].Information and the hard problem of consciousnesshttps://zbmath.org/1496.000342022-11-17T18:59:28.764376Z"Montemayor, Carlos"https://zbmath.org/authors/?q=ai:montemayor.carlos"de Barros, J. Acacio"https://zbmath.org/authors/?q=ai:de-barros.jose-acacioFor the entire collection see [Zbl 1496.00078].Editorial: Coding and cryptography 2019https://zbmath.org/1496.000652022-11-17T18:59:28.764376ZFrom the text: This volume contains 16 refereed papers addressing a wide range of topics in coding and cryptography. The selected papers are the full journal versions of extended abstracts accepted for presentation at the International Workshop on Coding and Cryptography (WCC 2019) held in Saint-Jacut-de-la-Mer, March 31 to April 5, 2019.Editorial: Special issue on sequences and their applications 2018https://zbmath.org/1496.000702022-11-17T18:59:28.764376ZFrom the text: The contributors to this volume are researchers participating at the event ``Sequences and Their Applications'' (SETA 2018) held in Hong Kong, October 1--6, 2018.Constructing saturating sets in projective spaces using subgeometrieshttps://zbmath.org/1496.050162022-11-17T18:59:28.764376Z"Denaux, Lins"https://zbmath.org/authors/?q=ai:denaux.linsSummary: A \(\varrho\)-saturating set of \(\mathrm{PG}(N,q)\) is a point set \({\mathcal{S}}\) such that any point of \(\mathrm{PG}(N,q)\) lies in a subspace of dimension at most \(\varrho\) spanned by points of \({\mathcal{S}}\). It is generally known that a \(\varrho\)-saturating set of \(\mathrm{PG}(N,q)\) has size at least \(c\cdot \varrho \,q^\frac{N-\varrho}{\varrho +1}\), with \(c>\frac{1}{3}\) a constant. Our main result is the discovery of a \(\varrho\)-saturating set of size roughly \(\frac{(\varrho +1)(\varrho +2)}{2}q^\frac{N-\varrho}{\varrho +1}\) if \(q=(q')^{\varrho +1}\), with \(q'\) an arbitrary prime power. The existence of such a set improves most known upper bounds on the smallest possible size of \(\varrho\)-saturating sets if \(\varrho <\frac{2N-1}{3}\). As saturating sets have a one-to-one correspondence to linear covering codes, this result improves existing upper bounds on the length and covering density of such codes. To prove that this construction is a \(\varrho\)-saturating set, we observe that the affine parts of \(q'\)-subgeometries of \(\mathrm{PG}(N,q)\) having a hyperplane in common, behave as certain lines of \(\mathrm{AG}\big (\varrho +1,(q')^N\big)\). More precisely, these affine lines are the lines of the linear representation of a \(q'\)-subgeometry \(\mathrm{PG}(\varrho ,q')\) embedded in \(\mathrm{PG}\big (\varrho +1,(q')^N\big)\).On sets of subspaces with two intersection dimensions and a geometrical junta boundhttps://zbmath.org/1496.050182022-11-17T18:59:28.764376Z"Longobardi, Giovanni"https://zbmath.org/authors/?q=ai:longobardi.giovanni"Storme, Leo"https://zbmath.org/authors/?q=ai:storme.leo"Trombetti, Rocco"https://zbmath.org/authors/?q=ai:trombetti.roccoSummary: In this article, constant dimension subspace codes whose codewords have subspace distance in a prescribed set of integers, are considered. The easiest example of such an object is a junta [\textit{I. Dinur} and \textit{E. Friedgut}, Comb. Probab. Comput. 18, No. 1--2, 107--122 (2009; Zbl 1243.05235)]; i.e. a subspace code in which all codewords go through a common subspace. We focus on the case when only two intersection values for the codewords, are assigned. In such a case we determine an upper bound for the dimension of the vector space spanned by the elements of a non-junta code. In addition, if the two intersection values are consecutive, we prove that such a bound is tight, and classify the examples attaining the largest possible dimension as one of four infinite families.Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entrieshttps://zbmath.org/1496.051002022-11-17T18:59:28.764376Z"Steinerberger, Stefan"https://zbmath.org/authors/?q=ai:steinerberger.stefan"Wu, Hau-tieng"https://zbmath.org/authors/?q=ai:wu.hau-tiengSummary: We consider the eigenvalue problem \(A x = \lambda x\) where \(A \in \mathbb{R}^{n \times n}\) and the eigenvalue is also real \(\lambda \in \mathbb{R} \). If we are given \(A, \lambda\) and, additionally, the absolute value of the entries of \(x\) (the vector \((|x_i|)_{i = 1}^n)\), is there a fast way to recover \(x\)? In particular, can this be done quicker than computing \(x\) from scratch? This may be understood as a special case of the phase retrieval problem. We present a randomized algorithm which provably converges in expectation whenever \(\lambda\) is a simple eigenvalue. The problem should become easier when \(| \lambda |\) is large and we discuss another algorithm for that case as well.A lattice of 0-1 SK-partitionshttps://zbmath.org/1496.060022022-11-17T18:59:28.764376Z"Sookoo, Norris"https://zbmath.org/authors/?q=ai:sookoo.norris(no abstract)Approximation of restrictions of \(q\)-valued logic functions to linear manifolds by affine analogueshttps://zbmath.org/1496.060162022-11-17T18:59:28.764376Z"Ryabov, Vladimir G."https://zbmath.org/authors/?q=ai:ryabov.vladimir-gSummary: For a finite \(q\)-element field \(\textbf{F}_q \), we established a relation between parameters characterizing the measure of affine approximation of a \(q\)-valued logic function and similar parameters for its restrictions to linear manifolds. For \(q > 2\), an analogue of the Parseval identity with respect to these parameters is proved, which implies the meaningful upper estimates \(q^{n -1}(q - 1) - q^{n/2-1}\) and \(q^{r -1}(q - 1) - q^{r/2-1} \), for the nonlinearity of an \(n\)-place \(q\)-valued logic function and of its restrictions to manifolds of dimension \(r\). Estimates characterizing the distribution of nonlinearity on manifolds of fixed dimension are obtained.On \((-1)\)-differential uniformity of ternary APN power functionshttps://zbmath.org/1496.140222022-11-17T18:59:28.764376Z"Yan, Haode"https://zbmath.org/authors/?q=ai:yan.haodeFunctions with low differential uniformity over finite fields have been widely investigated because of their applications in cryptography.
Classically, the differential uniformity of \(f:\mathbb{F}_{p^n}\rightarrow\mathbb{F}_{p^n}\) is defined as the maximum of the quantities
\[
\#\{x\in\mathbb{F}_{p^n}\,:\,f(x+a)-f(x)=b\}.
\]
with \(a,b\) ranging in \(\mathbb{F}_{p^n}\). Recently, inspired from the development of a new differential attack, Ellingsen et al. proposed a new type of differential uniformity (the so called c-differential uniformity), replacing the above mentioned quantity with
\[
\#\{x\in\mathbb{F}_{p^n}\,:\,f(x+a)-cf(x)=b\}.
\]
where \(c\in \mathbb{F}_{p^n}\).
In this paper, the authors investigate the \((-1)\)-differential uniformity of some ternary APN power functions \(f(x) = x^d\) over \(\mathbb{F}_{3^n}\), and they provide several examples of functions with low \((-1)\)-differential uniformity. In particular, some of these functions are almost perfect \((-1)\)-nonlinear, i.e. their \((-1)\)-differential uniformity is exactly \(2\).
Reviewer: Marco Timpanella (Perugia)Improved supersingularity testing of elliptic curves using Legendre formhttps://zbmath.org/1496.140312022-11-17T18:59:28.764376Z"Hashimoto, Yuji"https://zbmath.org/authors/?q=ai:hashimoto.yuji"Nuida, Koji"https://zbmath.org/authors/?q=ai:nuida.kojiThe paper improves the computational cost of an algorithm due to \textit{A. V. Sutherland} [LMS J. Comput. Math. 15, 317--325 (2012; Zbl 1307.11072)] which decides if a given elliptic curve \(E\)\, defined over a finite field \(\mathbb{F}_q\)\, of characteristic \(p\ge 5\)\, is ordinary or supersingular.
The test of Sutherland is based on the graph of \(l\)-isogenies (\(l\ne p\)) of \(E\). In the ordinary case the graph is a volcano, see [\textit{M. Fouquet} and \textit{F. Morain}, Lect. Notes Comput. Sci. 2369, 276--291 (2002; Zbl 1058.11041)], while in the supersingular case is an expander Ramanujan graph, see [\textit{A. K. Pizer}, Bull. Am. Math. Soc., New Ser. 23, No. 1, 127--137 (1990; Zbl 0752.05035)]. The Sutherland's algorithm take \(l=2\)\, (because it is the case most easy to compute).
The algorithm determines which is the type of the 2-graph of E. The computational complexity of the Sutherland's algorithm is dominated by the computation of square roots over \(\mathbb{F}_{p^2}\). The cost of an square root is \(O(n^2(log_2 n)^2);\, n=log_2 p\).
The algorithm proposed in the present paper takes Legendre models, instead of Weiertrasse models, for the elliptic curves and it substitutes the computation of two square roots by a quarter root computation. In the authors words ``we reduce this dominant cost of Sutherland's algorithm to approximately a half of the original.''
Sections 2 to 5 summarize the necessary concepts and results on elliptic curves and isogenies. Section 6 describes the Sutherland's algorithm and Section 6 the proposed variant of the supersingular testing algorithm.
Sections 8 and 9 shows the comparison of the performances of the Sutherland's algorithm and the present proposal, giving numerical results of an implementation using Magma (Tables 1, 2 and 3).
For the entire collection see [Zbl 1482.68009].
Reviewer: Juan Tena Ayuso (Valladolid)A chain of normalizers in the Sylow 2-subgroups of the symmetric group on \({\mathbf{2}}^n\) lettershttps://zbmath.org/1496.200032022-11-17T18:59:28.764376Z"Aragona, Riccardo"https://zbmath.org/authors/?q=ai:aragona.riccardo"Civino, Roberto"https://zbmath.org/authors/?q=ai:civino.roberto"Gavioli, Norberto"https://zbmath.org/authors/?q=ai:gavioli.norberto"Scoppola, Carlo Maria"https://zbmath.org/authors/?q=ai:scoppola.carlo-mariaSummary: On the basis of an initial interest in symmetric cryptography, in the present work we study a chain of subgroups. Starting from a Sylow 2-subgroup of \(\mathrm{AGL}(2,n)\), each term of the chain is defined as the normalizer of the previous one in the symmetric group on \(2^n\) letters. Partial results and computational experiments lead us to conjecture that, for large values of \(n\), the index of a normalizer in the consecutive one does not depend on \(n\). Indeed, there is a strong evidence that the sequence of the logarithms of such indices coincides with the sequence of the partial sums of the numbers of partitions into at least two distinct parts.Hermite-Hadamard trapezoid and mid-point divergenceshttps://zbmath.org/1496.260282022-11-17T18:59:28.764376Z"Dragomir, Silvestru Sever"https://zbmath.org/authors/?q=ai:dragomir.sever-silvestruSummary: In this paper, we introduce the concepts of Hermite-Hadamard trapezoid and mid-point divergences that are closely related to the Jensen divergence considered by \textit{J. Burbea} and \textit{C. R. Rao} in [IEEE Trans. Inf. Theory 28, 489--495 (1982; Zbl 0479.94009)]. The joint convexity of these divergences and several inequalities involving these measures are established. Various examples concerning the Csiszár, Lin-Wong, and HH \(f\)-divergence measures are also given.
For the entire collection see [Zbl 1485.65002].Dynamics of a new multistable 4D hyperchaotic Lorenz system and its applicationshttps://zbmath.org/1496.340792022-11-17T18:59:28.764376Z"Leutcho, Gervais Dolvis"https://zbmath.org/authors/?q=ai:leutcho.gervais-dolvis"Wang, Huihai"https://zbmath.org/authors/?q=ai:wang.huihai"Fozin, Theophile Fonzin"https://zbmath.org/authors/?q=ai:fozin.theophile-fonzin"Sun, Kehui"https://zbmath.org/authors/?q=ai:sun.kehui"Njitacke, Zeric Tabekoueng"https://zbmath.org/authors/?q=ai:njitacke.zeric-tabekoueng"Kengne, Jacques"https://zbmath.org/authors/?q=ai:kengne.jacquesBased on the three-dimensional Lorenz system, the authors constructs a new four-dimensional hyperchaotic system
\begin{align*} & \dot{x}=a\left( y-x \right), \\
& \dot{y}=bx-y-xz+u, \\
& \dot{z}=-cz+{{x}^{2}}, \\
& \dot{u}=-dx\left| x \right|+u, \\
\end{align*}
where \(a,b,c,d\) are positive constants. The authors study the dynamics of the new system. The results show that the system has three unstable equilibrium points and exhibits complex non-linear phenomena such as symmetry breaking, torus, chaos, hyperchaos, and heterogeneous multistability. In addition, a set of coexisting attractors has been found, consisting of both periodic and chaotic attractors. The implementation of the new hyperchaotic system based on a digital signal processor has been made. The proposed hyperchaotic system is used to construct an image encryption algorithm. Standard security analysis tools show that the proposed algorithm is effective.
Reviewer: Eduard Musafirov (Grodno)New entropy bounds via uniformly convex functionshttps://zbmath.org/1496.370142022-11-17T18:59:28.764376Z"Sayyari, Yamin"https://zbmath.org/authors/?q=ai:sayyari.yaminSummary: In this paper we give extensions of Jensen's discrete inequality considering the class of uniformly convex functions. We also introduce lower and upper bounds for Jensen's inequality (for uniformly convex functions), and we apply this results in information theory and obtain new and strong bounds for Shannon's entropy of a probability distribution.A new fractional one dimensional chaotic map and its application in high-speed image encryptionhttps://zbmath.org/1496.370992022-11-17T18:59:28.764376Z"Talhaoui, Mohamed Zakariya"https://zbmath.org/authors/?q=ai:talhaoui.mohamed-zakariya"Wang, Xingyuan"https://zbmath.org/authors/?q=ai:wang.xingyuanSummary: Chaos theory has been widely used in the design of image encryption schemes. Some low-dimensional chaotic maps have been proved to be easily predictable because of their small chaotic space. On the other hand, high-dimensional chaotic maps have a larger chaotic space. However, their structures are too complicated, and consequently, they are not suitable for real-time image encryption. Motivated by this, we propose a new fractional one-dimensional chaotic map with a large chaotic space. The proposed map has a simple structure and a high chaotic behavior in an extensive range of its control parameters values. Several chaos theoretical tools and tests have been carried out to analyze and prove the proposed map's high chaotic behavior. Moreover, we use the proposed map in the design of a novel real-time image encryption scheme. In this new scheme, we combine the substitution and permutation stages to simultaneously modify both of the pixels' positions and values. The merge of these two stages and the use of the new simple one-dimensional chaotic map significantly increase the proposed scheme's security and speed. Besides, the simulation and experimental analysis prove that the proposed scheme has high performances.Approximation of discontinuous signals by exponential sampling serieshttps://zbmath.org/1496.410082022-11-17T18:59:28.764376Z"Angamuthu, Sathish Kumar"https://zbmath.org/authors/?q=ai:angamuthu.sathish-kumar"Kumar, Prashant"https://zbmath.org/authors/?q=ai:kumar.prashant.1|kumar.prashant"Ponnaian, Devaraj"https://zbmath.org/authors/?q=ai:ponnaian.devarajThe approximation of jump discontinuity functions \(f\) by exponential sampling series \(S_{w}^{\chi}f\) is established using a representation lemma for \(S_{w}^{\chi}f\). The rate of approximation of \(S_{w}^{\chi}f\) is obtained in terms of logarithmic modulus of continuity, the round-off and time-jitter errors are also studied. The construction of a family of Mellin band-limited kernels is given such that \(\chi(1)=0\) for which \(S_{w}^{\chi}f\) converges at any jump discontinuities. Finally some graphical representation of approximation of discontinuous functions by \(S_{w}^{\chi}f\) are obtained.
Reviewer: Zoltán Finta (Cluj-Napoca)A noncommutative approach to the graphon Fourier transformhttps://zbmath.org/1496.420052022-11-17T18:59:28.764376Z"Ghandehari, Mahya"https://zbmath.org/authors/?q=ai:ghandehari.mahya"Janssen, Jeannette"https://zbmath.org/authors/?q=ai:janssen.jeannette-c-m"Kalyaniwalla, Nauzer"https://zbmath.org/authors/?q=ai:kalyaniwalla.nauzerSummary: Signal analysis on graphs relies heavily on the graph Fourier transform, which is defined as the projection of a signal onto an eigenbasis of the associated shift operator. Large graphs of similar structure may be represented by a graphon. Theoretically, graphons are limit objects of converging sequences of graphs. Our work extends previous research proposing a common scheme for signal analysis of graphs that are similar in structure to a graphon. We extend a previous definition of graphon Fourier transform, and show that the graph Fourier transforms of graphs in a converging graph sequence converge to the graphon Fourier transform of the limiting graphon. We then apply this convergence result to signal processing on Cayley graphons. We show that Fourier analysis of the underlying group enables the construction of a suitable eigen-decomposition for the graphon, which can be used as a common framework for signal processing on graphs converging to the graphon.Time-frequency transforms with Poisson kernel modulationhttps://zbmath.org/1496.420062022-11-17T18:59:28.764376Z"Zhang, Yiqiao"https://zbmath.org/authors/?q=ai:zhang.yiqiao"Chen, Qiuhui"https://zbmath.org/authors/?q=ai:chen.qiuhuiQuaternionic linear canonical wave packet transformhttps://zbmath.org/1496.420122022-11-17T18:59:28.764376Z"Bhat, Younis Ahmad"https://zbmath.org/authors/?q=ai:bhat.younis-ahmad"Sheikh, N. A."https://zbmath.org/authors/?q=ai:sheikh.neyaz-ahmed|sheikh.nadeem-ahmad|sheikh.neya-ahmad|sheikh.neyaz-ahmadThe wave packet transform is defined as the Fourier transform of a signal windowed with a given wavelet. This transform is later generalized by \textit{A. Prasad} and \textit{M. Kundu} [Integral Transforms Spec. Funct. 32, No. 11, 893--911 (2021; Zbl 1479.42019)] as linear canonical wave packet transform.
In this paper, the authors extend the concept of linear canonical wave packet transform to quaternion-valued signals. Essential properties (including uncertainty principles) of this quaternion linear canonical wave packet transform (QLCWPT) are presented. Applications of QLCWPT are not given.
Reviewer: Manfred Tasche (Rostock)Multi-dimensional linear canonical transform with applications to sampling and multiplicative filteringhttps://zbmath.org/1496.420152022-11-17T18:59:28.764376Z"Shah, Firdous A."https://zbmath.org/authors/?q=ai:shah.firdous-ahmad"Tantary, Azhar Y."https://zbmath.org/authors/?q=ai:tantary.azhar-yGiven a \(2n\times 2n\) symplectic matrix \(M=\left(\begin{matrix} A & B\\
C & D\end{matrix}\right)\), that is, \(M^T J M=J\) where \(J=\left(\begin{matrix} 0 & I_n\\
-I_n & 0\end{matrix}\right)\), the (multidimensional) linear canonical transform (LCT) \(\mathcal{L}_M\) of \(f\in L^2(\mathbb{R}^n)\) is
\[
\mathcal{L}_M[f](w)=\int_{\mathbb{R}^n} f(x) K_M(x,w)\, dx
\]
where (with \(\Omega(B,n)=(2\pi)^{-n/2} |\det{B}|^{-1/2}\) and \(|\det{B}|\neq 0\))
\[
K_M(x,w)=\Omega(B,n)\exp\left\{\frac{i}{2}(w^T DB^{-1}w-2w^TB^{-T}x+x^TB^{-1}Ax)\right\}\, .
\]
The Fourier transform corresponds to \(M=J\). The LCT satisfies the Parseval property \(\langle \mathcal{L}_M[f], \, \mathcal{L}_M[g]\rangle=\langle f,\, g\rangle\).
The authors define a linear canonical convolution by
\[
(f \circledast_M g)(t) =\int_{\mathbb{R}^n} f(x) g(t-x) \exp\left\{\frac{i}{2}(x^T B^{-1} A(x-t) + (x-t)^T B^{-1}A x )\right\}\, dx
\]
and prove (Thm.~2.1) that
\[
\mathcal{L}_M[(f \circledast_M g)](w)=\frac{\exp\left\{-i(w^T DB^{-1}w)/2\right\}}{\Omega(B,n)} \mathcal{L}_M[(f )](w) \mathcal{L}_M[(g )](w)\, .
\]
A corresponding result (Thm.~2.3) is proved for what the authors call the linear canonical correlation, which is the same as the convolution but with \(g\) replaced by \(\bar{g}\) in the corresponding convolution/transform integral (and with \(\mathcal{L}_M[(g )]\) replaced by \(\overline{\mathcal{L}_M[(g )]}\) in the corresponding product formula).
An analogue of the Heisenberg uncertainty inequality is proved (Thm.~3.1): \(\Delta_{f}^2\Delta_{\mathcal{L}_M[(f )]}^2\geq \frac{n^2}{4} |\det{B}|^2\) where \(\Delta_f^2=\frac{\|(x-x_0) f(x)\|^2}{\|f\|^2}\) with \(x_0=\|xf\|^2/\|f\|^2\). The inequality is an identity when \(f\) is a multiple of \(\exp\left(-\frac{ic x^TB^{-1}A x+2|x|^2}{2c}\right)\) for some \(c>0\). A version of Beckner's logarithmic (entropic) uncertainty inequality is also proved (Thm.~3.2), namely
\[
\int \ln |w| |\mathcal{L}_M[f](w)|^2\, dw +\int \ln |x| |f(x)|^2\, dx\geq \left[\frac{\Gamma'(n/4)}{\Gamma(n/4)}+\ln |\det{B}|-\ln\pi\right]\|f\|^2\, .
\]
Perhaps the main result (Thm.~4.1) is a sampling formula analogous to Shannon's sampling theorem in the context of the LCT. One assumes that \(f\in L^2(\mathbb{R}^n)\) is bandlimited in the LCT domain to a region \(\mathcal{D}\) that is optimally contained in a regular polyhedral region denoted by \(\tilde{\mathbb{U}}(2E)\). Then \(f\) can be expressed in terms of its samples \(f(Nk)\) via
\begin{multline*}
f(x)=\frac{\det{N}}{(2\pi)^n|\det{B}|}\exp\left\{-\frac{i}{2}(x^T B^{-1}Ax \right\} \sum_{k\in\mathbb{Z}^n} f(Nk)\\
\times \left[ \exp\left\{-\frac{i}{2}((Nk)^T B^{-1}A(Nk) \right\} \left\{ \int_{\tilde{\mathbb{U}}(2E)}\exp\left\{-i((B^{-1}w)^T)(x-Nk) \right\} dw\right\} \right]
\end{multline*}
provided \(EK=\pi BN^{-T}\) for some non-singular integer matrix \(K\). Here \(\mathbb{U}(N)=\{Nx: x\in [0,1)^n\}\) for a nonsingular \(n\times n\) matrix \(N\), and \(\tilde{\mathbb{U}}(2N)\) is a translation of \(\mathbb{U}(2N)\). An ample discussion of the lattice coset geometry that underlies the result is provided and the result is illustrated for specific choices of \(M\).
The authors assert that the approach here is the first that takes full advantage of the \(n(2n+1)\) dimensionality of the symplectic group.
Reviewer: Joseph Lakey (Las Cruces)Computational and theoretical aspects of Romanovski-Bessel polynomials and their applications in spectral approximationshttps://zbmath.org/1496.420372022-11-17T18:59:28.764376Z"Zaky, Mahmoud A."https://zbmath.org/authors/?q=ai:zaky.mahmoud-a"Abo-Gabal, Howayda"https://zbmath.org/authors/?q=ai:abo-gabal.howayda"Hafez, Ramy M."https://zbmath.org/authors/?q=ai:hafez.ramy-mahmoud"Doha, Eid H."https://zbmath.org/authors/?q=ai:doha.eid-hThe paper under review presents the main properties of a finite class of orthogonal polynomials with respect to the inverse gamma distribution over the positive real line called Romanovski-Bessel polynomials. More precisely, it introduces the related Romanovski-Bessel-Gauss-type quadrature formulae and the associated interpolation, discrete transforms, spectral differentiation and integration techniques in the physical and frequency spaces, and basic approximation results for the weighted projection operator in weighted Sobolev space. It also addresses the relationship between such kinds of finite orthogonal polynomials and other classes of finite and infinite orthogonal polynomials.
Reviewer: M. Abdessadek Saib (Tebessa)Exponential type bases on a finite union of certain disjoint intervals of equal lengthhttps://zbmath.org/1496.420402022-11-17T18:59:28.764376Z"Ghosh, Riya"https://zbmath.org/authors/?q=ai:ghosh.riya"Selvan, A. Antony"https://zbmath.org/authors/?q=ai:selvan.a-antonySummary: Let \(\Lambda\) be a sequence of distinct real numbers and \(\mathsf{T}=\{\epsilon_0,\dots ,\epsilon_{\nu -1}: \epsilon_i<\epsilon_{i+1}\}\) be a finite set of nonnegative integers. To each \((\Lambda ,\mathsf{T})\), we associate a system of exponentials
\[
\begin{aligned} \mathcal{E}(\Lambda,\mathsf{T}):=\left\{ x^{\epsilon_0}\mathrm{e}^{2\pi i\lambda x},x^{\epsilon_1}\mathrm{e}^{2\pi i\lambda x},\dots ,x^{\epsilon_{\nu -1}}\mathrm{e}^{2\pi i\lambda x}:\lambda \in \Lambda \right\}. \end{aligned}
\]
For a disconnected set \(\Omega\), the construction of a Riesz basis of exponential system \(\mathcal{E}(\Lambda,\mathsf{T})\) on \(L^2(\Omega)\) is generally a difficult problem. In the literature, the exponential Riesz basis problem is solved for certain disconnected sets \(\Omega\) for \(\nu =1\) and \(\epsilon_0=0\). It is well-known that this problem is equivalent to the construction of a complete interpolation set in the Paley-Wiener space \(\mathcal{PW}(\Omega)\). In this paper, we construct a complete interpolation set involving derivative samples in the Paley-Wiener space of a finite union of certain disjoint intervals of equal length. Furthermore, we provide an explicit sampling formula in this case.Toric symplectic geometry and full spark frameshttps://zbmath.org/1496.420412022-11-17T18:59:28.764376Z"Needham, Tom"https://zbmath.org/authors/?q=ai:needham.tom"Shonkwiler, Clayton"https://zbmath.org/authors/?q=ai:shonkwiler.claytonSummary: The collection of \(d \times N\) complex matrices with prescribed column norms and singular values forms an algebraic variety, which we refer to as a frame space. Elements of frame spaces -- i.e., frames -- are used to give robust signal representations, so that geometrical properties of frame spaces are of interest to the signal processing community. This paper is concerned with the question: what is the probability that a frame drawn at random from a given frame space has the property that any subset of \(d\) of its columns gives a basis for \(\mathbb{C}^d\)? We show that the probability is one, generalizing recent work of \textit{J. Cahill} et al. [SIAM J. Appl. Algebra Geom. 1, No. 1, 38--72 (2017; Zbl 1370.42023)]. To prove this, we show that frame spaces are related to highly structured objects called toric symplectic manifolds. As another application, we characterize the norm and spectral data for which the corresponding frame space has singularities, answering an open question in the literature.Persistent Laplacians: properties, algorithms and implicationshttps://zbmath.org/1496.550072022-11-17T18:59:28.764376Z"Mémoli, Facundo"https://zbmath.org/authors/?q=ai:memoli.facundo"Wan, Zhengchao"https://zbmath.org/authors/?q=ai:wan.zhengchao"Wang, Yusu"https://zbmath.org/authors/?q=ai:wang.yusuThis paper studies the \textit{persistent Laplacian}, i.e. an extension of the ordinary combinatorial Laplacian to sequences of simplicial complexes. Given two pairs of simplicial complexes \(K\) and \(L\), with \(K \hookrightarrow L\), the authors introduce an effective algorithm for finding a matrix representation of the \(q\)th persistent Laplacian \(\Delta_q^{K, L}\). Among other things, this enables the calculation of the \(q\)th persistent Betti number of the inclusion \(K \hookrightarrow L\). Next to these results, the authors also prove properties of the spectrum of \(\Delta_q^{K, L}\), as well as a link between its nullity and persistent Betti numbers. Furthermore, the persistent Laplacian is linked to the notion of effective resistance in graphs. This paper hence makes the previously-introduced concept of a persistent Laplacian effectively computable, providing both a highly-relevant formalisation as well as a contextualisation.
Reviewer: Bastian Rieck (Bern)Queueing models for cognitive wireless networks with sensing time of secondary usershttps://zbmath.org/1496.601142022-11-17T18:59:28.764376Z"Phung-Duc, Tuan"https://zbmath.org/authors/?q=ai:phung-duc.tuan"Akutsu, Kohei"https://zbmath.org/authors/?q=ai:akutsu.kohei"Kawanishi, Ken'ichi"https://zbmath.org/authors/?q=ai:kawanishi.kenichi"Salameh, Osama"https://zbmath.org/authors/?q=ai:salameh.osama"Wittevrongel, Sabine"https://zbmath.org/authors/?q=ai:wittevrongel.sabineSummary: This paper considers queueing models for cognitive radio networks that account for the sensing time of secondary users (SUs). In cognitive radio networks, secondary users are allowed to opportunistically use idle channels originally allocated to primary users (PUs). To this end, SUs must sense the state of the channels before transmission. After sensing, if an idle channel is available, the SU can start transmission immediately; otherwise, the SU must carry out another channel sensing. In this paper, we study two retrial queueing models with an unlimited number of sensing SUs, where PUs have preemptive priority over SUs. The two models differ in whether or not an arriving PU can interrupt a SU transmission also in case there are still idle channels available. We show that both models have the same stability condition and that the model without interruptions in case of available idle channels has a slightly lower number of sensing SUs than the model with interruptions.Cumulative past Fisher information measure and its extensionshttps://zbmath.org/1496.620282022-11-17T18:59:28.764376Z"Balakrishnan, Narayanaswamy"https://zbmath.org/authors/?q=ai:balakrishnan.narayanaswamy"Kharazmi, Omid"https://zbmath.org/authors/?q=ai:kharazmi.omidSummary: In this work, we define the cumulative past Fisher (CPF) information and the relative cumulative past Fisher (RCRF) information measures for parameter as well as for the distribution function of the underlying random variables. We show that these cumulative past Fisher information measures can be expressed in terms of the reversed hazard rate function. We also define three extensions of the CPF information measure. Further, we study these cumulative information measures and their Bayes versions for some well-known models used in reliability, economics and survival analysis. The associated results reveal some interesting connections between the proposed Fisher type information measures with some well-known information divergences and reliability measures.Conjugate predictive distributions and generalized entropieshttps://zbmath.org/1496.620302022-11-17T18:59:28.764376Z"Gutiérrez-Peña, Eduardo"https://zbmath.org/authors/?q=ai:gutierrez-pena.eduardo"Mendoza, Manuel"https://zbmath.org/authors/?q=ai:mendoza.manuelSummary: It is well-known that maximizing the Shannon entropy gives rise to an exponential family of distributions. On the other hand, some Bayesian predictive distributions, derived from exponential family sampling models with standard conjugate priors on the canonical parameter, maximize a generalized entropy indexed by a parameter \(\alpha\). As \(\alpha \rightarrow \infty\), this generalized entropy converges to the usual Shannon entropy, while the predictive distribution converges to its corresponding sampling model. The aim of this paper is to study this type of connection between generalized entropies based on a certain family of \(\alpha\)-divergences and the class of predictive distributions mentioned above. We discuss two important examples in some detail, and argue that similar results must also hold for other exponential families.
For the entire collection see [Zbl 1478.60006].The whole and the parts: the minimum description length principle and the a-contrario frameworkhttps://zbmath.org/1496.621112022-11-17T18:59:28.764376Z"von Gioi, Rafael Grompone"https://zbmath.org/authors/?q=ai:grompone-von-gioi.rafael"Paulino, Ignacio Ramírez"https://zbmath.org/authors/?q=ai:paulino.ignacio-ramirez"Randall, Gregory"https://zbmath.org/authors/?q=ai:randall.gregoryStochastic partial differential equations for computer vision with uncertain datahttps://zbmath.org/1496.650032022-11-17T18:59:28.764376Z"Preusser, Tobias"https://zbmath.org/authors/?q=ai:preusser.tobias"Kirby, Robert M."https://zbmath.org/authors/?q=ai:kirby.robert-m-ii"Pätz, Torben"https://zbmath.org/authors/?q=ai:patz.torbenPublisher's description: In image processing and computer vision applications such as medical or scientific image data analysis, as well as in industrial scenarios, images are used as input measurement data. It is good scientific practice that proper measurements must be equipped with error and uncertainty estimates. For many applications, not only the measured values but also their errors and uncertainties, should be -- and more and more frequently are -- taken into account for further processing. This error and uncertainty propagation must be done for every processing step such that the final result comes with a reliable precision estimate.
The goal of this book is to introduce the reader to the recent advances from the field of uncertainty quantification and error propagation for computer vision, image processing, and image analysis that are based on partial differential equations (PDEs). It presents a concept with which error propagation and sensitivity analysis can be formulated with a set of basic operations. The approach discussed in this book has the potential for application in all areas of quantitative computer vision, image processing, and image analysis. In particular, it might help medical imaging finally become a scientific discipline that is characterized by the classical paradigms of observation, measurement, and error awareness.
This book is comprised of eight chapters. After an introduction to the goals of the book (Chapter 1), we present a brief review of PDEs and their numerical treatment (Chapter 2), PDE-based image processing (Chapter 3), and the numerics of stochastic PDEs (Chapter 4). We then proceed to define the concept of stochastic images (Chapter 5), describe how to accomplish image processing and computer vision with stochastic images (Chapter 6), and demonstrate the use of these principles for accomplishing sensitivity analysis (Chapter 7). Chapter 8 concludes the book and highlights new research topics for the future.Multiscale approach for three-dimensional conformal image registrationhttps://zbmath.org/1496.650282022-11-17T18:59:28.764376Z"Han, Huan"https://zbmath.org/authors/?q=ai:han.huan"Wang, Zhengping"https://zbmath.org/authors/?q=ai:wang.zhengping"Zhang, Yimin"https://zbmath.org/authors/?q=ai:zhang.yimin|zhang.yimin.1WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditionshttps://zbmath.org/1496.650742022-11-17T18:59:28.764376Z"Colbrook, Matthew J."https://zbmath.org/authors/?q=ai:colbrook.matthew-jAdiabatic exponential midpoint rule for the dispersion-managed nonlinear Schrödinger equationhttps://zbmath.org/1496.651422022-11-17T18:59:28.764376Z"Jahnke, T."https://zbmath.org/authors/?q=ai:jahnke.thomas.2|jahnke.tobias"Mikl, M."https://zbmath.org/authors/?q=ai:mikl.marcel|mikl.michalSummary: Modeling long-haul data transmission through dispersion-managed optical fiber cables leads to a nonlinear Schrödinger equation where the linear part is multiplied by a large, discontinuous and rapidly changing coefficient function. Typical solutions oscillate with high frequency and have low regularity in time, such that traditional numerical methods suffer from severe step size restrictions and typically converge only with low order. We construct and analyse a norm-conserving, uniformly convergent time-integrator called the adiabatic exponential midpoint rule by extending techniques developed in [the authors, Numer. Math. 138, No. 4, 975--1009 (2018; Zbl 1448.65107)]. This method is several orders of magnitude more accurate than standard schemes for a relevant set of parameters. In particular, we prove that the accuracy of the method improves considerably if the step size is chosen in a special way.The science of quantitative information flowhttps://zbmath.org/1496.680012022-11-17T18:59:28.764376Z"Alvim, Mário S."https://zbmath.org/authors/?q=ai:alvim.mario-s"Chatzikokolakis, Konstantinos"https://zbmath.org/authors/?q=ai:chatzikokolakis.konstantinos"McIver, Annabelle"https://zbmath.org/authors/?q=ai:mciver.annabelle-k"Morgan, Carroll"https://zbmath.org/authors/?q=ai:morgan.carroll-c"Palamidessi, Catuscia"https://zbmath.org/authors/?q=ai:palamidessi.catuscia"Smith, Geoffrey"https://zbmath.org/authors/?q=ai:smith.geoffrey-b|smith.geoffrey-d|smith.geoffrey|smith.geoffrey-howard|smith.geoffrey-s|smith.geoffrey-lPublisher's description: This book presents a comprehensive mathematical theory that explains precisely what information flow is, how it can be assessed quantitatively -- so bringing precise meaning to the intuition that certain information leaks are small enough to be tolerated -- and how systems can be constructed that achieve rigorous, quantitative information-flow guarantees in those terms. It addresses the fundamental challenge that functional and practical requirements frequently conflict with the goal of preserving confidentiality, making perfect security unattainable.
Topics include: a systematic presentation of how unwanted information flow, i.e., ``leaks'', can be quantified in operationally significant ways and then bounded, both with respect to estimated benefit for an attacking adversary and by comparisons between alternative implementations; a detailed study of capacity, refinement, and Dalenius leakage, supporting robust leakage assessments; a unification of information-theoretic channels and information-leaking sequential programs within the same framework; and a collection of case studies, showing how the theory can be applied to interesting realistic scenarios.
The text is unified, self-contained and comprehensive, accessible to students and researchers with some knowledge of discrete probability and undergraduate mathematics, and contains exercises to facilitate its use as a course textbook.Tree-based cryptographic access controlhttps://zbmath.org/1496.680532022-11-17T18:59:28.764376Z"Alderman, James"https://zbmath.org/authors/?q=ai:alderman.james"Farley, Naomi"https://zbmath.org/authors/?q=ai:farley.naomi"Crampton, Jason"https://zbmath.org/authors/?q=ai:crampton.jasonSummary: As more and more data is outsourced to third party servers, the enforcement of access control policies using cryptographic techniques becomes increasingly important. Enforcement schemes based on symmetric cryptography typically issue users a small amount of secret material which, in conjunction with public information, allows the derivation of decryption keys for all data objects for which they are authorized.
We generalize the design of prior enforcement schemes by mapping access control policies to a graph-based structure. Unlike prior work, we envisage that this structure may be defined \textit{independently} of the policy to target different efficiency goals; the key issue then is how best to map policies to such structures. To exemplify this approach, we design a space-efficient KAS based on a binary tree which imposes a logarithmic bound on the required number of derivations whilst eliminating public information. In the worst case, users may require more cryptographic material than in prior schemes; we mitigate this by designing heuristic optimizations of the mapping and show through experimental results that our scheme performs well compared to existing schemes.
For the entire collection see [Zbl 1493.68010].POR for security protocol equivalences. Beyond action-determinismhttps://zbmath.org/1496.680552022-11-17T18:59:28.764376Z"Baelde, David"https://zbmath.org/authors/?q=ai:baelde.david"Delaune, Stéphanie"https://zbmath.org/authors/?q=ai:delaune.stephanie"Hirschi, Lucca"https://zbmath.org/authors/?q=ai:hirschi.luccaSummary: Formal methods have proved effective to automatically analyse protocols. Recently, much research has focused on verifying \textit{trace equivalence} on protocols, which is notably used to model interesting \textit{privacy} properties such as anonymity or unlinkability. Several tools for checking trace equivalence rely on a naive and expensive exploration of all interleavings of concurrent actions, which calls for partial-order reduction (POR) techniques. In this paper, we present the first POR technique for protocol equivalences that does not rely on an action-determinism assumption: we recast trace equivalence as a reachability problem, to which persistent and sleep set techniques can be applied, and we show how to effectively apply these results in the context of symbolic execution. We report on a prototype implementation, improving the tool DeepSec.
For the entire collection see [Zbl 1493.68018].Labeled homomorphic encryption. Scalable and privacy-preserving processing of outsourced datahttps://zbmath.org/1496.680562022-11-17T18:59:28.764376Z"Barbosa, Manuel"https://zbmath.org/authors/?q=ai:barbosa.manuel"Catalano, Dario"https://zbmath.org/authors/?q=ai:catalano.dario"Fiore, Dario"https://zbmath.org/authors/?q=ai:fiore.darioSummary: In privacy-preserving processing of outsourced data a Cloud server stores data provided by one or multiple data providers and then is asked to compute several functions over it. We propose an efficient methodology that solves this problem with the guarantee that a honest-but-curious Cloud learns no information about the data and the receiver learns nothing more than the results. Our main contribution is the proposal and efficient instantiation of a new cryptographic primitive called \textit{Labeled Homomorphic Encryption} (\textsf{labHE}). The fundamental insight underlying this new primitive is that homomorphic computation can be significantly accelerated whenever the program that is being computed over the encrypted data is known to the decrypter and is not secret -- previous approaches to homomorphic encryption do not allow for such a trade-off. Our realization and implementation of \textsf{labHE} targets computations that can be described by degree-two multivariate polynomials. As an application, we consider privacy preserving Genetic Association Studies (GAS), which require computing risk estimates from features in the human genome. Our approach allows performing GAS efficiently, non interactively and without compromising neither the privacy of patients nor potential intellectual property of test laboratories.
For the entire collection see [Zbl 1493.68010].Reusable two-round MPC from LPNhttps://zbmath.org/1496.680572022-11-17T18:59:28.764376Z"Bartusek, James"https://zbmath.org/authors/?q=ai:bartusek.james"Garg, Sanjam"https://zbmath.org/authors/?q=ai:garg.sanjam"Srinivasan, Akshayaram"https://zbmath.org/authors/?q=ai:srinivasan.akshayaram"Zhang, Yinuo"https://zbmath.org/authors/?q=ai:zhang.yinuoSummary: We present a new construction of maliciously-secure, two-round multiparty computation (MPC) in the CRS model, where the first message is reusable an unbounded number of times. The security of the protocol relies on the Learning Parity with Noise (LPN) assumption with inverse polynomial noise rate \(1/n^{1-\epsilon }\) for small enough constant \(\epsilon \), where \(n\) is the LPN dimension. Prior works on reusable two-round MPC required assumptions such as DDH or LWE that imply some flavor of homomorphic computation. We obtain our result in two steps:
\begin{itemize}
\item[--] In the first step, we construct a two-round MPC protocol in the \textit{silent pre-processing model}
[\textit{E. Boyle} et al., Lect. Notes Comput. Sci. 11694, 489--518 (2019; Zbl 07178325)].
Specifically, the parties engage in a computationally inexpensive setup procedure that generates some correlated random strings. Then, the parties commit to their inputs. Finally, each party sends a message depending on the function to be computed, and these messages can be decoded to obtain the output. Crucially, the complexity of the pre-processing phase and the input commitment phase do not grow with the size of the circuit to be computed. We call this\textit{ multiparty silent NISC} (msNISC), generalizing the notion of two-party silent NISC of
\textit{E. Boyle} et al. [``Efficient two-round OT extension and silent non-interactive secure computation'', in: Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, CCS'19. New York, NY: Association for Computing Machinery (ACM). 219--308 (2019; \url{doi:10.1145/3319535.3354255})].
We provide a construction of msNISC from LPN in the random oracle model.
\item[--] In the second step, we give a transformation that removes the pre-processing phase and use of random oracle from the previous protocol. This transformation additionally adds (unbounded) reusability of the first round message, giving the first construction of reusable two-round MPC from the LPN assumption. This step makes novel use of randomized encoding of circuits
[\textit{B. Applebaum} et al., SIAM J. Comput. 36, No. 4, 845--888 (2006; Zbl 1126.94014)]
and a variant of the ``tree of MPC message'' technique of
\textit{P. Ananth} et al. [Lect. Notes Comput. Sci. 12550, 28--57 (2020; Zbl 1479.94113)] and \textit{J. Bartusek} et al. [Lect. Notes Comput. Sci. 12551, 320--348 (2020; Zbl 07496584)].
\end{itemize}
For the entire collection see [Zbl 1490.94004].Zero round-trip time for the extended access control protocolhttps://zbmath.org/1496.680592022-11-17T18:59:28.764376Z"Brendel, Jacqueline"https://zbmath.org/authors/?q=ai:brendel.jacqueline"Fischlin, Marc"https://zbmath.org/authors/?q=ai:fischlin.marcSummary: The Extended Access Control (EAC) protocol allows to create a shared cryptographic key between a client and a server. While originally used in the context of identity card systems and machine readable travel documents, the EAC protocol is increasingly adopted as a universal solution to secure transactions or for attribute-based access control with smart cards. Here we discuss how to enhance the EAC protocol by a so-called zero-round trip time (0RTT) mode. Through this mode the client can, without further interaction, immediately derive a new key from cryptographic material exchanged in previous executions. This makes the 0RTT mode attractive from an efficiency viewpoint such that the upcoming TLS 1.3 standard, for instance, will include its own 0RTT mode. Here we show that also the EAC protocol can be augmented to support a 0RTT mode. Our proposed EAC+0RTT protocol is compliant with the basic EAC protocol and adds the 0RTT mode smoothly on top. We also prove the security of our proposal according to the common security model of Bellare and Rogaway in the multi-stage setting.
For the entire collection see [Zbl 1493.68010].Efficiently deciding equivalence for standard primitives and phaseshttps://zbmath.org/1496.680602022-11-17T18:59:28.764376Z"Cortier, Véronique"https://zbmath.org/authors/?q=ai:cortier.veronique"Dallon, Antoine"https://zbmath.org/authors/?q=ai:dallon.antoine"Delaune, Stéphanie"https://zbmath.org/authors/?q=ai:delaune.stephanieSummary: Privacy properties like anonymity or untraceability are now well identified, desirable goals of many security protocols. Such properties are typically stated as equivalence properties. However, automatically checking equivalence of protocols often yields efficiency issues.
We propose an efficient algorithm, based on graph planning and SAT-solving. It can decide equivalence for a bounded number of sessions, for protocols with standard cryptographic primitives and phases (often necessary to specify privacy properties), provided protocols are well-typed, that is encrypted messages cannot be confused. The resulting implementation, SAT-Equiv, demonstrates a significant speed-up w.r.t. other existing tools that decide equivalence, covering typically more than 100 sessions. Combined with a previous result, SAT-Equiv can now be used to prove security, for some protocols, for an unbounded number of sessions.
For the entire collection see [Zbl 1493.68018].A better composition operator for quantitative information flow analyseshttps://zbmath.org/1496.680612022-11-17T18:59:28.764376Z"Engelhardt, Kai"https://zbmath.org/authors/?q=ai:engelhardt.kaiSummary: Given a description of the quantitative information flow (qif) for components, how can we determine the qif of a system composed from components? We explore this fundamental question mathematically and provide an answer based on a new composition operator. We investigate its properties and prove that it generalises existing composition operators. We illustrate the results with a fresh look on Chaum's dining cryptographers. We show that the new operator enjoys various convenient algebraic properties and that it is well-behaved under composition refinement.
For the entire collection see [Zbl 1493.68010].Rifflescrambler -- a memory-hard password storing functionhttps://zbmath.org/1496.680622022-11-17T18:59:28.764376Z"Gotfryd, Karol"https://zbmath.org/authors/?q=ai:gotfryd.karol"Lorek, Paweł"https://zbmath.org/authors/?q=ai:lorek.pawel"Zagórski, Filip"https://zbmath.org/authors/?q=ai:zagorski.filipSummary: We introduce RiffleScrambler: a new family of directed acyclic graphs and a corresponding data-independent memory hard function with password independent memory access. We prove its memory hardness in the random oracle model.
RiffleScrambler is similar to Catena -- updates of hashes are determined by a graph (bit-reversal or double-butterfly graph in Catena). The advantage of the RiffleScrambler over Catena is that the underlying graphs are not predefined but are generated per salt, as in Balloon Hashing. Such an approach leads to higher immunity against practical parallel attacks. RiffleScrambler offers better efficiency than Balloon Hashing since the in-degree of the underlying graph is equal to 3 (and is much smaller than in Ballon Hashing). At the same time, because the underlying graph is an instance of a Superconcentrator, our construction achieves the same time-memory trade-offs.
For the entire collection see [Zbl 1493.68017].Anonymous single-sign-on for \(n\) designated services with traceabilityhttps://zbmath.org/1496.680642022-11-17T18:59:28.764376Z"Han, Jinguang"https://zbmath.org/authors/?q=ai:han.jinguang"Chen, Liqun"https://zbmath.org/authors/?q=ai:chen.liqun.1"Schneider, Steve"https://zbmath.org/authors/?q=ai:schneider.steve-a"Treharne, Helen"https://zbmath.org/authors/?q=ai:treharne.helen"Wesemeyer, Stephan"https://zbmath.org/authors/?q=ai:wesemeyer.stephanSummary: Anonymous Single-Sign-On authentication schemes have been proposed to allow users to access a service protected by a verifier without revealing their identity. This has become more important with the introduction of strong privacy regulations. In this paper we describe a new approach whereby anonymous authentication to different verifiers is achieved via authorisation tags and pseudonyms. The particular innovation of our scheme is that authentication can occur only between a user and its designated verifier for a service, and the verification cannot be performed by any other verifier. The benefit of this authentication approach is that it prevents information leakage of a user's service access information, even if the verifiers for these services collude. Our scheme also supports a trusted third party who is authorised to de-anonymise the user and reveal her whole service access information if required. Furthermore, our scheme is lightweight because it does not rely on attribute or policy-based signature schemes to enable access to multiple services. The scheme's security model is given together with a security proof, an implementation and a performance evaluation.
For the entire collection see [Zbl 1493.68018].Stateful protocol compositionhttps://zbmath.org/1496.680652022-11-17T18:59:28.764376Z"Hess, Andreas V."https://zbmath.org/authors/?q=ai:hess.andreas-v"Mödersheim, Sebastian A."https://zbmath.org/authors/?q=ai:modersheim.sebastian-alexander"Brucker, Achim D."https://zbmath.org/authors/?q=ai:brucker.achim-dSummary: We prove a parallel compositionality result for protocols with a shared mutable state, i.e., stateful protocols. For protocols satisfying certain compositionality conditions our result shows that verifying the component protocols in isolation is sufficient to prove security of their composition. Our main contribution is an extension of the compositionality paradigm to stateful protocols where participants maintain shared databases. Because of the generality of our result we also cover many forms of sequential composition as a special case of stateful parallel composition. Moreover, we support declassification of shared secrets. As a final contribution we prove the core of our result in Isabelle/HOL, providing a strong correctness guarantee of our proofs.
For the entire collection see [Zbl 1493.68018].Efficient proof composition for verifiable computationhttps://zbmath.org/1496.680672022-11-17T18:59:28.764376Z"Keuffer, Julien"https://zbmath.org/authors/?q=ai:keuffer.julien"Molva, Refik"https://zbmath.org/authors/?q=ai:molva.refik"Chabanne, Hervé"https://zbmath.org/authors/?q=ai:chabanne.herveSummary: Outsourcing machine learning algorithms helps users to deal with large amounts of data without the need to develop the expertise required by these algorithms. Outsourcing however raises severe security issues due to potentially untrusted service providers. Verifiable computing (VC) tackles some of these issues by assuring computational integrity for an outsourced computation. In this paper, we design a VC protocol tailored to verify a sequence of operations for which no existing VC scheme is suitable to achieve realistic performance objective for the entire sequence. We thus suggest a technique to compose several specialized and efficient VC schemes with a general purpose VC protocol, like Parno et al.'s Pinocchio, by integrating the verification of the proofs generated by these specialized schemes as a function that is part of the sequence of operations verified using the general purpose scheme. The resulting scheme achieves the objectives of the general purpose scheme with increased efficiency for the prover. The scheme relies on the underlying cryptographic assumptions of the composed protocols for correctness and soundness.
For the entire collection see [Zbl 1493.68018].Making \textit{any} attribute-based encryption accountable, efficientlyhttps://zbmath.org/1496.680682022-11-17T18:59:28.764376Z"Lai, Junzuo"https://zbmath.org/authors/?q=ai:lai.junzuo"Tang, Qiang"https://zbmath.org/authors/?q=ai:tang.qiangSummary: Attribute-based encryption (ABE) as one of the most interesting multi-recipient public encryption systems, naturally requires some ``tracing mechanisms'' to identify misbehaving users to foster accountability when unauthorized key re-distributions are taken place.
We give a generic construction of (black-box) traceable ABE which only doubles the ciphertext size of the underlying ABE scheme. When instantiating properly, it yields the first such scheme with constant size ciphertext and expressive access control.
Furthermore, we extend our generic construction of traceable ABE to support authority accountability. This property is essential for generating an un-deniable proof for user misbehaviors. Our new generic construction gives the first black-box traceable ABE with authority accountability, and constant size ciphertext. All properties are achieved in standard security models.
For the entire collection see [Zbl 1493.68017].Automated identification of desynchronisation attacks on shared secretshttps://zbmath.org/1496.680712022-11-17T18:59:28.764376Z"Mauw, Sjouke"https://zbmath.org/authors/?q=ai:mauw.sjouke"Smith, Zach"https://zbmath.org/authors/?q=ai:smith.zach"Toro-Pozo, Jorge"https://zbmath.org/authors/?q=ai:toro-pozo.jorge"Trujillo-Rasua, Rolando"https://zbmath.org/authors/?q=ai:trujillo-rasua.rolandoSummary: Key-updating protocols are a class of communication protocol that aim to increase security by having the participants change encryption keys between protocol executions. However, such protocols can be vulnerable to desynchronisation attacks, a denial of service attack in which the agents are tricked into updating their keys improperly, impeding future communication. In this work we introduce a method that can be used to automatically verify (or falsify) resistance to desynchronisation attacks for a range of protocols. This approach is then used to identify previously unreported vulnerabilities in two published RFID grouping protocols.
For the entire collection see [Zbl 1493.68018].Decentralized policy-hiding ABE with receiver privacyhttps://zbmath.org/1496.680722022-11-17T18:59:28.764376Z"Michalevsky, Yan"https://zbmath.org/authors/?q=ai:michalevsky.yan"Joye, Marc"https://zbmath.org/authors/?q=ai:joye.marcSummary: Attribute-based encryption (ABE) enables limiting access to encrypted data to users with certain attributes. Different aspects of ABE were studied, such as the multi-authority setting (MA-ABE), and policy hiding, meaning the access policy is unknown to unauthorized parties. However, no practical scheme so far provably provides both properties, which are often desirable in real-world applications: supporting decentralization while hiding the access policy. We present the first practical decentralized ABE scheme with a proof of being policy-hiding. Our construction is based on a decentralized inner-product predicate encryption scheme, introduced in this paper, which hides the encryption policy. It results in an ABE scheme supporting conjunctions, disjunctions and threshold policies, that protects the access policy from parties that are not authorized to decrypt the content. Further, we address the issue of receiver privacy. By using our scheme in combination with vector commitments, we hide the overall set of attributes possessed by the receiver from individual authorities, only revealing the attribute that the authority is controlling. Finally, we propose randomizing-polynomial encodings that immunize the scheme in the presence of corrupt authorities.
For the entire collection see [Zbl 1493.68017].Symmetric-key corruption detection: when XOR-MACs meet combinatorial group testinghttps://zbmath.org/1496.680732022-11-17T18:59:28.764376Z"Minematsu, Kazuhiko"https://zbmath.org/authors/?q=ai:minematsu.kazuhiko"Kamiya, Norifumi"https://zbmath.org/authors/?q=ai:kamiya.norifumiSummary: We study a class of MACs, which we call corruption detectable MAC, that is able to not only check the integrity of the whole message, but also detect a part of the message that is corrupted. It can be seen as an application of the classical Combinatorial Group Testing (CGT) to message authentication. However, previous work on this application has an inherent limitation in its communication cost. We present a novel approach to combine CGT and a class of linear MACs (XOR-MAC) that breaks this limit. Our proposal, \textsf{XOR}-\textsf{GTM}, has a significantly smaller communication cost than any of the previous corruption detectable MACs, while keeping the same corruption detection capability. Our numerical examples for storage application show a reduction of communication by a factor of around 15 to 70 compared with previous schemes. \textsf{XOR}-\textsf{GTM} is parallelizable and is as efficient as standard MACs. We prove that \textsf{XOR}-\textsf{GTM} is provably secure under the standard cryptographic assumptions.
For the entire collection see [Zbl 1493.68022].Forward-secure revocable identity-based encryptionhttps://zbmath.org/1496.680742022-11-17T18:59:28.764376Z"Qin, Baodong"https://zbmath.org/authors/?q=ai:qin.baodong"Bai, Xue"https://zbmath.org/authors/?q=ai:bai.xue"Zheng, Dong"https://zbmath.org/authors/?q=ai:zheng.dong"Cui, Hui"https://zbmath.org/authors/?q=ai:cui.hui"Luo, Yiyuan"https://zbmath.org/authors/?q=ai:luo.yiyuanSummary: For identity-based encryption (IBE), if a user's private key is compromised, the security of his/her ciphertexts will fail completely. Revocation capability provides an effective way to mitigate above harm, so that the adversary cannot access to future ciphertexts anymore. However, current revocable IBE schemes do not provide any means to guarantee the security of the user's previous ciphertexts. In this paper, we propose a new cryptographic primitive, namely forward-secure revocable identity-based encryption (FS-RIBE), to address this issue. In FS-RIBE, when the event of full exposure of the user's current private key occurs, the forward security can guarantee that the user's private keys prior to this remain secure, while the revocation capability further guarantees that the adversary cannot obtain any valid decryption keys for future times. We provide formal definition and security model for FS-RIBE, and give a generic construction that is secure under the security model from (Hierarchical) IBE. Finally, we show some results of instantiations from various IBE and Hierarchical IBE schemes.
For the entire collection see [Zbl 1487.68013].Cross-domain attribute-based access control encryptionhttps://zbmath.org/1496.680752022-11-17T18:59:28.764376Z"Sedaghat, Mahdi"https://zbmath.org/authors/?q=ai:sedaghat.mahdi"Preneel, Bart"https://zbmath.org/authors/?q=ai:preneel.bartSummary: Logic access control enforces who can read and write data; the enforcement is typically performed by a fully trusted entity.
At TCC 2016 [Lect. Notes Comput. Sci. 9986, 547--576 (2016; Zbl 1400.94138)], \textit{I. Damgård} et al.
proposed Access Control Encryption (ACE) schemes where a predicate function decides whether or not users can read (decrypt) and write (encrypt) data, while the message secrecy and the users' anonymity are preserved against malicious parties. Subsequently, several ACE constructions with an arbitrary identity-based access policy have been proposed, but they have huge ciphertext and key sizes and/or rely on indistinguishability obfuscation.
At SP 2021 [``Cross-domain access control encryption: arbitrary-policy, constant-size, efficient'', in: Proceeding of the 2021 IEEE symposium on security and privacy, SP 2021. Los Alamitos, CA: IEEE Computer Society. 748--761 (2021; \url{doi:10.1109/SP40001.2021.00023})], \textit{X. Wang} and \textit{S. M. Chow}
proposed a Cross-Domain ACE scheme with constant-size ciphertext and arbitrary identity-based policy; the key generators are separated into two distinct parties, called Sender Authority and Receiver Authority. In this paper, we improve over their work with a novel construction that provides a more expressive access control policy based on attributes rather than on identities, the security of which relies on standard assumptions. Our generic construction combines Structure-Preserving Signatures, Non-Interactive Zero-Knowledge proofs, and Re-randomizable Ciphertext-Policy Attribute-Based Encryption schemes. Moreover, we propose an efficient scheme in which the sizes of ciphertexts and encryption and decryption keys are constant and thus independent of the number of receivers and their attributes. Our experiments demonstrate that not only is our system more flexible, but it also is more efficient and results in shorter decryption keys (reduced from about 100 to 47 bytes) and ciphertexts (reduced from about 1400 to 1047).
For the entire collection see [Zbl 1490.68011].Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) securityhttps://zbmath.org/1496.680762022-11-17T18:59:28.764376Z"Zuo, Cong"https://zbmath.org/authors/?q=ai:zuo.cong"Sun, Shi-Feng"https://zbmath.org/authors/?q=ai:sun.shifeng"Liu, Joseph K."https://zbmath.org/authors/?q=ai:liu.joseph-k-k"Shao, Jun"https://zbmath.org/authors/?q=ai:shao.jun"Pieprzyk, Josef"https://zbmath.org/authors/?q=ai:pieprzyk.josef-pSummary: Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in encrypted cloud storage. However, it has been reported that DSSE usually suffers from file-injection attacks and content leak of deleted documents. To mitigate these attacks, forward security and backward security have been proposed. Nevertheless, the existing forward/backward-secure DSSE schemes can only support single keyword queries. To address this problem, in this paper, we propose two DSSE schemes supporting range queries. One is forward-secure and supports a large number of documents. The other can achieve both forward security and backward security, while it can only support a limited number of documents. Finally, we also give the security proofs of the proposed DSSE schemes in the random oracle model.
For the entire collection see [Zbl 1493.68017].Ways of synthesizing binary programs admitting recursive call of procedureshttps://zbmath.org/1496.681212022-11-17T18:59:28.764376Z"Zhukov, V. V."https://zbmath.org/authors/?q=ai:zhukov.vladimir-v|zhukov.vitalii-vladimirovichSummary: A model of binary programs implementing the functions of the algebra of logic (Boolean functions) is considered. The programs consist of one or several modules containing instructions of three types: computational and redirecting instructions and instructions for summoning the procedures. In contrast to earleir models of binary programs, a model is introduced that admits the recursive summoning of procedures; i.e., the procedures can directly summon themselves while executing a binary program, or through other procedures. The functioning of this model of programs is described, as is its relationship to other discrete control systems (e.g., circuits made of functional elements or binary decision diagrams). Ways are presented for obtaining lower and upper estimates of the Shannon function for the complexity of using Boolean functions in the class of binary programs. The proposed technique allows the asymptotics of the Shannon function to be established under certain structural and parametric limitations imposed on the model of binary programs.Generic multi-keyword ranked search on encrypted cloud datahttps://zbmath.org/1496.681322022-11-17T18:59:28.764376Z"Kasra Kermanshahi, Shabnam"https://zbmath.org/authors/?q=ai:kasra-kermanshahi.shabnam"Liu, Joseph K."https://zbmath.org/authors/?q=ai:liu.joseph-k-k"Steinfeld, Ron"https://zbmath.org/authors/?q=ai:steinfeld.ron"Nepal, Surya"https://zbmath.org/authors/?q=ai:nepal.suryaSummary: Although searchable encryption schemes allow secure search over the encrypted data, they mostly support conventional Boolean keyword search, without capturing any relevance of the search results. This leads to a large amount of post-processing overhead to find the most matching documents and causes an unnecessary communication cost between the servers and end-users. Such problems can be addressed efficiently using a ranked search system that retrieves the most relevant documents. However, existing state-of-the-art solutions in the context of Searchable Symmetric Encryption (SSE) suffer from either (a) security and privacy breaches due to the use of Order Preserving Encryption (OPE) or (b) non-practical solutions like using the two non-colluding servers. In this paper, we present a generic solution for multi-keyword ranked search over the encrypted cloud data. The proposed solution can be applied over different symmetric searchable encryption schemes. To demonstrate the practicality of our technique, in this paper we leverage the Oblivious Cross Tags (OXT) protocol of
\textit{D. Cash} et al. [Lect. Notes Comput. Sci. 8042, 353--373 (2013; Zbl 1311.68057)]
due to its scalability and remarkable flexibility to support different settings. Our proposed scheme supports the multi-keyword search on Boolean, ranked and limited range queries while keeping all of the OXT's properties intact. The key contribution of this paper is that our scheme is resilience against all common attacks that take advantage of OPE leakage while only a single cloud server is used. Moreover, the results indicate that using the proposed solution the communication overhead decreases drastically when the number of matching results is large.
For the entire collection see [Zbl 1493.68023].Towards efficient verifiable forward secure searchable symmetric encryptionhttps://zbmath.org/1496.681332022-11-17T18:59:28.764376Z"Zhang, Zhongjun"https://zbmath.org/authors/?q=ai:zhang.zhongjun"Wang, Jianfeng"https://zbmath.org/authors/?q=ai:wang.jianfeng.2|wang.jianfeng|wang.jianfeng.1"Wang, Yunling"https://zbmath.org/authors/?q=ai:wang.yunling"Su, Yaping"https://zbmath.org/authors/?q=ai:su.yaping"Chen, Xiaofeng"https://zbmath.org/authors/?q=ai:chen.xiaofengSummary: Searchable Symmetric Encryption (SSE) allows a server to perform search directly over encrypted data outsourced by user. Recently, the primitive of forward secure SSE has attracted significant attention due to its favorable property for dynamic data searching. That is, it can prevent the linkability from newly update data to previously searched keyword. However, the server is assumed to be honest-but-curious in the existing work. How to achieve verifiable forward secure SSE in malicious server model remains a challenging problem. In this paper, we propose an efficient verifiable forward secure SSE scheme, which can simultaneously achieve verifiability of search result and forward security property. In particular, we propose a new verifiable data structure based on the primitive of multiset hash functions, which enables efficient verifiable data update by incrementally hash operation. Compared with the state-of-the-art solution, our proposed scheme is superior in search and update efficiency while providing verifiability of search result. Finally, we present a formal security analysis and implement our scheme, which demonstrates that our proposed scheme is equipped with the desired security properties with practical efficiency.
For the entire collection see [Zbl 1493.68023].Dynamic searchable symmetric encryption with forward and stronger backward privacyhttps://zbmath.org/1496.681342022-11-17T18:59:28.764376Z"Zuo, Cong"https://zbmath.org/authors/?q=ai:zuo.cong"Sun, Shi-Feng"https://zbmath.org/authors/?q=ai:sun.shifeng"Liu, Joseph K."https://zbmath.org/authors/?q=ai:liu.joseph-k-k"Shao, Jun"https://zbmath.org/authors/?q=ai:shao.jun"Pieprzyk, Josef"https://zbmath.org/authors/?q=ai:pieprzyk.josef-pSummary: Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform updates and searches on encrypted data which makes it very useful in practice. To protect DSSE from the leakage of updates (leading to break query or data privacy), two new security notions, forward and backward privacy, have been proposed recently. Although extensive attention has been paid to forward privacy, this is not the case for backward privacy. Backward privacy, first formally introduced by Bost et al., is classified into three types from weak to strong, exactly Type-III to Type-I. To the best of our knowledge, however, no practical DSSE schemes without trusted hardware (e.g. SGX) have been proposed so far, in terms of the strong backward privacy and constant roundtrips between the client and the server.
In this work, we present a new DSSE scheme by leveraging simple symmetric encryption with homomorphic addition and bitmap index. The new scheme can achieve both forward and backward privacy with one roundtrip. In particular, the backward privacy we achieve in our scheme (denoted by Type-I\(^-\)) is stronger than Type-I. Moreover, our scheme is very practical as it involves only lightweight cryptographic operations. To make it scalable for supporting billions of files, we further extend it to a multi-block setting. Finally, we give the corresponding security proofs and experimental evaluation which demonstrate both security and practicality of our schemes, respectively.
For the entire collection see [Zbl 1493.68023].On the privacy of a code-based single-server computational PIR schemehttps://zbmath.org/1496.681352022-11-17T18:59:28.764376Z"Bordage, Sarah"https://zbmath.org/authors/?q=ai:bordage.sarah"Lavauzelle, Julien"https://zbmath.org/authors/?q=ai:lavauzelle.julienSummary: We show that the single-server computational PIR protocol proposed by \textit{L. Holzbaur} et al. in [``Computational code-based single-server private information retrieval'', Preprint, \url{arxiv:2001.07049}] is not private, in the sense that the server can recover in polynomial time the index of the desired file with very high probability. The attack relies on the following observation. Removing rows of the query matrix corresponding to the desired file yields a large decrease of the dimension over \(\mathbb{F}_q\) of the vector space spanned by the rows of this punctured matrix. Such a dimension loss only shows up with negligible probability when rows unrelated to the requested file are deleted.Formalizing and proving privacy properties of voting protocols using alpha-beta privacyhttps://zbmath.org/1496.681362022-11-17T18:59:28.764376Z"Gondron, Sébastien"https://zbmath.org/authors/?q=ai:gondron.sebastien"Mödersheim, Sebastian"https://zbmath.org/authors/?q=ai:modersheim.sebastian-alexanderSummary: Most common formulations of privacy-type properties for security protocols are specified as bisimilarity of processes in applied-\( \pi\) calculus. For instance, voting privacy is specified as the bisimilarity between two processes that differ only by a swap of two votes. Similar methods are applied to formalize receipt-freeness. We believe that there exists a gap between these technical encodings and an intuitive understanding of these properties.
We use \((\alpha ,\beta )\)-privacy to formalize privacy goals in a different way, namely as a reachability problem. Every state consists of a pair of formulae: \( \alpha\) expresses the publicly released information (like the result of the vote) and \(\beta\) expresses the additional information available to the intruder (like observed messages). Privacy holds in a state if every model of \(\alpha\) can be extended to a model of \(\beta \), i.e., the intruder cannot make any deductions beyond what was deliberately released; and privacy of a protocol holds if privacy holds in every reachable state.
This allows us to give formulations of voting privacy and receipt-freeness that are more declarative than the common bisimilarity based formulations, since we reason about models that are consistent with all observations like interaction with coerced (but potentially lying) voters. Also, we show a relation between the goals: receipt-freeness implies voting privacy.
Finally, the logical approach also allows for declarative manual proofs (as opposed to long machine-generated proofs) like reasoning about a permutation of votes and the intruder's knowledge about that permutation.
For the entire collection see [Zbl 1493.68022].Improved signature schemes for secure multi-party computation with certified inputshttps://zbmath.org/1496.681482022-11-17T18:59:28.764376Z"Blanton, Marina"https://zbmath.org/authors/?q=ai:blanton.marina"Jeong, Myoungin"https://zbmath.org/authors/?q=ai:jeong.myounginSummary: The motivation for this work comes from the need to strengthen security of secure multi-party protocols with the ability to guarantee that the participants provide their truthful inputs in the computation. This is outside the traditional security models even in the presence of malicious participants, but input manipulation can often lead to privacy and result correctness violations. Thus, in this work we treat the problem of combining secure multi-party computation (SMC) techniques based on secret sharing with signatures to enforce input correctness in the form of certification. We modify two currently available signature schemes to achieve private verification and efficiency of batch verification and show how to integrate them with two prominent SMC protocols.
For the entire collection see [Zbl 1493.68017].Enforcing input correctness via certification in garbled circuit evaluationhttps://zbmath.org/1496.681492022-11-17T18:59:28.764376Z"Zhang, Yihua"https://zbmath.org/authors/?q=ai:zhang.yihua"Blanton, Marina"https://zbmath.org/authors/?q=ai:blanton.marina"Bayatbabolghani, Fattaneh"https://zbmath.org/authors/?q=ai:bayatbabolghani.fattanehSummary: Secure multi-party computation allows a number of participants to securely evaluate a function on their private inputs and has a growing number of applications. Two standard adversarial models that treat the participants as semi-honest or malicious, respectively, are normally considered for showing security of constructions in this framework. In this work, we go beyond the standard security model in the presence of malicious participants and treat the problem of enforcing correct inputs to be entered into the computation. We achieve this by having a certification authority certify user's information, which is consequently used in secure two-party computation based on garbled circuit evaluation. The focus of this work on enforcing correctness of garbler's inputs via certification, as prior work already allows one to achieve this goal for circuit evaluator's input. Thus, in this work, we put forward a novel approach for certifying user's input and tying certification to garbler's input used during secure function evaluation based on garbled circuits. Our construction achieves notable performance of adding only one (standard) signature verification and \(O(n\rho )\) symmetric key/hash operations to the cost of garbled circuit evaluation in the malicious model via cut-and-choose, in which \(\rho\) circuits are garbled and \(n\) is the length of the garbler's input in bits. Security of our construction is rigorously proved in the standard model.
For the entire collection see [Zbl 1493.68009].Optimizing the combined automation scheme in the ASIS basishttps://zbmath.org/1496.681722022-11-17T18:59:28.764376Z"Barkalov, A. A."https://zbmath.org/authors/?q=ai:barkalov.alexander-a-jun|barkalov.alexander-a"Titarenko, L. A."https://zbmath.org/authors/?q=ai:titarenko.l-a"Baiev, A. V."https://zbmath.org/authors/?q=ai:baev.andrei-vladimirovich|baev.artem-v"Matviienko, A. V."https://zbmath.org/authors/?q=ai:matviienko.a-vSummary: A method is proposed for decreasing the area of the ASIS occupied by the scheme of a combined automation. The method is based on the encoding of the classes of pseudoequivalent states of Moore automation by additional variables. This approach leads to a four-level scheme implemented as two nano-PLAs and decreases the area of a nano-PLA that generates microoperations of the Moore automation and additional variables. An example of synthesis with the use of the proposed scheme is considered. The results of the efficiency analysis of the proposed method with the use of the library of benchmarks are presented.Universal equivalence and majority of probabilistic programs over finite fieldshttps://zbmath.org/1496.681862022-11-17T18:59:28.764376Z"Barthe, Gilles"https://zbmath.org/authors/?q=ai:barthe.gilles"Jacomme, Charlie"https://zbmath.org/authors/?q=ai:jacomme.charlie"Kremer, Steve"https://zbmath.org/authors/?q=ai:kremer.steveVerification of asynchronous circuits by BDD-based model checking of Petri netshttps://zbmath.org/1496.681942022-11-17T18:59:28.764376Z"Roig, Oriol"https://zbmath.org/authors/?q=ai:roig.oriol"Cortadella, Jordi"https://zbmath.org/authors/?q=ai:cortadella.jordi"Pastor, Enric"https://zbmath.org/authors/?q=ai:pastor.enricSummary: This paper presents a methodology for the verification of speed-independent asynchronous circuits against a Petri net specification. The technique is based on symbolic reachability analysis, modeling both the specification and the gate-level network behavior by means of Boolean functions. These functions are efficiently handled by using \textit{Binary Decision Diagrams}. Algorithms for verifying the correctness of designs, as well as several circuit properties are proposed. Finally, the applicability of our verification method has been proven by checking the correctness of different benchmarks.
For the entire collection see [Zbl 1492.68015].A sparse deep learning model for privacy attack on remote sensing imageshttps://zbmath.org/1496.682892022-11-17T18:59:28.764376Z"Wang, Eric Ke"https://zbmath.org/authors/?q=ai:kewang.eric"Zhe, Nie"https://zbmath.org/authors/?q=ai:zhe.nie"Li, Yueping"https://zbmath.org/authors/?q=ai:li.yueping"Liang, Zuodong"https://zbmath.org/authors/?q=ai:liang.zuodong"Zhang, Xun"https://zbmath.org/authors/?q=ai:zhang.xun"Yu, Juntao"https://zbmath.org/authors/?q=ai:yu.juntao"Ye, Yunming"https://zbmath.org/authors/?q=ai:ye.yunming(no abstract)Angle aided circle detection based on randomized Hough transform and its application in welding spots detectionhttps://zbmath.org/1496.683452022-11-17T18:59:28.764376Z"Liang, Qiaokang"https://zbmath.org/authors/?q=ai:liang.qiaokang"Long, Jianyong"https://zbmath.org/authors/?q=ai:long.jianyong"Nan, Yang"https://zbmath.org/authors/?q=ai:nan.yang"Coppola, Gianmarc"https://zbmath.org/authors/?q=ai:coppola.gianmarc"Zou, Kunlin"https://zbmath.org/authors/?q=ai:zou.kunlin"Zhang, Dan"https://zbmath.org/authors/?q=ai:zhang.dan"Sun, Wei"https://zbmath.org/authors/?q=ai:sun.wei.3(no abstract)Adaptive correction method of two-dimensional image deviation in visual communication designhttps://zbmath.org/1496.683562022-11-17T18:59:28.764376Z"Kong, Cheng"https://zbmath.org/authors/?q=ai:kong.cheng(no abstract)Electronic circuit simulation and the development of new Krylov-subspace methodshttps://zbmath.org/1496.780042022-11-17T18:59:28.764376Z"Freund, Roland W."https://zbmath.org/authors/?q=ai:freund.roland-wSummary: Ever since the 1960s, the semiconductor industry has heavily relied on simulation in order to analyze and verify the design of integrated circuits before actual chips are manufactured. Over the decades, the algorithms and tools of circuit simulation have evolved in order to keep up with the ever-increasing complexity of integrated circuits, and at certain points of this evolution, new simulation techniques were required. Such a point was reached in the early 1990s, when a new approach was needed to efficiently and accurately simulate the effects of the ever-increasing amount of on-chip wiring on the proper functioning of the chip. The industry's proposed solution for this task, the AWE approach, worked well for small- to moderate-size networks of on-chip wiring, but suffered from numerical issues for larger networks. It turned out that for the special case of networks with single inputs and single outputs, these problems can be remedied by exploiting the connection between AWE and the classical Lanczos algorithm for single starting vectors. However, the general case of on-chip wiring involves networks with multiple inputs and outputs, and so a Lanczostype algorithm was needed that could handle such multiple starting vectors. Since no such extension existed, a new band Lanczos algorithm for multiple starting vectors was developed. It turned out that this new band approach can also be employed to devise extensions of other Krylov-subspace methods. In this chapter, we describe the band Lanczos algorithm and the band Arnoldi process and how their developments were driven by the need to efficiently and accurately simulate the effects of on-chip wiring of integrated circuits.
For the entire collection see [Zbl 1483.65008].Partial stability criterion for a heterogeneous power grid with hub structureshttps://zbmath.org/1496.780092022-11-17T18:59:28.764376Z"Khramenkov, Vladislav"https://zbmath.org/authors/?q=ai:khramenkov.vladislav"Dmitrichev, Aleksei"https://zbmath.org/authors/?q=ai:dmitrichev.aleksei"Nekorkin, Vladimir"https://zbmath.org/authors/?q=ai:nekorkin.vladimir-iSummary: One of the priority tasks in studying power grids is to find the conditions of their stable operation. The fundamental requirement is synchronizing all the elements (generators and consumers) of a power grid. However, various disturbances can destroy the synchronization. Moreover, desynchronization occurring in a small part of the grid can lead to severe large-scale power outages (or blackouts) due to numerous cascading failures. Here we consider the model of a heterogeneous power grid with hub structures (subgrids), taking into account arbitrary lengths and impedances of grid's transmission lines and also their arbitrary amount. Using the auxiliary comparison systems approach, we analyze the dynamics of a hub subgrid. Based on the findings, we develop a novel criterion of partial stability of power grids featuring hub structures. The criterion makes it possible to identify the regions of safe operation of individual hub subgrid elements. First, the criterion allows obtaining parameters' values that guarantee existence and local stability of either synchronous or quasi-synchronous modes in individual hub subgrid elements, i.e. steady-state stability. Second, the criterion allows obtaining the safe values of abrupt frequency and phase disturbances that eventually vanish, i.e. imply transient stability with respect to state disturbance. Third, the criterion permits determining the safe ranges of parameters' disturbances that do not lead to catastrophic desynchronizing effects, i.e. imply transient stability with respect to parameters' disturbance. Also, we discover typical dependences of the safe regions on the parameters of transmission lines. We demonstrate the applicability of the criterion on two test power grids with arbitrary distributions of powers as well as effective lengths and impedances of transmission lines. The results may help optimize stability and contribute to developing new real-time control schemes for smart grids that can automatically recover from failures.Magnetic coupling based control of a chaotic circuit: case of the van der Pol oscillator coupled to a linear circuithttps://zbmath.org/1496.780102022-11-17T18:59:28.764376Z"Ngamsa Tegnitsap, J. V."https://zbmath.org/authors/?q=ai:ngamsa-tegnitsap.j-v"Fotsin, H. B."https://zbmath.org/authors/?q=ai:fotsin.hilaire-bertrand"Megam Ngouonkadi, E. B."https://zbmath.org/authors/?q=ai:megam-ngouonkadi.e-bSummary: This paper investigates the control of the dynamics of the van der Pol oscillator coupled to Linear circuit (VDPCL oscillator). The method consists of carrying out a magnetic coupling (wireless interaction) of a VDPCL oscillator to a magnetic core coil supplied by a sinusoidal voltage. One of the most important outlets of the proposed control scheme is the ability to control the dynamic of the oscillator by varying three external parameters as well as to generate very rich and complicated behaviors including attractors not yet reported in the non-controlled model. In this impetus, the frequency and the amplitude of the excitation source of the RL circuit as well as the magnetic coupling coefficient are thus used to adjust the VDPCL oscillator dynamics in a desired state. The basic properties of the model are discussed, such as fixed point stability, symmetry and dissipation. Using the control parameters mentioned above, the dynamic behaviors of the model are studied using the classical tools of nonlinear dynamics such as the two-parameters and one parameter Lyapunov exponents, the one-parameter bifurcation diagrams, phase portraits and time series. Numerical simulation reveals a rich repertoire of dynamic behaviors in the system, including periodicity, period doubling, quasi-periodicity, 2-torus, 3-torus and chaos. In particular, complex and striking phenomena such as antimonotonicity, intermittency, coexistence of attractors and amplitude modulation are reported in the model when monitoring the frequency of the sinusoidal excitation. Sample coexisting bifurcation diagrams are drawn and the coexistence of attractors is illustrated using the phase portraits and the cross section of the basin of attraction. Pspice based simulations and laboratory experimental measurements are included to confirm the theoretical results and the feasibility of the proposed control scheme.Classical and quantum information.https://zbmath.org/1496.810082022-11-17T18:59:28.764376Z"Marinescu, Dan C."https://zbmath.org/authors/?q=ai:marinescu.dan-cristian"Marinescu, Gabriela M."https://zbmath.org/authors/?q=ai:marinescu.gabriela-mPublisher's description: A new discipline, Quantum Information Science, has emerged in the last two decades of the twentieth century at the intersection of Physics, Mathematics, and Computer Science. Quantum Information Processing is an application of Quantum Information Science which covers the transformation, storage, and transmission of quantum information; it represents a revolutionary approach to information processing.
This book covers topics in quantum computing, quantum information theory, and quantum error correction, three important areas of quantum information processing.
Quantum information theory and quantum error correction build on the scope, concepts, methodology, and techniques developed in the context of their close relatives, classical information theory and classical error correcting codes.Approximate Petz recovery from the geometry of density operatorshttps://zbmath.org/1496.810282022-11-17T18:59:28.764376Z"Cree, Sam"https://zbmath.org/authors/?q=ai:cree.sam"Sorce, Jonathan"https://zbmath.org/authors/?q=ai:sorce.jonathanSummary: We derive a new bound on the effectiveness of the Petz map as a universal recovery channel in approximate quantum error correction using the second sandwiched Rényi relative entropy \(\widetilde{D}_2 \). For large Hilbert spaces, our bound implies that the Petz map performs quantum error correction with order-\(\epsilon\) accuracy whenever the data processing inequality for \(\widetilde{D}_2\) is saturated up to terms of order \(\epsilon^2\) times the inverse Hilbert space dimension. Conceptually, our result is obtained by extending [\textit{S. Cree} and \textit{J. Sorce}, ``Geometric conditions for saturating the data processing inequality'', J. Phys. A, Math. Theor. 55, No. 13, Article ID 135202, 24 p. (2022; \url{doi:10.1088/1751-8121/ac5648})], in which we studied exact saturation of the data processing inequality using differential geometry, to the case of approximate saturation. Important roles are played by (i) the fact that the exponential of the second sandwiched Rényi relative entropy is quadratic in its first argument, and (ii) the observation that the second sandwiched Rényi relative entropy satisfies the data processing inequality even when its first argument is a non-positive Hermitian operator.Optimal adaptive strategies for sequential quantum hypothesis testinghttps://zbmath.org/1496.810292022-11-17T18:59:28.764376Z"Li, Yonglong"https://zbmath.org/authors/?q=ai:li.yonglong"Tan, Vincent Y. F."https://zbmath.org/authors/?q=ai:tan.vincent-yan-fu"Tomamichel, Marco"https://zbmath.org/authors/?q=ai:tomamichel.marcoSummary: We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. In this setting, samples of an unknown state are requested sequentially and a decision to either continue or to accept one of the two hypotheses is made after each test. Under the constraint that the number of samples is bounded, either in expectation or with high probability, we exhibit adaptive strategies that minimize both types of misidentification errors. Namely, we show that these errors decrease exponentially (in the stopping time) with decay rates given by the measured relative entropies between the two states. Moreover, if we allow joint measurements on multiple samples, the rates are increased to the respective quantum relative entropies. We also fully characterize the achievable error exponents for non-adaptive strategies and provide numerical evidence showing that adaptive measurements are necessary to achieve our bounds.Effect of noise in the quantum bidirectional direct communication protocol using non-maximally entangled stateshttps://zbmath.org/1496.810392022-11-17T18:59:28.764376Z"Ramachandran, Meera"https://zbmath.org/authors/?q=ai:ramachandran.meera"Balakrishnan, S."https://zbmath.org/authors/?q=ai:balakrishnan.sivasubramanya|balakrishnan.suhrid|balakrishnan.sivaraman|balakrishnan.srinivasan|balakrishnan.sarasija-perurkada|balakrishnan.srivatsan|balakrishnan.swaminathan|balakrishnan.sreeram|balakrishnan.s-n|balakrishnan.sudha|balakrishnan.shankar|balakrishnan.subramaniam|balakrishnan.shanmugamSummary: Possibility of using non-maximally entangled states in quantum bidirectional direct communication has been shown recently by \textit{A. Srikanth} and \textit{S. Balakrishnan} [``Controller-independent quantum bidirectional communication using non-maximally entangled states'', Quantum Inf. Process. 19, Paper No. 133, 11 p. (2020; \url{doi:10.1007/s11128-020-02628-2})]. The effect of noise in this protocol is analyzed by considering amplitude and phase damping models. Suitable combinations of messages and initial states are identified to minimize the effect of noise in the protocol. Further, we have shown the possibility of demarking the effects due to noise and the intruder.Explosive synchronization induced by environmental couplinghttps://zbmath.org/1496.810742022-11-17T18:59:28.764376Z"Ramesan, Gayathri"https://zbmath.org/authors/?q=ai:ramesan.gayathri"Shajan, Emilda"https://zbmath.org/authors/?q=ai:shajan.emilda"Shrimali, Manish Dev"https://zbmath.org/authors/?q=ai:shrimali.manish-devSummary: The occurrence of explosive synchronization transition in a system of limit-cycle oscillators in the presence of two types of coupling; direct mean field diffusive and indirect environmental couplings, both operating simultaneously, is reported. The dynamics of coupled nonlinear Van der Pol and Rayleigh oscillators are studied in detail as a function of the distribution of intrinsic parameters of the oscillators. This explosive synchronization transition depends on the strength of indirect coupling and is irreversible giving rise to a characteristic hysteresis region. The different routes to synchronization observed in these coupled oscillators are studied in detail with the help of effective frequency and time series analysis. We have investigated the efficiency of the proposed scheme in various other topologies such as random, scale-free, and two-community networks as well.A moment closure based on a projection on the boundary of the realizability domain: extension and analysishttps://zbmath.org/1496.820212022-11-17T18:59:28.764376Z"Pichard, Teddy"https://zbmath.org/authors/?q=ai:pichard.teddySummary: A closure relation for moments equations in kinetic theory was recently introduced in [the author, Kinet. Relat. Models 13, No. 6, 1243--1280 (2020; Zbl 1458.35350)], based on the study of the geometry of the set of moments. This relation was constructed from a projection of a moment vector toward the boundary of the set of moments and corresponds to approximating the underlying kinetic distribution as a sum of a chosen equilibrium distribution plus a sum of purely anisotropic Dirac distributions. The present work generalizes this construction for kinetic equations involving unbounded velocities, i.e. to the Hamburger problem, and provides a deeper analysis of the resulting moment system. Especially, we provide representation results for moment vectors along the boundary of the moment set that implies the well-definition of the model. And the resulting moment model is shown to be weakly hyperbolic with peculiar properties of hyperbolicity and entropy of two subsystems, corresponding respectively to the equilibrium and to the purely anisotropic parts of the underlying kinetic distribution.Viscous absorption of ultra-high-frequency gravitonshttps://zbmath.org/1496.830082022-11-17T18:59:28.764376Z"Giovannini, Massimo"https://zbmath.org/authors/?q=ai:giovannini.massimoSummary: The high-frequency gravitons can be absorbed by the first and second viscosities of the post-inflationary plasma as the corresponding wavelengths reenter the Hubble radius prior to big-bang nucleosynthesis. When the total sound speed of the medium is stiffer than radiation the rate of expansion still exceeds the shear rate but the bulk viscosity is not negligible. Depending on the value of the entropy density at the end of inflation the spectral energy density of the relic gravitons gets modified in comparison with the inviscid result when the frequency ranges between the kHz band and the GHz region. In the nHz domain the spectrum inherits a known suppression due to neutrino free-streaming but also a marginal spike potentially caused by a sudden outbreak of the bulk viscosity around the quark-hadron phase transition, as suggested by the hadron spectra produced in the collisions of heavy ions.On superstatistics and black hole quasinormal modeshttps://zbmath.org/1496.830302022-11-17T18:59:28.764376Z"Martínez-Merino, A."https://zbmath.org/authors/?q=ai:martinez-merino.aldo-a"Sabido, M."https://zbmath.org/authors/?q=ai:sabido.miguelSummary: It is known that using Boltzmann-Gibbs statistics, Bekenstein-Hawking entropy \(S_{HB}\), and the quasinormal modes of black holes, one finds that the lowest value of spin is \(j_{min} = 1\). In this paper, we determine \(j_{min}\), using non-extensive entropies that depend only on the probability (known as Obregon's entropies and have been derived from superstatistics). We also calculate \(j_{min}\) for a set of non-extensive entropies that have free parameters and are written in terms of \(S_{BH}\). We find that \(j_{min}\) depends on the area and the non-extensive parameter.
For the non-extensive entropies that only depend on the probability, we find that the modification is only present for micro black holes. For classical black holes the results are the same as for the Boltzmann-Gibbs statistics.3D reconstruction of porous media using a batch normalized variational auto-encoderhttps://zbmath.org/1496.860232022-11-17T18:59:28.764376Z"Zhang, Ting"https://zbmath.org/authors/?q=ai:zhang.ting.1|zhang.ting.3|zhang.ting|zhang.ting.2"Yang, Yi"https://zbmath.org/authors/?q=ai:yang.yi"Zhang, Anqin"https://zbmath.org/authors/?q=ai:zhang.anqinSummary: The 3D reconstruction of porous media plays a key role in many engineering applications. There are two main methods for the reconstruction of porous media: physical experimental methods and numerical reconstruction methods. The former are usually expensive and restricted by the limited size of experimental samples, while the latter are relatively cost-effective but still suffer from a lengthy processing time and unsatisfactory performance. With the vigorous development of deep learning in recent years, applying deep learning methods to 3D reconstruction of porous media has become an important direction. Variational auto-encoder (VAE) is one of the typical deep learning methods with a strong ability of extracting features from training images (TIs), but it has the problem of posterior collapse, meaning the generated data from the decoder are not related to its input data, i.e. the latent space \(Z\). This paper proposes a VAE model (called SE-FBN-VAE) based on squeeze-and-excitation network (SENet) and fixed batch normalization (FBN) for the reconstruction of porous media. SENet is a simple and efficient channel attention mechanism, which improves the sensitivity of the model to channel characteristics. The application of SENet to VAE can further improve its ability of extracting features from TIs. Batch normalization (BN) is a common method for data normalization in neural networks, which reduces the convergence time of the network. In this paper, BN is slightly modified to solve the problem of posterior collapse of VAE. Compared with some other numerical methods, the effectiveness and practicability of the proposed method are demonstrated.Foundations for fintechhttps://zbmath.org/1496.910092022-11-17T18:59:28.764376ZPublisher's description: In the digital era, emerging technologies such as artificial intelligence, big data, and blockchain have revolutionized various ways of people's daily lives and brought many opportunities and challenges to the industries. With the increasing demand for talents in the fintech realm, this book serves as a good guide for practitioners who are seeking to understand the basics of fintech and applications of different technologies. This book covers important knowledge in statistics, quantitative methods, and financial innovation to lay the foundation for fintech. It is especially useful for people who are relatively new to this area and would like to become professionals in fintech.
The articles of this volume will not be indexed individually.Cryptography, information theory, and error-correction. A handbook for the 21st centuryhttps://zbmath.org/1496.940012022-11-17T18:59:28.764376Z"Bruen, Aiden A."https://zbmath.org/authors/?q=ai:bruen.aiden-a"Forcinito, Mario A."https://zbmath.org/authors/?q=ai:forcinito.mario-a"McQuillan, James M."https://zbmath.org/authors/?q=ai:mcquillan.james-mPublisher's description: As technology continues to evolve Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century is an indispensable resource for anyone interested in the secure exchange of financial information. Identity theft, cybercrime, and other security issues have taken center stage as information becomes easier to access. Three disciplines offer solutions to these digital challenges: cryptography, information theory, and error-correction, all of which are addressed in this book.
This book is geared toward a broad audience. It is an excellent reference for both graduate and undergraduate students of mathematics, computer science, cybersecurity, and engineering. It is also an authoritative overview for professionals working at financial institutions, law firms, and governments who need up-to-date information to make critical decisions. The book's discussions will be of interest to those involved in blockchains as well as those working in companies developing and applying security for new products, like self-driving cars. With its reader-friendly style and interdisciplinary emphasis this book serves as both an ideal teaching text and a tool for self-learning for IT professionals, statisticians, mathematicians, computer scientists, electrical engineers, and entrepreneurs.
Six new chapters cover current topics like Internet of Things security, new identities in information theory, blockchains, cryptocurrency, compression, cloud computing and storage. Increased security and applicable research in elliptic curve cryptography are also featured. The book also:
\par i) Shares vital, new research in the field of information theory
\par ii) Provides quantum cryptography updates
\par iii) Includes over 350 worked examples and problems for greater understanding of ideas.
Cryptography, Information Theory, and Error-Correction guides readers in their understanding of reliable tools that can be used to store or transmit digital information safely.
See the review of the first edition in [Zbl 1071.94001].Modern cryptography. Volume 1. A classical introduction to informational and mathematical principlehttps://zbmath.org/1496.940022022-11-17T18:59:28.764376Z"Zheng, Zhiyong"https://zbmath.org/authors/?q=ai:zheng.zhiyongThe present book is a textbook of theoretical cryptography suitable for senior students in mathematics, compulsory for cryptography and science, and engineering postgraduates. It deals with information theory, the statistical characteristics of cryptosystems, and the computational complexity of cryptographic algorithms, and discusses several important public-key cryptosystems. It emphasises the mathematical principles behind various cryptographic and authentication schemes. The book contains seven chapters.
The first chapter presents some preliminary knowledge. Basic facts about maps are recalled, and the computational complexity of an algorithm that receives as input integers is introduced. Furthermore, Jensen inequality and the Stirling formula are presented. Finally, the \(n\)-fold Bernoulli experiment, Chebyshev inequality, and stochastic process are discussed.
The second chapter is devoted to code theory. Its goal is to give an introduction of the theory of error-correcting codes. It includes Hamming distance, Lee distance, linear codes, some typical good codes, and Mac Williams and Shannon theorems.
The third chapter presents Shannon's theory. The information space, the entropy, the redundancy, the Markov space, and the source coding theorem are discussed. Furthermore, the optimal code theory is investigated and several examples of compressing codes are given. Finally, Shannon's channel coding theorem is proved.
Cryptography is the topic of the fourth chapter. It gives an introduction to Shannon's ideas and results in cryptography, and in public key cryptography. First, it deals with the statistical characteristic of cryptosystems, fully confidential systems, and ideal security systems. Further, the message authentication systems and the forgery and substitute attacks are discussed. Moreover, some classical encryption algorithms and the public-key cryptosystems RSA, ElGamal scheme, and knapsack scheme are described.
In the fifth chapter, the primality tests, which are necessary for the construction of a wide class of public key cryptosystems, are presented. The Fermat and Euler tests are described and the Monte Carlo method is introduced. Furthermore, the factor basis method and the continuous fraction method are given.
The important topic of elliptic curves is introduced in the sixth chapter. The basic theory is presented and some classical public key cryptosystems based on elliptic curves are discussed. Finally, the elliptic curve factorisation method is described.
The last chapter contains classical results on lattices and their applications in public-key cryptography. It gives an introduction to the geometry of numbers and discusses the basic properties of lattices. Furthermore, it studies the reduced bases and the LLL algorithm and presents approximation algorithms for the shortest vector problem and the closest vector problem. Finally, the GGH/HNF cryptosystem, the NTRU cryptosystem, the McEliece/Niederreiter cryptosystem, and the Ajtai/Dwork cryptosystem are presented.
Reviewer: Dimitros Poulakis (Thessaloniki)Post-quantum cryptography. 11th international conference, PQCrypto 2020, Paris, France, April 15--17, 2020. Proceedingshttps://zbmath.org/1496.940032022-11-17T18:59:28.764376ZThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1418.94003].
Indexed articles:
\textit{Renner, Julian; Jerkovits, Thomas; Bartz, Hannes; Puchinger, Sven; Loidreau, Pierre; Wachter-Zeh, Antonia}, Randomized decoding of Gabidulin codes beyond the unique decoding radius, 3-19 [Zbl 07601026]
\textit{Sendrier, Nicolas; Vasseur, Valentin}, About low DFR for QC-MDPC decoding, 20-34 [Zbl 07601027]
\textit{Drucker, Nir; Gueron, Shay; Kostic, Dusan}, QC-MDPC decoders with several shades of gray, 35-50 [Zbl 07601028]
\textit{Howe, James; Prest, Thomas; Ricosset, Thomas; Rossi, Mélissa}, Isochronous Gaussian sampling: from inception to implementation, 53-71 [Zbl 07601029]
\textit{Paquin, Christian; Stebila, Douglas; Tamvada, Goutam}, Benchmarking post-quantum cryptography in TLS, 72-91 [Zbl 07601030]
\textit{Petzoldt, Albrecht}, Efficient key generation for Rainbow, 92-107 [Zbl 07601031]
\textit{Castryck, Wouter; Decru, Thomas}, CSIDH on the surface, 111-129 [Zbl 07601032]
\textit{Beullens, Ward; De Saint Guilhem, Cyprien Delpech}, LegRoast: efficient post-quantum signatures from the Legendre PRF, 130-150 [Zbl 07601033]
\textit{Costello, Craig; Smith, Benjamin}, The supersingular isogeny problem in genus 2 and beyond, 151-168 [Zbl 07601034]
\textit{Cozzo, Daniele; Smart, Nigel P.}, Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol, 169-186 [Zbl 07601035]
\textit{Amiet, Dorian; Curiger, Andreas; Leuenberger, Lukas; Zbinden, Paul}, Defeating NewHope with a single trace, 189-205 [Zbl 07601036]
\textit{Bindel, Nina; Schanck, John M.}, Decryption failure is more likely after success, 206-225 [Zbl 07601037]
\textit{Bootle, Jonathan; Lehmann, Anja; Lyubashevsky, Vadim; Seiler, Gregor}, Compact privacy protocols from post-quantum and timed classical assumptions, 226-246 [Zbl 07601038]
\textit{Boschini, Cecilia; Camenisch, Jan; Ovsiankin, Max; Spooner, Nicholas}, Efficient post-quantum SNARKs for RSIS and RLWE and their applications to privacy, 247-267 [Zbl 07601039]
\textit{Tao, Yang; Wang, Xi; Zhang, Rui}, Short zero-knowledge proof of knowledge for lattice-based commitment, 268-283 [Zbl 07601040]
\textit{Zhao, Raymond K.; Steinfeld, Ron; Sakzad, Amin}, COSAC: COmpact and Scalable Arbitrary-Centered discrete Gaussian sampling over integers, 284-303 [Zbl 07601041]
\textit{Apon, Daniel; Moody, Dustin; Perlner, Ray; Smith-Tone, Daniel; Verbel, Javier}, Combinatorial rank attacks against the rectangular simple matrix encryption scheme, 307-322 [Zbl 07601042]
\textit{Furue, Hiroki; Kinjo, Koha; Ikematsu, Yasuhiko; Wang, Yacheng; Takagi, Tsuyoshi}, A structural attack on block-anti-circulant UOV at SAC 2019, 323-339 [Zbl 07601043]
\textit{Santoso, Bagus}, Generalization of isomorphism of polynomials with two secrets and its application to public key encryption, 340-359 [Zbl 07601044]
\textit{Smith-Tone, Daniel}, Practical cryptanalysis of \(k\)-ary \(C^\ast\), 360-380 [Zbl 07601045]
\textit{Smith-Tone, Daniel; Verbel, Javier}, A rank attack against extension field cancellation, 381-401 [Zbl 07601046]
\textit{Yasuda, Takanori; Wang, Yacheng; Takagi, Tsuyoshi}, Multivariate encryption schemes based on polynomial equations over real numbers, 402-421 [Zbl 07601047]
\textit{Häner, Thomas; Jaques, Samuel; Naehrig, Michael; Roetteler, Martin; Soeken, Mathias}, Improved quantum circuits for elliptic curve discrete logarithms, 425-444 [Zbl 07601048]
\textit{Helm, Alexander; May, Alexander}, The power of few qubits and collisions -- subset sum below Grover's bound, 445-460 [Zbl 07601049]
\textit{Hodžić, Samir; Ramkilde, Lars Knudsen; Kidmose, Andreas Brasen}, On quantum distinguishers for type-3 generalized Feistel network based on separability, 461-480 [Zbl 07601050]
\textit{Dowling, Benjamin; Hansen, Torben Brandt; Paterson, Kenneth G.}, Many a mickle makes a muckle: a framework for provably quantum-secure hybrid key exchange, 483-502 [Zbl 07601052]
\textit{Eaton, Edward; Song, Fang}, A note on the instantiability of the quantum random oracle, 503-523 [Zbl 07601053]
\textit{Gunsing, Aldo; Mennink, Bart}, Collapseability of tree hashes, 524-538 [Zbl 07601054]
\textit{Krämer, Juliane; Struck, Patrick}, Encryption schemes using random oracles: from classical to post-quantum security, 539-558 [Zbl 07601055]Public-key cryptography -- PKC 2020. 23rd IACR international conference on practice and theory of public-key cryptography, Edinburgh, UK, May 4--7, 2020. Proceedings. Part Ihttps://zbmath.org/1496.940042022-11-17T18:59:28.764376ZThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1408.94006; Zbl 1408.94007]. For Part II of the proceedings of the present conference see [Zbl 1481.94004].
Indexed articles:
\textit{Tomida, Junichi; Kawahara, Yuto; Nishimaki, Ryo}, Fast, compact, and expressive attribute-based encryption, 3-33 [Zbl 07600969]
\textit{Agrawal, Shweta; Libert, Benoît; Maitra, Monosij; Titiu, Radu}, Adaptive simulation security for inner product functional encryption, 34-64 [Zbl 07600970]
\textit{Soroush, Najmeh; Iovino, Vincenzo; Rial, Alfredo; Roenne, Peter B.; Ryan, Peter Y. A.}, Verifiable inner product encryption scheme, 65-94 [Zbl 07600971]
\textit{Gay, Romain}, A new paradigm for public-key functional encryption for degree-2 polynomials, 95-120 [Zbl 07600972]
\textit{Garg, Sanjam; Gay, Romain; Hajiabadi, Mohammad}, Master-key KDM-secure IBE from pairings, 123-152 [Zbl 07600973]
\textit{Langrehr, Roman; Pan, Jiaxin}, Hierarchical identity-based encryption with tight multi-challenge security, 153-183 [Zbl 07600974]
\textit{Agrikola, Thomas; Couteau, Geoffroy; Hofheinz, Dennis}, The usefulness of sparsifiable inputs: how to avoid subexponential iO, 187-219 [Zbl 07600975]
\textit{Chakraborty, Suvradip; Prabhakaran, Manoj; Wichs, Daniel}, Witness maps and applications, 220-246 [Zbl 07600976]
\textit{Bhattacharyya, Rishiraj}, Memory-tight reductions for practical key encapsulation mechanisms, 249-278 [Zbl 07600977]
\textit{Cao, Nairen; O'Neill, Adam; Zaheri, Mohammad}, Toward RSA-OAEP without random oracles, 279-308 [Zbl 07600978]
\textit{Sun, Shi-Feng; Sakzad, Amin; Steinfeld, Ron; Liu, Joseph K.; Gu, Dawu}, Public-key puncturable encryption: modular and compact constructions, 309-338 [Zbl 07600979]
\textit{Dowling, Benjamin; Rösler, Paul; Schwenk, Jörg}, Flexible authenticated and confidential channel establishment (fACCE): analyzing the noise protocol framework, 341-373 [Zbl 07600980]
\textit{Guo, Siyao; Kamath, Pritish; Rosen, Alon; Sotiraki, Katerina}, Limits on the efficiency of (Ring) LWE based non-interactive key exchange, 374-395 [Zbl 07600981]
\textit{Jiang, Shaoquan; Gong, Guang; He, Jingnan; Khoa Nguyen; Wang, Huaxiong}, PAKEs: new framework, new techniques and more efficient lattice-based constructions in the standard model, 396-427 [Zbl 07600982]
\textit{Peikert, Chris; Shiehian, Sina}, Constraining and watermarking PRFs from milder assumptions, 431-461 [Zbl 07600983]
\textit{Derler, David; Samelin, Kai; Slamanig, Daniel}, Bringing order to chaos: the case of collision-resistant Chameleon-hashes, 462-492 [Zbl 07600984]
\textit{Baum, Carsten; Nof, Ariel}, Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography, 495-526 [Zbl 07600985]
\textit{Daza, Vanesa; Ràfols, Carla; Zacharakis, Alexandros}, Updateable inner product argument with logarithmic verifier and applications, 527-557 [Zbl 07600986]
\textit{Abe, Masayuki; Ambrona, Miguel; Ohkubo, Miyako}, On black-box extensions of non-interactive zero-knowledge arguments, and signatures directly from simulation soundness, 558-589 [Zbl 07600987]
\textit{Abdolmaleki, Behzad; Lipmaa, Helger; Siim, Janno; Zając, Michał}, On QA-NIZK in the BPK model, 590-620 [Zbl 07600988]
\textit{Genise, Nicholas; Micciancio, Daniele; Peikert, Chris; Walter, Michael}, Improved discrete Gaussian and Subgaussian analysis for lattice cryptography, 623-651 [Zbl 07600990]
\textit{Lai, Qiqi; Liu, Feng-Hao; Wang, Zhedong}, Almost tight security in lattices with polynomial moduli -- PRF, IBE, all-but-many LTF, and more, 652-681 [Zbl 07600991]Fractional diffusion equation-based image denoising model using CN-GL schemehttps://zbmath.org/1496.940052022-11-17T18:59:28.764376Z"Abirami, A."https://zbmath.org/authors/?q=ai:abirami.a"Prakash, P."https://zbmath.org/authors/?q=ai:prakash.pradyot|prakash.prem|prakash.prathibha|prakash.p-v|prakash.pankaj|prakash.periasamy"Thangavel, K."https://zbmath.org/authors/?q=ai:thangavel.kSummary: In recent decades, variational methods have achieved great success in reducing noise owing to the use of total variation (TV). The TV-based denoising model introduced by Rudin-Osher-Fatemi (ROF) is playing vital role in denoising the different types of images. In this paper, a new denoising model based on space fractional diffusion equation is proposed with a finite domain discretized using effective applications of Crank-Nicholson and Grünwald Letnikov difference schemes. The ROF model has been adopted to solve the proposed model with the help of Alternative Direction Implicit method to denoise the image. The experimental results of the proposed model have been compared with those of the Gaussian model and it is observed that the Peak Signal-to-Noise Ratio has been improved.On the application of Lehmer means in signal and image processinghttps://zbmath.org/1496.940062022-11-17T18:59:28.764376Z"Amat, Sergio"https://zbmath.org/authors/?q=ai:amat.sergio-p"Magreñán, Ángel A."https://zbmath.org/authors/?q=ai:magrenan.angel-alberto"Ruiz, Juan"https://zbmath.org/authors/?q=ai:ruiz.juan-carlos|ruiz.juan-p|ruiz.juan-miguel|ruiz.juan-f"Trillo, Juan C."https://zbmath.org/authors/?q=ai:trillo.juan-carlos"Yáñez, Dionisio F."https://zbmath.org/authors/?q=ai:yanez.dionisio-fSummary: This paper is devoted to the construction and analysis of some new non-linear subdivision and multiresolution schemes using the Lehmer means. Our main objective is to attain adaption close to discontinuities. We present theoretical, numerical results and applications for different schemes. The main theoretical result is related to the four-point interpolatory scheme, that we write as a perturbation of a linear scheme. Our aim is to establish a one-step contraction property that allows to prove the stability of the new scheme. Indeed with a one-step contraction property for the scheme of differences, it is possible to prove the stability of the 2D algorithm constructed using a tensor product approach. In this article, we also consider the associated three points cell-average scheme, that we will use to present some results for image compression, and a non-interpolatory scheme, that we will use to introduce an application to subdivision curves in 2D. These applications show that the use of the Lehmer mean is suitable for the design of subdivision schemes for the generation of curves and for image processing.Color image inpainting via robust pure quaternion matrix completion: error bound and weighted losshttps://zbmath.org/1496.940072022-11-17T18:59:28.764376Z"Chen, Junren"https://zbmath.org/authors/?q=ai:chen.junren"Ng, Michael K."https://zbmath.org/authors/?q=ai:ng.michael-k|ng.michael-ka-shingClassification of images by using distance functions defined on intuitionistic fuzzy setshttps://zbmath.org/1496.940082022-11-17T18:59:28.764376Z"Michalíková, Alžbeta"https://zbmath.org/authors/?q=ai:michalikova.alzbetaSummary: Intuitionistic fuzzy sets are mathematical structures which could be, together with operations, relations and functions defined on them, applied in many different spheres. In this paper, the distance functions defined on intuitionistic fuzzy sets are used to solve the problem of classification of images. Our specific problem is that we need to classify tire tread images into selected classes. Each class is characterized by its pattern. In the first step, the pre-processing of the image into the numeric data is done. The numerical data are represented by the specific vector. Then the values of membership function, non-membership function and hesitance margin for each coordinate of vector are calculated. As the last step of algorithm, the values of distance function between image and class patterns are computed. Classification is performed with the use of special function \textit{Sim} whose values are dependent on distance function.
For the entire collection see [Zbl 1478.03003].Cauchy noise removal by nonlinear diffusion equationshttps://zbmath.org/1496.940092022-11-17T18:59:28.764376Z"Shi, Kehan"https://zbmath.org/authors/?q=ai:shi.kehan"Dong, Gang"https://zbmath.org/authors/?q=ai:dong.gang"Guo, Zhichang"https://zbmath.org/authors/?q=ai:guo.zhichangSummary: This paper focuses on the problem of image restoration under Cauchy noise. The variational method, which constructs the data fidelity term involving the Cauchy distribution by MAP estimator, has been proven to be a successful approach. In this paper, a nonlinear diffusion equation is proposed to deal with it. The main ingredients of the proposed equation are a gray level based diffusivity that estimates the amplitude of the noise and a classical gradient based diffusivity that controls the anisotropic diffusion according to the image's local structure. The proposed equation has the nondivergence form, and its properties, including the existence, uniqueness, and stability of solutions, are established by the notion of viscosity solution. Experimental results show the superiority of the proposed equation over variational methods in restoring small details of images.The springback penalty for robust signal recoveryhttps://zbmath.org/1496.940102022-11-17T18:59:28.764376Z"An, Congpei"https://zbmath.org/authors/?q=ai:an.congpei"Wu, Hao-Ning"https://zbmath.org/authors/?q=ai:wu.hao-ning"Yuan, Xiaoming"https://zbmath.org/authors/?q=ai:yuan.xiaomingSummary: We propose a new penalty, the springback penalty, for constructing models to recover an unknown signal from incomplete and inaccurate measurements. Mathematically, the springback penalty is a weakly convex function. It bears various theoretical and computational advantages of both the benchmark convex \(\ell_1\) penalty and many of its non-convex surrogates that have been well studied in the literature. We establish the exact and stable recovery theory for the recovery model using the springback penalty for both sparse and nearly sparse signals, respectively, and derive an easily implementable difference-of-convex algorithm. In particular, we show its theoretical superiority to some existing models with a sharper recovery bound for some scenarios where the level of measurement noise is large or the amount of measurements is limited. We also demonstrate its numerical robustness regardless of the varying coherence of the sensing matrix. The springback penalty is particularly favorable for the scenario where the incomplete and inaccurate measurements are collected by coherence-hidden or -static sensing hardware due to its theoretical guarantee of recovery with severe measurements, computational tractability, and numerical robustness for ill-conditioned sensing matrices.Fast algorithms for solving the inverse scattering problem for the Zakharov-Shabat system of equations and their applicationshttps://zbmath.org/1496.940112022-11-17T18:59:28.764376Z"Delitsyn, A. L."https://zbmath.org/authors/?q=ai:delitsyn.andrei-lSummary: The problem of numerical solution of a nonlinear Schrödinger equation is considered from the point of view of applications to the compensation of signal distortions in a fiber optic communication line. The problem of constructing fast algorithms for the direct and inverse scattering problems for the Zakharov-Shabat system of equations is studied. An overview of the main methods used currently is given. The time complexity of the algorithms is described together with their applicability to realistic signals.The novel method of the estimation of the Fourier transform based on noisy measurementshttps://zbmath.org/1496.940122022-11-17T18:59:28.764376Z"Galkowski, Tomasz"https://zbmath.org/authors/?q=ai:galkowski.tomasz"Pawlak, Miroslaw"https://zbmath.org/authors/?q=ai:pawlak.miroslawThe authors deal with the subject of analyzing the spectrum of signals associated with noise. They propose a method for estimating the frequency content of a signal derived from a nonparametric technique for function estimation. The mechanism used is based on orthogonal series expansions. Thus, the paper proposes a new integral version of nonparametric spectrum estimation using trigonometric series. Examples and numerical experiments are presented as well.
For the entire collection see [Zbl 1364.68015].
Reviewer: Liviu Goraş (Iaşi)Robust recovery of a kind of weighted \(l_1\)-minimization without noise levelhttps://zbmath.org/1496.940132022-11-17T18:59:28.764376Z"Gao, Yi"https://zbmath.org/authors/?q=ai:gao.yi"Zhang, Wenjie"https://zbmath.org/authors/?q=ai:zhang.wenjiePerformance analysis for unconstrained analysis based approacheshttps://zbmath.org/1496.940142022-11-17T18:59:28.764376Z"Ge, Huanmin"https://zbmath.org/authors/?q=ai:ge.huanmin"Chen, Wengu"https://zbmath.org/authors/?q=ai:chen.wengu"Li, Dongfang"https://zbmath.org/authors/?q=ai:li.dongfang"Wu, Fengyan"https://zbmath.org/authors/?q=ai:wu.fengyanThe finite steps of convergence of the fast thresholding algorithms with \(f\)-feedbacks in compressed sensinghttps://zbmath.org/1496.940152022-11-17T18:59:28.764376Z"Han, Ningning"https://zbmath.org/authors/?q=ai:han.ningning"Lu, Jian"https://zbmath.org/authors/?q=ai:lu.jian.2|lu.jian.1|lu.jian"Li, Shidong"https://zbmath.org/authors/?q=ai:li.shidongSummary: Iterative algorithms based on thresholding, feedback, and null space tuning (NST+HT+FB) for sparse signal recovery are exceedingly effective and efficient, particularly for large-scale problems. The core algorithm is shown to converge in finitely many steps under a (preconditioned) restricted isometry condition. We derive in this article the number of iterations to guarantee the convergence of the NST+HT+FB algorithm. Moreover, an accelerated class of adaptive feedback scheme of the iterative algorithm, termed NST+HT+\(f\)-FB, is proposed and analyzed. The scheme NST+HT+\(f\)-FB has a variable/adaptive index selection and different feedback principles at each iteration defined by a function \(f(k)\). It is even more effective, both from its ability to recover sparse signals with a larger number of non-zeros and from its rate of convergence. The convergence of the accelerated scheme is established. The finite number of iterations for guaranteed convergence by the NST+HT+\(f\)-FB scheme is also obtained. Furthermore, it is possible to accelerate the rate of convergence and improve the condition of convergence by selecting an appropriate size of the thresholding index set \(T_k\) per iteration. The theoretical findings are validated through extensive numerical experiments. It has been shown that the proposed algorithm has a clearly advantageous balance of efficiency, adaptivity, and accuracy compared with other state-of-the-art greedy algorithms. Detailed comparisons are provided.On the conditions for the passage of a signal through a chain of asynchronous threshold elementshttps://zbmath.org/1496.940162022-11-17T18:59:28.764376Z"Kuznetsov, O. P."https://zbmath.org/authors/?q=ai:kuznetsov.oleg-pSummary: We investigate the signal propagation process in a chain of series-connected asynchronous threshold elements. The asynchronous nature of the elements is manifested in the fact that they can have varying duration of switching from a passive state to an active state and vice versa. The elements are reactive; i.e., they are excited as a result of external influences and become passive when there are no external influences. It is shown that, depending on the element on-off switching transient duration ratio, the duration of the signal passing through the chain can be preserved, increase, or decrease. In the last case, the signal does not pass through a sufficiently long chain. The conditions for the passage of a signal through the chain are stated.Multifractal characteristics of singular signalshttps://zbmath.org/1496.940172022-11-17T18:59:28.764376Z"Oświęcimka, Paweł"https://zbmath.org/authors/?q=ai:oswiecimka.pawel"Minati, Ludovico"https://zbmath.org/authors/?q=ai:minati.ludovicoStarting with locally Hölder continuous functions satisfying \[g(x+h)-g(x)\propto C\cdot h^{\alpha(x)},\] multifractal processes are characterized by a typically concave form of the ``singularity spectrum'' \(f(\alpha)\). The spectrum is defined as \(f(\alpha)=d(\{x\mid \alpha(x)\stackrel{!}{=}\alpha\})\), where \(d(\cdot)\) denotes the Hausdorff dimension of the respective set. Such processes are applied in such diverse areas as financial time series or medical applications [\textit{A. L. Karperien} et al., Banach Cent. Publ. 109, 23--45 (2016; Zbl 1355.28014)].
The present paper compares two spectrum estimation techniques, namely the ``Multifractal Detrended Fluctuation Analysis'' (MDFA) [\textit{J. W. Kantelhardt} et al., Physica A 316, No. 1--4, 87--114 (2002; Zbl 1001.62029)] and the ``Wavelet Leader'' (WL)-method [\textit{S. Jaffard}, Proc. Symp. Pure Math. 72, 91--151 (2004; Zbl 1093.28005)] on three data sets. Two of them exhibit typical recursive multiscale structures like Binomial cascades or similar Cantor-like constructions.
The third signal, however, exhibits clearly visible isolated singularities, and a comparision of MDFA/WL results with a standard wavelet analysis diagram -- clearly locating these isolated singularities -- indicates, that a multifractal interpretation of the signal, based on MDFA/WL might be misleading in this case.
For the entire collection see [Zbl 1491.93003].
Reviewer: Hans-Georg Stark (Aschaffenburg)Quasi-FM waveform using chaotic oscillator for joint radar and communication systemshttps://zbmath.org/1496.940182022-11-17T18:59:28.764376Z"Pappu, Chandra S."https://zbmath.org/authors/?q=ai:pappu.chandra-s"Carroll, Thomas L."https://zbmath.org/authors/?q=ai:carroll.thomas-lSummary: The authors propose a novel signal design for generating wideband quasi-Frequency Modulated (FM) waveforms using chaotic systems. The receiver is based on a self synchronizing chaotic system, making for fast synchronization that is robust to timing errors or Doppler shifts. The chaotic oscillator has fast and slow time scales, and the slow oscillating part of the chaotic system is used to sweep the fast oscillating part thereby generating a modulated waveform that changes its frequency as a function of time. The potentials of these waveforms are demonstrated for joint radar-communication (RadComm) systems. Using the same nonlinear system a chaos frequency shift keying (CFSK) approach is utilized to encode the digital information. To decode the information, a drive-response synchronization scheme is utilized. Results indicate that our proposed signal design closely matches the bit-error rate (BER) of theoretical noncoherent frequency shift keying (FSK) while having good radar imaging capabilities.Exact reconstruction of sparse non-harmonic signals from their Fourier coefficientshttps://zbmath.org/1496.940192022-11-17T18:59:28.764376Z"Petz, Markus"https://zbmath.org/authors/?q=ai:petz.markus"Plonka, Gerlind"https://zbmath.org/authors/?q=ai:plonka.gerlind"Derevianko, Nadiia"https://zbmath.org/authors/?q=ai:derevianko.nadiiaIn this paper, the authors propose a new method to reconstruct real non-harmonic Fourier sums, i.e. real signals which can be represented as sparse exponential sums of the form
\[
f(t)=\sum_{j=1}^{K}\gamma_{j}\cos(2\pi a_j t + b_j),
\]
from their Fourier coefficients. They assume that \(K\in\mathbb{N}\), \(\gamma_j\in (0,\infty)\), \((a_j, b_j) \in (0, \infty)\times[0, 2\pi )\), and that the frequency parameters \(a_j\) are pairwise distinct.
Their approach is based on two steps. The first one consists of reconstructing the non-\(P\)-periodic part of \(f\), employing a modification of the recently proposed AAA algorithm [\textit{Y. Nakatsukasa} et al., SIAM J. Sci. Comput. 40, No. 3, A1494--A1522 (2018; Zbl 1390.41015)]; the second step concerns the determination of possible \(P\)-periodic terms of \(f\). In particular, they prove that their method allows to uniquely determine \(f\) from at most \(2K+2\) of its Fourier coefficients.
Finally, the authors present two numerical experiments, which show that the considered reconstruction scheme provides very good reconstruction results even for small frequency gaps if \(P\) is chosen suitably. These results are compared with the ones obtained with a stabilized variant of Prony's method.
Reviewer: Mariarosaria Natale (Firenze)Characterizing complexity of non-invertible chaotic maps in the Shannon-Fisher information plane with ordinal patternshttps://zbmath.org/1496.940202022-11-17T18:59:28.764376Z"Spichak, David"https://zbmath.org/authors/?q=ai:spichak.david"Kupetsky, Audrey"https://zbmath.org/authors/?q=ai:kupetsky.audrey"Aragoneses, Andrés"https://zbmath.org/authors/?q=ai:aragoneses.andresSummary: Being able to distinguish the different types of dynamics present in a given nonlinear system is of great importance in complex dynamics. It allows to characterize the system, find similarities and differences with other nonlinear systems, and classify those dynamical regimes to understand them better. For systems that develop chaos it is not always easy to distinguish determinism from stochasticity. We analyze several non-invertible maps by projecting them on the two-dimensional Fisher-Shannon plane using ordinal patterns. We find that this technique unfolds the complex structure of chaotic systems, showing more details than other methods. It also reveals signatures common to most of the non-invertible maps, and demonstrates its capability to distinguish determinism from stochasticity.Monotonicity of code symbol frequencies in recency rank encodinghttps://zbmath.org/1496.940212022-11-17T18:59:28.764376Z"Ellison, Matthew"https://zbmath.org/authors/?q=ai:ellison.matthew"Johnson, Joseph"https://zbmath.org/authors/?q=ai:johnson.joseph-francis|johnson.joseph|johnson.joseph-a-iii|johnson.joseph-p|johnson.joseph-g|johnson.joseph-dSummary: In recency rank encoding, the encoder reads along the source text, and, as each symbol \(s\) is read, the code symbol \(c_j\) is added to the code text, where \(j\) is the number of distinct symbols which have appeared since the previous occurrence of \(s\). We consider an idealized source text model which is two-way infinite \((\mathbb{Z}\)-indexed), and where at each position, independently, one of \(m\) source symbols \(s_1, \dots,s_m\) is chosen at random according to fixed global frequencies \(f_1,\dots,f_m>0\). Applying recency rank encoding to this source text yields a two-way infinite code text on code symbols \(c_0,\dots,c_{m-1}\), and we let \(g_i=g_i(f_1,\dots,f_m)\) denote the probability that the symbol at a given source index is encoded by \(c_i\). We prove that \(g_0 \ge\dots\ge g_{m-1}\), with equality at any point if and only if \(f_1=\dots =f_m=\frac 1m\), confirming a conjecture of \textit{C. Buhse} et al. [ibid. 10, No. 2, 175--184 (2015; Zbl 1434.94050)].Distributed (correlation) samplers: how to remove a trusted dealer in one roundhttps://zbmath.org/1496.940222022-11-17T18:59:28.764376Z"Abram, Damiano"https://zbmath.org/authors/?q=ai:abram.damiano"Scholl, Peter"https://zbmath.org/authors/?q=ai:scholl.peter"Yakoubov, Sophia"https://zbmath.org/authors/?q=ai:yakoubov.sophiaSummary: Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys.
In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things, indistinguishability obfuscation. We introduce what we call a distributed sampler, which enables \(n\) parties to sample a single public value (SRS) from any distribution. We construct a semi-malicious distributed sampler in the plain model, and use it to build a semi-malicious public-key PCF in the plain model. A public-key PCF can be thought of as a distributed correlation sampler; instead of producing a public SRS, it gives each party a private random value (where the values satisfy some correlation).
We introduce a general technique called an anti-rusher which compiles any one-round protocol with semi-malicious security without inputs to a similar one-round protocol with active security by making use of a programmable random oracle. This gets us actively secure distributed samplers and public-key PCFs in the random oracle model.
Finally, we explore some tradeoffs. Our first PCF construction is limited to reverse-sampleable correlations (where the random outputs of honest parties must be simulatable given the random outputs of corrupt parties); we additionally show a different construction without this limitation, but which does not allow parties to hold secret parameters of the correlation. We also describe how to avoid the use of a random oracle at the cost of relying on sub-exponentially secure indistinguishability obfuscation.
For the entire collection see [Zbl 1493.94001].Secure non-interactive reduction and spectral analysis of correlationshttps://zbmath.org/1496.940232022-11-17T18:59:28.764376Z"Agarwal, Pratyush"https://zbmath.org/authors/?q=ai:agarwal.pratyush"Narayanan, Varun"https://zbmath.org/authors/?q=ai:narayanan.varun"Pathak, Shreya"https://zbmath.org/authors/?q=ai:pathak.shreya"Prabhakaran, Manoj"https://zbmath.org/authors/?q=ai:prabhakaran.manoj-m"Prabhakaran, Vinod M."https://zbmath.org/authors/?q=ai:prabhakaran.vinod-m"Rehan, Mohammad Ali"https://zbmath.org/authors/?q=ai:rehan.mohammad-aliSummary: Correlated pairs of random variables are a central concept in information-theoretically secure cryptography. Secure reductions between different correlations have been studied, and completeness results are known. Further, the complexity of such reductions is intimately connected with circuit complexity and efficiency of locally decodable codes. As such, making progress on these complexity questions faces strong barriers. Motivated by this, in this work, we study a restricted form of secure reductions -- namely, Secure Non-Interactive Reductions (SNIR) -- which is still closely related to the original problem, and establish several fundamental results and relevant techniques for it.
We uncover striking connections between SNIR and linear algebraic properties of correlations. Specifically, we define the spectrum of a correlation, and show that a target correlation has a SNIR to a source correlation only if the spectrum of the latter contains the entire spectrum of the former. We also establish a ``mirroring lemma'' that shows an unexpected symmetry between the two parties in a SNIR, when viewed through the lens of spectral analysis. We also use cryptographic insights and elementary linear algebraic analysis to fully characterize the role of common randomness as well as local randomness in SNIRs. We employ these results to resolve several fundamental questions about SNIRs, and to define future directions.
For the entire collection see [Zbl 1493.94003].Unclonable polymers and their cryptographic applicationshttps://zbmath.org/1496.940242022-11-17T18:59:28.764376Z"Almashaqbeh, Ghada"https://zbmath.org/authors/?q=ai:almashaqbeh.ghada"Canetti, Ran"https://zbmath.org/authors/?q=ai:canetti.ran"Erlich, Yaniv"https://zbmath.org/authors/?q=ai:erlich.yaniv"Gershoni, Jonathan"https://zbmath.org/authors/?q=ai:gershoni.jonathan"Malkin, Tal"https://zbmath.org/authors/?q=ai:malkin.tal-g"Pe'er, Itsik"https://zbmath.org/authors/?q=ai:peer.itsik"Roitburd-Berman, Anna"https://zbmath.org/authors/?q=ai:roitburd-berman.anna"Tromer, Eran"https://zbmath.org/authors/?q=ai:tromer.eranSummary: We propose a mechanism for generating and manipulating protein polymers to obtain a new type of consumable storage that exhibits intriguing cryptographic ``self-destruct'' properties, assuming the hardness of certain polymer-sequencing problems.
To demonstrate the cryptographic potential of this technology, we first develop a formalism that captures (in a minimalistic way) the functionality and security properties provided by the technology. Next, using this technology, we construct and prove security of two cryptographic applications that are currently obtainable only via trusted hardware that implements logical circuitry (either classical or quantum). The first application is a password-controlled secure vault where the stored data is irrecoverably erased once a threshold of unsuccessful access attempts is reached. The second is (a somewhat relaxed version of) one-time programs, namely a device that allows evaluating a secret function only a limited number of times before self-destructing, where each evaluation is made on a fresh user-chosen input.
Finally, while our constructions, modeling, and analysis are designed to capture the proposed polymer-based technology, they are sufficiently general to be of potential independent interest.
For the entire collection see [Zbl 1493.94001].CoCoA: concurrent continuous group key agreementhttps://zbmath.org/1496.940252022-11-17T18:59:28.764376Z"Alwen, Joël"https://zbmath.org/authors/?q=ai:alwen.joel"Auerbach, Benedikt"https://zbmath.org/authors/?q=ai:auerbach.benedikt"Noval, Miguel Cueto"https://zbmath.org/authors/?q=ai:noval.miguel-cueto"Klein, Karen"https://zbmath.org/authors/?q=ai:klein.karen"Pascual-Perez, Guillermo"https://zbmath.org/authors/?q=ai:pascual-perez.guillermo"Pietrzak, Krzyzstof"https://zbmath.org/authors/?q=ai:pietrzak.krzyzstof"Walter, Michael"https://zbmath.org/authors/?q=ai:walter.michael.1|walter.michaelSummary: Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can efficiently scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security.
In current proposals -- most notably in TreeKEM (which is part of the IETF's Messaging Layer Security (MLS) protocol draft) - for users in a group of size \(n\) to rotate their keys, they must each craft a message of size \(\log (n)\) to be broadcast to the group using an (untrusted) delivery server.
In larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any \(T \le n\) users to simultaneously rotate their keys in just 2 communication rounds have been suggested (e.g. ``Propose and Commit'' by MLS). Unfortunately, 2-round concurrent updates are either damaging or expensive (or both); i.e. they either result in future operations being more costly (e.g. via ``blanking'' or ``tainting'') or are costly themselves requiring \(\varOmega (T)\) communication for each user.
In this paper we propose CoCoA; a new scheme that allows for \(T\) concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require \(\varOmega (\log^2(n))\) communication per user. To circumvent the lower bound, CoCoA increases the number of rounds needed to complete all updates from 2 up to (at most) \(\log (n)\); though typically fewer rounds are needed.
The key insight of our protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets \(T\) concurrent update requests will approve one and reject the remaining \(T-1\). In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most \(\log (n)\) such update rounds.
To keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol.
For the entire collection see [Zbl 1493.94002].Refined cryptanalysis of the GPRS ciphers GEA-1 and GEA-2https://zbmath.org/1496.940262022-11-17T18:59:28.764376Z"Amzaleg, Dor"https://zbmath.org/authors/?q=ai:amzaleg.dor"Dinur, Itai"https://zbmath.org/authors/?q=ai:dinur.itaiSummary: \textit{C. Beierle} et al. [Lect. Notes Comput. Sci. 12697, 155--183 (2021; Zbl 1479.94125)] presented the first public analysis of the GPRS ciphers GEA-1 and GEA-2. They showed that although GEA-1 uses a 64-bit session key, it can be recovered with the knowledge of only 65 bits of keystream in time \(2^{40}\) using 44 GiB of memory. The attack exploits a weakness in the initialization process of the cipher that was presumably hidden intentionally by the designers to reduce its security.
While no such weakness was found for GEA-2, the authors presented an attack on this cipher with time complexity of about \(2^{45}\). The main practical obstacle is the required knowledge of 12800 bits of keystream used to encrypt a full GPRS frame. Variants of the attack are applicable (but more expensive) when given less consecutive keystream bits, or when the available keystream is fragmented (it contains no long consecutive block).
In this paper, we improve and complement the previous analysis of GEA-1 and GEA-2. For GEA-1, we devise an attack in which the memory complexity is reduced by a factor of about \(2^{13} = 8192\) from 44 GiB to about 4 MiB, while the time complexity remains \(2^{40}\). Our implementation recovers the GEA-1 session key in average time of 2.5 h on a modern laptop.
For GEA-2, we describe two attacks that complement the analysis of Beierle et al. [loc.cit.] The first attack obtains a linear tradeoff between the number of consecutive keystream bits available to the attacker (denoted by \(\ell)\) and the time complexity. It improves upon the previous attack in the range of (roughly) \(\ell \le 7000\). Specifically, for \(\ell = 1100\) the complexity of our attack is about \(2^{54}\), while the previous one is not faster than the \(2^{64}\) brute force complexity. In case the available keystream is fragmented, our second attack reduces the memory complexity of the previous attack by a factor of 512 from 32 GiB to 64 MiB with no time complexity penalty.
Our attacks are based on new combinations of stream cipher cryptanalytic techniques and algorithmic techniques used in other contexts (such as solving the \(k\)-XOR problem).
For the entire collection see [Zbl 1493.94003].Field instruction multiple datahttps://zbmath.org/1496.940272022-11-17T18:59:28.764376Z"Aung, Khin Mi Mi"https://zbmath.org/authors/?q=ai:aung.khin-mi-mi"Lim, Enhui"https://zbmath.org/authors/?q=ai:lim.enhui"Sim, Jun Jie"https://zbmath.org/authors/?q=ai:sim.jun-jie"Tan, Benjamin Hong Meng"https://zbmath.org/authors/?q=ai:tan.benjamin-hong-meng"Wang, Huaxiong"https://zbmath.org/authors/?q=ai:wang.huaxiong"Yeo, Sze Ling"https://zbmath.org/authors/?q=ai:yeo.sze-lingSummary: Fully homomorphic encryption (FHE) has flourished since it was first constructed by \textit{C. Gentry} [in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC '09. Bethesda, MD, USA, May 31--June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 169--178 (2009; Zbl 1304.94059)]. Single instruction multiple data (SIMD) gave rise to efficient homomorphic operations on vectors in \((\mathbb{F}_{t^d})^\ell\), for prime \(t\). RLWE instantiated with cyclotomic polynomials of the form \(X^{2^N}+1\) dominate implementations of FHE due to highly efficient fast Fourier transformations. However, this choice yields very short SIMD plaintext vectors and high degree extension fields, e.g. \(\ell < 100\), \(d > 100\) for small primes \((t = 3, 5, \dots)\).
In this work, we describe a method to encode more data on top of SIMD, Field Instruction Multiple Data, applying reverse multiplication friendly embedding (RMFE) to FHE. With RMFE, length-\(k\) \(\mathbb{F}_t\) vectors can be encoded into \(\mathbb{F}_{t^d}\) and multiplied once. The results have to be recoded (decoded and then re-encoded) before further multiplications can be done. We introduce an FHE-specific technique to additionally evaluate arbitrary linear transformations on encoded vectors for free during the FHE recode operation. On top of that, we present two optimizations to unlock high degree extension fields with small \(t\) for homomorphic computation: \(r\)-fold RMFE, which allows products of up to \(2^r\) encoded vectors before recoding, and a three-stage recode process for RMFEs obtained by composing two smaller RMFEs. Experiments were performed to evaluate the effectiveness of FIMD from various RMFEs compared to standard SIMD operations. Overall, we found that FIMD generally had \(>2{\times }\) better (amortized) multiplication times compared to FHE for the same amount of data, while using almost \(k/2{\times }\) fewer ciphertexts required.
For the entire collection see [Zbl 1493.94001].Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifierhttps://zbmath.org/1496.940282022-11-17T18:59:28.764376Z"Bootle, Jonathan"https://zbmath.org/authors/?q=ai:bootle.jonathan"Chiesa, Alessandro"https://zbmath.org/authors/?q=ai:chiesa.alessandro"Liu, Siqi"https://zbmath.org/authors/?q=ai:liu.siqiSummary: Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs.
We present an IOP that simultaneously achieves the properties of zero knowledge, linear-time proving, and polylogarithmic-time verification. We construct a zero-knowledge IOP where, for the satisfiability of an N-gate arithmetic circuit over any field of size \(\varOmega (N)\), the prover uses \(O(N)\) field operations and the verifier uses \({\mathsf{polylog}}(N)\) field operations (with proof length \(O(N)\) and query complexity \({\mathsf{polylog}}(N))\). Polylogarithmic verification is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-time-computable encoding of the circuit whose satisfiability is being proved).
Our result implies progress on a basic goal in the area of efficient zero knowledge. Via a known transformation, we obtain a zero knowledge argument system where the prover runs in linear time and the verifier runs in polylogarithmic time; the construction is plausibly post-quantum and only makes a black-box use of lightweight cryptography (collision-resistant hash functions).
For the entire collection see [Zbl 1493.94002].Secure multiparty computation with sublinear preprocessinghttps://zbmath.org/1496.940292022-11-17T18:59:28.764376Z"Boyle, Elette"https://zbmath.org/authors/?q=ai:boyle.elette"Gilboa, Niv"https://zbmath.org/authors/?q=ai:gilboa.niv"Ishai, Yuval"https://zbmath.org/authors/?q=ai:ishai.yuval"Nof, Ariel"https://zbmath.org/authors/?q=ai:nof.arielSummary: A common technique for enhancing the efficiency of secure multiparty computation (MPC) with dishonest majority is via preprocessing: In an offline phase, parties engage in an input-independent protocol to securely generate correlated randomness. Once inputs are known, the correlated randomness is consumed by a ``non-cryptographic'' and highly efficient online protocol.
The correlated randomness in such protocols traditionally comes in two flavors: multiplication triples, which suffice for security against semi-honest parties, and authenticated multiplication triples that yield efficient protocols against malicious parties.
Recent constructions of pseudorandom correlation generators [\textit{E. Boyle} et al., Lect. Notes Comput. Sci. 11694, 489--518 (2019; Zbl 07178325)] enable concretely efficient secure generation of multiplication triples with sublinear communication complexity. However, these techniques do not efficiently apply to authenticated triples, except in the case of secure two-party computation of arithmetic circuits over large fields.
In this work, we propose the first concretely efficient approach for (malicious) MPC with preprocessing in which the offline communication is sublinear in the circuit size. More specifically, the offline communication scales with the square root of the circuit size.
From a feasibility point of view, our protocols can make use of any secure protocol for generating (unauthenticated) multiplication triples together with any additive homomorphic encryption. We propose concretely efficient instantiations (based on strong but plausible ``linear-only'' assumptions) from existing homomorphic encryption schemes and pseudorandom correlation generators.
Our technique is based on a variant of a recent protocol of \textit{E. Boyle} et al. [ibid. 12826, 457--485 (2021; Zbl 07511740)] for MPC with preprocessing. As a result, our protocols inherit the succinct correlated randomness feature of the latter protocol.
For the entire collection see [Zbl 1493.94001].Batch-OT with optimal ratehttps://zbmath.org/1496.940302022-11-17T18:59:28.764376Z"Brakerski, Zvika"https://zbmath.org/authors/?q=ai:brakerski.zvika"Branco, Pedro"https://zbmath.org/authors/?q=ai:branco.pedro"Döttling, Nico"https://zbmath.org/authors/?q=ai:dottling.nico"Pu, Sihang"https://zbmath.org/authors/?q=ai:pu.sihangSummary: We show that it is possible to perform \(n\) independent copies of 1-out-of-2 oblivious transfer in two messages, where the communication complexity of the receiver and sender (each) is \(n(1+o(1))\) for sufficiently large \(n\). Note that this matches the information-theoretic lower bound. Prior to this work, this was only achievable by using the heavy machinery of rate-1 fully homomorphic encryption (Rate-1 FHE [\textit{Z. Brakerski} et al., Lect. Notes Comput. Sci. 11892, 407--437 (2019; Zbl 1455.94132)]).
To achieve rate-1 both on the receiver's and sender's end, we use the LPN assumption, with slightly sub-constant noise rate \(1/m^{\epsilon}\) for any \(\epsilon >0\) together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive ``bootstrapping'' operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE).
For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to ``emulate'' the binary group \(\mathbb{Z}_2\) (or any other small-order group) inside a prime-order group \(\mathbb{Z}_p\) in a function-private manner. That is, \(\mathbb{Z}_2\) operations are mapped to \(\mathbb{Z}_p\) operations such that the outcome of the latter do not reveal additional information beyond the \(\mathbb{Z}_2\) outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.
For the entire collection see [Zbl 1493.94002].COA-secure obfuscation and applicationshttps://zbmath.org/1496.940312022-11-17T18:59:28.764376Z"Canetti, Ran"https://zbmath.org/authors/?q=ai:canetti.ran"Chakraborty, Suvradip"https://zbmath.org/authors/?q=ai:chakraborty.suvradip"Khurana, Dakshita"https://zbmath.org/authors/?q=ai:khurana.dakshita"Kumar, Nishant"https://zbmath.org/authors/?q=ai:kumar.nishant"Poburinnaya, Oxana"https://zbmath.org/authors/?q=ai:poburinnaya.oxana"Prabhakaran, Manoj"https://zbmath.org/authors/?q=ai:prabhakaran.manoj-mSummary: We put forth a new paradigm for program obfuscation, where obfuscated programs are endowed with proofs of ``well formedness.'' In addition to asserting existence of an underlying plaintext program with an attested structure, these proofs also prevent mauling attacks, whereby an adversary surreptitiously creates an obfuscated program based on secrets which are embedded in other obfuscated programs. We call this new guarantee Chosen Obfuscation Attacks (COA) security.
We show how to enhance a large class of obfuscation mechanisms to be COA-secure, assuming subexponentially secure IO for circuits and subexponentially secure one-way functions. To demonstrate the power of the new notion, we also use it to realize:
\par i) A new form of software watermarking, which provides significantly broader protection than current schemes against counterfeits that pass a keyless, public verification process.
\par ii) Completely CCA encryption, which is a strengthening of completely non-malleable encryption.
For the entire collection see [Zbl 1493.94001].Universally composable subversion-resilient cryptographyhttps://zbmath.org/1496.940322022-11-17T18:59:28.764376Z"Chakraborty, Suvradip"https://zbmath.org/authors/?q=ai:chakraborty.suvradip"Magri, Bernardo"https://zbmath.org/authors/?q=ai:magri.bernardo"Nielsen, Jesper Buus"https://zbmath.org/authors/?q=ai:nielsen.jesper-buus"Venturi, Daniele"https://zbmath.org/authors/?q=ai:venturi.danieleSummary: Subversion attacks undermine security of cryptographic protocols by replacing a legitimate honest party's implementation with one that leaks information in an undetectable manner. An important limitation of all currently known techniques for designing cryptographic protocols with security against subversion attacks is that they do not automatically guarantee security in the realistic setting where a protocol session may run concurrently with other protocols.
We remedy this situation by providing a foundation of reverse firewalls in the universal composability (UC) framework. More in details, our contributions are threefold:
\par i) We generalize the UC framework to the setting where each party consists of a core (which has secret inputs and is in charge of generating protocol messages) and a firewall (which has no secrets and sanitizes the outgoing/incoming communication from/to the core). Both the core and the firewall can be subject to different flavors of corruption, modeling different kinds of subversion attacks. For instance, we capture the setting where a subverted core looks like the honest core to any efficient test, yet it may leak secret information via covert channels (which we call specious subversion).
\par ii) We show how to sanitize UC commitments and UC coin tossing against specious subversion, under the DDH assumption.
\par iii) We show how to sanitize the classical GMW compiler for turning MPC with security in the presence of semi-honest adversaries into MPC with security in the presence of malicious adversaries. This yields a completeness theorem for maliciously secure MPC in the presence of specious subversion. Additionally, all our sanitized protocols are transparent, in the sense that communicating with a sanitized core looks indistinguishable from communicating with an honest core. Thanks to the composition theorem, our methodology allows, for the first time, to design subversion-resilient protocols by sanitizing different sub-components in a modular way.
For the entire collection see [Zbl 1493.94001].On succinct non-interactive arguments in relativized worldshttps://zbmath.org/1496.940332022-11-17T18:59:28.764376Z"Chen, Megan"https://zbmath.org/authors/?q=ai:chen.megan"Chiesa, Alessandro"https://zbmath.org/authors/?q=ai:chiesa.alessandro"Spooner, Nicholas"https://zbmath.org/authors/?q=ai:spooner.nicholasSummary: Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfortunately, SNARKs with desirable features such as a transparent (public-coin) setup are known only in the random oracle model (ROM). In applications this oracle must be heuristically instantiated and used in a non-black-box way.
In this paper we identify a natural oracle model, the low-degree random oracle model, in which there exist transparent SNARKs for all NP computations relative to this oracle. Informally, letting \(\mathcal{O}\) be a low-degree encoding of a random oracle, and assuming the existence of (standard-model) collision-resistant hash functions, there exist SNARKs relative to \(\mathcal{O}\) for all languages in \(\text{NP}^{\mathcal{O}}\). Such a SNARK can directly prove a computation about its own verifier.
To analyze this model, we introduce a more general framework, the linear code random oracle model (LCROM).
We show how to obtain SNARKs in the LCROM for computations that query the oracle, given an accumulation scheme for oracle queries. Then we construct such an accumulation scheme for the special case of a low degree random oracle.
For the entire collection see [Zbl 1493.94002].Limits of polynomial packings for \(\mathbb{Z}_{p^k}\) and \(\mathbb{F}_{p^k}\)https://zbmath.org/1496.940342022-11-17T18:59:28.764376Z"Cheon, Jung Hee"https://zbmath.org/authors/?q=ai:cheon.jung-hee"Lee, Keewoo"https://zbmath.org/authors/?q=ai:lee.keewooSummary: We formally define polynomial packing methods and initiate a unified study of related concepts in various contexts of cryptography. This includes homomorphic encryption (HE) packing and reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). We prove several upper bounds and impossibility results on packing methods for \(\mathbb{Z}_{p^k}\) or \(\mathbb{F}_{p^k}\)-messages into \(\mathbb{Z}_{p^t}[x]/f(x)\) in terms of (i) packing density, (ii) level-consistency, and (iii) surjectivity. These results have implications on recent development of HE-based MPC over \(\mathbb{Z}_{2^k}\) secure against actively corrupted majority and provide new proofs for upper bounds on RMFE.
For the entire collection see [Zbl 1493.94001].Round-optimal multi-party computation with identifiable aborthttps://zbmath.org/1496.940352022-11-17T18:59:28.764376Z"Ciampi, Michele"https://zbmath.org/authors/?q=ai:ciampi.michele"Ravi, Divya"https://zbmath.org/authors/?q=ai:ravi.divya"Siniscalchi, Luisa"https://zbmath.org/authors/?q=ai:siniscalchi.luisa"Waldner, Hendrik"https://zbmath.org/authors/?q=ai:waldner.hendrikSummary: Secure multi-party computation (MPC) protocols that are resilient to a dishonest majority allow the adversary to get the output of the computation while, at the same time, forcing the honest parties to abort. \textit{Y. Aumann} and \textit{Y. Lindell} [J. Cryptology 23, No. 2, 281--343 (2010; Zbl 1181.94091)] introduced the enhanced notion of security with identifiable abort, which still allows the adversary to trigger an abort but, at the same time, it enables the honest parties to agree on the identity of the party that led to the abort. More recently, \textit{S. Garg} et al. [Lect. Notes Comput. Sci. 9666, 448--476 (2016; Zbl 1371.94637)] showed that, assuming access to a simultaneous message exchange channel for all the parties, at least four rounds of communication are required to securely realize non-trivial functionalities in the plain model.
Following Garg et al. [loc.cit.], a sequence of works has matched this lower bound, but none of them achieved security with identifiable abort. In this work, we close this gap and show that four rounds of communication are also sufficient to securely realize any functionality with identifiable abort using standard and generic polynomial-time assumptions. To achieve this result we introduce the new notion of bounded-rewind secure MPC that guarantees security even against an adversary that performs a mild form of reset attacks. We show how to instantiate this primitive starting from any MPC protocol and by assuming trapdoor-permutations.
The notion of bounded-rewind secure MPC allows for easier parallel composition of MPC protocols with other (interactive) cryptographic primitives. Therefore, we believe that this primitive can be useful in other contexts in which it is crucial to combine multiple primitives with MPC protocols while keeping the round complexity of the final protocol low.
For the entire collection see [Zbl 1493.94001].Optimum attack on 3-round Feistel-2 structurehttps://zbmath.org/1496.940362022-11-17T18:59:28.764376Z"Daiza, Takanori"https://zbmath.org/authors/?q=ai:daiza.takanori"Kurosawa, Kaoru"https://zbmath.org/authors/?q=ai:kurosawa.kaoruSummary: Feistel-2 structure is a variant of Feistel structure such that the \(i^{th}\) round function is given by \(\mathrm{F}_i(k_i \oplus x)\), where \(\mathrm{F}_i\) is a public random function and \(k_i\) is a key of \(n/2\) bits. \textit{R. Lampe} and \textit{Y. Seurin} [Lect. Notes Comput. Sci. 8540, 243--264 (2015; Zbl 1382.94133)] showed that 3-round Feistel-2 structure is secure if \(D+T \ll 2^{n/4} \) (which is equivalent to \(D \ll 2^{n/4}\) and \(T \ll 2^{n/4}\)), where \(D\) is the number of queries to the encryption oracle and \(T\) is the number of queries to each \(\mathrm{F}_i\) oracle. On the other hand, only the meet-in-the-middle attack is known for 3-round Feistel-2 structure which works only for \((D,T)=(O(1), O(2^{n/2}))\) with \(O(2^{n/2})\) amount of memory.
In this paper, we first show that 3-round Feistel-2 structure is broken by a key recovery attack if \(DT \ge 2^{n/2} \) (which requires \(O(D+T)\) amount of memory). Since it works for \(D=T=O(2^{n/4})\), this attack proves that the security bound of Lampe and Seurin [loc. cit.] is tight at \(D=T=O(2^{n/4})\). We next present a memoryless key recovery attack for \((D,T)=(O(1), O(2^{n/2}))\). We finally show a memoryless key recovery attack for \(D=O(2^{n/4})\) and \(T=O(2^{n/4})\).
For the entire collection see [Zbl 1484.68016].An efficient eCK secure identity based two party authenticated key agreement scheme with security against active adversarieshttps://zbmath.org/1496.940372022-11-17T18:59:28.764376Z"Daniel, Renu Mary"https://zbmath.org/authors/?q=ai:daniel.renu-mary"Rajsingh, Elijah Blessing"https://zbmath.org/authors/?q=ai:rajsingh.elijah-blessing"Silas, Salaja"https://zbmath.org/authors/?q=ai:silas.salajaSummary: A Two-Party Authenticated Key Agreement (2-PAKA) protocol facilitates two communicating entities to equally contribute to the establishment of a shared session key. IDentity-based 2-PAKA (ID-2-PAKA) protocols are widely researched, since it eliminates the need for explicit public-key verification using digital certificates. Over the years, ID-2-PAKA protocols with perfect forward secrecy and Key Generation Center forward secrecy were devised, to circumvent the inherent key escrows in identity based cryptosystems. Nevertheless, cryptanalysis of the recent ID-2-PAKA schemes reveals that many of the protocols are insecure. We reconstruct the possible attacks against the schemes and propose a secure escrowless pairing-free ID-2-PAKA protocol. The proposed scheme is proven secure in the modified extended Canetti-Krawczyk model, which captures all the desirable security attributes of ID-2-PAKA protocols, including, public key replacement attack resilience. Comparative analysis of the protocol with other pairing-free ID-2-PAKA schemes suggests that the proposed scheme offers a fine trade-off between efficiency and security.On the concrete security of TLS 1.3 PSK modehttps://zbmath.org/1496.940382022-11-17T18:59:28.764376Z"Davis, Hannah"https://zbmath.org/authors/?q=ai:davis.hannah"Diemert, Denis"https://zbmath.org/authors/?q=ai:diemert.denis"Günther, Felix"https://zbmath.org/authors/?q=ai:gunther.felix|gunther.felix.1"Jager, Tibor"https://zbmath.org/authors/?q=ai:jager.tiborSummary: The pre-shared key (PSK) handshake modes of TLS 1.3 allow for the performant, low-latency resumption of previous connections and are widely used on the Web and by resource-constrained devices, e.g., in the Internet of Things. Taking advantage of these performance benefits with optimal and theoretically-sound parameters requires tight security proofs. We give the first tight security proofs for the TLS 1.3 PSK handshake modes.
Our main technical contribution is to address a gap in prior tight security proofs of TLS 1.3 which modeled either the entire key schedule or components thereof as independent random oracles to enable tight proof techniques. These approaches ignore existing interdependencies in TLS 1.3's key schedule, arising from the fact that the same cryptographic hash function is used in several components of the key schedule and the handshake more generally. We overcome this gap by proposing a new abstraction for the key schedule and carefully arguing its soundness via the indifferentiability framework. Interestingly, we observe that for one specific configuration, PSK-only mode with hash function SHA-384, it seems difficult to argue indifferentiability due to a lack of domain separation between the various hash function usages. We view this as an interesting insight for the design of protocols, such as future TLS versions.
For all other configurations however, our proofs significantly tighten the security of the TLS 1.3 PSK modes, confirming standardized parameters (for which prior bounds provided subpar or even void guarantees) and enabling a theoretically-sound deployment.
For the entire collection see [Zbl 1493.94002].Asymptotically quasi-optimal cryptographyhttps://zbmath.org/1496.940392022-11-17T18:59:28.764376Z"de Castro, Leo"https://zbmath.org/authors/?q=ai:de-castro.leo"Hazay, Carmit"https://zbmath.org/authors/?q=ai:hazay.carmit"Ishai, Yuval"https://zbmath.org/authors/?q=ai:ishai.yuval"Vaikuntanathan, Vinod"https://zbmath.org/authors/?q=ai:vaikuntanathan.vinod"Venkitasubramaniam, Muthu"https://zbmath.org/authors/?q=ai:venkitasubramaniam.muthuSummary: The question of minimizing the computational overhead of cryptography was put forward by the work of \textit{Y. Ishai} et al. [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 433--442 (2008; Zbl 1231.94050)]. The main conclusion was that, under plausible assumptions, most cryptographic primitives can be realized with constant computational overhead. However, this ignores an additive term that may depend polynomially on the (concrete) computational security parameter \(\lambda\). In this work, we study the question of obtaining optimal efficiency, up to polylogarithmic factors, for all choices of \(n\) and \(\lambda\), where \(n\) is the size of the given task. In particular, when \(n=\lambda\), we would like the computational cost to be only \(\tilde{O}(\lambda)\). We refer to this goal as asymptotically quasi-optimal (AQO) cryptography.
We start by realizing the first AQO semi-honest batch oblivious linear evaluation (BOLE) protocol. Our protocol applies to OLE over small fields and relies on the near-exponential security of the ring learning with errors (RLWE) assumption. Building on the above and on known constructions of AQO PCPs, we design the first AQO zero-knowledge (ZK) argument system for Boolean circuit satisfiability. Our construction combines a new AQO ZK-PCP construction that respects the AQO property of the underlying PCP along with a technique for converting statistical secrecy into soundness via OLE reversal. Finally, combining the above results, we get AQO secure computation protocols for Boolean circuits with security against malicious parties under RLWE.
For the entire collection see [Zbl 1493.94001].Revamped differential-linear cryptanalysis on reduced round ChaChahttps://zbmath.org/1496.940402022-11-17T18:59:28.764376Z"Dey, Sabyasachi"https://zbmath.org/authors/?q=ai:dey.sabyasachi"Garai, Hirendra Kumar"https://zbmath.org/authors/?q=ai:garai.hirendra-kumar"Sarkar, Santanu"https://zbmath.org/authors/?q=ai:sarkar.santanu"Sharma, Nitin Kumar"https://zbmath.org/authors/?q=ai:sharma.nitin-kumarSummary: In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has 20 rounds. \textit{C. Beierle} et al. [``Improved differential-linear attacks with applications to ARX ciphers'', Lect. Notes Comput. Sci. 12172, 329--358 (2020; \url{doi:10.1007/978-3-030-56877-1_12})] observed a differential in the 3.5-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need \(2^5\) iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a strategical improvement in PNB construction, modification of complexity calculation and an alternative attack method using two input-output pairs. Using these, we improve the time complexity, reducing it to \(2^{221.95}\) from \(2^{230.86}\) reported by Beierle et al. [loc. cit.] for 256 bit version of ChaCha. Also, after a decade, we improve existing complexity [\textit{Z. Shi} et al., ibid. 7839, 337--351 (2013; Zbl 1342.94096)] for a 6-round of 128 bit version of ChaCha by more than 11 million times and produce the first-ever attack on 6.5-round ChaCha128 with time complexity \(2^{123.04}\).
For the entire collection see [Zbl 1493.94003].Key guessing strategies for linear key-schedule algorithms in rectangle attackshttps://zbmath.org/1496.940412022-11-17T18:59:28.764376Z"Dong, Xiaoyang"https://zbmath.org/authors/?q=ai:dong.xiaoyang"Qin, Lingyue"https://zbmath.org/authors/?q=ai:qin.lingyue"Sun, Siwei"https://zbmath.org/authors/?q=ai:sun.siwei"Wang, Xiaoyun"https://zbmath.org/authors/?q=ai:wang.xiaoyunSummary: When generating quartets for the rectangle attacks on ciphers with linear key-schedule, we find the right quartets which may suggest key candidates have to satisfy some nonlinear relations. However, some quartets generated always violate these relations, so that they will never suggest any key candidates. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of invalid quartets. However, guessing a lot of key cells at once may lose the benefit from the early abort technique, which may lead to a higher overall complexity. To get better tradeoff, we build a new rectangle framework on ciphers with linear key-schedule with the purpose of reducing overall complexity or attacking more rounds.
In the tradeoff model, there are many parameters affecting the overall complexity, especially for the choices of the number and positions of key guessing cells before generating quartets. To identify optimal parameters, we build a uniform automatic tool on \texttt{SKINNY} as an example, which includes the optimal rectangle distinguishers for key-recovery phase, the number and positions of key guessing cells before generating quartets, the size of key counters to build that affecting the exhaustive search step, etc. Based on the automatic tool, we identify a 32-round key-recovery attack on \texttt{SKINNY}-128-384 in the related-key setting, which extends the best previous attack by 2 rounds. For other versions with \(n-2n\) or \(n-3n\), we also achieve one more round than before. In addition, using the previous rectangle distinguishers, we achieve better attacks on round-reduced \texttt{ForkSkinny, Deoxys-BC}-384 and \texttt{GIFT}-64. At last, we discuss the conversion of our rectangle framework from related-key setting into single-key setting and give new single-key rectangle attack on 10-round \texttt{Serpent}.
For the entire collection see [Zbl 1493.94003].\textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon}https://zbmath.org/1496.940422022-11-17T18:59:28.764376Z"Espitau, Thomas"https://zbmath.org/authors/?q=ai:espitau.thomas"Fouque, Pierre-Alain"https://zbmath.org/authors/?q=ai:fouque.pierre-alain"Gérard, François"https://zbmath.org/authors/?q=ai:gerard.francois"Rossi, Mélissa"https://zbmath.org/authors/?q=ai:rossi.melissa"Takahashi, Akira"https://zbmath.org/authors/?q=ai:takahashi.akira"Tibouchi, Mehdi"https://zbmath.org/authors/?q=ai:tibouchi.mehdi"Wallet, Alexandre"https://zbmath.org/authors/?q=ai:wallet.alexandre"Yu, Yang"https://zbmath.org/authors/?q=ai:yu.yangSummary: This work describes the \textsc{Mitaka} signature scheme: a new hash-and-sign signature scheme over NTRU lattices which can be seen as a variant of NIST finalist \textsc{Falcon}. It achieves comparable efficiency but is considerably simpler, online/offline, and easier to parallelize and protect against side-channels, thus offering significant advantages from an implementation standpoint. It is also much more versatile in terms of parameter selection.
We obtain this signature scheme by replacing the FFO lattice Gaussian sampler in \textsc{Falcon} by the ``hybrid'' sampler of \textit{L. Ducas} and \textit{T. Prest} [in: Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20--22, 2016. New York, NY: Association for Computing Machinery (ACM). 191--198 (2016; Zbl 1365.65105)], for which we carry out a detailed and corrected security analysis. In principle, such a change can result in a substantial security loss, but we show that this loss can be largely mitigated using new techniques in key generation that allow us to construct much higher quality lattice trapdoors for the hybrid sampler relatively cheaply. This new approach can also be instantiated on a wide variety of base fields, in contrast with \textsc{Falcon}'s restriction to power-of-two cyclotomics.
We also introduce a new lattice Gaussian sampler with the same quality and efficiency, but which is moreover compatible with the integral matrix Gram root technique of \textit{L. Ducas} et al. [Lect. Notes Comput. Sci. 8874, 22--41 (2014; Zbl 1317.94103)], allowing us to avoid floating point arithmetic. This makes it possible to realize the same signature scheme as \textsc{Mitaka} efficiently on platforms with poor support for floating point numbers.
Finally, we describe a provably secure masking of \textsc{Mitaka}. More precisely, we introduce novel gadgets that allow provable masking at any order at much lower cost than previous masking techniques for Gaussian sampling-based signature schemes, for cheap and dependable side-channel protection.
For the entire collection see [Zbl 1493.94003].Generating pairing-friendly elliptic curve parameters using sparse familieshttps://zbmath.org/1496.940432022-11-17T18:59:28.764376Z"Fotiadis, Georgios"https://zbmath.org/authors/?q=ai:fotiadis.georgios"Konstantinou, Elisavet"https://zbmath.org/authors/?q=ai:konstantinou.elisavetLet \(E/\mathbb{F}_q\) be an ordinary elliptic curve with Frobenius trace \(t = q+1 - \# E(\mathbb{F}_q)\) such that \(\# E(\mathbb{F}_q) = hr\) for some large prime \(r\). \(E\) is said to be pairing friendly if \(\log q \approx \log r\) (measured by the \(\rho\) value \(\rho = \log q / \log r\)) and there exists a bilinear pairing \(\hat{e}: G_1 \times G_2 \mapsto G_T\) where \(G_1, G_2 \leq E(\mathbb{F}_q)\), \(G_T \leq \mathbb{F}^\ast_{q^k}\) and \(\# G_1 = \# G_2 = \# G_T = r\) such that the discrete logarithm problem in all three groups is believed to be hard. The integer \(k\), called the embedding degree, should also be sufficiently small that arithmetic in \(G_T\) is efficient.
One method to construct pairing-friendly curves involves parameterizing the values of \(q\), \(t\), \(r\) via polynomial families, triples of polynomials \((q(x),t(x),r(x))\) in \(\mathbb{Q}[x].\) Sparse polynomial families are those satisfying \(4 q(x) - t(x)^2 = g(x) y(x)^2\) with \(g(x)\) quadratic with positive leading coefficient; these are attractive because the resulting curves have large CM discriminants, providing some resistance against certain attacks on the discrete logarithm problem.
In this paper, the authors propose a novel method for constructing sparse polynomial families that combines methods of \textit{H.-S. Lee} and \textit{C.-M. Park} [Lect. Notes Comput. Sci. 5671, 66--77 (2009; Zbl 1250.14017)] and \textit{R. Dryło} [ibid. 7107, 310--319 (2011; Zbl 1291.94075)]. The construction is used to produce new sparse families with \(\rho \leq 2\) and the same embedding degrees as those appearing in the literature, as well as first examples for several other embedding degrees. These families were used to produce numerical examples of pairing-friendly curves with parameters of cryptographically-relevant size, considering recent progress on the tower number field sieve algorithm for solving the discrete logarithm problem in \(G_T\).
Reviewer: Michael J. Jacobson jun. (Calgary)A novel completeness test for leakage models and its application to side channel attacks and responsibly engineered simulatorshttps://zbmath.org/1496.940442022-11-17T18:59:28.764376Z"Gao, Si"https://zbmath.org/authors/?q=ai:gao.si"Oswald, Elisabeth"https://zbmath.org/authors/?q=ai:oswald.elisabethSummary: Today's side channel attack targets are often complex devices in which instructions are processed in parallel and work on 32-bit data words. Consequently, the state that is involved in producing leakage in these modern devices is not only large, but also hard to predict due to various micro-architectural factors that users might not be aware of. On the other hand, security evaluations -- basing on worst case attacks or simulators -- explicitly rely on the underlying state: a potentially incomplete state can easily lead to wrong conclusions.
We put forward a novel notion for the ``completeness'' of an assumed state, together with an efficient statistical test that is based on ``collapsed models''. Our novel test can be used to recover a state that contains multiple 32-bit variables in a grey box setting. We illustrate how our novel test can help to guide side channel attacks and we reveal new attack vectors for existing implementations. We then demonstrate the application of this test in the context of leakage modelling for leakage simulators and confirm that even the most recent leakage simulators do not capture all available leakage of their respective target devices. Our new test enables finding nominal models that capture all available leakage but do not give a helping hand to adversaries. Thereby we make a first step towards leakage simulators that are responsibly engineered.
For the entire collection see [Zbl 1493.94003].Dynamic collusion bounded functional encryption from identity-based encryptionhttps://zbmath.org/1496.940452022-11-17T18:59:28.764376Z"Garg, Rachit"https://zbmath.org/authors/?q=ai:garg.rachit"Goyal, Rishab"https://zbmath.org/authors/?q=ai:goyal.rishab"Lu, George"https://zbmath.org/authors/?q=ai:lu.george-jingfeng"Waters, Brent"https://zbmath.org/authors/?q=ai:waters.brentSummary: Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function \(f\) such that decryption recovers the function evaluation \(f(m)\). Informally, security states that a user with access to function keys \(\mathsf{sk}_{f_1}\), \(\mathsf{sk}_{f_2}, \ldots\) (and so on) can only learn \(f_1(m), f_2(m), \ldots\) (and so on) but nothing more about the message. The system is said to be \(q\)-bounded collusion resistant if the security holds as long as an adversary gets access to at most \(q = q(\lambda)\) function keys. A major drawback of such statically bounded collusion systems is that the collusion bound \(q\) must be declared at setup time and is fixed for the entire lifetime of the system.
We initiate the study of dynamically bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as:
Fine-grained individualized selection. It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience.
Evolving encryption strategies. Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc.
Ease and simplicity of updatability. None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key \(\mathsf{sk}_f\) can be used to decrypt ciphertexts for collusion bound \(q = 2\) as well as \(q = 2^\lambda\).
We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.
For the entire collection see [Zbl 1493.94002].On the security of ECDSA with additive key derivation and presignatureshttps://zbmath.org/1496.940462022-11-17T18:59:28.764376Z"Groth, Jens"https://zbmath.org/authors/?q=ai:groth.jens"Shoup, Victor"https://zbmath.org/authors/?q=ai:shoup.victorSummary: Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed. In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient ``online phase'' of the protocol. Recent works have advocated for both of these variations, sometimes combined together. However, somewhat surprisingly, we are aware of no prior security proof for additive key derivation, let alone for additive key derivation in combination with presignatures.
In this paper, we provide a thorough analysis of these variations, both in isolation and in combination. Our analysis is in the generic group model (GGM). Importantly, we do not modify ECDSA or weaken the standard notion of security in any way. Of independent interest, we also present a version of the GGM that is specific to elliptic curves. This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA. In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported. For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA. We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation. Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).
For the entire collection see [Zbl 1493.94001].Highly efficient OT-based multiplication protocolshttps://zbmath.org/1496.940472022-11-17T18:59:28.764376Z"Haitner, Iftach"https://zbmath.org/authors/?q=ai:haitner.iftach"Makriyannis, Nikolaos"https://zbmath.org/authors/?q=ai:makriyannis.nikolaos"Ranellucci, Samuel"https://zbmath.org/authors/?q=ai:ranellucci.samuel"Tsfadia, Eliad"https://zbmath.org/authors/?q=ai:tsfadia.eliadSummary: We present a new OT-based two-party multiplication protocol that is almost as efficient as Gilboa's semi-honest protocol [\textit{N. Gilboa}, Lect. Notes Comput. Sci. 1666, 116--129 (1999; Zbl 0940.94011)], but has a high-level of security against malicious adversaries without further compilation. The achieved security suffices for many applications, and, assuming DDH, can be cheaply compiled into full security.
For the entire collection see [Zbl 1493.94001].Garbled circuits with sublinear evaluatorhttps://zbmath.org/1496.940482022-11-17T18:59:28.764376Z"Haque, Abida"https://zbmath.org/authors/?q=ai:haque.abida"Heath, David"https://zbmath.org/authors/?q=ai:heath.david-g"Kolesnikov, Vladimir"https://zbmath.org/authors/?q=ai:kolesnikov.vladimir"Lu, Steve"https://zbmath.org/authors/?q=ai:lu.steve"Ostrovsky, Rafail"https://zbmath.org/authors/?q=ai:ostrovsky.rafail"Shah, Akash"https://zbmath.org/authors/?q=ai:shah.akashSummary: A recent line of work, Stacked Garbled Circuit (SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the \(b\) total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor \(\log b\) extra work as compared to standard GC.
We extend the sublinearity of SGC to also include the work performed by the GC evaluator \(E\); thus we achieve a fully sublinear \(E\), which is essential when optimizing for the online phase. We formalize our approach as a garbling scheme called \(\mathsf{GCWise}\): GC WIth Sublinear Evaluator.
We show one attractive and immediate application, Garbled PIR, a primitive that marries GC with Private Information Retrieval. Garbled PIR allows the GC to non-interactively and sublinearly access a privately indexed element from a publicly known database, and then use this element in continued GC evaluation.
For the entire collection see [Zbl 1493.94001].On IND-qCCA security in the ROM and its applications. CPA security is sufficient for TLS 1.3https://zbmath.org/1496.940492022-11-17T18:59:28.764376Z"Huguenin-Dumittan, Loïs"https://zbmath.org/authors/?q=ai:huguenin-dumittan.lois"Vaudenay, Serge"https://zbmath.org/authors/?q=ai:vaudenay.sergeSummary: Bounded IND-CCA security (IND-qCCA) is a notion similar to the traditional IND-CCA security, except the adversary is restricted to a constant number \(q\) of decryption/decapsulation queries. We show in this work that IND-qCCA is easily obtained from any passively secure PKE in the (Q)ROM. That is, simply adding a confirmation hash or computing the key as the hash of the plaintext and ciphertext holds an IND-qCCA KEM. In particular, there is no need for derandomization or re-encryption as in the Fujisaki-Okamoto (FO) transform. This makes the decapsulation process of such IND-qCCA KEM much more efficient than its FO-derived counterpart. In addition, IND-qCCA KEMs could be used in the recently proposed KEMTLS protocol that requires IND-1CCA ephemeral key-exchange mechanisms, or in TLS 1.3. Then, using similar proof techniques, we show that CPA-secure KEMs are sufficient for the TLS 1.3 handshake to be secure, solving an open problem in the ROM. In turn, this implies that the PRF-ODH assumption used to prove the security of TLS 1.3 is not necessary and can be replaced by the CDH assumption in the ROM. We also highlight and briefly discuss several use cases of IND-1CCA KEMs in protocols and ratcheting primitives.
For the entire collection see [Zbl 1493.94003].Multiple coexisting analysis of a fractional-order coupled memristive system and its application in image encryptionhttps://zbmath.org/1496.940502022-11-17T18:59:28.764376Z"Hu, Yongbing"https://zbmath.org/authors/?q=ai:hu.yongbing"Li, Qian"https://zbmath.org/authors/?q=ai:li.qian"Ding, Dawei"https://zbmath.org/authors/?q=ai:ding.dawei"Jiang, Li"https://zbmath.org/authors/?q=ai:jiang.li"Yang, Zongli"https://zbmath.org/authors/?q=ai:yang.zongli"Zhang, Hongwei"https://zbmath.org/authors/?q=ai:zhang.hongwei.1|zhang.hongwei|zhang.hongwei.2"Zhang, Zhixin"https://zbmath.org/authors/?q=ai:zhang.zhixinSummary: In this paper, a fractional-order chaotic circuit with different coupled memristors is established. The dimensionality of the system is reduced by the flux-charge analysis method and the stability of the equilibrium points is analyzed by the fractional-order stability theory. Then, the complex dynamic behaviors, including periodic and chaotic attractors, period doubling bifurcation orbit, coexistence bifurcation, and asymmetric coexisting attractors, are studied by phase diagrams, bifurcation portraits, Lyapunov exponent spectra, and attractive basins. Moreover, the analog circuit of the fractional-order coupled system is constructed and the results validate the correctness of the theoretical analysis. Finally, a novel encryption scheme based on the fractional-order coupled memristive system combined with Josephus traversal and DNA operations is proposed. The simulation results show that this algorithm has a good effect.A trace map attack against special ring-LWE sampleshttps://zbmath.org/1496.940512022-11-17T18:59:28.764376Z"Ikematsu, Yasuhiko"https://zbmath.org/authors/?q=ai:ikematsu.yasuhiko"Nakamura, Satoshi"https://zbmath.org/authors/?q=ai:nakamura.satoshi"Yasuda, Masaya"https://zbmath.org/authors/?q=ai:yasuda.masayaSummary: The learning with errors (LWE) problem is one of the hard problems supporting the security of modern lattice-based cryptography. Ring-LWE is the analog of LWE over the ring of integers of a cyclotomic field, and it has provided efficient cryptosystems. In this paper, we give cryptanalysis against ring-LWE using the trace map over the ring of integers of a cyclotomic field, without using any reduction to other structured lattice problems. Since it maps to a ring of a smaller degree, a trace map attack is expected to be able to decrease the hardness of ring-LWE. However, the trace map does not necessarily transform ring-LWE samples to samples over the smaller ring with a common secret. We give a sufficient and necessary condition on a pair of ring-LWE samples for which the trace map attack is applicable. We call such a pair of samples special. We demonstrate how efficiently the trace map attack can solve ring-LWE when a special pair of samples is given. Specifically, we compare block sizes of the Blockwise Korkine-Zolotarev (BKZ) algorithm required for solving ring-LWE in the trace map attack and a standard attack. Moreover, we discuss the (in)feasibility of the trace map attack for random ring-LWE samples to evaluate how the trace map attack can give a threat against ring-LWE-based cryptosystems on a practical side.
For the entire collection see [Zbl 1484.68016].Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)https://zbmath.org/1496.940522022-11-17T18:59:28.764376Z"Jain, Aayush"https://zbmath.org/authors/?q=ai:jain.aayush"Lin, Huijia"https://zbmath.org/authors/?q=ai:lin.huijia"Sahai, Amit"https://zbmath.org/authors/?q=ai:sahai.amitSummary: In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation \((i\mathcal{O})\). We prove:
Theorem (Informal): Assume sub-exponential security of the following assumptions:
\par i) the Learning Parity with Noise \((\mathsf{LPN})\) assumption over general prime fields \(\mathbb{F}_p\) with polynomially many \(\mathsf{LPN}\) samples and error rate \(1/k^\delta\), where \(k\) is the dimension of the \(\mathsf{LPN}\) secret, and \(\delta >0\) is any constant;
\par ii) the existence of a Boolean Pseudo-Random Generator \((\mathsf{PRG})\) in \(\mathsf{NC}^0\) with stretch \(n^{1+\tau }\), where \(n\) is the length of the \(\mathsf{PRG}\) seed, and \(\tau >0\) is any constant;
\par iii) the Decision Linear \textsf{DLIN} assumption on symmetric bilinear groups of prime order.
Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.
This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of \textit{A. Jain} et al. [Lect. Notes Comput. Sci. 13275, 670--699 (2022; Zbl 07577745)]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption.
Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE), that essentially can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of \(i\mathcal{O}\) while still maintaining reliance only on well-studied assumptions.
For the entire collection see [Zbl 1493.94001].Sine series approximation of the mod function for bootstrapping of approximate HEhttps://zbmath.org/1496.940532022-11-17T18:59:28.764376Z"Jutla, Charanjit S."https://zbmath.org/authors/?q=ai:jutla.charanjit-s"Manohar, Nathan"https://zbmath.org/authors/?q=ai:manohar.nathanSummary: While it is well known that the sawtooth function has a point-wise convergent Fourier series, the rate of convergence is not the best possible for the application of approximating the mod function in small intervals around multiples of the modulus. We show a different sine series, such that the sine series of order \(n\) has error \(O(\epsilon^{2n+1})\) for approximating the mod function in \(\epsilon\)-sized intervals around multiples of the modulus. Moreover, the resulting polynomial, after Taylor series approximation of the sine function, has small coefficients, and the whole polynomial can be computed at a precision that is only slightly larger than \(-(2n+1)\log \epsilon\), the precision of approximation being sought. This polynomial can then be used to approximate the mod function to almost arbitrary precision, and hence allows practical CKKS-HE bootstrapping with arbitrary precision. We validate our approach by an implementation and obtain 100 bit precision bootstrapping as well as improvements over prior work even at lower precision.
For the entire collection see [Zbl 1493.94001].Encryption schemes using anti-orthogonal of type I matriceshttps://zbmath.org/1496.940542022-11-17T18:59:28.764376Z"Kamyun, Nilobol"https://zbmath.org/authors/?q=ai:kamyun.nilobol"Pingyot, Krittiya"https://zbmath.org/authors/?q=ai:pingyot.krittiya"Sompong, Supunnee"https://zbmath.org/authors/?q=ai:sompong.supunneeSummary: Applications of the orthogonal matrix have been applied to many circumstance such as signal processing, image processing, coding theory, cryptology. In this paper, we are not only introduce the new type of matrices, anti-orthogonal and \(H\)-anti-orthogonal of type I matrices but also apply these matrices in cryptology.High-precision bootstrapping for approximate homomorphic encryption by error variance minimizationhttps://zbmath.org/1496.940552022-11-17T18:59:28.764376Z"Lee, Yongwoo"https://zbmath.org/authors/?q=ai:lee.yongwoo"Lee, Joon-Woo"https://zbmath.org/authors/?q=ai:lee.joon-woo"Kim, Young-Sik"https://zbmath.org/authors/?q=ai:kim.young-sik"Kim, Yongjune"https://zbmath.org/authors/?q=ai:kim.yongjune"No, Jong-Seon"https://zbmath.org/authors/?q=ai:no.jong-seon"Kang, HyungChul"https://zbmath.org/authors/?q=ai:kang.hyungchulSummary: The Cheon-Kim-Kim-Song (CKKS) scheme is one of the most promising homomorphic encryption (HE) schemes as it enables privacy-preserving computing over real (or complex) numbers. It is known that bootstrapping is the most challenging part of the CKKS scheme. Further, homomorphic evaluation of modular reduction is the core of the CKKS bootstrapping. As modular reduction is not represented by the addition and multiplication of complex numbers, approximate polynomials for modular reduction should be used. The best-known techniques use a polynomial approximation for trigonometric functions and their composition. However, all the previous methods are based on an indirect approximation, and thus it requires lots of multiplicative depth to achieve high accuracy. This paper proposes a direct polynomial approximation of modular reduction for CKKS bootstrapping, which is optimal in error variance and depth. Further, we propose an efficient algorithm, namely the lazy baby-step giant-step (BSGS) algorithm, to homomorphically evaluate the approximate polynomial, utilizing the lazy relinearization/rescaling technique. The lazy-BSGS reduces the computational complexity by half compared to the ordinary BSGS algorithm. The performance improvement for the CKKS scheme by the proposed algorithm is verified by implementation using HE libraries. The implementation results show that the proposed method has a multiplicative depth of 10 for modular reduction to achieve the state-of-the-art accuracy, while the previous methods have depths of 11 to 12. Moreover, we achieve higher accuracy within a small multiplicative depth, for example, 93-bit within multiplicative depth 11.
For the entire collection see [Zbl 1493.94001].(Short paper) Analysis of a strong fault attack on static/ephemeral CSIDHhttps://zbmath.org/1496.940562022-11-17T18:59:28.764376Z"LeGrow, Jason T."https://zbmath.org/authors/?q=ai:legrow.jason-t"Hutchinson, Aaron"https://zbmath.org/authors/?q=ai:hutchinson.aaronSummary: CSIDH is an isogeny-based post-quantum key establishment protocol proposed in [\textit{W. Castryck} et al., Lect. Notes Comput. Sci. 11274, 395--427 (2018; Zbl 1407.81084)]. In this work we analyze attacking implementations of CSIDH which use dummy isogeny operations using fault injections from a mathematical perspective. We detail an attack (implicit in prior works on implementations of CSIDH) by which a static private key can be learned (up to sign) by the attacker with certainty using \(\sum \lceil \log_2(b_i) + 1 \rceil\) faults using a binary search approach, where \(b\) is the bound vector defining the keyspace. A natural idea for a countermeasure to this attack is to randomly mix the real degree \(\ell_j\) isogenies together with the dummy ones, so that binary search becomes ineffective. In this work we evaluate the efficacy of this idea as a fault attack countermeasure; in particular, we give bounds (as a function of the bound vector entries) on the number of fault injections (of a particular relatively strong, hypothetical type) required for an attacker to have a given success probability for guessing an unknown key, and present the results of simulated attacks on keys sampled from 6 keyspaces found in the literature. We find that the number of faults required to reach any constant success probability in guessing a static key is quadratic in the bound vector entries, rather than logarithmic as in the ``real-then-dummy'' setting -- concretely, the number of faults required increases from a few hundred to tens of thousands. Broadly, this behaviour is reflected in our simulations.
For the entire collection see [Zbl 1484.68016].One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard modelhttps://zbmath.org/1496.940572022-11-17T18:59:28.764376Z"Libert, Benoît"https://zbmath.org/authors/?q=ai:libert.benoit"Khoa Nguyen"https://zbmath.org/authors/?q=ai:khoa-nguyen."Peters, Thomas"https://zbmath.org/authors/?q=ai:peters.thomas-j|peters.thomas-d|peters.thomas-a"Yung, Moti"https://zbmath.org/authors/?q=ai:yung.motiSummary: The standard model security of the Fiat-Shamir transform has been an active research area for many years. In breakthrough results, \textit{R. Canetti} et al. [in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 1082--1090 (2019; Zbl 1434.94060)] and \textit{C. Peikert} and \textit{S. Shiehian} [Lect. Notes Comput. Sci. 11692, 89--114 (2019; Zbl 1456.94106)] showed that, under the Learning-With-Errors \textsf{(LWE)} assumption, it provides soundness by applying correlation-intractable (CI) hash functions to so-called trapdoor \(\varSigma\)-protocols. In order to be compatible with CI hash functions based on standard \textsf{LWE} assumptions with polynomial approximation factors, all known such protocols have been obtained via parallel repetitions of a basic protocol with binary challenges. In this paper, we consider languages related to Paillier's composite residuosity assumption \((\mathsf{DCR})\) for which we give the first trapdoor \(\varSigma\)-protocols providing soundness in one shot, via exponentially large challenge spaces. This improvement is analogous to the one enabled by Schnorr over the original Fiat-Shamir protocol in the random oracle model. Using the correlation-intractable hash function paradigm, we then obtain simulation-sound NIZK arguments showing that an element of \(\mathbb{Z}_{N^2}^\ast\) is a composite residue, which opens the door to space-efficient applications in the standard model. As a concrete example, we build logarithmic-size ring signatures (assuming a common reference string) with the shortest signature length among schemes based on standard assumptions in the standard model. We prove security under the \(\mathsf{DCR}\) and \textsf{LWE} assumptions, while keeping the signature size comparable with that of random-oracle-based schemes.
For the entire collection see [Zbl 1493.94002].AMBTC based high payload data hiding with modulo-2 operation and Hamming codehttps://zbmath.org/1496.940582022-11-17T18:59:28.764376Z"Li, Li"https://zbmath.org/authors/?q=ai:li.li.25"He, Min"https://zbmath.org/authors/?q=ai:he.min"Zhang, Shanqing"https://zbmath.org/authors/?q=ai:zhang.shanqing"Luo, Ting"https://zbmath.org/authors/?q=ai:luo.ting"Chang, Chin-Chen"https://zbmath.org/authors/?q=ai:chang.chin-chenSummary: An efficient data hiding method with modulo-2 operation and Hamming code (3, 2) based on absolute moment block truncation coding (AMBTC) is proposed. In order to obtain good data hiding performance, different textures are assigned to different embedding strategies. The AMBTC compressed codes are divided into smooth and complex blocks according to texture. In the smooth block, the secret data and the four most significant bits plane of the two quantization levels are calculated using modulo-2 operation to replace the bitmap in order to improve the security of data transmission. Moreover, Hamming code (3, 2) is used to embed the two additional secret bits in the three significant bits planes of the two quantization levels. In the complex block, one secret bit is embedded by swapping the order of two quantization levels and flipping the bitmap. Experimental results show that the proposed method achieves higher capacity than the existing data hiding methods and maintains good visual quality.Double image encryption algorithm based on neural network and chaoshttps://zbmath.org/1496.940592022-11-17T18:59:28.764376Z"Man, Zhenlong"https://zbmath.org/authors/?q=ai:man.zhenlong"Li, Jinqing"https://zbmath.org/authors/?q=ai:li.jinqing"Di, Xiaoqiang"https://zbmath.org/authors/?q=ai:di.xiaoqiang"Sheng, Yaohui"https://zbmath.org/authors/?q=ai:sheng.yaohui"Liu, Zefei"https://zbmath.org/authors/?q=ai:liu.zefeiSummary: To realize the secure transmission of double images, this paper proposes a double image encryption algorithm based on convolutional neural network (CNN) and dynamic adaptive diffusion. This scheme is different from the existing double image encryption technology. According to the characteristics of digital image, we design a dual-channel (digital channel / optical channel) encryption method, which not only ensures the security of double image, but also improves the encryption efficiency and reduces the possibility of being attacked. First, a chaotic map is used to control the initial values of the 5D conservative chaotic system to enhance the security of the key. Secondary, in order to effectively resist known-plaintext attack and chosen-plaintext attack, we employ a chaotic sequence as convolution kernel of convolution neural network to generate plaintext related chaotic pointer to control the scrambling operation of two images. On this basis, a novel image fusion method is designed, which splits and fuses two images into two different parts according to the amount of information contained. In addition, a dual-channel image encryption scheme, optical encryption channel and digital encryption channel, is designed for the two parts after fusion. The former has better parallelism and higher encryption efficiency, while the latter has higher computational complexity and better encryption reliability. Especially in the digital encryption channel, a new dynamic adaptive diffusion method is designed, which is more flexible and secure than the existing encryption algorithm. Finally, numerical simulation and experimental analysis verify the feasibility and effectiveness of the scheme.FFT program generation for ring LWE-based cryptographyhttps://zbmath.org/1496.940602022-11-17T18:59:28.764376Z"Masuda, Masahiro"https://zbmath.org/authors/?q=ai:masuda.masahiro"Kameyama, Yukiyoshi"https://zbmath.org/authors/?q=ai:kameyama.yukiyoshiSummary: Fast Fourier Transform (FFT) enables an efficient implementation of polynomial multiplication, which is at the core of any cryptographic constructions based on the hardness of the ring learning with errors (RLWE) problem. Existing implementations of FFT for RLWE-based cryptography rely on hand-written assembly code for performance, making it difficult to understand, maintain, and extend for new architectures.
We present a novel framework to implement FFT for RLWE-based cryptography, based on a principled program-generation approach. We start with a high-level, abstract definition of an FFT program, and generate low-level code by interpreting high-level primitives and delegating low-level details to an architecture-specific module. Since low-level details concerning modular arithmetic and vectorization are separated from high-level logic, we can easily generate both AVX2- and AVX512-optimized low-level code from the same high-level description of the FFT program. Our generated code is highly competitive compared to expert-written assembly code: For AVX2 (and AVX512, resp) it runs 1.13x (and 1.39x, resp) faster than the AVX2-optimized assembly implementation in the NewHope key-exchange protocol.
For the entire collection see [Zbl 1484.68016].Multi-designated receiver signed public key encryptionhttps://zbmath.org/1496.940612022-11-17T18:59:28.764376Z"Maurer, Ueli"https://zbmath.org/authors/?q=ai:maurer.ueli-m"Portmann, Christopher"https://zbmath.org/authors/?q=ai:portmann.christopher"Rito, Guilherme"https://zbmath.org/authors/?q=ai:rito.guilhermeSummary: This paper introduces a new type of public-key encryption scheme, called Multi-Designated Receiver Signed Public Key Encryption (MDRS-PKE), which allows a sender to select a set of designated receivers and both encrypt and sign a message that only these receivers will be able to read and authenticate (confidentiality and authenticity). An MDRS-PKE scheme provides several additional security properties which allow for a fundamentally new type of communication not considered before. Namely, it satisfies consistency -- a dishonest sender cannot make different receivers receive different messages -- off-the-record -- a dishonest receiver cannot convince a third party of what message was sent (e.g., by selling their secret key), because dishonest receivers have the ability to forge signatures -- and anonymity -- parties that are not in the set of designated receivers cannot identify who the sender and designated receivers are.
We give a construction of an MDRS-PKE scheme from standard assumptions. At the core of our construction lies yet another new type of public-key encryption scheme, which is of independent interest: Public Key Encryption for Broadcast (PKEBC) which provides all the security guarantees of MDRS-PKE schemes, except authenticity.
We note that MDRS-PKE schemes give strictly more guarantees than Multi-Designated Verifier Signature (MDVS) schemes with privacy of identities. This in particular means that our MDRS-PKE construction yields the first MDVS scheme with privacy of identities from standard assumptions. The only prior construction of such schemes was based on Verifiable Functional Encryption for general circuits.
For the entire collection see [Zbl 1493.94002].Approximate divisor multiples -- factoring with only a third of the secret CRT-exponentshttps://zbmath.org/1496.940622022-11-17T18:59:28.764376Z"May, Alexander"https://zbmath.org/authors/?q=ai:may.alexander"Nowakowski, Julian"https://zbmath.org/authors/?q=ai:nowakowski.julian"Sarkar, Santanu"https://zbmath.org/authors/?q=ai:sarkar.santanuSummary: We address Partial Key Exposure attacks on CRT-RSA on secret exponents \(d_p\), \(d_q\) with small public exponent \(e\). For constant \(e\) it is known that the knowledge of half of the bits of one of \(d_p\), \(d_q\) suffices to factor the RSA modulus \(N\) by Coppersmith's famous factoring with a hint result [\textit{D. Coppersmith}, Lect. Notes Comput. Sci. 1070, 178--189 (1996; Zbl 1304.94043)]. We extend this setting to non-constant \(e\). Somewhat surprisingly, our attack shows that RSA with \(e\) of size \(N^{\frac{1}{12}}\) is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both \(d_p\), \(d_q\) suffices to factor \(N\) in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB).
Let \(ed_p = 1 + k(p-1)\) and \(ed_q = 1 + \ell (q-1)\). On the technical side, we find the factorization of \(N\) in a novel two-step approach. In a first step we recover \(k\) and \(\ell\) in polynomial time, in the MSB case completely elementary and in the LSB case using Coppersmith's lattice-based method. We then obtain the prime factorization of \(N\) by computing the root of a univariate polynomial modulo \(kp\) for our known \(k\). This can be seen as an extension of Howgrave-Graham's approximate divisor algorithm [\textit{N. Howgrave-Graham}, ibid. 2146, 51--66 (2001; Zbl 1006.94528)] to the case of approximate divisor multiples for some known multiple \(k\) of an unknown divisor \(p\) of \(N\). The point of approximate divisor multiples is that the unknown that is recoverable in polynomial time grows linearly with the size of the multiple \(k\).
Our resulting Partial Key Exposure attack with known MSBs is completely rigorous, whereas in the LSB case we rely on a standard Coppersmith-type heuristic. We experimentally verify our heuristic, thereby showing that in practice we reach our asymptotic bounds already using small lattice dimensions. Thus, our attack is highly efficient.
For the entire collection see [Zbl 1493.94003].Anamorphic encryption: private communication against a dictatorhttps://zbmath.org/1496.940632022-11-17T18:59:28.764376Z"Persiano, Giuseppe"https://zbmath.org/authors/?q=ai:persiano.giuseppe"Duong Hieu Phan"https://zbmath.org/authors/?q=ai:duong-hieu-phan."Yung, Moti"https://zbmath.org/authors/?q=ai:yung.motiSummary: Cryptosystems have been developed over the years under the typical prevalent setting which assumes that the receiver's key is kept secure from the adversary, and that the choice of the message to be sent is freely performed by the sender and is kept secure from the adversary as well. Under these fundamental and basic operational assumptions, modern Cryptography has flourished over the last half a century or so, with amazing achievements: New systems (including public-key Cryptography), beautiful and useful models (including security definitions such as semantic security), and new primitives (such as zero-knowledge proofs) have been developed. Furthermore, these fundamental achievements have been translated into actual working systems, and span many of the daily human activities over the Internet.
However, in recent years, there is an overgrowing pressure from many governments to allow the government itself access to keys and messages of encryption systems (under various names: escrow encryption, emergency access, communication decency acts, etc.). Numerous non-direct arguments against such policies have been raised, such as ``the bad guys can utilize other encryption system'' so all other cryptosystems have to be declared illegal, or that ``allowing the government access is an ill-advised policy since it creates a natural weak systems security point, which may attract others (to masquerade as the government).'' It has remained a fundamental open issue, though, to show directly that the above mentioned efforts by a government (called here ``a dictator'' for brevity) which mandate breaking of the basic operational assumption (and disallowing other cryptosystems), is, in fact, a futile exercise. This is a direct technical point which needs to be made and has not been made to date.
In this work, as a technical demonstration of the futility of the dictator's demands, we invent the notion of ``Anamorphic Encryption'' which shows that even if the dictator gets the keys and the messages used in the system (before anything is sent) and no other system is allowed, there is a covert way within the context of well established public-key cryptosystems for an entity to immediately (with no latency) send piggybacked secure messages which are, in spite of the stringent dictator conditions, hidden from the dictator itself! We feel that this may be an important direct technical argument against the nature of governments' attempts to police the use of strong cryptographic systems, and we hope to stimulate further works in this direction.
For the entire collection see [Zbl 1493.94002].A correlation attack on full SNOW-V and SNOW-Vihttps://zbmath.org/1496.940642022-11-17T18:59:28.764376Z"Shi, Zhen"https://zbmath.org/authors/?q=ai:shi.zhen"Jin, Chenhui"https://zbmath.org/authors/?q=ai:jin.chenhui"Zhang, Jiyan"https://zbmath.org/authors/?q=ai:zhang.jiyan"Cui, Ting"https://zbmath.org/authors/?q=ai:cui.ting"Ding, Lin"https://zbmath.org/authors/?q=ai:ding.lin"Jin, Yu"https://zbmath.org/authors/?q=ai:jin.yuSummary: In this paper, a method for searching correlations between the binary stream of Linear Feedback Shift Register (LFSR) and the keystream of SNOW-V and SNOW-Vi is presented based on the technique of approximation to composite functions. With the aid of the linear relationship between the four taps of LFSR input into Finite State Machine (FSM) at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a series of linear approximation trails with high correlation. By exhausting the intermediate masks, we find a binary linear approximation with a correlation \(-2^{-47.76}\). Using such approximation, we propose a correlation attack on SNOW-V with an expected time complexity \(2^{246.53}\), a memory complexity \(2^{238.77}\) and \(2^{237.5}\) keystream words generated by the same key and Initial Vector (IV). For SNOW-Vi, we provide a binary linear approximation with the same correlation and mount a correlation attack with the same complexity as that of SNOW-V. To the best of our knowledge, this is the first known attack on full SNOW-V and SNOW-Vi, which is better than the exhaustive key search with respect to time complexity. The results indicate that neither SNOW-V nor SNOW-Vi can guarantee the 256-bit security level if we ignore the design constraint that the maximum length of keystream for a single pair of key and IV is less than \(2^{64}\).
For the entire collection see [Zbl 1493.94003].A greater \texttt{GIFT}: strengthening \texttt{GIFT} against statistical cryptanalysishttps://zbmath.org/1496.940652022-11-17T18:59:28.764376Z"Sun, Ling"https://zbmath.org/authors/?q=ai:sun.ling"Preneel, Bart"https://zbmath.org/authors/?q=ai:preneel.bart"Wang, Wei"https://zbmath.org/authors/?q=ai:wang.wei.23"Wang, Meiqin"https://zbmath.org/authors/?q=ai:wang.meiqinSummary: \texttt{GIFT}-64 is a 64-bit block cipher with a 128-bit key that is more lightweight than \texttt{PRESENT}. This paper provides a detailed analysis of \texttt{GIFT}-64 against differential and linear attacks. Our work complements automatic search methods for the best differential and linear characteristics with a careful manual analysis. This hybrid approach leads to new insights. In the differential setting, we theoretically explain the existence of differential characteristics with two active S-boxes per round and derive some novel properties of these characteristics. Furthermore, we prove that all optimal differential characteristics of \texttt{GIFT}-64 covering more than seven rounds must activate two S-boxes per round. We can construct all optimal characteristics by hand. In parallel to the work in the differential setting, we conduct a similar analysis in the linear setting. However, unlike the clear view in differential setting, the optimal linear characteristics of \texttt{GIFT}-64 must have at least one round activating only one S-box. Moreover, with the assistance of automatic searching methods, we identify 24 \texttt{GIFT}-64 variants achieving better resistance against differential attack while maintaining a similar security level against a linear attack. Since the new variants strengthen \texttt{GIFT}-64 against statistical cryptanalysis, we claim that the number of rounds could be reduced from 28 to 26 for the variants. This observation enables us to create a cipher with lower energy consumption than \texttt{GIFT}-64. Similarly to the case in \texttt{GIFT}-64, we do not claim any related-key security for the round-reduced variant as this is not relevant for most applications.
For the entire collection see [Zbl 1493.94003].Construction of one-way hash functions with increased key space using adaptive chaotic mapshttps://zbmath.org/1496.940662022-11-17T18:59:28.764376Z"Tutueva, Aleksandra V."https://zbmath.org/authors/?q=ai:tutueva.aleksandra-v"Karimov, Artur I."https://zbmath.org/authors/?q=ai:karimov.artur-i"Moysis, Lazaros"https://zbmath.org/authors/?q=ai:moysis.lazaros"Volos, Christos"https://zbmath.org/authors/?q=ai:volos.christos-k"Butusov, Denis N."https://zbmath.org/authors/?q=ai:butusov.denis-nSummary: Chaotic hash functions are a prospective branch of modern cryptography. Being compared with traditional hashing algorithms, an approach based on deterministic chaos allows achieving diffusion and confusion with less computational costs. Most of the recently proposed chaotic hash functions use piecewise maps. Cryptosystems based on such maps are not vulnerable to attack by the reconstruction of phase space but their key spaces depend on maps parameters and therefore can be insufficient. In this paper, we propose an approach for the construction of piecewise hash functions from adaptive chaotic maps. The idea is to match different values of the adaptive coefficient to several sub-domains of the chaotic map. Thus, the adaptive coefficient values are part of the hash function key. Therefore, an increase in the sub-functions number potentially enhances the cryptographic strength of the algorithm. Thus, hash functions based on novel adaptive maps have larger key space compared to conventional piecewise maps. We explicitly show that the proposed hash generation technique allows obtaining digests with the required statistical properties. Moreover, we run a collision test to prove that the collision probability is small. The obtained results can be useful in chaos-based cryptography as well for the various simulations of real processes and phenomena with chaotic behavior, in computer graphics and multimedia.A fast and simple partially oblivious PRF, with applicationshttps://zbmath.org/1496.940672022-11-17T18:59:28.764376Z"Tyagi, Nirvan"https://zbmath.org/authors/?q=ai:tyagi.nirvan"Celi, Sofía"https://zbmath.org/authors/?q=ai:celi.sofia"Ristenpart, Thomas"https://zbmath.org/authors/?q=ai:ristenpart.thomas"Sullivan, Nick"https://zbmath.org/authors/?q=ai:sullivan.nick"Tessaro, Stefano"https://zbmath.org/authors/?q=ai:tessaro.stefano"Wood, Christopher A."https://zbmath.org/authors/?q=ai:wood.christopher-aSummary: We build the first construction of a partially oblivious pseudorandom function (POPRF) that does not rely on bilinear pairings. Our construction can be viewed as combining elements of the 2HashDH OPRF of \textit{S. Jarecki} et al. [Lect. Notes Comput. Sci. 8874, 233--253 (2014; Zbl 1311.94106)] with the Dodis-Yampolskiy PRF [\textit{Y. Dodis} and \textit{A. Yampolskiy}, Lect. Notes Comput. Sci. 3386, 416--431 (2005; Zbl 1081.94521)]. We analyze our POPRF's security in the random oracle model via reduction to a new one-more gap strong Diffie-Hellman inversion assumption. The most significant technical challenge is establishing confidence in the new assumption, which requires new proof techniques that enable us to show that its hardness is implied by the \(q\)-DL assumption in the algebraic group model.
Our new construction is as fast as the current, standards-track OPRF 2HashDH protocol, yet provides a new degree of flexibility useful in a variety of applications. We show how POPRFs can be used to prevent token hoarding attacks against Privacy Pass, reduce key management complexity in the OPAQUE password authenticated key exchange protocol, and ensure stronger security for password breach alerting services.
For the entire collection see [Zbl 1493.94002].A zero-knowledge identification protocol in the ring of Gaussian integershttps://zbmath.org/1496.940682022-11-17T18:59:28.764376Z"Valluri, Maheswara Rao"https://zbmath.org/authors/?q=ai:valluri.maheswara-raoSummary: In this paper, a zero-knowledge identification protocol is proposed by extending from the rational of natural integers \(\mathbb{Z} \), to the ring of Gaussian integers \(\mathbb{Z} [i]\). Its security relies on the integer factorization problem and extraction of square roots of a Gaussian integer over \(\mathbb{Z}_n\). Properties, space complexity and time complexity of the proposed protocol are also discussed.Optimal broadcast encryption and CP-ABE from evasive lattice assumptionshttps://zbmath.org/1496.940692022-11-17T18:59:28.764376Z"Wee, Hoeteck"https://zbmath.org/authors/?q=ai:wee.hoeteckSummary: We present a new, simple candidate broadcast encryption scheme for \(N\) users with parameter size \textsf{poly}\((\log N)\). We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.
For the entire collection see [Zbl 1493.94002].Orientations and the supersingular endomorphism ring problemhttps://zbmath.org/1496.940702022-11-17T18:59:28.764376Z"Wesolowski, Benjamin"https://zbmath.org/authors/?q=ai:wesolowski.benjaminSummary: We study two important families of problems in isogeny-based cryptography and how they relate to each other: computing the endomorphism ring of supersingular elliptic curves, and inverting the action of class groups on oriented supersingular curves. We prove that these two families of problems are closely related through polynomial-time reductions, assuming the generalised Riemann hypothesis.
We identify two classes of essentially equivalent problems. The first class corresponds to the problem of computing the endomorphism ring of oriented curves. The security of a large family of cryptosystems (such as CSIDH) reduces to (and sometimes from) this class, for which there are heuristic quantum algorithms running in subexponential time. The second class corresponds to computing the endomorphism ring of orientable curves. The security of essentially all isogeny-based cryptosystems reduces to (and sometimes from) this second class, for which the best known algorithms are still exponential.
Some of our reductions not only generalise, but also strengthen previously known results. For instance, it was known that in the particular case of curves defined over \(\mathcal{F}_p\), the security of CSIDH reduces to the endomorphism ring problem in subexponential time. Our reductions imply that the security of CSIDH is actually equivalent to the endomorphism ring problem, under polynomial time reductions (circumventing arguments that proved such reductions unlikely).
For the entire collection see [Zbl 1493.94003].A complete characterization of game-theoretically fair, multi-party coin tosshttps://zbmath.org/1496.940712022-11-17T18:59:28.764376Z"Wu, Ke"https://zbmath.org/authors/?q=ai:wu.ke"Asharov, Gilad"https://zbmath.org/authors/?q=ai:asharov.gilad"Shi, Elaine"https://zbmath.org/authors/?q=ai:shi.elaineSummary: Cleve's celebrated lower bound [\textit{R. Cleve}, ``Limits on the security of coin flips when half the processors are faulty'', in: STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, May 28--30, 1986. Berkeley California, USA: ACM. 364--369 (1986), \url{https://dl.acm.org/doi/10.1145/12130.12168}] showed that a de facto strong fairness notion is impossible in 2-party coin toss, i.e., the corrupt party always has a strategy of biasing the honest party's outcome by a noticeable amount. Nonetheless, Blum's famous coin-tossing protocol [\textit{M. Blum}, SIGACT News 15, No. 1, 23--27 (1983; Zbl 0501.68011)] achieves a strictly weaker ``game-theoretic'' notion of fairness -- specifically, it is a 2-party coin toss protocol in which neither party can bias the outcome towards its own preference; and thus the honest protocol forms a Nash equilibrium in which neither party would want to deviate. Surprisingly, an \(n\)-party analog of Blum's famous coin toss protocol was not studied till recently. The work by \textit{K.-M. Chung} et al. [Lect. Notes Comput. Sci. 11239, 563--596 (2018; Zbl 1443.94051)] was the first to explore the feasibility of game-theoretically fair \(n\)-party coin toss in the presence of corrupt majority. We may assume that each party has a publicly stated preference for either the bit 0 or 1, and if the outcome agrees with the party's preference, it obtains utility 1; else it obtains nothing.
A natural game-theoretic formulation is to require that the honest protocol form a coalition-resistant Nash equilibrium, i.e., no coalition should have incentive to deviate from the honest behavior. Chung et al. [loc. cit.] phrased this game-theoretic notion as ``cooperative-strategy-proofness'' or ``CSP-fairness'' for short. Unfortunately, Chung et al. showed that under \((n-1)\)-sized coalitions, it is impossible to design such a CSP-fair coin toss protocol, unless all parties except one prefer the same bit.
In this paper, we show that the impossibility of Chung et al. is in fact not as broad as it may seem. When coalitions are majority but not \(n-1\) in size, we can indeed get feasibility results in some meaningful parameter regimes. We give a complete characterization of the regime in which CSP-fair coin toss is possible, by providing a matching upper- and lower-bound. Our complete characterization theorem also shows that the mathematical structure of game-theoretic fairness is starkly different from the de facto strong fairness notion in the multi-party computation literature.
For the entire collection see [Zbl 1493.94001].Cryptanalysis of candidate obfuscators for affine determinant programshttps://zbmath.org/1496.940722022-11-17T18:59:28.764376Z"Yao, Li"https://zbmath.org/authors/?q=ai:yao.li"Chen, Yilei"https://zbmath.org/authors/?q=ai:chen.yilei"Yu, Yu"https://zbmath.org/authors/?q=ai:yu.yu\textit{J. Bartusek} et al. [``Affine determinant programs: a framework for obfuscation and witness encryption'', Preprint, \url{https://eprint.iacr.org/2020/889.pdf}] proposed a candidate indistinguishability obfuscator for affine determinant programs (ADPs). The candidate is special since it directly applies specific randomization techniques to the underlying ADP, without relying on the hardness of traditional cryptographic assumptions like discrete-log or learning with errors. It is relatively efficient compared to the rest of the indistinguishability obfuscator candidates. However, the obfuscation scheme requires further cryptanalysis since it was not known to be based on any well-formed mathematical assumptions. In this paper, the authors show cryptanalytic attacks on the indistinguishability obfuscator candidate provided by Bartusek et al. [loc. cit.]. Their attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper, they discuss plausible countermeasures to defend against attacks.
For the entire collection see [Zbl 1493.94001].
Reviewer: Janaka Alawatugoda (Peradeniya)(Short paper) Simple matrix signature schemehttps://zbmath.org/1496.940732022-11-17T18:59:28.764376Z"Yin, Changze"https://zbmath.org/authors/?q=ai:yin.changze"Wang, Yacheng"https://zbmath.org/authors/?q=ai:wang.yacheng"Takagi, Tsuyoshi"https://zbmath.org/authors/?q=ai:takagi.tsuyoshiSummary: Multivariate cryptography plays an important role in post-quantum cryptography. Many signature schemes, such as Rainbow remain secure despite the development of several attempted attack algorithms. However, most multivariate signature schemes use relatively large public keys compared with those of other post-quantum signature schemes. In this paper, we present an approach for constructing a multivariate signature scheme based on matrix multiplication. At the same security level, our proposed signature scheme has smaller public key and signature sizes compared with the Rainbow signature scheme.
For the entire collection see [Zbl 1484.68016].Efficient schemes for committing authenticated encryptionhttps://zbmath.org/1496.940742022-11-17T18:59:28.764376Z"Bellare, Mihir"https://zbmath.org/authors/?q=ai:bellare.mihir"Viet Tung Hoang"https://zbmath.org/authors/?q=ai:viet-tung-hoang.Summary: This paper provides efficient authenticated-encryption (AE) schemes in which a ciphertext is a commitment to the key. These are extended, at minimal additional cost, to schemes where the ciphertext is a commitment to all encryption inputs, meaning key, nonce, associated data and message. Our primary schemes are modifications of GCM (for basic, unique-nonce AE security) and AES-GCM-SIV (for misuse-resistant AE security) and add both forms of commitment without any increase in ciphertext size. We also give more generic, but somewhat more costly, solutions.
For the entire collection see [Zbl 1493.94002].On the multi-user security of short Schnorr signatures with preprocessinghttps://zbmath.org/1496.940752022-11-17T18:59:28.764376Z"Blocki, Jeremiah"https://zbmath.org/authors/?q=ai:blocki.jeremiah"Lee, Seunghoon"https://zbmath.org/authors/?q=ai:lee.seunghoonSummary: The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., 4k-bit signatures for \(k\) bits of security. A Schnorr signature \(\sigma\) over a group of size \(p\approx 2^{2k}\) consists of a tuple \((s,e)\), where \(e \in \{0,1\}^{2k}\) is a hash output and \(s\in \mathbb{Z}_p\) must be computed using the secret key. While the hash output \(e\) requires \(2k\) bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security.
In this paper, we prove that short Schnorr signatures of length \(3k\) bits provide \(k\) bits of multi-user security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multi-user security of key-prefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length \(3k + \log S + \log N\) bits. Here, \(N\) denotes the number of users and \(S\) denotes the size of the hint generated by our preprocessing attacker, e.g., if \(S=2^{k/2}\), then we would obtain secure 3.75k-bit signatures for groups of up to \(N \le 2^{k/4}\) users.
Our techniques easily generalize to several other Fiat-Shamir-based signature schemes, allowing us to establish analogous results for Chaum-Pedersen signatures and Katz-Wang signatures. As a building block, we also analyze the 1-out-of-\(N\) discrete-log problem in the generic group model, with and without preprocessing.
For the entire collection see [Zbl 1493.94002].Lightweight, maliciously secure verifiable function secret sharinghttps://zbmath.org/1496.940762022-11-17T18:59:28.764376Z"de Castro, Leo"https://zbmath.org/authors/?q=ai:de-castro.leo"Polychroniadou, Anitgoni"https://zbmath.org/authors/?q=ai:polychroniadou.anitgoniSummary: In this work, we present a lightweight construction of verifiable two-party function secret sharing (FSS) for point functions and multi-point functions. Our verifiability method is lightweight in two ways. Firstly, it is concretely efficient, making use of only symmetric key operations and no public key or MPC techniques are involved. Our performance is comparable with the state-of-the-art non-verifiable DPF constructions, and we outperform all prior DPF verification techniques in both computation and communication complexity, which we demonstrate with an implementation of our scheme. Secondly, our verification procedure is essentially unconstrained. It will verify that distributed point function (DPF) shares correspond to some point function irrespective of the output group size, the structure of the DPF output, or the set of points on which the DPF must be evaluated. This is in stark contrast with prior works, which depend on at least one and often all three of these constraints. In addition, our construction is the first DPF verification protocol that can verify general DPFs while remaining secure even if one server is malicious. Prior work on maliciously secure DPF verification could only verify DPFs where the non-zero output is binary and the output space is a large field.
As an additional feature, our verification procedure can be batched so that verifying a polynomial number of DPF shares requires the exact same amount of communication as verifying one pair of DPF shares. We combine this packed DPF verification with a novel method for packing DPFs into shares of a multi-point function where the evaluation time, verification time, and verification communication are independent of the number of non-zero points in the function.
An immediate corollary of our results are two-server protocols for PIR and PSI that remain secure when any one of the three parties is malicious (either the client or one of the servers).
For the entire collection see [Zbl 1493.94001].Authentication in the bounded storage modelhttps://zbmath.org/1496.940772022-11-17T18:59:28.764376Z"Dodis, Yevgeniy"https://zbmath.org/authors/?q=ai:dodis.yevgeniy"Quach, Willy"https://zbmath.org/authors/?q=ai:quach.willy"Wichs, Daniel"https://zbmath.org/authors/?q=ai:wichs.danielSummary: We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size \(n\). The adversary also operates as a streaming algorithm, but has a much larger memory size \(m \gg n\). The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In this work, we construct message authentication and signatures in the BSM.
First, we consider the symmetric-key setting, where Alice and Bob share a small secret key. Alice can authenticate arbitrarily many messages to Bob by streaming long authentication tags of size \(k \gg m\), while ensuring that the tags can be generated and verified using only \(n\) bits of memory. We show a solution using local extractors, which allows for up to exponentially large adversarial memory \(m = 2^{O(n)}\), and has tags of size \(k= O(m)\).
Second, we consider the same setting as above, but now additionally require each individual tag to be small, of size \(k \le n\). We show a solution is still possible when the adversary's memory is \(m = O(n^2)\), which is optimal. Our solution relies on a space lower bound for leaning parities.
Third, we consider the public-key signature setting. A signer Alice initially streams a long verification key over an authentic channel, while only keeping a short signing key in her memory. A verifier Bob receives the streamed verification key and generates a short verification digest that he keeps in his memory. Later, Alice can sign arbitrarily many messages using her signing key by streaming large signatures to Bob, who can verify them using his verification digest. We show a solution for \(m= O(n^2)\), which we show to be optimal. Our solution relies on a novel entropy lemma, of independent interest. We show that, if a sequence of blocks has sufficiently high min-entropy, then a large fraction of individual blocks must have high min-entropy. Naive versions of this lemma are false, but we show how to patch it to make it hold.
For the entire collection see [Zbl 1493.94003].Practical non-interactive publicly verifiable secret sharing with thousands of partieshttps://zbmath.org/1496.940782022-11-17T18:59:28.764376Z"Gentry, Craig"https://zbmath.org/authors/?q=ai:gentry.craig"Halevi, Shai"https://zbmath.org/authors/?q=ai:halevi.shai"Lyubashevsky, Vadim"https://zbmath.org/authors/?q=ai:lyubashevsky.vadimSummary: Non-interactive publicly verifiable secret sharing (PVSS) schemes enables (re-)sharing of secrets in a decentralized setting in the presence of malicious parties. A recently proposed application of PVSS schemes is to enable permissionless proof-of-stake blockchains to ``keep a secret'' via a sequence of committees that share that secret. These committees can use the secret to produce signatures on the blockchain's behalf, or to disclose hidden data conditioned on consensus that some event has occurred. That application needs very large committees with thousands of parties, so the PVSS scheme in use must be efficient enough to support such large committees, in terms of both computation and communication. Yet, previous PVSS schemes have large proofs and/or require many exponentiations over large groups.
We present a non-interactive PVSS scheme in which the underlying encryption scheme is based on the learning with errors (LWE) problem. While lattice-based encryption schemes are very fast, they often have long ciphertexts and public keys. We use the following two techniques to conserve bandwidth: First, we adapt the Peikert-Vaikuntanathan-Waters (PVW) encryption scheme to the multi-receiver setting, so that the bulk of the parties' keys is a common random string. The resulting scheme yields \(\varOmega (1)\) amortized plaintext/ciphertext rate, where concretely the rate is \(\approx 1/60\) for 100 parties, \(\approx 1/8\) for 1000 parties, and approaching 1/2 as the number of parties grows. Second, we use bulletproofs over a DL-group of order about 256 bits to get compact proofs of correct encryption/decryption of shares.
Alternating between the lattice and DL settings is relatively painless, as we equate the LWE modulus with the order of the group. We also show how to reduce the the number of exponentiations in the bulletproofs by applying Johnson-Lindenstrauss-like compression to reduce the dimension of the vectors whose properties must be verified.
An implementation of our PVSS with 1000 parties showed that it is feasible even at that size, and should remain so even with one or two order of magnitude increase in the committee size.
For the entire collection see [Zbl 1493.94001].Evolving homomorphic secret sharing for hierarchical access structureshttps://zbmath.org/1496.940792022-11-17T18:59:28.764376Z"Phalakarn, Kittiphop"https://zbmath.org/authors/?q=ai:phalakarn.kittiphop"Suppakitpaisarn, Vorapong"https://zbmath.org/authors/?q=ai:suppakitpaisarn.vorapong"Attrapadung, Nuttapong"https://zbmath.org/authors/?q=ai:attrapadung.nuttapong"Matsuura, Kanta"https://zbmath.org/authors/?q=ai:matsuura.kantaSummary: Secret sharing is a cryptographic primitive that divides a secret into several shares, and allows only some combinations of shares to recover the secret. As it can also be used in secure multi-party computation protocol with outsourcing servers, several variations of secret sharing are devised for this purpose. Most of the existing protocols require the number of computing servers to be determined in advance. However, in some situations we may want the system to be ``evolving''. We may want to increase the number of servers and strengthen the security guarantee later in order to improve availability and security of the system. Although evolving secret sharing schemes are available, they do not support computing on shares. On the other hand, ``homomorphic'' secret sharing allows computing on shares with small communication, but they are not evolving. As the contribution of our work, we give the definition of ``evolving homomorphic'' secret sharing supporting both properties. We propose two schemes, one with hierarchical access structure supporting multiplication, and the other with partially hierarchical access structure supporting computation of low degree polynomials. Comparing to the work with similar functionality of \textit{A. R. Choudhuri} et al. [Lect. Notes Comput. Sci. 12826, 94--123 (2021; Zbl 07511728)], our schemes have smaller communication costs.
For the entire collection see [Zbl 1484.68016].An inductive construction of minimal codeshttps://zbmath.org/1496.940802022-11-17T18:59:28.764376Z"Bartoli, Daniele"https://zbmath.org/authors/?q=ai:bartoli.daniele"Bonini, Matteo"https://zbmath.org/authors/?q=ai:bonini.matteo"Güneş, Burçin"https://zbmath.org/authors/?q=ai:gunes.burcinA codeword \(c\) from a code \(C\) is minimal if it only covers the codewords \(\lambda c,\) with \(\lambda\in \mathbb{F}_q^\ast\) which means that for every codeword \(c'\) if the support of \(c\) is subset of the support of \(c'\) then \(c'=\lambda c.\) A code \(C\) is minimal if every nonzero codeword \(c\in C\) is minimal. Minimal codewords are of particular interest since they can be used to describe access structures in linear code-based secret sharing schemes.
In this paper, the authors provide a total of three new constructions of minimal linear code. The first construction is an inductive construction of minimal linear codes which has a generator matrix in the form \(A_{t,q}=(I_t\vert B_{t,q}),\) where \(I_t\) is the identity matrix and \(B_{t,q}\) is a \(t\times \binom{t}{2}(q-1)\) matrix over \(\mathbb{F}_q\) with columns \(e_i+\lambda e_j, \lambda\in\mathbb{F}_q^\ast.\)
The second construction considers codes with generator matrix \(\widetilde{A}_{t,q}=(I_t\vert \widetilde{B}_{t,q}),\) where \(\widetilde{B}_{t,q}\) is a \(t\times \binom{t}{2}(q-1)^{k-1}\) matrix over \(\mathbb{F}_q\) with columns \(e_{i_1}+\sum_{j=2}^{k}{\lambda_{i_j}e_{i_j}}, \lambda\in\mathbb{F}_q^\ast.\) It is proved that this code is minimal linear and an investigation on the weight distribution of such minimal codes is performed.
The third construction is more general and it is proven that if \(\mathbb{F}_q^\ast=\langle\xi\rangle\) and \(t\geq 2\) is an integer, codes with generator matrix \(A_{t,q}'=\left(\begin{array}{cc} & \xi\ \xi^2 \ \ldots \xi^{q-2} \\
A_{t,q} & O \\
\end{array}\right)\) are minimal and satisfy that for every nonzero codeword \(w=(w_1,\ldots, w_n)\in C\) it follows \(|\{w_i : i \in \{1,\ldots, n\}\}| = q.\)
The parameters of the codes investigated in this paper are not particularly good but their relevance is in allowing the construction of secret sharing schemes as well as in the fact that the knowledge of their weight distribution can be important in their classification. Multiple examples of minimal linear codes in any characteristic are given.
Reviewer: Nikolay Yankov (Shumen)Bounds on the cardinality of subspace codes with non-maximum code distancehttps://zbmath.org/1496.940812022-11-17T18:59:28.764376Z"Gabidulin, E. M."https://zbmath.org/authors/?q=ai:gabidulin.ernst-m"Pilipchuk, N. I."https://zbmath.org/authors/?q=ai:pilipchuk.nina-i"Trushina, O. V."https://zbmath.org/authors/?q=ai:trushina.o-vThis paper studies subspace codes with nonmaximum code distance. The subspace distance between two subspaces \(U, V \in \mathrm{GF}(q)^n\) is
\[d_{\text{sub}}(U,V) = \dim(U) + \dim(V) -2\dim(U\cap V ).\]
If \(U, V\) are of the same dimension \(m,\) the subspace distance equals \(d_{\text{sub}}(U, V)=2(m-\dim(U\cap V)) = 2\delta\), \(\delta=m-\dim(U\cap V)\) known as the Grassmannian metric.
Families of nonspreads based on using the Silva-Kotter-Kschischang (SKK) subspace code construction and Gabidulin-Bossert multicomponent codes with zero prefix (MZP) are considered. Numerical estimates for cardinalities of nonspreads for a large number of parameters are given. Moreover, it is shown that for large dimensions all the three codes almost attain the maximum cardinality bound given by the Johnson inequality
\[M(n + 1,d_{\text{sub}},m + 1)\leq \frac{q^{n+1}-1}{q^{m+1}-1}M(n, d_{\text{sub}}, m).\]
The authors present examples of nonspreads with the best values of the cardinality against previously known subspace codes with the same parameters.
Reviewer: Nikolay Yankov (Shumen)New binary self-dual codes of lengths 80, 84 and 96 from composite matriceshttps://zbmath.org/1496.940822022-11-17T18:59:28.764376Z"Gildea, Joe"https://zbmath.org/authors/?q=ai:gildea.joe"Korban, Adrian"https://zbmath.org/authors/?q=ai:korban.adrian"Roberts, Adam Michael"https://zbmath.org/authors/?q=ai:roberts.adam-michaelOne of the most used techniques for generating binary self-dual codes is the pure double circulant construction using the matrix \(G = (I_n\mid A)\) where \(A\) is a circulant matrix. This technique has since been generalised by assuming a generator matrix of the form \(G = (I_n |\sigma(v))\) where \(\sigma\) is an isomorphism from a group ring. A composite matrix it this work denotes \(G = (I_n |\Omega(v))\) where \(\Omega(v)\) is a matrix that arises from group rings. The code generated by \(G\) is self-dual if and only if \(\Omega(v)\Omega(v)T = -I_n.\)
Using this type of generator matrices for a number of different composite matrices \(\Omega(v)\) over different alphabets \(\mathbb{F}_2,\) \(\mathbb{F}_2 + u\mathbb{F}_2\) and \(\mathbb{F}_4\), the authors find many binary self-dual codes with large length and weight enumerator parameters of previously unknown values. Studying this type of construction the necessary and sufficient conditions needed by each construction to produce a self-dual code are proved. Applying the results, a total of 361 new binary self-dual codes are found, including 28 singly-even binary self-dual \([80, 40, 14]\) codes, 107 binary self-dual \([84, 42, 14]\) codes, 105 singly-even binary self-dual \([96, 48, 16]\) codes and 121 doubly-even binary self-dual \([96, 48, 16]\) codes. All the necessary information for generating these codes as well as the orders of their automorphism group are given in tables.
Reviewer: Nikolay Yankov (Shumen)Linear complementary pairs of codes over ringshttps://zbmath.org/1496.940832022-11-17T18:59:28.764376Z"Hu, Peng"https://zbmath.org/authors/?q=ai:hu.peng"Liu, Xiusheng"https://zbmath.org/authors/?q=ai:liu.xiushengLet \(C\) and \(D\) are two linear codes of length \(n\) over finite commutative ring with identity \(R\) such that \(C\cap D = \{0\}\) and \(C\oplus D = R^n,\) then we call such \((C, D)\) a linear complementary pair (LCP) of codes over \(R.\) LCP code are of particular interest for their applications in cryptography.
This work introduces a generalization of LCP of codes over finite fields to LCP of codes over finite rings and a criterion for LCP of linear codes over finite rings is shown. In particular, free LCP of codes over finite commutative rings are characterized. Using the characterization of free LCP of codes, a maximum distance separable LCP of codes over ring \(\mathbb{Z}_4\) is constructed as an example.
The authors give a necessary and sufficient condition for a pair of linear codes over finite chain rings to be LCP. Special attention is devoted to investigate constacyclic and quasi-cyclic LCP of codes over finite chain rings. As a result a characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes is obtained. This result for the constacyclic and quasi-cyclic complementary pairs extends the characterization of LCP of constacyclic and quasi-cyclic codes known before.
Lastly, some results about general LCP of codes and free cyclic LCD codes over principal ideal rings are established.
Reviewer: Nikolay Yankov (Shumen)Construction of LCD and new quantum codes from cyclic codes over a finite non-chain ringhttps://zbmath.org/1496.940842022-11-17T18:59:28.764376Z"Islam, Habibul"https://zbmath.org/authors/?q=ai:islam.habibul"Prakash, Om"https://zbmath.org/authors/?q=ai:prakash.omSummary: For an odd prime \(p\) and \(q = p^r\), this paper deals with LCD codes obtained from cyclic codes of length \(n\) over a finite commutative non-chain ring \(\mathcal{R}=\mathbb{F}_q [u,v]/\langle u^2 -\alpha u,v^2 -1, uv-vu\rangle\) where \(\alpha\) is a non-zero element in \(\mathbb{F}_q\). Initially, we impose certain conditions on the generator polynomials of cyclic codes when \(\gcd (n,p)=1\) and \(\gcd (n,p)\neq 1\), respectively so that these codes become LCD. Then, by defining a Gray map \(\psi\), we show that the Gray image of an LCD code of length \(n\) over \(\mathcal{R}\) is an LCD code of length \(4n\) over \(\mathbb{F}_q\). In this way, we obtain many optimal and best-known linear codes (BKLC) from the Gray images of both cyclic and LCD codes over \(\mathcal{R}\). Eventually, by applying the CSS construction on cyclic codes over \(\mathcal{R}\) that contain their Euclidean duals, we determine many superior quantum codes compared to the existing codes in the recent references.New constant dimension subspace codes from parallel linkage construction and multilevel constructionhttps://zbmath.org/1496.940852022-11-17T18:59:28.764376Z"Niu, Yongfeng"https://zbmath.org/authors/?q=ai:niu.yongfeng"Yue, Qin"https://zbmath.org/authors/?q=ai:yue.qin"Huang, Daitao"https://zbmath.org/authors/?q=ai:huang.daitaoConstant dimension subspace codes have efficient encoding and decoding algorithms and have important applications in network coding. Inspired by the results in [\textit{H. Chen} et al., IEEE Trans. Inf. Theory 66, No. 9, 5317--5321 (2020; Zbl 1448.94256); \textit{S. Liu} et al., IEEE Trans. Inf. Theory 66, No. 11, 6884--6897 (2020; Zbl 1453.94146)], The authors of this paper present an improved version of parallel construction and multilevel constructions, and are thus able to construct constant dimension codes with more codewords.
More precisely, after giving some basic results on Ferrers diagram rank-metric codes, \(SC\)-representation, parallel linkage construction, the Delsarte theorem and so on, in section 3, the authors proved the following main results:
Theorem 3.2. Let \(\mathcal{U} \subseteq \mathbb{F}_{q}^{k \times m}\) be SC-representation of constant dimension codes \(\mathcal{C}(\mathcal{U})\) with \(m \geq k,|\mathcal{U}|=N_{1}\), and \(d_{S}(\mathcal{C}(\mathcal{U}))=2 d\). Let \(\mathcal{P} \subseteq \mathbb{F}_{q}^{k \times n}\) be a rank-metric code with \(|\mathcal{P}|=N_{2}\) and \(d_{R}(\mathcal{P})=d\). Define a constant dimension code
\[
\mathcal{C}_{1}=\{r s(U |P): U \in \mathcal{U}, P \in \mathcal{P}\}.
\]
Let \(\mathcal{V} \subseteq \mathbb{F}_{q}^{k \times n}\) be SC-representation of constant dimension codes \(\mathcal{C}(\mathcal{V})\) with \(n \geq k,|\mathcal{V}|=\) \(N_{3}\), and \(d_{S}(\mathcal{C}(\mathcal{V}))=2 d\). Let \(\mathcal{Q} \subseteq \mathbb{F}_{q}^{k \times m}\) be a rank-metric code with \(|\mathcal{Q}|=N_{4}\) and \(d_{R}(\mathcal{Q})=d\) such that the rank of each matrix in \(\mathcal{Q}\) is at most \(k-d\). Define a constant dimension code
\[
\mathcal{C}_{2}=\{r s(Q |V): Q \in \mathcal{Q}, V \in \mathcal{V}\}.
\]
Consider the constant dimension code defined by \(\mathcal{C}=\mathcal{C}_{1} \cup \mathcal{C}_{2} \cup \mathcal{C}_{\mathcal{F}}\), where \(\mathcal{C}_{\mathcal{F}}=\) \(\cup_{1 \leq i, j \leq 3} \mathcal{C}_{\mathcal{F}_{i j}}\) is the same as Lemma 3.1. Then \(\mathcal{C}\) is an \((m+n,|\mathcal{C}|, 2 d, k)_{q}\) constant dimension code with \(|\mathcal{C}|=N_{1} N_{2}+N_{3} N_{4}+\sum_{1 \leq i, j \leq 3}\left|\mathcal{C}_{\mathcal{F}_{i j}}\right|\).
Finally, let \(A_{q}(n, d, k)\) be the maximal sizes of an \((n, M, d, k)_q\) constant dimension code. We heve
Corollary 3.3. Let \(m, n, k, d\) be integers with \(m, n \geq k \geq 3 d\). Then
\[
A_{q}(m+n, 2 d, k) \geq A_{q}(m, 2 d, k) q^{m \times(k-d+1)}+\sum_{j=d}^{k-d} A_{j}(\mathcal{Q}) A_{q}(n, 2 d, k)+\sum_{1 \leq i, j \leq 3}\left|\mathcal{C}_{\mathcal{F}_{i j}}\right|. \]
Specially, the maximal sizes \(A_{q}(18,6,9)\) and \(A_{q}(17,6,8)\) are discussed in the last two corollaries. From Table 2, we find these constant dimension codes own new lower bounds, which are better than the known lower bounds in [\textit{D. Heinlein} et al., Des. Codes Cryptography 87, No. 2--3, 375--391 (2019; Zbl 1409.51010)].
Reviewer: Weidong Cheng (Chongqing)On list decoding of certain \(\mathbb{F}_q\)-linear codeshttps://zbmath.org/1496.940862022-11-17T18:59:28.764376Z"Polyanskii, N. A."https://zbmath.org/authors/?q=ai:polyanskii.nikita-andreevichDenote by \(C_q^s(m, d)\) the generalization of Reed-Solomon \(s\)-code. A list decoding algorithm for \(\mathbb{F}_q\)-linear codes that generalize the Reed-Solomon \(s\)-codes is found. In the course of the proof a deduction of a statement which helps the improvement of the bound on the minimum distance of the \(C_q^s(m, d)\) codes is shown.
For integers \(q,s\)-powers of a prime \(p,\) and a positive numbers \(m\geq 2\) and \(d\) satisfying \(d\leq sq -m-2(s-1)\) and \(m + s \leq q,\) define the integer \(\widetilde{d}= q^{m-1}(s-1 + \frac{q-1}{q}(m + d-1)\) and fixed an integer parameter \(\varphi\geq 3.\) Then there exist a list decoding algorithm that is proved to has runtime \(\text{poly}\left(q^m,\left(\varphi \sqrt{sqm/\widetilde{d}}\right)^{s^m}\right)\) and the list size is shown that can be bounded by \(O\left(\varphi \sqrt{sqm/\widetilde{d}}\right)^{s^m}.\) A brief explanation of each step of the algorithm as well as an analysis of the important aspects of some of its steps are given in more details.
Reviewer: Nikolay Yankov (Shumen)On the number of \(q\)-ary quasi-perfect codes with covering radius 2https://zbmath.org/1496.940872022-11-17T18:59:28.764376Z"Romanov, Alexander M."https://zbmath.org/authors/?q=ai:romanov.alexander-mikhailovichLet \(q\) be a prime power, and let \((n, M, d ; \rho)_{q}\) be a \(q\)-ary code of length \(n\), size \(M\), minimum distance \(d\), and covering radius \(\rho\). In this paper, the author use the switching construction to construct a family of \(q\)-ary nonlinear quasi-perfect codes with covering radius \(\rho=2\), and a lower bound of the number of such codes was given.
More precisely, Let \(RM_{q}((q-1)m-2, m)\) be the generalized Reed-Muller code of order \((q-1)m-2\) over the field \(\mathbb{F}_q\), and let \(\mathscr{R}_{i}\) be a subspace spanned by the set of all triples of \(RM_{q}((q-1) m-2, m)\) having 1 in the \(i\)th coordinate, with \(i \in\{1, \ldots, n\}\). Let \(q \geq 3, m \geq 2\), and \(n=q^{m}\).
Theorem 1 says that, let \(\mathscr{R}_{i}+\mathbf{x} \subset R M_{q}((q-1) m-2, m)\), then
\[
\mathscr{C}^{\prime}=\left(R M_{q}((q-1) m-2, m) \backslash\left(\mathscr{R}_{i}+\mathbf{x}\right)\right) \cup\left(\mathscr{R}_{i}+\mathbf{x}+\lambda \mathbf{e}_{i}\right)
\]
is a \(q\)-ary nonlinear quasi-perfect code with parameters \(\left(n, q^{n-m-1}, 3; 2\right)_{q}\), for any \(\lambda \in\) \(\mathbb{F}_{q} \backslash\{0\}\) and for any \(i \in\{1,2, \ldots, n\}\).
Theorem 2 says that, let \(\mathscr{R}_{i}+\mathbf{x}_{t} \subset R M_{q}((q-1) m-2, m)\), \(1 \leq t \leq q^{[m]_{q}-m},\left(\mathscr{R}_{i}+\mathbf{x}_{t_{1}}\right) \cap\left(\mathscr{R}_{i}+\mathbf{x}_{t_{2}}\right)=\emptyset\) for all \(1 \leq t_{1} \leq q^{[m]_{q}-m}, 1 \leq t_{2} \leq q^{[m]_{q}-m}\), \(t_{1} \neq t_{2}\), then
\[
\mathscr{C}^{\prime}=\bigcup_{t=1}^{q^{[m] q-m}}\left(\mathscr{R}_{i}+\mathbf{x}_{t}+\lambda_{t} \mathbf{e}_{i}\right)
\]
is a \(q\)-ary quasi-perfect code with parameters \(\left(n, q^{n-m-1}, 3; 2\right)_{q}, \lambda_{t} \in \mathbb{F}_{q}, i \in\) \(\{1,2, \ldots, n\}\).
Theorem 3 says that there are more than \(q^{q^{[m] q-m}-n(m+2)}\) nonequivalent such \(q\)-ary quasi-perfect codes with parameters \(\left(n, q^{n-m-1}, 3; 2\right)_{q}\)
Finally, we note that before this paper, in [\textit{A. M. Romanov}, Probl. Inf. Transm. 57, No. 3, 199--211 (2021; Zbl 1495.94117); translation from Probl. Peredachi Inf. 57, No. 3, 3--16 (2021)], by using the concatenation construction, a family of \(q\)-ary even quasi-perfect codes with covering radius \(\rho=2\) was constructed.
Reviewer: Weidong Cheng (Chongqing)On the generalized concatenated construction for the Nordstrom-Robinson code and the binary Golay codehttps://zbmath.org/1496.940882022-11-17T18:59:28.764376Z"Zinoviev, V. A."https://zbmath.org/authors/?q=ai:zinovev.viktor-aleksandrovich"Zinoviev, D. V."https://zbmath.org/authors/?q=ai:zinovev.dmitrii-viktorovichFor an alphabet \(E_q =\{0, 1,\ldots, q-1\}\) of size \(q\), every \(C\subseteq E_q^n\) is a \(q\)-ary code and its denoted by \((n, N, d)_q,\) where \(N=|C|, \) \(d\) is the minimum (Hamming) distance. A linear code \(C\) with parameters \((n, N = q^k, d)_q\) is denoted by \([n, k, d]_q.\)
Based on the known fact that Nordstrom-Robinson code and the binary Golay code are unique up to equivalence, this work shows that the nonlinear binary Nordstrom-Robinson code with parameters \(n = 16, N = 28, d = 6\) constructed by Nordstrom and Robinson is a generalized concatenated code of order 3. This is achieved using the code \(C\) based on the outer codes \(A = \{(0 0 0 0), (1 1 1 1)\}\), \(A_1 \cup V_1\) and \(A_1 \cup V_1\) and the inner code \(B = B_1 \cup B_2\); the code \(C_1\) based on the outer codes \(A_1\) and \(A_2\) and the inner code \(B_1\); the code \(C_2\) based on the outer codes \(V_1\) and \(V_2\) and the inner code \(B_2\).
The same fact is shown for the binary extended perfect Golay code with parameters \(n = 24\), \(N = 212\), \(d = 8\) constructed in 1949 by Golay.
Reviewer: Nikolay Yankov (Shumen)Left dihedral codes over finite chain ringshttps://zbmath.org/1496.940892022-11-17T18:59:28.764376Z"Aghili, H."https://zbmath.org/authors/?q=ai:aghili.houtan"Sobhani, R."https://zbmath.org/authors/?q=ai:sobhani.rezaSummary: Let \(R\) be a finite commutative chain ring, \(D_{2n}\) be the dihedral group of size \(2n\) and \(R[D_{2n}]\) be the dihedral group ring. In this paper, we completely characterize left ideals of \(R[D_{2n}]\) (called left \(D_{2n}\)-codes) when \(\gcd(\text{char}(R),n)=1\). In this way, we explore the structure of some skew-cyclic codes of length \(2\) over \(R\) and also over \(R\times S\), where \(S\) is an isomorphic copy of \(R\). As a particular result, we give the structure of cyclic codes of length \(2\) over \(R\). In the case where \(R=\mathbb{F}_{p^m}\) is a Galois field, we give a classification for left \(D_{2N}\)-codes over \(\mathbb{F}_{p^m}\), for any positive integer \(N\). In both cases we determine dual codes and identify self-dual ones.Sum-rank product codes and bounds on the minimum distancehttps://zbmath.org/1496.940902022-11-17T18:59:28.764376Z"Alfarano, Gianira N."https://zbmath.org/authors/?q=ai:alfarano.gianira-n"Lobillo, F. J."https://zbmath.org/authors/?q=ai:lobillo.francisco-javier"Neri, Alessandro"https://zbmath.org/authors/?q=ai:neri.alessandro"Wachter-Zeh, Antonia"https://zbmath.org/authors/?q=ai:wachter-zeh.antonia\textit{U. Martínez-Peñas} introduced the family of cyclic-skew-cyclic codes endowed with the sum-rank metric [IEEE Trans. Inf. Theory 67, No. 8, 5149--5167 (2021; Zbl 1486.94178)]. Inspired by this work, the authors of the paper under review consider the tensor product of a cyclic code endowed with the Hamming metric with a skew-cyclic code endowed with the rank-metric, both defined over the same field \(\mathbb{F}\). Such a product code turns out to be a cyclic-skew-cyclic code which naturally inherits the sum-rank metric. A group theoretical description of these codes is given, after investigating the semilinear isometries in the sum-rank metric. As a nice application, the authors provide a generalization of the Roos and the Hartmann-Tzeng bounds for cyclic-skew-cyclic codes endowed with the sum-rank metric.
Reviewer: Sami Omar (Sukhair)Skew cyclic codes over \(\mathbb{F}_4R\)https://zbmath.org/1496.940912022-11-17T18:59:28.764376Z"Benbelkacem, Nasreddine"https://zbmath.org/authors/?q=ai:benbelkacem.nasreddine"Ezerman, Martianus Frederic"https://zbmath.org/authors/?q=ai:ezerman.martianus-frederic"Abualrub, Taher"https://zbmath.org/authors/?q=ai:abualrub.taher-a"Aydin, Nuh"https://zbmath.org/authors/?q=ai:aydin.nuh"Batoul, Aicha"https://zbmath.org/authors/?q=ai:batoul.aichaThe paper under review deals with skew cyclic codes over a new alphabet set which is the ring \(\mathbb{F}_4R\), where \(\mathbb{F}_4\) is the field of \(4\) elements and \(R=\{ a+vb\mid a,b\in \mathbb{F}_4\} \) is the commutative ring with 16 elements, where \(v^2 = v\). The authors first study the algebraic properties of such codes and their duals. For instance, they show that skew cyclic codes over \(\mathbb{F}_4R\) are left \(R[X, \theta]\)-submodules of \(R_{\alpha, \beta} :=\mathbb{F}_4[X]/<X^\alpha-1>\times R[X, \theta]/<X^\beta-1>\). Then, they derive conditions for skew cyclic codes over \(\mathbb{F}_4R\) to be self-orthogonal. Using the Gray mapping, it is shown that the Gray image of any skew cyclic code over \(\mathbb{F}_4R\) is the product of a cyclic code over \(\mathbb{F}_4\) of length \(\alpha\) and two skew cyclic codes, each of length \(\beta\) over \(\mathbb{F}_4\). As an application, they construct optimal linear codes over \(\mathbb{F}_4\) as images of skew cyclic codes over \(\mathbb{F}_4R\) under the Gray mapping.
Reviewer: Sami Omar (Sukhair)Complex dynamical behavior of modified MLC circuithttps://zbmath.org/1496.940922022-11-17T18:59:28.764376Z"Fu, Shihui"https://zbmath.org/authors/?q=ai:fu.shihui"Liu, Yuan"https://zbmath.org/authors/?q=ai:liu.yuanSummary: In this paper, we mainly investigate the complex dynamical behavior of modified MLC circuit. When its external excitation doesn't equal zero, it is nonautonomous and non-smooth, hence we theoretically give the conditions under which grazing bifurcation occurs and the periodic orbits only lie in some one zone. More complex grazing bifurcations and coexisting attractors are also found by numerical simulation, among which is mainly produced by the symmetry. Grazing bifurcations and doubling-period bifurcations that can induce chaotic motion and some basins of attraction are given in this paper. If the external excitation of this system equal zero, it is a non-smooth autonomous system. For this case, we theoretically analysis its non-smooth bifurcations of equilibrium points and limit cycle bifurcation, which is also verified by numerical simulation.Connected Boolean functions with a locally extremal number of prime implicantshttps://zbmath.org/1496.940932022-11-17T18:59:28.764376Z"Chukhrov, Igor' Petrovich"https://zbmath.org/authors/?q=ai:chukhrov.igor-petrovichSummary: The well-known lower bound for the maximum number of prime implicants of a Boolean function (the length of the reduced DNF) differs by \(\Theta(\sqrt{n})\) times from the upper bound and is asymptotically attained at a symmetric belt function with belt width \(n/3\). To study the properties of connected Boolean functions with many prime implicants, we introduce the notion of a locally extremal function in a certain neighborhood in terms of the number of prime implicants. Some estimates are obtained for the change in the number of prime implicants as the values of the belt function range over a \(d\)-neighborhood. We prove that the belt function for which the belt width and the number of the lower layer of unit vertices are asymptotically equal to \(n/3\) is locally extremal in some neighborhood for \(d \le \Theta(n)\) and not locally extremal if \(d \ge 2^{\Theta(n)} \). A similar statement is true for the functions that have prime implicants of different ranks. The local extremality property is preserved after applying some transformation to the Boolean function that preserves the distance between the vertices of the unit cube.An algorithm for group coding in an equation of logichttps://zbmath.org/1496.940942022-11-17T18:59:28.764376Z"Kabulov, V. K."https://zbmath.org/authors/?q=ai:kabulov.vasil-kabulovich(no abstract)A complete characterization of \(\mathcal{D}_0 \cap\mathcal{M}^\#\) and a general framework for specifying bent functions in \(\mathcal{C}\) outside \(\mathcal{M}^\#\)https://zbmath.org/1496.940952022-11-17T18:59:28.764376Z"Kudin, Sadmir"https://zbmath.org/authors/?q=ai:kudin.sadmir"Pasalic, Enes"https://zbmath.org/authors/?q=ai:pasalic.enesBent functions are functions \(f\colon \{0,1\}^n \to \{-1,1\}\) in which the absolute value of all Fourier coefficients is \(2^{n/2}\). There is no classification of all bent functions, but many classes of bent functions are known. Among these are the Maiorana-McFarland class \(\mathcal{M}\) and its completion \(\mathcal{M}^\sharp\), Carlet's classes \(\mathcal{C},\mathcal{D},\mathcal{D}_0\), and the partial spread class \(\mathcal{PS}_{ap}\).
The main result of this paper, Theorem 7, gives a criterion for when a \(\mathcal{D}_0\) class function belongs to \(\mathcal{M}^\sharp\), following up on the work of \textit{C. Carlet} introducing the classes \(\mathcal{C},\mathcal{D}\) [Lect. Notes Comput. Sci. 765, 77--101 (1994; Zbl 0951.94542)].
Other results include a new construction of bent functions of \(\mathcal{C}\) class which are outside of \(\mathcal{M}^\sharp\), and a proof that most functions in \(\mathcal{PS}_{ap}\) do not belong to \(\mathcal{C}\) class. The latter is shown using rank: the authors show that \(\mathcal{C}\) class functions on \(2n\) variables have rank \(O(2^n)\), whereas most functions in \(\mathcal{PS}_{ap}\) have rank \(\omega(2^n)\) [\textit{G. Weng} et al., Finite Fields Appl. 13, No. 4, 1096--1116 (2007; Zbl 1168.05011)].
Reviewer: Yuval Filmus (Haifa)Low \(c\)-differential and \(c\)-boomerang uniformity of the swapped inverse functionhttps://zbmath.org/1496.940962022-11-17T18:59:28.764376Z"Stănică, Pantelimon"https://zbmath.org/authors/?q=ai:stanica.pantelimonModifying the inverse function over the field \(\mathbb{F}_{2^n}\) in two points produces a 4-differential uniform permutation function. For this modified version of the inverse function its boomerang uniformity has been determined in [\textit{K. Li} et al., IEEE Trans. Inf. Theory 65, No. 11, 7542--7553 (2019; Zbl 1433.94088)]. In this paper, the author characterizes the c-differential and c-boomerang uniformity for the (0,1)-swapped inverse function in even characteristic In particular, for \(c\ne 1\) we have that the c-differential uniformity is upper bounded by 4 and the c-boomerang uniformity by 5. Both bounds can be attained for \(n\ge 4\).
Reviewer: Marco Calderini (Bergen)