Recent zbMATH articles in MSC 94https://www.zbmath.org/atom/cc/942021-04-16T16:22:00+00:00WerkzeugSynchronization and spatial patterns in a light-dependent neural network.https://www.zbmath.org/1456.340492021-04-16T16:22:00+00:00"Liu, Yong"https://www.zbmath.org/authors/?q=ai:liu.yong.2|liu.yong.1|liu.yong.3|liu.yong.5|liu.yong.4"Xu, Ying"https://www.zbmath.org/authors/?q=ai:xu.ying"Ma, Jun"https://www.zbmath.org/authors/?q=ai:ma.junSummary: Nonlinear oscillators and networks can be synchronized by channel coupling for signal exchange, while non-coupling synchronization between chaotic oscillators can be obtained by applying the same stochastic disturbance for inducing resonance. For most of realistic dynamical systems, physical energy and biophysical energy are pumped along the coupling channels and then the variables are regulated to present different modes in oscillation. In this paper, a new photosensitive neuron is proposed to detect the dynamics in isolated neuron and synchronization stability by changing the illumination, which can adjust the photocurrent across the branch circuit, even no direct synapse coupling is applied. The generation of photocurrents with diversity is explained from physical viewpoint. Furthermore, the collective responses of these photosensitive neurons in network are detected by calculating the synchronization stability and pattern formation. It is found that the spatial patterns in the network are dependent on the illumination. Uniform illumination can induce complete synchronization while non-uniform illumination can develop rich spatial patterns. Furthermore, uniform and stochastic photocurrents are imposed on all neurons to realize complete synchronization even synapse connection are removed from the network. These results can give potential guidance for designing functional neural circuits with potential application to identify optical signals as electronic eyes.Analysis of an information-theoretic model for communication.https://www.zbmath.org/1456.940042021-04-16T16:22:00+00:00"Dickman, Ronald"https://www.zbmath.org/authors/?q=ai:dickman.ronald"Moloney, Nicholas R."https://www.zbmath.org/authors/?q=ai:moloney.nicholas-r"Altmann, Eduardo G."https://www.zbmath.org/authors/?q=ai:altmann.eduardo-gConstant conditional entropy and related hypotheses.https://www.zbmath.org/1456.911132021-04-16T16:22:00+00:00"Ferrer-i-Cancho, Ramon"https://www.zbmath.org/authors/?q=ai:ferrer-i-cancho.ramon"Dębowski, Łukasz"https://www.zbmath.org/authors/?q=ai:debowski.lukasz"Moscoso del Prado Martín, Fermín"https://www.zbmath.org/authors/?q=ai:del-prado-martin.fermin-moscosoOn group rings and some of their applications to combinatorics and symmetric cryptography.https://www.zbmath.org/1456.940582021-04-16T16:22:00+00:00"Carlet, Claude"https://www.zbmath.org/authors/?q=ai:carlet.claude"Tan, Yin"https://www.zbmath.org/authors/?q=ai:tan.yinSummary: We give a survey of recent applications of group rings to combinatorics and to cryptography, including their use in the differential cryptanalysis of block ciphers.Type I and type II codes over the ring \(\mathbb{F}_2+s \mathbb{F}_2+s^2\mathbb{F}_2\).https://www.zbmath.org/1456.941302021-04-16T16:22:00+00:00"Ankur"https://www.zbmath.org/authors/?q=ai:ankur.Summary: We take a ring \(R = \mathbb{F}_2+s\mathbb{F}_2+s^2\mathbb{F}_2\). We consider a Gray map on this ring, discuss self-dual codes, define various weight enumerators over the ring, and discuss equivalence class of codes over the ring. We construct self-dual codes of Type I and Type II over the given ring for different lengths.Group rings for communications.https://www.zbmath.org/1456.941352021-04-16T16:22:00+00:00"Hurley, Ted"https://www.zbmath.org/authors/?q=ai:hurley.tedSummary: This is a survey of some recent applications of abstract algebra, and in particular group rings, to the communications' areas.Nonnegative tensor patch dictionary approaches for image compression and deblurring applications.https://www.zbmath.org/1456.650282021-04-16T16:22:00+00:00"Newman, Elizabeth"https://www.zbmath.org/authors/?q=ai:newman.elizabeth"Kilmer, Misha E."https://www.zbmath.org/authors/?q=ai:kilmer.misha-eTypical \(l_1\)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices.https://www.zbmath.org/1456.150362021-04-16T16:22:00+00:00"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyuki"Vehkaperä, Mikko"https://www.zbmath.org/authors/?q=ai:vehkapera.mikko"Chatterjee, Saikat"https://www.zbmath.org/authors/?q=ai:chatterjee.saikat.1Hidden attractors and multistability in a modified Chua's circuit.https://www.zbmath.org/1456.340572021-04-16T16:22:00+00:00"Wang, Ning"https://www.zbmath.org/authors/?q=ai:wang.ning"Zhang, Guoshan"https://www.zbmath.org/authors/?q=ai:zhang.guoshan"Kuznetsov, N. V."https://www.zbmath.org/authors/?q=ai:kuznetsov.nikolay-v"Bao, Han"https://www.zbmath.org/authors/?q=ai:bao.hanSummary: The first hidden chaotic attractor was discovered in a dimensionless piecewise-linear Chua's system with a special Chua's diode. But designing such physical Chua's circuit is a challenging task due to the distinct slopes of Chua's diode. In this paper, a modified Chua's circuit is implemented using a 5-segment piecewise-linear Chua's diode. In particular, the coexisting phenomena of hidden attractors and three point attractors are noticed in the entire period-doubling bifurcation route. Attraction basins of different coexisting attractors are explored. It is demonstrated that the hidden attractors have very small basins of attraction not being connected with any fixed point. The PSIM circuit simulations and DSP-assisted experiments are presented to illustrate the existence of hidden attractors and coexisting attractors.Noise-enhanced stability and double stochastic resonance of active Brownian motion.https://www.zbmath.org/1456.602222021-04-16T16:22:00+00:00"Zeng, Chunhua"https://www.zbmath.org/authors/?q=ai:zeng.chunhua"Zhang, Chun"https://www.zbmath.org/authors/?q=ai:zhang.chun"Zeng, Jiakui"https://www.zbmath.org/authors/?q=ai:zeng.jiakui"Liu, Ruifen"https://www.zbmath.org/authors/?q=ai:liu.ruifen"Wang, Hua"https://www.zbmath.org/authors/?q=ai:wang.hua.1|wang.hua|wang.hua.2Relative entropy via non-sequential recursive pair substitution.https://www.zbmath.org/1456.940312021-04-16T16:22:00+00:00"Benedetto, D."https://www.zbmath.org/authors/?q=ai:benedetto.dario"Caglioti, E."https://www.zbmath.org/authors/?q=ai:caglioti.emanuele"Cristadoro, G."https://www.zbmath.org/authors/?q=ai:cristadoro.giampaolo"Degli Esposti, M."https://www.zbmath.org/authors/?q=ai:esposti.m-degli|degli-esposti.mirkoA new upper bound on the order of affine sub-families of NFSRs.https://www.zbmath.org/1456.940372021-04-16T16:22:00+00:00"Liu, Junying"https://www.zbmath.org/authors/?q=ai:liu.junying"Zheng, Qunxiong"https://www.zbmath.org/authors/?q=ai:zheng.qunxiong"Lin, Dongdai"https://www.zbmath.org/authors/?q=ai:lin.dongdaiSummary: Nonlinear feedback shift registers (NFSRs) are widely used as building blocks in the design of stream ciphers. Let NFSR\((f)\) be an NFSR with the characteristic function \(f\) and let \(G(f)\) be the set of output sequences of NFSR\((f)\). For a given NFSR\((f)\), if there exists an affine Boolean function \(l\) such that \(G(l)\subseteq G(f)\), then \(G(l)\) is called an affine sub-family of NFSR\((f)\). In this paper, by skillfully combining previous ideas, the authors give a new upper bound on the order of affine sub-families of NFSR\((f)\). Compared with the four known bounds, the bound is better than three of them, and in some cases is also better than the rest one.Large-sample variance of simulation using refined descriptive sampling: case of independent variables.https://www.zbmath.org/1456.600042021-04-16T16:22:00+00:00"Baiche, Leila"https://www.zbmath.org/authors/?q=ai:baiche.leila"Ourbih-Tari, Megdouda"https://www.zbmath.org/authors/?q=ai:ourbih-tari.megdoudaSummary: Derived from descriptive sampling (DS) as a better approach to Monte Carlo simulation, refined DS is a method of sampling that can be used to produce input values for estimation of expectations of functions of output variables. In this article, the asymptotic variance of such an estimate in case of independent input variables is obtained and it was shown that asymptotically, the variance is less than that obtained using simple random sampling.Ham-sandwich cuts and center transversals in subspaces.https://www.zbmath.org/1456.520102021-04-16T16:22:00+00:00"Schnider, Patrick"https://www.zbmath.org/authors/?q=ai:schnider.patrickSummary: The Ham-Sandwich theorem is a well-known result in geometry. It states that any \(d\) mass distributions in \(\mathbb{R}^d\) can be simultaneously bisected by a hyperplane. The result is tight, that is, there are examples of \(d + 1\) mass distributions that cannot be simultaneously bisected by a single hyperplane. In this paper we will study the following question: given a continuous assignment of mass distributions to certain subsets of \(\mathbb{R}^d\), is there a subset on which we can bisect more masses than what is guaranteed by the Ham-Sandwich theorem? We investigate two types of subsets. The first type are linear subspaces of \(\mathbb{R}^d\), i.e., \(k\)-dimensional flats containing the origin. We show that for any continuous assignment of \(d\) mass distributions to the \(k\)-dimensional linear subspaces of \(\mathbb{R}^d\), there is always a subspace on which we can simultaneously bisect the images of all \(d\) assignments. We extend this result to center transversals, a generalization of Ham-Sandwich cuts. As for Ham-Sandwich cuts, we further show that for \(d - k + 2\) masses, we can choose \(k-1\) of the vectors defining the \(k\)-dimensional subspace in which the solution lies. The second type of subsets we consider are subsets that are determined by families of \(n\) hyperplanes in \(\mathbb{R}^d\). Also in this case, we find a Ham-Sandwich-type result. In an attempt to solve a conjecture by Langerman about bisections with several cuts, we show that our underlying topological result can be used to prove this conjecture in a relaxed setting.Investigation graph isomorphism problem via entanglement entropy in strongly regular graphs.https://www.zbmath.org/1456.940332021-04-16T16:22:00+00:00"Jafarizadeh, M. A."https://www.zbmath.org/authors/?q=ai:jafarizadeh.mohamad-ali|jafarizadeh.mohammad-ali"Eghbalifam, F."https://www.zbmath.org/authors/?q=ai:eghbalifam.f"Nami, S."https://www.zbmath.org/authors/?q=ai:nami.susanThe codon information index: a quantitative measure of the information provided by the codon bias.https://www.zbmath.org/1456.920852021-04-16T16:22:00+00:00"Caniparoli, Luca"https://www.zbmath.org/authors/?q=ai:caniparoli.luca"Marsili, Matteo"https://www.zbmath.org/authors/?q=ai:marsili.matteo"Vendruscolo, Michele"https://www.zbmath.org/authors/?q=ai:vendruscolo.micheleLocally active memristor with three coexisting pinched hysteresis loops and its emulator circuit.https://www.zbmath.org/1456.780132021-04-16T16:22:00+00:00"Zhu, Minghao"https://www.zbmath.org/authors/?q=ai:zhu.minghao"Wang, Chunhua"https://www.zbmath.org/authors/?q=ai:wang.chunhua"Deng, Quanli"https://www.zbmath.org/authors/?q=ai:deng.quanli"Hong, Qinghui"https://www.zbmath.org/authors/?q=ai:hong.qinghuiThe authors propose a new locally active memristor with three coexisting pinched hysteresis loops. This new memristor is used in the Chua chaotic system to study the effects of the locally active memristor. The power-off plot and DC \(V\)-\(I\) plot are in particular studied by the authors. The memristor emulator and chaotic system are also implemented in commericial circuit elements. The hardware experiments completed by the authors are shown to be consistent with numerical simulations.
Reviewer: Eric Stachura (Marietta)Automorphisms and isomorphisms of some \(p\)-ary bent functions.https://www.zbmath.org/1456.941442021-04-16T16:22:00+00:00"Dempwolff, Ulrich"https://www.zbmath.org/authors/?q=ai:dempwolff.ulrichIn this continuation of the author's paper [Commun. Algebra 34, No. 3, 1077--1131 (2006; Zbl 1085.05019)]
on Boolean (bent) functions, \(p\)-ary bent functions are similarly investigated. EA-equivalence of (bent) functions is in general not easy to decide. Simple invariants, like algebraic degree, are usually not sufficient to decide equivalence of bent functions, stronger methods seem necessary.
In this paper, group-theoretic methods are applied to analyse equivalence of (some classes of) \(p\)-ary bent functions. For a given (bent) function \(f\) from an \(n\)-dimensional vector space \(V\) over \(\mathbb{F}_p\) to \(\mathbb{F}_p\), the author considers the group \(\mathbf{EA}(f)\) of EA automorphisms, i.e. \(\phi_{11} \in (V)\),
\(\phi_{22} \in \mathrm{GL}(\mathbb{F}_p)\), \(\phi_{12} \in \Hom(V,\mathbb{F}_p)\) and \(v\in V, w\in \mathbb{F}_p\) such that
\[ f(\phi_{11}(x)+v) = \phi_{22}(f(x)) + \phi_{12}(x) + w \quad\text{for all }x\in V. \]
The structure of this group is invariant under EA-equivalence.
As another invariant under EA-equivalence for \(p\)-ary functions, the author suggests the set \(\{v\in V, D_v^2f = 0\}\), where \(D_vf(x) = f(x+v)-f(x)\) denotes the derivative of \(f\) in direction \(v\).
In the first part, the author discusses a secondary construction of three types of (non-quadratic) bent functions \(f\), describes \(\mathbf{EA}(f)\) and as a consequence solves the equivalence problem for these types of bent functions.
In the second part of the paper, \(\mathbf{EA}(f)\) is described for Maiorana-McFarland bent functions of the form \(\mathrm{Tr}_n(xy^l)\), \(\gcd(l,p^n-1) = 1\), and the question when two such bent functions are EA-equivalent is solved.
Reviewer: Wilfried Meidl (Linz)Existence of metastable, hyperchaos, line of equilibria and self-excited attractors in a new hyperjerk oscillator.https://www.zbmath.org/1456.370502021-04-16T16:22:00+00:00"Rajagopal, Karthikeyan"https://www.zbmath.org/authors/?q=ai:rajagopal.karthikeyan"Singh, Jay Prakash"https://www.zbmath.org/authors/?q=ai:singh.jay-prakash"Karthikeyan, Anitha"https://www.zbmath.org/authors/?q=ai:karthikeyan.anitha"Roy, Binoy Krishna"https://www.zbmath.org/authors/?q=ai:roy.binoy-krishnaThe biparametric Fisher-Rényi complexity measure and its application to the multidimensional blackbody radiation.https://www.zbmath.org/1456.811152021-04-16T16:22:00+00:00"Puertas-Centeno, D."https://www.zbmath.org/authors/?q=ai:puertas-centeno.david"Toranzo, I. V."https://www.zbmath.org/authors/?q=ai:toranzo.irene-v"Dehesa, J. S."https://www.zbmath.org/authors/?q=ai:dehesa.jesus-sFinancial cryptography and data security. FC 2020 international workshops, AsiaUSEC, codefi, VOTING, and WTSC, Kota Kinabalu, Malaysia, February 14, 2020. Revised selected papers.https://www.zbmath.org/1456.940022021-04-16T16:22:00+00:00"Bernhard, Matthew (ed.)"https://www.zbmath.org/authors/?q=ai:bernhard.matthew"Bracciali, Andrea (ed.)"https://www.zbmath.org/authors/?q=ai:bracciali.andrea"Camp, L. Jean (ed.)"https://www.zbmath.org/authors/?q=ai:camp.l-jean"Matsuo, Shin'ichiro (ed.)"https://www.zbmath.org/authors/?q=ai:matsuo.shinichiro"Maurushat, Alana (ed.)"https://www.zbmath.org/authors/?q=ai:maurushat.alana"Rønne, Peter B. (ed.)"https://www.zbmath.org/authors/?q=ai:ronne.peter-b"Sala, Massimiliano (ed.)"https://www.zbmath.org/authors/?q=ai:sala.massimilianoThe articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 1428.94011].Infinite Shannon entropy.https://www.zbmath.org/1456.820062021-04-16T16:22:00+00:00"Baccetti, Valentina"https://www.zbmath.org/authors/?q=ai:baccetti.valentina"Visser, Matt"https://www.zbmath.org/authors/?q=ai:visser.mattInformation flow in layered networks of non-monotonic units.https://www.zbmath.org/1456.940272021-04-16T16:22:00+00:00"Neves, Fabio Schittler"https://www.zbmath.org/authors/?q=ai:neves.fabio-schittler"Schubert, Benno Martim"https://www.zbmath.org/authors/?q=ai:schubert.benno-martim"Erichsen, Rubem jun."https://www.zbmath.org/authors/?q=ai:erichsen.rubem-junRényi entropies as a measure of the complexity of counting problems.https://www.zbmath.org/1456.827052021-04-16T16:22:00+00:00"Chamon, Claudio"https://www.zbmath.org/authors/?q=ai:chamon.claudio"Mucciolo, Eduardo R."https://www.zbmath.org/authors/?q=ai:mucciolo.eduardo-rIntegrating feature direction information with a level set formulation for image segmentation.https://www.zbmath.org/1456.940082021-04-16T16:22:00+00:00"Li, Meng"https://www.zbmath.org/authors/?q=ai:li.meng"Zhan, Yi"https://www.zbmath.org/authors/?q=ai:zhan.yiSummary: A feature-dependent variational level set formulation is proposed for image segmentation. Two second order directional derivatives act as the external constraint in the level set evolution, with the directional derivative across the image features direction playing a key role in contour extraction and another only slightly contributes. To overcome the local gradient limit, we integrate the information from the maximal (in magnitude) second-order directional derivative into a common variational framework. It naturally encourages the level set function to deform (up or down) in opposite directions on either side of the image edges, and thus automatically generates object contours. An additional benefit of this proposed model is that it does not require manual initial contours, and our method can capture weak objects in noisy or intensity-inhomogeneous images. Experiments on infrared and medical images demonstrate its advantages.Quantum multi-level wavelet transforms.https://www.zbmath.org/1456.420472021-04-16T16:22:00+00:00"Li, Hai-Sheng"https://www.zbmath.org/authors/?q=ai:li.haisheng.1|li.haisheng"Fan, Ping"https://www.zbmath.org/authors/?q=ai:fan.ping"Xia, Hai-ying"https://www.zbmath.org/authors/?q=ai:xia.haiying"Song, Shuxiang"https://www.zbmath.org/authors/?q=ai:song.shuxiangSummary: The classical wavelet transform has been widely applied in the information processing field. It implies that quantum wavelet transform (QWT) may play an important role in quantum information processing. In this paper, we present the iteration equations of the general QWT using generalized tensor product. Then, Haar QWT (HQWT), Daubechies D4 QWT (DQWT), and their inverse transforms are proposed respectively. Meanwhile, the circuits of the two kinds of multi-level HQWT are designed. What's more, the multi-level DQWT based on the periodization extension is implemented for the first time. The complexity analysis shows that the proposed multi-level QWTs on \(2^n\) elements can be implemented by \(O(n^3)\) basic operations. Simulation experiments demonstrate that the proposed QWTs are correct and effective.A simple method for estimating the entropy of neural activity.https://www.zbmath.org/1456.920282021-04-16T16:22:00+00:00"Berry, Michael J. II"https://www.zbmath.org/authors/?q=ai:berry.michael-j-ii"Tkačik, Gašper"https://www.zbmath.org/authors/?q=ai:tkacik.gasper"Dubuis, Julien"https://www.zbmath.org/authors/?q=ai:dubuis.julien-o"Marre, Olivier"https://www.zbmath.org/authors/?q=ai:marre.olivier"Azeredo, Da Silveira Rava"https://www.zbmath.org/authors/?q=ai:azeredo.da-silveira-ravaMulti-source information diffusion in online social networks.https://www.zbmath.org/1456.940282021-04-16T16:22:00+00:00"Xiong, Fei"https://www.zbmath.org/authors/?q=ai:xiong.fei"Liu, Yun"https://www.zbmath.org/authors/?q=ai:liu.yun"Zhang, Hai-Feng"https://www.zbmath.org/authors/?q=ai:zhang.haifengLogical universality from a minimal two-dimensional glider gun.https://www.zbmath.org/1456.681032021-04-16T16:22:00+00:00"Gómez Soto, José Manuel"https://www.zbmath.org/authors/?q=ai:gomez-soto.jose-manuel"Wuensche, Andrew"https://www.zbmath.org/authors/?q=ai:wuensche.andrewSummary: To understand the underlying principles of self-organization and computation in cellular automata, it would be helpful to find the simplest form of the essential ingredients, glider guns and eaters, because then the dynamics would be easier to interpret. Such minimal components emerge spontaneously in the newly discovered Sayab rule, a binary two-dimensional cellular automaton with a Moore neighborhood and isotropic dynamics. The Sayab rule's glider gun, which has just four live cells at its minimal phases, can implement complex dynamical interactions and the gates required for logical universality.Minimal complete fault detection tests for circuits of functional elements in standard basis.https://www.zbmath.org/1456.941402021-04-16T16:22:00+00:00"Popkov, K. A."https://www.zbmath.org/authors/?q=ai:popkov.kirill-aSummary: for each Boolean function we calculate the exact value of the minimal possible length of a complete fault detection test for logic networks implementing this function in the basis ``conjunction, disjunction, negation'' under one-type stuck-at faults at outputs of gates.New results on Modular Inversion Hidden Number problem and inversive congruential generator.https://www.zbmath.org/1456.941202021-04-16T16:22:00+00:00"Xu, Jun"https://www.zbmath.org/authors/?q=ai:xu.jun"Sarkar, Santanu"https://www.zbmath.org/authors/?q=ai:sarkar.santanu"Hu, Lei"https://www.zbmath.org/authors/?q=ai:hu.lei"Wang, Huaxiong"https://www.zbmath.org/authors/?q=ai:wang.huaxiong"Pan, Yanbin"https://www.zbmath.org/authors/?q=ai:pan.yanbinSummary: The Modular Inversion Hidden Number problem (MIHNP), introduced by \textit{D. Boneh} et al. [Lect. Notes Comput. Sci. 2248, 36--51 (2001; Zbl 1062.94545)], is briefly described as follows: let \(\mathrm{MSB}_{\delta}(z)\) refer to the \(\delta\) most significant bits of \(z\). Given many samples \((t_i,\mathrm{MSB}_{\delta}((\alpha+t_i)^{-1}\bmod{p}))\) for random \(t_i\in\mathbb{Z}_p\), the goal is to recover the hidden number \(\alpha\in\mathbb{Z}_p\). MIHNP is an important class of Hidden Number problem.
For the entire collection see [Zbl 1428.94004].Middle-product learning with rounding problem and its applications.https://www.zbmath.org/1456.940432021-04-16T16:22:00+00:00"Bai, Shi"https://www.zbmath.org/authors/?q=ai:bai.shi"Boudgoust, Katharina"https://www.zbmath.org/authors/?q=ai:boudgoust.katharina"Das, Dipayan"https://www.zbmath.org/authors/?q=ai:das.dipayan"Roux-Langlois, Adeline"https://www.zbmath.org/authors/?q=ai:roux-langlois.adeline"Wen, Weiqiang"https://www.zbmath.org/authors/?q=ai:wen.weiqiang"Zhang, Zhenfei"https://www.zbmath.org/authors/?q=ai:zhang.zhenfeiSummary: \textit{M. Roşca} et al. [Lect. Notes Comput. Sci. 10403, 283--297 (2017; Zbl 1406.94078)] introduce a new variant of the Learning with Errors (LWE) problem, called the Middle-Product LWE (MP-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning with Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called middle-product computational learning with rounding, an adaption of the computational LWR problem over rings, introduced by \textit{L. Chen} et al. [ibid. 11272, 435--464 (2018; Zbl 1446.94115)]. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.
For the entire collection see [Zbl 1428.94008].Blind sensor calibration using approximate message passing.https://www.zbmath.org/1456.940172021-04-16T16:22:00+00:00"Schülke, Christophe"https://www.zbmath.org/authors/?q=ai:schulke.christophe"Caltagirone, Francesco"https://www.zbmath.org/authors/?q=ai:caltagirone.francesco"Zdeborová, Lenka"https://www.zbmath.org/authors/?q=ai:zdeborova.lenkaHilbert modular forms and codes over \(\mathbb{F}_{p^2}\).https://www.zbmath.org/1456.110772021-04-16T16:22:00+00:00"Brown, Jim"https://www.zbmath.org/authors/?q=ai:brown.jim-l"Gunsolus, Beren"https://www.zbmath.org/authors/?q=ai:gunsolus.beren"Lilly, Jeremy"https://www.zbmath.org/authors/?q=ai:lilly.jeremy"Manganiello, Felice"https://www.zbmath.org/authors/?q=ai:manganiello.feliceSummary: Let \(p\) be an odd prime and consider the finite field \(\mathbb{F}_{p^2}\). Given a linear code \(\mathcal{C}\subset\mathbb{F}_{p^2}^n\), we use algebraic number theory to construct an associated lattice \(\Lambda_{\mathcal{C}}\subset\mathcal{O}_L^n\) for \(L\) an algebraic number field and \(\mathcal{O}_L\) the ring of integers of \(L\). We attach a theta series \(\theta_{\Lambda_{\mathcal{C}}}\) to the lattice \(\Lambda_{\mathcal{C}}\) and prove a relation between \(\theta_{\Lambda_{\mathcal{C}}}\) and the complete weight enumerator evaluated on weight one theta series.Statistical mechanics approach to 1-bit compressed sensing.https://www.zbmath.org/1456.940212021-04-16T16:22:00+00:00"Xu, Yingying"https://www.zbmath.org/authors/?q=ai:xu.yingying"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyukiPSO image thresholding on images compressed via fuzzy transforms.https://www.zbmath.org/1456.682242021-04-16T16:22:00+00:00"Martino, Ferdinando Di"https://www.zbmath.org/authors/?q=ai:di-martino.ferdinando"Sessa, Salvatore"https://www.zbmath.org/authors/?q=ai:sessa.salvatoreSummary: We present a new multi-level image thresholding method in which a Chaotic Darwinian Particle Swarm Optimization algorithm is applied on images compressed by using Fuzzy Transforms. The method requires a partition of the pixels of the image under several thresholds which are obtained by maximizing a fuzzy entropy. The usage of compressed images produces benefits in terms of execution CPU times. In a pre-processing phase the best compression rate is found by comparing the grey level histograms of the source and compressed images. Comparisons with the classical Darwinian Particle Swarm Optimization multi-level image thresholding algorithm and other meta-heuristic algorithms are presented in terms of quality of the segmented image via PSNR and SSIM.A comprehensible form of the product of two Gaussian \(Q\) functions and its usefulness in \(\kappa-\mu\) shadowed fading distribution.https://www.zbmath.org/1456.940252021-04-16T16:22:00+00:00"Sadhwani, Dharmendra"https://www.zbmath.org/authors/?q=ai:sadhwani.dharmendra"Yadav, Ram Narayan"https://www.zbmath.org/authors/?q=ai:yadav.ram-narayanSummary: \textit{G. K. Karagiannidis} and \textit{A. S. Lioumpas} [``An improved approximation for the Gaussian \(Q\)-function'', IEEE Commun. Lett. 11, No. 8, 644--646 (2007)], contrary to other approximations, proposed a more accurate approximation of the Gaussian \(Q\) function and its integer powers, for all the positive arguments. However, when it is used to compute the symbol error probability (SEP) of various coherent digital modulation techniques over parametric fading distributions like the \(\kappa-\mu\) shadowed fading, it loses its analytical tractability. In this paper, using Taylor series approximation of the exponential function, we comprehend the approximation of interest (with accuracy intact) which facilitates in the simplification of the key integrals used in the SEP computation of digital modulation techniques over \(\kappa-\mu\) shadowed fading distribution. Apart from various applications, the significance of the \(\kappa-\mu\) shadowed fading statistics lies in the fact that it unifies most of the popular fading models like one sided Gaussian, Rayleigh, Nakagami-\(m\), Nakagami-\(q\), Rician, Rician-shadowed, \(\eta-\mu\) and \(\kappa-\mu\), under one umbrella. In order to show the utility of the proposed work, the SEP of hexagonal-QAM is calculated over Rayleigh fading channel which is one of the widely used cases of the \(\kappa-\mu\) shadowed fading distribution. Monte Carlo simulations have also been carried out to justify the accuracy of the analysis.Relay selection schemes in threshold DF cooperative systems with wireless power transfer.https://www.zbmath.org/1456.940062021-04-16T16:22:00+00:00"Yao, Jin"https://www.zbmath.org/authors/?q=ai:yao.jin"Ye, Jia"https://www.zbmath.org/authors/?q=ai:ye.jia"Pan, Gaofeng"https://www.zbmath.org/authors/?q=ai:pan.gaofeng"Xie, Yiyuan"https://www.zbmath.org/authors/?q=ai:xie.yiyuan"Feng, Quanyuan"https://www.zbmath.org/authors/?q=ai:feng.quanyuanSummary: In this work, a dual-hop cooperative wireless energy harvesting system, in which there are a source-destination \((S-D)\) pair and several relay candidates is considered. all relay candidates adopt threshold decode-and-forward (DF) relaying scheme to decide whether to aid \(S-D\) pair information transmission or not. We assumed that these relay candidates and \(S\) are all equipped with single receiving antenna while \(D\) is equipped multiple receiving antenna and adopts generalized selection combining scheme to achieve receiving diversity gain. We also consider that relay candidates and \(S\) can harvest energy from \(D\) with finite energy storage capacity under time switching scheme. Three kinds of best relay selection (RS) schemes based threshold (TH) DF relay scheme, that is, the TH optimal source-relay link, the TH optimal relay-destination link, and the TH optimal source-relay-destination link, are proposed and studied. Closed-form analytical expressions for the outage probability over the three proposed RS schemes are derived and verified by Monte-Carlo simulations.Non-sequential recursive pair substitution: some rigorous results.https://www.zbmath.org/1456.940362021-04-16T16:22:00+00:00"Benedetto, Dario"https://www.zbmath.org/authors/?q=ai:benedetto.dario"Caglioti, Emanuele"https://www.zbmath.org/authors/?q=ai:caglioti.emanuele"Gabrielli, Davide"https://www.zbmath.org/authors/?q=ai:gabrielli.davideBose-Fermi duality and entanglement entropies.https://www.zbmath.org/1456.810692021-04-16T16:22:00+00:00"Headrick, Matthew"https://www.zbmath.org/authors/?q=ai:headrick.matthew"Lawrence, Albion"https://www.zbmath.org/authors/?q=ai:lawrence.albion"Roberts, Matthew"https://www.zbmath.org/authors/?q=ai:roberts.matthew-mStereology with cylinder probes.https://www.zbmath.org/1456.621262021-04-16T16:22:00+00:00"Cruz-Orive, Luis Manuel"https://www.zbmath.org/authors/?q=ai:cruz-orive.luis-manuel"Gual-Arnau, Ximo"https://www.zbmath.org/authors/?q=ai:gual-arnau.ximoSummary: Intersection formulae of Crofton type for general geometric probes are well known in integral geometry. For the special case of cylinders with non necessarily convex directrix, however, no equivalent formula seems to exist in the literature. We derive this formula resorting to motion invariant probability elements associated with test systems, instead of using a traditional approach. Because cylinders are seldom used as probes in stereological practice, however, this note is mainly of a theoretical nature.Using low-density parity-check codes to improve the McEliece cryptosystem.https://www.zbmath.org/1456.940562021-04-16T16:22:00+00:00"Branco, Pedro"https://www.zbmath.org/authors/?q=ai:branco.pedro"Mateus, Paulo"https://www.zbmath.org/authors/?q=ai:mateus.paulo-c"Salema, Carlos"https://www.zbmath.org/authors/?q=ai:salema.carlos"Souto, André"https://www.zbmath.org/authors/?q=ai:souto.andreSummary: Developing secure and fast asymmetric cryptographic primitives is a priority in cryptography. This fact steams from high demand for fast communication involving an increasing amount of private and sensible information. To this end, we propose an efficient McEliece-based cryptosystem to handle large messages that can be easily implemented in hardware. The main idea is to incorporate Low-Density Parity-Check (LDPC) codes after several parallel runs of the original McEliece cryptosystem. In this way, we achieve a low circuit-depth complexity while profiting from the capability of LDPC codes to deal with high-dimensional data. The proposed cryptosystem is at least as hard as the original McEliece cryptosystem, and therefore, it is believed to be robust to quantum attacks. Moreover, known attacks to McEliece cryptosystems based on LDPC codes are ineffective against our proposal. The key size of the cryptosystem is roughly ten times smaller than the original McEliece for similar levels of security. Finally, we present a variant of the proposed cryptosystem that is resistant to adaptive indistinguishability chosen-chiphertext attacks (IND-CCA2), which is a desirable property that the original McEliece cryptosystem does not fulfill.Efficient chameleon hash functions in the enhanced collision resistant model.https://www.zbmath.org/1456.940922021-04-16T16:22:00+00:00"Khalili, Mojtaba"https://www.zbmath.org/authors/?q=ai:khalili.mojtaba"Dakhilalian, Mohammad"https://www.zbmath.org/authors/?q=ai:dakhilalian.mohammad"Susilo, Willy"https://www.zbmath.org/authors/?q=ai:susilo.willySummary: Chameleon hash functions are collision resistant when only the hashing keys of the functions are known. In particular, without the knowledge of the secret information, the chameleon hash function is merely like a regular cryptographic hash function, where it is hard to find collisions. However anyone who has trapdoor keys can efficiently generate pre-images for the chameleon hash function. In some applications, such as redactable blockchains, unfortunately the existing properties do not suffice and we need more features. Actually, it is required that without knowing the trapdoor keys, nobody can compute collisions, even if he can see collisions for arbitrary hash functions. In 2017, Ateniese et al. introduced the notion of chameleon hash functions in the enhanced collision resistant model and proposed a construction in the standard model satifying the features. To date, efficient constructions of this kind of chameleon hash functions remain as an open research problem. In this paper, we answer this problem affirmatively by presenting efficient constructions of the chameleon hash function satisfying the enhanced collision resistance. The contributions of this work are twofold. First, we show the weakness of previous work. Then, we proceed with proposing new schemes with more efficiency. Technically, we present a new chameleon hash function in the basic model and based on simple assumptions. This chameleon hash function is well compatible with Groth-Sahai proof systems and the Cramer-Shoup encryption schemes, and can be used as a stepping stone to construct an efficient chameleon hash function in the enhanced collision resistant model. Moreover, we show our basic chameleon hash can be combined with optimal ZK-SNARKs of Groth and Maller that leads to shorter sizes for chameleon hash function in the enhanced collision resistant model.Uniqueness and characterization theorems for generalized entropies.https://www.zbmath.org/1456.940322021-04-16T16:22:00+00:00"Enciso, Alberto"https://www.zbmath.org/authors/?q=ai:enciso.alberto"Tempesta, Piergiulio"https://www.zbmath.org/authors/?q=ai:tempesta.piergiulioThe role of entropy in topological quantum error correction.https://www.zbmath.org/1456.811332021-04-16T16:22:00+00:00"Beverland, Michael E."https://www.zbmath.org/authors/?q=ai:beverland.michael-e"Brown, Benjamin J."https://www.zbmath.org/authors/?q=ai:brown.benjamin-j"Kastoryano, Michael J."https://www.zbmath.org/authors/?q=ai:kastoryano.michael-j"Marolleau, Quentin"https://www.zbmath.org/authors/?q=ai:marolleau.quentinTypical reconstruction limits for distributed compressed sensing based on \(\ell_{2,1} \)-norm minimization and Bayesian optimal reconstruction.https://www.zbmath.org/1456.940182021-04-16T16:22:00+00:00"Shiraki, Yoshifumi"https://www.zbmath.org/authors/?q=ai:shiraki.yoshifumi"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyukiStatistical mechanics analysis of thresholding 1-bit compressed sensing.https://www.zbmath.org/1456.940222021-04-16T16:22:00+00:00"Xu, Yingying"https://www.zbmath.org/authors/?q=ai:xu.yingying"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyukiDouble circulant LCD codes over \(\mathbb{Z}_4\).https://www.zbmath.org/1456.941382021-04-16T16:22:00+00:00"Shi, Minjia"https://www.zbmath.org/authors/?q=ai:shi.minjia"Huang, Daitao"https://www.zbmath.org/authors/?q=ai:huang.daitao"Sok, Lin"https://www.zbmath.org/authors/?q=ai:sok.lin"Solé, Patrick"https://www.zbmath.org/authors/?q=ai:sole.patrickThe authors show the existence of LCD codes over \(Z_4\) by using the CRT approach to quasi-cyclic codes. This approach is explained in Section 3. Afterwards, in Section 4 they give the number of LCD double circulant codes over \(Z_4\) (Theorem 3). Assuming that the Artin conjecture holds, the authors show that there exists an infinite family of double circulant LCD \(Z_4\)-codes with special properties (Theorem 5). In Table 1 (Section 6), some examples with best parameters are given. Finally in Section 7, the authors give some open problems, e.g.~the challenging problem to extend the results from \(Z_4\) to \(Z_{2^m}\).
Reviewer: Carolin Hannusch (Debrecen)Counting Richelot isogenies between superspecial abelian surfaces.https://www.zbmath.org/1456.140552021-04-16T16:22:00+00:00"Katsura, Toshiyuki"https://www.zbmath.org/authors/?q=ai:katsura.toshiyuki"Takashima, Katsuyuki"https://www.zbmath.org/authors/?q=ai:takashima.katsuyukiSummary: \textit{W. Castryck} et al. [``Hash functions from superspecial genus-2 curves using Richelot isogenies'', J. Math. Crypt. 14, 268--292 (2020; \url{doi:10.1515/jmc-2019-0021})] used superspecial genus-2 curves and their Richelot isogeny graph for basing genus-2 isogeny cryptography, and recently, \textit{C. Costello} and \textit{B. Smith} [``The supersingular isogeny problem in genus 2 and beyond'', in: Post-quantum cryptography. Cham: Springer. 151--168 (2020)], devised an improved isogeny path-finding algorithm in the genus-2 setting. In order to establish a firm ground for the cryptographic construction and analysis, we give a new characterization of decomposed Richelot isogenies in terms of involutive reduced automorphisms of genus-2 curves over a finite field, and explicitly count such decomposed (and nondecomposed) Richelot isogenies between superspecial principally polarized abelian surfaces. As a corollary, we give another algebraic geometric proof of Theorem 2 in the paper of Castryck et al. [loc. cit.].
For the entire collection see [Zbl 1452.11005].A theoretical result of sparse signal recovery via alternating projection method.https://www.zbmath.org/1456.940152021-04-16T16:22:00+00:00"Liu, Haifeng"https://www.zbmath.org/authors/?q=ai:liu.haifeng"Peng, Jigen"https://www.zbmath.org/authors/?q=ai:peng.jigen"Lin, Zhipeng"https://www.zbmath.org/authors/?q=ai:lin.zhipengSummary: Compressive sensing is a technique that can sample compressible signals below the traditional rate. One of fundamental problems in compressive sensing is the sparse signal recovery. Recently, alternating projection method was proposed for this kind of recovery. Two sufficient conditions for the recovery guarantee of the method were also given. In this paper, we establish another sufficient condition for the recovery guarantee of alternating projection method in terms of the restricted isometry constants and singular values of the measurement matrix, it is a useful improvement on one of the existing two conditions. The famous Weyl inequality, Cauchy interlace theorem and partition skills of involved matrices are utilized. The requirement for the measurement matrix is lowered. Thus, this improvement allows more measurement matrices to be used for alternating projection method. This can enhance the applicability of the method.Cascading failure and recovery of spatially interdependent networks.https://www.zbmath.org/1456.941422021-04-16T16:22:00+00:00"Hong, Sheng"https://www.zbmath.org/authors/?q=ai:hong.sheng"Zhu, Juxing"https://www.zbmath.org/authors/?q=ai:zhu.juxing"Braunstein, Lidia A."https://www.zbmath.org/authors/?q=ai:braunstein.lidia-a"Zhao, Tingdi"https://www.zbmath.org/authors/?q=ai:zhao.tingdi"You, Qiuju"https://www.zbmath.org/authors/?q=ai:you.qiujuEvaluation codes and their basic parameters.https://www.zbmath.org/1456.140342021-04-16T16:22:00+00:00"Jaramillo, Delio"https://www.zbmath.org/authors/?q=ai:jaramillo.delio"Vaz Pinto, Maria"https://www.zbmath.org/authors/?q=ai:vaz-pinto.maria"Villarreal, Rafael H."https://www.zbmath.org/authors/?q=ai:villarreal.rafael-heraclioLet \(K=GF(q)\) denote the finite field with \(q\) elements, where \(q\) is a
prime power, and let \(S=K[t_1,\dots,t_s]\) be the polynomial ring associated
with the affine space \({\mathbb{A}}^s\).
If \(X=\{P_1,\dots,P_m\}\subset {\mathbb{A}}^s\) is a
finite set of points then we can define a \(K\)-linear
evaluation map
\[
mathrm{ev}_X:S\to K^m, \ \ mathrm{ev}_X(f)=(f(P_1),\dots,f(P_m)).
\]
If \(L\subset S\) is a finite dimensional space then
its image under \(mathrm{ev}_X\), \(L_X=mathrm{ev}_X(L)\), is called an
\textit{evaluation code} on \(X\).
In the paper under review, the authors study the basic parameters of the
family of evaluation codes and those of certain interesting
subfamilies. The parameters investigated are
(a) the length \(|X|\),
(b) the dimension \(\dim_K(L_X)\),
(c) the generalized Hamming weights \(\delta_r(L_X)\), \(1\leq r \leq \dim_K(L_X)\).
The first main result of the authors is a formula for
\(\delta_r(L_X)\) in terms of ring-theoretic data involving
\(S\), the vanishing ideal of \(X\) and related ideals. The second
main result is a lower bound for the
\(\delta_r(L_X)\) in terms of what they call the footprint of \(L_X\), a
quantity expressed in terms of ring-theoretic data.
These two results are applied to
toric codes and to ``squarefree'' evaluation codes,
when \(X\) is taken to be the set of all \(K\)-rational
points of the affine torus.
For those families of codes, the authors obtain explicit formulas for both the
minimum distance (namely, \(\delta_1(L_X)\)) and the second
generalized Hamming weight \(\delta_2(L_X)\).
The exact statements are too technical to state in this review,
so the reader is referred to the paper for details.
Reviewer: David Joyner (Annapolis)Group public key encryption with equality test against offline message recovery attack.https://www.zbmath.org/1456.940972021-04-16T16:22:00+00:00"Ling, Yunhao"https://www.zbmath.org/authors/?q=ai:ling.yunhao"Ma, Sha"https://www.zbmath.org/authors/?q=ai:ma.sha"Huang, Qiong"https://www.zbmath.org/authors/?q=ai:huang.qiong"Li, Ximing"https://www.zbmath.org/authors/?q=ai:li.ximing"Ling, Yunzhi"https://www.zbmath.org/authors/?q=ai:ling.yunzhiSummary: Public key encryption with equality test (PKEET) allows a tester to check whether two ciphertexts encrypted under different public keys contain the same message without decrypting them. In this paper, we first introduce group mechanism into PKEET and propose a new primitive, namely group public key encryption with equality test (G-PKEET). G-PKEET can resist the attack that the tester can recover the message from a given ciphertext by exhaustively guessing the message offline. Furthermore, the group mechanism makes PKEET supporting group granularity authorization, which could authorize a tester to perform the equality test only on ciphertexts of group users, and could greatly reduce not only the storage cost of trapdoors but also the cost of computation and communication. We define security models for G-PKEET, present its concrete construction in bilinear pairings and prove its security in the random oracle model.GVFOM: a novel external force for active contour based image segmentation.https://www.zbmath.org/1456.940132021-04-16T16:22:00+00:00"Zhang, Ziyang"https://www.zbmath.org/authors/?q=ai:zhang.ziyang"Duan, Chenrui"https://www.zbmath.org/authors/?q=ai:duan.chenrui"Lin, Tao"https://www.zbmath.org/authors/?q=ai:lin.tao.1|lin.tao"Zhou, Shoujun"https://www.zbmath.org/authors/?q=ai:zhou.shoujun"Wang, Yuanquan"https://www.zbmath.org/authors/?q=ai:wang.yuanquan"Gao, Xuedong"https://www.zbmath.org/authors/?q=ai:gao.xuedongSummary: The GVF snake is effective on converging into concave areas and being insensitive to initialization. However, it fails to converge to areas with deep and narrow concavities or preserve weak edges. In this paper, a novel external force called gradient vector flow over manifold (GVFOM) is proposed for active contours. The proposed model takes the GVF vector as a 2D manifold embedded into a 4D Euclidean space, leading to the generalization of the Laplacian operator in Euclidean Space to that over manifold, and the two components of the external force are couples with each other to improve the properties of the GVF snake. The GVFOM snake has been tested with different kinds of images, and experimental results and comparison manifest that the GVFOM snake has better performance than the GVF and other state-of-the-art snakes on object separation, deep and narrow concavity convergence, weak edge protection, noise robustness while keeping some desirable properties of the GVF model such as initialization insensitivity and large capture range.Improved (semi-free-start/near-) collision and distinguishing attacks on round-reduced RIPEMD-160.https://www.zbmath.org/1456.941182021-04-16T16:22:00+00:00"Wang, Gaoli"https://www.zbmath.org/authors/?q=ai:wang.gaoli"Liu, Fukang"https://www.zbmath.org/authors/?q=ai:liu.fukang"Cui, Binbin"https://www.zbmath.org/authors/?q=ai:cui.binbin"Mendel, Florian"https://www.zbmath.org/authors/?q=ai:mendel.florian"Dobraunig, Christoph"https://www.zbmath.org/authors/?q=ai:dobraunig.christophSummary: In this paper, we present an improved cryptanalysis of the double-branch hash function RIPEMD-160 standardized by ISO/IEC. First, how to theoretically calculate the step differential probability of RIPEMD-160 is solved, which was stated as an open problem by \textit{F. Mendel} et al. [Lect. Notes Comput. Sci. 8270, 484--503 (2013; Zbl 1326.94115)]. Then, we apply the start-from-the-middle framework to a newly discovered 32-step differential path of RIPEMD-160. Compared with the collision attack on 30 steps of RIPEMD-160 at [\textit{F. Liu} et al., ibid. 10624, 158--186 (2017; Zbl 1420.94084)], two steps are extended and the time complexity is \(2^{71.9}\). We propose a new start-from-the-middle near-collision attack framework, and achieve a near-collision attack on 39 steps of RIPEMD-160 with a time complexity of \(2^{65}\). For the semi-free-start collision attack on 36 steps of RIPEMD-160 at F. Mendel et al. [loc. cit.], by a different choice of the message words to merge two branches, adding some conditions on the starting point as well as solving the equation \(T^{\lll S_0}\boxplus C_0=(T\boxplus C_1)^{\lll S_1}(T\) is the variable) in an optimized way, the time complexity of this semi-free-start collision attack is reduced by a factor of \(2^{15.3}\) to \(2^{55.1}\). Finally, we present a 2-dimension sum distinguisher on 52 steps of RIPEMD-160 by using other message differences compared to ACNS 2012, which improves the best 2-dimension sum distinguisher on RIPEMD-160 by one step. Our attack takes into consideration the modular difference of the internal states when doing message modification in the first part of the differential path, and evaluating the probability of the last part of differential paths by experiment.Multimedia IPP codes with efficient tracing.https://www.zbmath.org/1456.941282021-04-16T16:22:00+00:00"Jiang, Jing"https://www.zbmath.org/authors/?q=ai:jiang.jing"Gu, Yujie"https://www.zbmath.org/authors/?q=ai:gu.yujie"Cheng, Minquan"https://www.zbmath.org/authors/?q=ai:cheng.minquanSummary: \textit{W. Trappe} et al. [IEEE Trans. Signal Process. 51, No. 4, 1069--1087 (2003; Zbl 1369.94591)] showed that fingerprinting system can be designed according to different criteria: catching one, catching many and catching all. For the case of ``catching many'', binary multimedia identifiable parent property codes \((t\)-MIPPCs) were introduced to construct fingerprints resistant to the averaging collusion attack on multimedia contents. In this paper, we focus on such a case, and introduce the binary strongly multimedia identifiable parent property code \((t\)-SMIPPC) whose tracing algorithm is more efficient than that of a binary \(t\)-MIPPC. Then a concatenation construction for binary \(t\)-SMIPPCs from \(q\)-ary \(t\)-SMIPPCs is provided. Moreover, we establish a probabilistic lower bound on \(q\)-ary \(t\)-SMIPPCs, whose code rate is asymptotically as good as that of \(q\)-ary \(t\)-MIPPCs. Finally, several infinite series of optimal \(q\)-ary \(t\)-SMIPPCs of length 2 with \(t=2,3\) are derived from the relationships among \(t\)-SMIPPCs and other fingerprinting codes, such as \(t\)-MIPPCs and \(\overline{t}\)-separable codes.Construction of a near-optimal quasi-complementary sequence set from almost difference set.https://www.zbmath.org/1456.940382021-04-16T16:22:00+00:00"Li, Yu"https://www.zbmath.org/authors/?q=ai:li.yu"Yan, Tongjiang"https://www.zbmath.org/authors/?q=ai:yan.tongjiang"Lv, Chuan"https://www.zbmath.org/authors/?q=ai:lv.chuanSummary: Compared with the perfect complementary sequence sets, quasi-complementary sequence sets (QCSSs) can support more users to work in multicarrier CDMA communications. A near-optimal periodic QCSS is constructed in this paper by using an optimal quaternary sequence set and an almost difference set. With the changes of the values of parameters in the QCSS, the number of users supported by the subcarrier channels in CDMA system has an exponential growth.A lower bound on the size of the largest metrically regular subset of the Boolean cube.https://www.zbmath.org/1456.941022021-04-16T16:22:00+00:00"Oblaukhov, Alexey"https://www.zbmath.org/authors/?q=ai:oblaukhov.alexeySummary: Let \(A\) be an arbitrary subset of the Boolean cube, and \(\widehat {A}\) be the set of all vectors of the Boolean cube, which are at the maximal possible distance from the set \(A\). If the set of all vectors at the maximal distance from \(\widehat {A}\) coincides with \(A\), then the set \(A\) is called a metrically regular set. The problem of investigating metrically regular sets appears when studying bent functions, which have important applications in cryptography and coding theory. In this work a special subclass of strongly metrically regular subsets of the Boolean cube is studied. An iterative construction of strongly metrically regular sets is obtained. The formula for the number of sets which can be obtained via this construction is derived. Constructions for two families of large metrically regular sets are presented. Exact sizes of sets from these families are calculated. These sizes give us the best lower bound on sizes of largest metrically regular subsets of the Boolean cube.Deterministic constructions of compressed sensing matrices based on codes.https://www.zbmath.org/1456.940202021-04-16T16:22:00+00:00"Wang, Gang"https://www.zbmath.org/authors/?q=ai:wang.gang.4|wang.gang.3|wang.gang|wang.gang.2|wang.gang.5|wang.gang.1"Niu, Min-Yao"https://www.zbmath.org/authors/?q=ai:niu.minyao"Fu, Fang-Wei"https://www.zbmath.org/authors/?q=ai:fu.fangweiSummary: Compressed sensing theory is a sampling technique which provides a fundamentally new approach to data acquisition and makes sure that a sparse signal can be reconstructed from few measurements by taking full use of sparsity. In this paper, firstly, the deterministic compressed sensing matrices using a sparse optimal compressed sensing matrix and codes are constructed, which is a generalization of \textit{X. Wang} et al.'s construction [Int. J. Found. Comput. Sci., 28, 99--109 (2017; Zbl 1379.94020)]. Then, using specific linear and nonlinear codes, we present deterministic constructions of compressed sensing matrices, which is a generalization of \textit{R. A. DeVore}'s construction [J. Complexity 23, No. 4--6, 918--925 (2007; Zbl 1134.94312)] and \textit{S. Li} et al.'s construction [ IEEE Trans. Inf. Theory, 58, 5035--5041 (2012; Zbl 1364.94696)]. Comparing with DeVore's matrices and Li et al.'s matrices, by using specific codes and an appropriate sparse optimal compressed sensing matrix, the compressed sensing matrices we construct are superior to DeVore's matrices and Li et al.'s matrices.Divisible e-cash from constrained pseudo-random functions.https://www.zbmath.org/1456.940552021-04-16T16:22:00+00:00"Bourse, Florian"https://www.zbmath.org/authors/?q=ai:bourse.florian"Pointcheval, David"https://www.zbmath.org/authors/?q=ai:pointcheval.david"Sanders, Olivier"https://www.zbmath.org/authors/?q=ai:sanders.olivierSummary: Electronic cash (e-cash) is the digital analogue of regular cash which aims at preserving users' privacy. Following \textit{D. Chaum}'s seminal work [in: Advances in Cryptology, Proc. Workshop Santa Barbara/Calif. 1982, 199--203 (1983; Zbl 0521.94012)], several new features were proposed for e-cash to address the practical issues of the original primitive. Among them, divisibility has proved very useful to enable efficient storage and spendings. Unfortunately, it is also very difficult to achieve and, to date, quite a few constructions exist, all of them relying on complex mechanisms that can only be instantiated in one specific setting. In addition security models are incomplete and proofs sometimes hand-wavy.
In this work, we first provide a complete security model for divisible e-cash, and we study the links with constrained pseudo-random functions (PRFs), a primitive recently formalized by \textit{D. Boneh} and \textit{B. Waters} [Lect. Notes Comput. Sci. 8270, 280--300 (2013; Zbl 1314.94057)]. We exhibit two frameworks of divisible e-cash systems from constrained PRFs achieving some specific properties: either key homomorphism or delegability. We then formally prove these frameworks, and address two main issues in previous constructions: two essential security notions were either not considered at all or not fully proven. Indeed, we introduce the notion of clearing, which should guarantee that only the recipient of a transaction should be able to do the deposit, and we show the exculpability, that should prevent an honest user to be falsely accused, was wrong in most proofs of the previous constructions. Some can easily be repaired, but this is not the case for most complex settings such as constructions in the standard model. Consequently, we provide the first construction secure in the standard model, as a direct instantiation of our framework.
For the entire collection see [Zbl 1428.94008].Settling the mystery of \(Z_{r} = r\) in RC4.https://www.zbmath.org/1456.940722021-04-16T16:22:00+00:00"Dey, Sabyasachi"https://www.zbmath.org/authors/?q=ai:dey.sabyasachi"Sarkar, Santanu"https://www.zbmath.org/authors/?q=ai:sarkar.santanuSummary: In this paper, using a matrix, at first we revisit the work of \textit{I. Mantin} [Analysis of the stream cipher RC4. Master's Thesis. The Weizmann Institute of Science, Israel (2001)] on finding the probability distribution of the RC4 permutation after the completion of the KSA. After that, we extend the same idea to analyse the probabilities during any iteration of the Pseudo Random Generation Algorithm. Next, we study the bias of \(Z_{r} = r\) (where \(Z_{r}\) is the \(r\)-th output keystream byte), which is one of the significant biases observed in the RC4 output keystream. This bias has played an important role in the plaintext recovery attack proposed by \textit{T. Isobe} et al. [FSE 2013, Lect. Notes Comput. Sci. 8424, 179--202 (2014; Zbl 1321.94064)]. However, the accurate theoretical explanation of the bias of \(Z_{r} = r\) is still a mystery. Though several attempts have been made to prove this bias, none of those provides an accurate justification. Here, using the results found with the help of the probability transition matrix we justify this bias of \(Z_{r} = r\) accurately and settle this issue. The bias obtained from our proof matches the experimental observations perfectly.Qfactory: classically-instructed remote secret qubits preparation.https://www.zbmath.org/1456.940662021-04-16T16:22:00+00:00"Cojocaru, Alexandru"https://www.zbmath.org/authors/?q=ai:cojocaru.alexandru"Colisson, Léo"https://www.zbmath.org/authors/?q=ai:colisson.leo"Kashefi, Elham"https://www.zbmath.org/authors/?q=ai:kashefi.elham"Wallden, Petros"https://www.zbmath.org/authors/?q=ai:wallden.petrosSummary: The functionality of classically-instructed remotely prepared random secret qubits was introduced in [\textit{A. Cojocaru} et al. ``On the possibility of classical client blind quantum computing'', Preprint, \url{arXiv:1802.08759}] as a way to enable classical parties to participate in secure quantum computation and communications protocols. The idea is that a classical party (client) instructs a quantum party (server) to generate a qubit to the server's side that is random, unknown to the server but known to the client. Such task is only possible under computational assumptions. In this contribution we define a simpler (basic) primitive consisting of only BB84 states, and give a protocol that realizes this primitive and that is secure against the strongest possible adversary (an arbitrarily deviating malicious server). The specific functions used, were constructed based on known trapdoor one-way functions, resulting to the security of our basic primitive being reduced to the hardness of the Learning with Errors problem. We then give a number of extensions, building on this basic module: extension to larger set of states (that includes non-Clifford states); proper consideration of the abort case; and verifiablity on the module level. The latter is based on ``blind self-testing'', a notion we introduced, proved in a limited setting and conjectured its validity for the most general case.
For the entire collection see [Zbl 1428.94008].Quantum random oracle model with auxiliary input.https://www.zbmath.org/1456.940842021-04-16T16:22:00+00:00"Hhan, Minki"https://www.zbmath.org/authors/?q=ai:hhan.minki"Xagawa, Keita"https://www.zbmath.org/authors/?q=ai:xagawa.keita"Yamakawa, Takashi"https://www.zbmath.org/authors/?q=ai:yamakawa.takashiSummary: The random oracle model (ROM) is an idealized model where hash functions are modeled as random functions that are only accessible as oracles. Although the ROM has been used for proving many cryptographic schemes, it has (at least) two problems. First, the ROM does not capture quantum adversaries. Second, it does not capture non-uniform adversaries that perform preprocessings. To deal with these problems, \textit{D. Boneh} et al. [Lect. Notes Comput. Sci. 7073, 41--69 (2011; Zbl 1227.94033)] proposed using the quantum ROM (QROM) to argue post-quantum security, and \textit{D. Unruh} [ibid. 4622, 205--223 (2007; Zbl 1215.94071)] proposed the ROM with auxiliary input (ROM-AI) to argue security against preprocessing attacks. However, to the best of our knowledge, no work has dealt with the above two problems simultaneously.
In this paper, we consider a model that we call the QROM with (classical) auxiliary input (QROM-AI) that deals with the above two problems simultaneously and study security of cryptographic primitives in the model. That is, we give security bounds for one-way functions, pseudorandom generators, (post-quantum) pseudorandom functions, and (post-quantum) message authentication codes in the QROM-AI.
We also study security bounds in the presence of quantum auxiliary inputs. In other words, we show a security bound for one-wayness of random permutations (instead of random functions) in the presence of quantum auxiliary inputs. This resolves an open problem posed by \textit{A. Nayebi} et al. [``Quantum lower bound for inverting a permutation with advice'', Quantum Inf. Comput. 15, No. 11--12, 901--913 (2015; \url{doi:10.5555/2871350.2871351})]. In a context of complexity theory, this implies \(\mathrm{NP}\cap\mathrm{coNP}\not\subseteq\mathrm{BQP/qpoly}\) relative to a random permutation oracle, which also answers an open problem posed by \textit{S. Aaronson} [Theory Comput. 1, Paper No. 1, 1--28 (2005; Zbl 1213.68278)].
For the entire collection see [Zbl 1428.94008].Quantum attacks without superposition queries: the offline Simon's algorithm.https://www.zbmath.org/1456.940522021-04-16T16:22:00+00:00"Bonnetain, Xavier"https://www.zbmath.org/authors/?q=ai:bonnetain.xavier"Hosoyamada, Akinori"https://www.zbmath.org/authors/?q=ai:hosoyamada.akinori"Naya-Plasencia, María"https://www.zbmath.org/authors/?q=ai:naya-plasencia.maria"Sasaki, Yu"https://www.zbmath.org/authors/?q=ai:sasaki.yu"Schrottenloher, André"https://www.zbmath.org/authors/?q=ai:schrottenloher.andreSummary: In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.
In this paper, we introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time \(\tilde{O}(2^{n/3})\), with \(O(2^{n/3})\) classical queries and \(O(n^2)\) qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.
Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover's algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.
We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.
For the entire collection see [Zbl 1428.94008].Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving.https://www.zbmath.org/1456.940932021-04-16T16:22:00+00:00"Kirshanova, Elena"https://www.zbmath.org/authors/?q=ai:kirshanova.elena"Mårtensson, Erik"https://www.zbmath.org/authors/?q=ai:martensson.erik"Postlethwaite, Eamonn W."https://www.zbmath.org/authors/?q=ai:postlethwaite.eamonn-w"Moulik, Subhayan Roy"https://www.zbmath.org/authors/?q=ai:moulik.subhayan-roySummary: The Shortest Vector problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a \(d\)-dimensional lattice in \(2^{\mathsf{c}d+o(d)}\) time steps with \(2^{\mathsf{c}^\prime d+o(d)}\) memory for constants \(c, c^\prime\). In this work, we give various quantum sieving algorithms that trade computational steps for memory.
We first give a quantum analogue of the classical \(k\)-Sieve algorithm [\textit{G. Herold} et al., Lect. Notes Comput. Sci. 10769, 407--436 (2018; Zbl 1439.94033)] in the quantum random access memory (QRAM) model, achieving an algorithm that heuristically solves SVP in \(2^{0.2989d+o(d)}\) time steps using \(2^{0.1395d+o(d)}\) memory. This should be compared to the state-of-the-art algorithm [\textit{T. Laarhoven} [Search problems in cryptography. Eindhoven University of Technology (PhD Thesis) (2015)] which, in the same model, solves SVP in \(2^{0.2653d+o(d)}\) time steps and memory. In the QRAM model these algorithms can be implemented using \(\mathrm{poly}(d)\) width quantum circuits. Secondly, we frame the \(k\)-Sieve as the problem of \(k\)-clique listing in a graph and apply quantum \(k\)-clique finding techniques to the \(k\)-Sieve.
Finally, we explore the large quantum memory regime by adapting parallel quantum search [\textit{R. Beals} et al., Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 469, No. 2153, Article ID 20120686, 20 p. (2013; Zbl 1371.81074)] to the 2-Sieve, and give an analysis in the quantum circuit model. We show how to solve SVP in \(2^{0.1037d+o(d)}\) time steps using \(2^{0.2075d+o(d)}\) quantum memory.
For the entire collection see [Zbl 1428.94008].Card-based cryptography meets formal verification.https://www.zbmath.org/1456.940942021-04-16T16:22:00+00:00"Koch, Alexander"https://www.zbmath.org/authors/?q=ai:koch.alexander-k"Schrempp, Michael"https://www.zbmath.org/authors/?q=ai:schrempp.michael"Kirsten, Michael"https://www.zbmath.org/authors/?q=ai:kirsten.michaelSummary: Card-based cryptography provides simple and practicable protocols for performing secure multi-party computation (MPC) with just a deck of cards. For the sake of simplicity, this is often done using cards with only two symbols, e.g., \(\clubsuit\) and \(\heartsuit\). Within this paper, we target the setting where all cards carry distinct symbols, catering for use-cases with commonly available standard decks and a weaker indistinguishability assumption. As of yet, the literature provides for only three protocols and no proofs for non-trivial lower bounds on the number of cards. As such complex proofs (handling very large combinatorial state spaces) tend to be involved and error-prone, we propose using formal verification for finding protocols and proving lower bounds. In this paper, we employ the technique of software bounded model checking (SBMC), which reduces the problem to a bounded state space, which is automatically searched exhaustively using a SAT solver as a backend.
Our contribution is twofold: (a) We identify two protocols for converting between different bit encodings with overlapping bases, and then show them to be card-minimal. This completes the picture of tight lower bounds on the number of cards with respect to runtime behavior and shuffle properties of conversion protocols. For computing AND, we show that there is no protocol with finite runtime using four cards with distinguishable symbols and fixed output encoding, and give a four-card protocol with an expected finite runtime using only random cuts. (b) We provide a general translation of proofs for lower bounds to a bounded model checking framework for automatically finding card- and length-minimal protocols and to give additional confidence in lower bounds. We apply this to validate our method and, as an example, confirm our new AND protocol to have a shortest run for protocols using this number of cards.
For the entire collection see [Zbl 1428.94008].Beyond honest majority: the round complexity of fair and robust multi-party computation.https://www.zbmath.org/1456.941042021-04-16T16:22:00+00:00"Patra, Arpita"https://www.zbmath.org/authors/?q=ai:patra.arpita"Ravi, Divya"https://www.zbmath.org/authors/?q=ai:ravi.divyaSummary: Two of the most sought-after properties of multi-party computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however, brings in the necessary requirement of malicious-minority. In a generalised adversarial setting where the adversary is allowed to corrupt both actively and passively, the necessary bound for a \(n\)-party fair or robust protocol turns out to be \(t_a+t_p<n\), where \(t_a\), \(t_p\) denote the threshold for active and passive corruption with the latter subsuming the former. Subsuming the malicious-minority as a boundary special case, this setting, denoted as dynamic corruption, opens up a range of possible corruption scenarios for the adversary. While dynamic corruption includes the entire range of thresholds for \((t_a,t_p)\) starting from \((\lceil\frac{n}{2}\rceil-1,\lfloor n/2 \rfloor)\) to \((0,n-1)\), the boundary corruption restricts the adversary only to the boundary cases of \((\lceil\frac{n}{2} \rceil-1,\lfloor n/2\rfloor)\) and \((0,n-1)\). Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond \(\lceil\frac{n}{2}\rceil-1\). We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, \(\lceil n/2\rceil+1\) rounds are necessary and sufficient for fair as well as robust MPC tolerating dynamic corruption. The non-constant barrier raised by dynamic corruption can be sailed through for a boundary adversary. The round complexity of 3 and 4 is necessary and sufficient for fair and GOD protocols respectively, with the latter having an exception of allowing 3 round protocols in the presence of a single active corruption. While all our lower bounds assume pair-wise private and broadcast channels and are resilient to the presence of both public (CRS) and private (PKI) setup, our upper bounds are broadcast-only and assume only public setup. The traditional and popular setting of malicious-minority, being restricted compared to both dynamic and boundary setting, requires 3 and 2 rounds in the presence of public and private setup respectively for both fair as well as GOD protocols.
For the entire collection see [Zbl 1428.94008].The broadcast message complexity of secure multiparty computation.https://www.zbmath.org/1456.940772021-04-16T16:22:00+00:00"Garg, Sanjam"https://www.zbmath.org/authors/?q=ai:garg.sanjam"Goel, Aarushi"https://www.zbmath.org/authors/?q=ai:goel.aarushi"Jain, Abhishek"https://www.zbmath.org/authors/?q=ai:jain.abhishekSummary: We study the broadcast message complexity of secure multiparty computation (MPC), namely, the total number of messages that are required for securely computing any functionality in the broadcast model of communication.
MPC protocols are traditionally designed in the simultaneous broadcast model, where each round consists of every party broadcasting a message to the other parties. We show that this method of communication is sub-optimal; specifically, by eliminating simultaneity, it is, in fact, possible to reduce the broadcast message complexity of MPC.
More specifically, we establish tight lower and upper bounds on the broadcast message complexity of \(n\)-party MPC for every \(t<n\) corruption threshold, both in the plain model as well as common setup models. For example, our results show that the optimal broadcast message complexity of semi-honest MPC can be much lower than \(2n\), but necessarily requires at least three rounds of communication. We also extend our results to the malicious setting in setup models.
For the entire collection see [Zbl 1428.94008].Typical reconstruction performance for distributed compressed sensing based on \(\ell_{2,1} \)-norm regularized least square and Bayesian optimal reconstruction: influences of noise.https://www.zbmath.org/1456.940192021-04-16T16:22:00+00:00"Shiraki, Yoshifumi"https://www.zbmath.org/authors/?q=ai:shiraki.yoshifumi"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyukiCollusion resistant watermarking schemes for cryptographic functionalities.https://www.zbmath.org/1456.941292021-04-16T16:22:00+00:00"Yang, Rupeng"https://www.zbmath.org/authors/?q=ai:yang.rupeng"Au, Man Ho"https://www.zbmath.org/authors/?q=ai:au.man-ho"Lai, Junzuo"https://www.zbmath.org/authors/?q=ai:lai.junzuo"Xu, Qiuliang"https://www.zbmath.org/authors/?q=ai:xu.qiuliang"Yu, Zuoxia"https://www.zbmath.org/authors/?q=ai:yu.zuoxiaSummary: A cryptographic watermarking scheme embeds a message into a program while preserving its functionality. Recently, a number of watermarking schemes have been proposed, which are proven secure in the sense that given one marked program, any attempt to remove the embedded message will substantially change its functionality.
In this paper, we formally initiate the study of collusion attacks for watermarking schemes, where the attacker's goal is to remove the embedded messages given multiple copies of the same program, each with a different embedded message. This is motivated by practical scenarios, where a program may be marked multiple times with different messages.
The results of this work are twofold. First, we examine existing cryptographic watermarking schemes and observe that all of them are vulnerable to collusion attacks. Second, we construct collusion resistant watermarking schemes for various cryptographic functionalities (e.g., pseudorandom function evaluation, decryption, etc.). To achieve our second result, we present a new primitive called puncturable functional encryption scheme, which may be of independent interest.
For the entire collection see [Zbl 1428.94008].Dual-mode NIZKs from obfuscation.https://www.zbmath.org/1456.940852021-04-16T16:22:00+00:00"Hofheinz, Dennis"https://www.zbmath.org/authors/?q=ai:hofheinz.dennis"Ursu, Bogdan"https://www.zbmath.org/authors/?q=ai:ursu.bogdanSummary: Two standard security properties of a non-interactive zero-knowledge (NIZK) scheme are soundness and zero-knowledge. But while standard NIZK systems can only provide one of those properties against unbounded adversaries, dual-mode NIZK systems allow to choose dynamically and adaptively which of these properties holds unconditionally. The only known dual-mode NIZK schemes are Groth-Sahai proofs (which have proved extremely useful in a variety of applications), and the FHE-based NIZK constructions of \textit{R. Canetti} et al. [Lect. Notes Comput. Sci. 9015, 468--497 (2015; Zbl 1382.94078)] and \textit{C. Peikert} et al. [ibid. 5157, 554--571 (2008; Zbl 1183.94046)], which are concurrent and independent to this work. However, all these constructions rely on specific algebraic settings.
Here, we provide a generic construction of dual-mode NIZK systems for all of NP. The public parameters of our scheme can be set up in one of two indistinguishable ways. One way provides unconditional soundness, while the other provides unconditional zero-knowledge. Our scheme relies on subexponentially secure indistinguishability obfuscation and subexponentially secure one-way functions, but otherwise only on comparatively mild and generic computational assumptions. These generic assumptions can be instantiated under any one of the DDH, \(k\)-LIN, DCR, or QR assumptions.
As an application, we reduce the required assumptions necessary for several recent obfuscation-based constructions of multilinear maps. Combined with previous work, our scheme can be used to construct multilinear maps from obfuscation and a group in which the strong Diffie-Hellman assumption holds. We also believe that our work adds to the understanding of the construction of NIZK systems, as it provides a conceptually new way to achieve dual-mode properties.
For the entire collection see [Zbl 1428.94008].Strongly secure authenticated key exchange from supersingular isogenies.https://www.zbmath.org/1456.941212021-04-16T16:22:00+00:00"Xu, Xiu"https://www.zbmath.org/authors/?q=ai:xu.xiu"Xue, Haiyang"https://www.zbmath.org/authors/?q=ai:xue.haiyang"Wang, Kunpeng"https://www.zbmath.org/authors/?q=ai:wang.kunpeng"Au, Man Ho"https://www.zbmath.org/authors/?q=ai:au.man-ho"Tian, Song"https://www.zbmath.org/authors/?q=ai:tian.songSummary: This paper aims to address the open problem, namely, to find new techniques to design and prove security of supersingular isogeny-based authenticated key exchange (AKE) protocols against the widest possible adversarial attacks, raised by Galbraith in 2018. Concretely, we present two AKEs based on a double-key PKE in the supersingular isogeny setting secure in the sense of \(CK^+\), one of the strongest security models for AKE. Our contributions are summarised as follows. Firstly, we propose a strong OW-CPA secure PKE, \(\mathrm{2PKE_{sidh}}\), based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a [OW-CCA, OW-CPA] secure KEM, \(\mathrm{2KEM_{sidh}}\). Secondly, we propose a two-pass AKE, \(\mathrm{SIAKE}_2\), based on SI-DDH assumption, using \(\mathrm{2KEM_{sidh}}\) as a building block. Thirdly, we present a modified version of \(\mathrm{2KEM_{sidh}}\) that is secure against leakage under the 1-Oracle SI-DH assumption. Using the modified \(\mathrm{2KEM_{sidh}}\) as a building block, we then propose a three-pass AKE, \(\mathrm{SIAKE}_3\), based on 1-Oracle SI-DH assumption. Finally, we prove that both \(\mathrm{SIAKE}_2\) and \(\mathrm{SIAKE}_3\) are \(\mathrm{CK}^+\) secure in the random oracle model and supports arbitrary registration. We also provide an implementation to illustrate the efficiency of our schemes. Our schemes compare favourably against existing isogeny-based AKEs. To the best of our knowledge, they are the first of its kind to offer security against arbitrary registration, wPFS, KCI, and MEX simultaneously. Regarding efficiency, our schemes outperform existing schemes in terms of bandwidth as well as CPU cycle count.
For the entire collection see [Zbl 1428.94008].Verifiable delay functions from supersingular isogenies and pairings.https://www.zbmath.org/1456.940702021-04-16T16:22:00+00:00"De Feo, Luca"https://www.zbmath.org/authors/?q=ai:de-feo.luca"Masson, Simon"https://www.zbmath.org/authors/?q=ai:masson.simon"Petit, Christophe"https://www.zbmath.org/authors/?q=ai:petit.christophe.2|petit.christophe.1"Sanso, Antonio"https://www.zbmath.org/authors/?q=ai:sanso.antonioSummary: We present two new verifiable delay functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.
For the entire collection see [Zbl 1428.94008].CSI-FiSh: efficient isogeny based signatures through class group computations.https://www.zbmath.org/1456.940502021-04-16T16:22:00+00:00"Beullens, Ward"https://www.zbmath.org/authors/?q=ai:beullens.ward"Kleinjung, Thorsten"https://www.zbmath.org/authors/?q=ai:kleinjung.thorsten"Vercauteren, Frederik"https://www.zbmath.org/authors/?q=ai:vercauteren.frederikSummary: In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first sketched by \textit{A. Stolbunov} [Cryptographic schemes based on isogenies. Trondheim: Norwegian University of Science and Technology (PhD Thesis) (2012)]. We further optimize the scheme using multiple public keys and Merkle trees, following an idea by \textit{L. De Feo} and \textit{S. D. Galbraith} [Lect. Notes Comput. Sci. 11478, 759--789 (2019; Zbl 07162747)]. We also show that including quadratic twists allows to cut the public key size in half for free. Optimizing for signature size, our implementation takes 390 ms to sign/verify and results in signatures of 263 bytes, at the expense of a large public key. This is 300 times faster and over 3 times smaller than an optimized version of SeaSign for the same parameter set. Optimizing for public key and signature size combined, results in a total size of 1468 bytes, which is smaller than any other post-quantum signature scheme at the 128-bit security level.
For the entire collection see [Zbl 1428.94008].Anomalies and vector space search: tools for S-box analysis.https://www.zbmath.org/1456.940532021-04-16T16:22:00+00:00"Bonnetain, Xavier"https://www.zbmath.org/authors/?q=ai:bonnetain.xavier"Perrin, Léo"https://www.zbmath.org/authors/?q=ai:perrin.leo"Tian, Shizhu"https://www.zbmath.org/authors/?q=ai:tian.shizhuSummary: S-boxes are functions with an input so small that the simplest way to specify them is their lookup table (LUT). How can we quantify the distance between the behavior of a given S-box and that of an S-box picked uniformly at random?
To answer this question, we introduce various ``anomalies''. These real numbers are such that a property with an anomaly equal to \(a\) should be found roughly once in a set of \(2^a\) random S-boxes. First, we present statistical anomalies based on the distribution of the coefficients in the difference distribution table, linear approximation table, and for the first time, the boomerang connectivity table.
We then count the number of S-boxes that have block-cipher like structures to estimate the anomaly associated to those. In order to recover these structures, we show that the most general tool for decomposing S-boxes is an algorithm efficiently listing all the vector spaces of a given dimension contained in a given set, and we present such an algorithm.
Combining these approaches, we conclude that all permutations that are actually picked uniformly at random always have essentially the same cryptographic properties and the same lack of structure.
For the entire collection see [Zbl 1428.94008].Indifferentiability of truncated random permutations.https://www.zbmath.org/1456.940652021-04-16T16:22:00+00:00"Choi, Wonseok"https://www.zbmath.org/authors/?q=ai:choi.wonseok"Lee, Byeonghak"https://www.zbmath.org/authors/?q=ai:lee.byeonghak"Lee, Jooyoung"https://www.zbmath.org/authors/?q=ai:lee.jooyoungSummary: One of natural ways of constructing a pseudorandom function from a pseudorandom permutation is to simply truncate the output of the permutation. When \(n\) is the permutation size and \(m\) is the number of truncated bits, the resulting construction is known to be indistinguishable from a random function up to \(2^{\frac{n+m}{2}}\) queries, which is tight.
In this paper, we study the indifferentiability of a truncated random permutation where a fixed prefix is prepended to the inputs. We prove that this construction is (regularly) indifferentiable from a public random function up to \(\mathrm{min}\{2^{\frac{n+m}{3}},2^m, 2^\ell \}\) queries, while it is publicly indifferentiable up to \(\mathrm{min}\{\mathrm{max}\{2^{\frac{n+m}{3}},2^{\frac{n}{2}}\},2^\ell\}\) queries, where \(\ell\) is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when \(m+\ell\ll n\).
Our results significantly improve upon the previous bound of \(\min\{ 2^{\frac{m}{2}},2^\ell\}\) given by \textit{Y. Dodis} et al. [Lect. Notes Comput. Sci. 5665, 104--121 (2009; Zbl 1248.94065)], allowing us to construct, for instance, an \(\frac{n}{2}\)-to-\(\frac{n}{2}\) bit random function that makes a single call to an \(n\)-bit permutation, achieving \(\frac{n}{2}\)-bit security.
For the entire collection see [Zbl 1428.94008].4-round Luby-Rackoff construction is a qPRP.https://www.zbmath.org/1456.940862021-04-16T16:22:00+00:00"Hosoyamada, Akinori"https://www.zbmath.org/authors/?q=ai:hosoyamada.akinori"Iwata, Tetsu"https://www.zbmath.org/authors/?q=ai:iwata.tetsuSummary: The Luby-Rackoff construction, or the Feistel construction, is one of the most important approaches to construct secure block ciphers from secure pseudorandom functions. The 3- and 4-round Luby-Rackoff constructions are proven to be secure against chosen-plaintext attacks (CPAs) and chosen-ciphertext attacks (CCAs), respectively, in the classical setting. However, \textit{H. Kuwakado} and \textit{M. Morii} [``Quantum distinguisher between the 3-round Feistel cipher and the random permutation'', in: Proceedings of the 2010 IEEE international symposium on information theory, ISIT 2010, Austin, TX, USA, June 13--18, 2010. Piscataway, NJ: IEEE. 2682--2685 (2010; \url{doi:10.1109/ISIT.2010.5513654})] showed that a quantum superposed chosen-plaintext attack (qCPA) can distinguish the 3-round Luby-Rackoff construction from a random permutation in polynomial time. In addition, Ito et al. recently showed a quantum superposed chosen-ciphertext attack (qCCA) that distinguishes the 4-round Luby-Rackoff construction. Since H. Kuwakado and M. Morii [loc. cit.] showed the result, a problem of much interest has been how many rounds are sufficient to achieve provable security against quantum query attacks. This paper answers to this fundamental question by showing that 4-rounds suffice against qCPAs. Concretely, we prove that the 4-round Luby-Rackoff construction is secure up to \(O(2^{n/12})\) quantum queries. We also give a query upper bound for the problem of distinguishing the 4-round Luby-Rackoff construction from a random permutation by showing a distinguishing qCPA with \(O(2^{n/6})\) quantum queries. Our result is the first to demonstrate the security of a typical block-cipher construction against quantum query attacks, without any algebraic assumptions. To give security proofs, we use an alternative formalization of Zhandry's compressed oracle technique.
For the entire collection see [Zbl 1428.94008].Towards attribute-based encryption for RAMs from LWE: sub-linear decryption, and more.https://www.zbmath.org/1456.940422021-04-16T16:22:00+00:00"Ananth, Prabhanjan"https://www.zbmath.org/authors/?q=ai:ananth.prabhanjan-vijendra"Fan, Xiong"https://www.zbmath.org/authors/?q=ai:fan.xiong"Shi, Elaine"https://www.zbmath.org/authors/?q=ai:shi.elaineSummary: Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key is represented by a random access machine (RAM) and a database, with the runtime of the RAM program being sublinear in the database size. In this work we study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of \textit{S. Goldwasser} et al. [Lect. Notes Comput. Sci. 8043, 536--553 (2013; Zbl 1311.94082)]. We present a construction of attribute based encryption for RAMs satisfying sublinear decryption complexity assuming learning with errors; this is the first construction based on standard assumptions. Previously, S. Goldwasser et al. [loc. cit] achieved this result based on non-falsifiable knowledge assumptions. We also consider a dual notion of ABE for RAMs, where the database is in the ciphertext and we show how to achieve this dual notion, albeit with large attribute keys, also based on learning with errors.
For the entire collection see [Zbl 1428.94008].A novel CCA attack using decryption errors against LAC.https://www.zbmath.org/1456.940802021-04-16T16:22:00+00:00"Guo, Qian"https://www.zbmath.org/authors/?q=ai:guo.qian"Johansson, Thomas"https://www.zbmath.org/authors/?q=ai:johansson.thomas"Yang, Jing"https://www.zbmath.org/authors/?q=ai:yang.jingSummary: Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST post-quantum cryptography standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme LAC, a proposal to the NIST post-quantum cryptography standardization that has advanced to round 2.
In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding LAC256, the version for achieving the 256-bit classical security level, we recover one key among approximately \(2^{64}\) public keys with complexity \(2^{79}\), if the precomputation cost of \(2^{162}\) is excluded. We also show the possibility to attack a more probable key (say with probability \(2^{-16})\). This attack is verified via extensive simulation.
We further apply this attack to LAC256-v2, a new version of LAC256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from \(2^{162}\) to \(2^{171})\). One can also explain this attack in the single-key setting as an attack with precomputation complexity of \(2^{171}\) and success probability of \(2^{-64}\).
For the entire collection see [Zbl 1428.94008].A new rank metric for convolutional codes.https://www.zbmath.org/1456.150272021-04-16T16:22:00+00:00"Almeida, P."https://www.zbmath.org/authors/?q=ai:almeida.paulo-j"Napp, D."https://www.zbmath.org/authors/?q=ai:napp.diegoSummary: Let \(\mathbb{F}[D]\) be the polynomial ring with entries in a finite field \(\mathbb{F}\). Convolutional codes are submodules of \(\mathbb{F} [D]^n\) that can be described by left prime polynomial matrices. In the last decade there has been a great interest in convolutional codes equipped with a rank metric, called sum rank metric, due to their wide range of applications in reliable linear network coding. However, this metric suits only for delay free networks. In this work we continue this thread of research and introduce a new metric that overcomes this restriction and therefore is suitable to handle more general networks. We study this metric and provide characterizations of the distance properties in terms of the polynomial matrix representations of the convolutional code. Convolutional codes that are optimal with respect to this new metric are investigated and concrete constructions are presented. These codes are the analogs of Maximum Distance Profile convolutional codes in the context of network coding. Moreover, we show that they can be built upon a class of superregular matrices, with entries in an extension field, that preserve their superregularity properties even after multiplication with some matrices with entries in the ground field.Wave: a new family of trapdoor one-way preimage sampleable functions based on codes.https://www.zbmath.org/1456.940692021-04-16T16:22:00+00:00"Debris-Alazard, Thomas"https://www.zbmath.org/authors/?q=ai:debris-alazard.thomas"Sendrier, Nicolas"https://www.zbmath.org/authors/?q=ai:sendrier.nicolas"Tillich, Jean-Pierre"https://www.zbmath.org/authors/?q=ai:tillich.jean-pierreSummary: We present here a new family of trapdoor one-way functions that are preimage sampleable on average (PSA) based on codes, the Wave-PSA family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized \((U,U+V)\)-codes. Our proof follows the GPV strategy [\textit{C. Gentry} 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). 197--206 (2008; Zbl 1231.68124)]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSA family with ternary generalized \((U,U+V)\)-codes to design a ``hash-and-sign'' signature scheme which achieves existential unforgeability under adaptive chosen message attacks (EUF-CMA) in the random oracle model.
For the entire collection see [Zbl 1428.94008].Streamlined blockchains: a simple and elegant approach (a tutorial and survey).https://www.zbmath.org/1456.941132021-04-16T16:22:00+00:00"Shi, Elaine"https://www.zbmath.org/authors/?q=ai:shi.elaineSummary: A blockchain protocol (also called state machine replication) allows a set of nodes to agree on an ever-growing, linearly ordered log of transactions. The classical consensus literature suggests two approaches for constructing a blockchain protocol: (1) through composition of single-shot consensus instances often called Byzantine agreement; and (2) through direct construction of a blockchain where there is no clear-cut boundary between single-shot consensus instances. While conceptually simple, the former approach precludes cross-instance optimizations in a practical implementation. This perhaps explains why the latter approach has gained more traction in practice: specifically, well-known protocols such as Paxos and PBFT all follow the direct-construction approach.
In this tutorial, we present a new paradigm called ``streamlined blockchains'' for directly constructing blockchain protocols. This paradigm enables a new family of protocols that are extremely simple and natural: every epoch, a proposer proposes a block extending from a notarized parent chain, and nodes vote if the proposal's parent chain is not too old. Whenever a block gains enough votes, it becomes notarized. Whenever a node observes a notarized chain with several blocks of consecutive epochs at the end, then the entire chain chopping off a few blocks at the end is final.
By varying the parameters highlighted in blue, we illustrate two variants for the partially synchronous and synchronous settings respectively. We present very simple proofs of consistency and liveness. We hope that this tutorial provides a compelling argument why this new family of protocols should be used in lieu of classical candidates (e.g., PBFT, Paxos, and their variants), both in practical implementation and for pedagogical purposes.
For the entire collection see [Zbl 1428.94008].Security in the presence of key reuse: context-separable interfaces and their applications.https://www.zbmath.org/1456.941052021-04-16T16:22:00+00:00"Patton, Christopher"https://www.zbmath.org/authors/?q=ai:patton.christopher"Shrimpton, Thomas"https://www.zbmath.org/authors/?q=ai:shrimpton.thomasSummary: Key separation is often difficult to enforce in practice. While key reuse can be catastrophic for security, we know of a number of cryptographic schemes for which it is provably safe. But existing formal models, such as the notions of joint security [\textit{S. Haber} and \textit{B. Pinkas}, ``Securely combining public-key cryptosystems'', in: Proceedings of the 8th ACM conference on computer and communications security, CCS '01, Philadelphia, PA, USA, November 2001. New York, NY: Association for Computing Machinery (ACM). 215--224 (2001; \url{doi:10.1145/501983.502013})]) and agility [\textit{T. Acar} et al. [Lect. Notes Comput. Sci. 6110, 403--422 (2010; Zbl 1280.94034)], do not address the full range of key-reuse attacks -- in particular, those that break the abstraction of the scheme, or exploit protocol interactions at a higher level of abstraction. This work attends to these vectors by focusing on two key elements: the game that codifies the scheme under attack, as well as its intended adversarial model; and the underlying interface that exposes secret key operations for use by the game. Our main security experiment considers the implications of using an interface (in practice, the API of a software library or a hardware platform such as TPM) to realize the scheme specified by the game when the interface is shared with other unspecified, insecure, or even malicious applications. After building up a definitional framework, we apply it to the analysis of two real-world schemes: the EdDSA signature algorithm and the Noise protocol framework. Both provide some degree of context separability, a design pattern for interfaces and their applications that aids in the deployment of secure protocols.
For the entire collection see [Zbl 1428.94004].Leakage certification revisited: bounding model errors in side-channel security evaluations.https://www.zbmath.org/1456.940572021-04-16T16:22:00+00:00"Bronchain, Olivier"https://www.zbmath.org/authors/?q=ai:bronchain.olivier"Hendrickx, Julien M."https://www.zbmath.org/authors/?q=ai:hendrickx.julien-m"Massart, Clément"https://www.zbmath.org/authors/?q=ai:massart.clement"Olshevsky, Alex"https://www.zbmath.org/authors/?q=ai:olshevsky.alex"Standaert, François-Xavier"https://www.zbmath.org/authors/?q=ai:standaert.francois-xavierSummary: Leakage certification aims at guaranteeing that the statistical models used in side-channel security evaluations are close to the true statistical distribution of the leakages, hence can be used to approximate a worst-case security level. Previous works in this direction were only qualitative: for a given amount of measurements available to an evaluation laboratory, they rated a model as ``good enough'' if the model assumption errors (i.e., the errors due to an incorrect choice of model family) were small with respect to the model estimation errors. We revisit this problem by providing the first quantitative tools for leakage certification. For this purpose, we provide bounds for the (unknown) mutual information metric that corresponds to the true statistical distribution of the leakages based on two easy-to-compute information theoretic quantities: the perceived information, which is the amount of information that can be extracted from a leaking device thanks to an estimated statistical model, possibly biased due to estimation and assumption errors, and the hypothetical information, which is the amount of information that would be extracted from an hypothetical device exactly following the model distribution. This positive outcome derives from the observation that while the estimation of the mutual information is in general a hard problem (i.e., estimators are biased and their convergence is distribution-dependent), it is significantly simplified in the case of statistical inference attacks where a target random variable (e.g., a key in a cryptographic setting) has a constant (e.g., uniform) probability. Our results therefore provide a general and principled path to bound the worst-case security level of an implementation. They also significantly speed up the evaluation of any profiled side-channel attack, since they imply that the estimation of the perceived information, which embeds an expensive cross-validation step, can be bounded by the computation of a cheaper hypothetical information, for any estimated statistical model.
For the entire collection see [Zbl 1428.94004].Unifying leakage models on a Rényi day.https://www.zbmath.org/1456.941082021-04-16T16:22:00+00:00"Prest, Thomas"https://www.zbmath.org/authors/?q=ai:prest.thomas"Goudarzi, Dahmun"https://www.zbmath.org/authors/?q=ai:goudarzi.dahmun"Martinelli, Ange"https://www.zbmath.org/authors/?q=ai:martinelli.ange"Passelègue, Alain"https://www.zbmath.org/authors/?q=ai:passelegue.alainSummary: In the last decade, several works have focused on finding the best way to model the leakage in order to obtain provably secure implementations. One of the most realistic models is the noisy leakage model, introduced in [\textit{E. Prouff} and \textit{M. Rivain}, Lect. Notes Comput. Sci. 7881, 142--159 (2013; Zbl 1306.94087)], and \textit{A. Duc} et al. [ibid. 8441, 423--440 (2014; Zbl 1326.94086)] together with secure constructions. These works suffer from various limitations, in particular the use of ideal leak-free gates in [Prouff and Rivain, loc. cit.] and an important loss (in the size of the field) in the reduction in [Duc et al., loc. cit.].
In this work, we provide new strategies to prove the security of masked implementations and start by unifying the different noisiness metrics used in prior works by relating all of them to a standard notion in information theory: the pointwise mutual information. Based on this new interpretation, we define two new natural metrics and analyze the security of known compilers with respect to these metrics. In particular, we prove (1) a tighter bound for reducing the noisy leakage models to the probing model using our first new metric, (2) better bounds for amplification-based security proofs using the second metric.
For the entire collection see [Zbl 1428.94004].Symmetric primitives with structured secrets.https://www.zbmath.org/1456.940412021-04-16T16:22:00+00:00"Alamati, Navid"https://www.zbmath.org/authors/?q=ai:alamati.navid"Montgomery, Hart"https://www.zbmath.org/authors/?q=ai:montgomery.hart"Patranabis, Sikhar"https://www.zbmath.org/authors/?q=ai:patranabis.sikharSummary: Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a wide variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric setting are key-homomorphic (weak) PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE.
This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that:
Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption but also a variety of primitives such as PIR, lossy TDFs, and even IBE.
Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE.
In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.
For the entire collection see [Zbl 1428.94004].Homomorphic time-lock puzzles and applications.https://www.zbmath.org/1456.940992021-04-16T16:22:00+00:00"Malavolta, Giulio"https://www.zbmath.org/authors/?q=ai:malavolta.giulio"Thyagarajan, Sri Aravinda Krishnan"https://www.zbmath.org/authors/?q=ai:thyagarajan.sri-aravinda-krishnanSummary: Time-lock puzzles allow one to encrypt messages for the future, by efficiently generating a puzzle with a solution \(s\) that remains hidden until time \(\mathcal{T}\) has elapsed. The solution is required to be concealed from the eyes of any algorithm running in (parallel) time less than \(\mathcal{T}\). We put forth the concept of homomorphic time-lock puzzles, where one can evaluate functions over puzzles without solving them, i.e., one can manipulate a set of puzzles with solutions \((s_1,\dots,s_n)\) to obtain a puzzle that solves to \(f(s_1, \dots,s_n)\), for any function \(f\). We propose candidate constructions under concrete cryptographic assumptions for different classes of functions. Then we show how homomorphic time-lock puzzles overcome the limitations of classical time-lock puzzles by proposing new protocols for applications of interest, such as e-voting, multi-party coin flipping, and fair contract signing.
For the entire collection see [Zbl 1428.94004].On the plausibility of fully homomorphic encryption for RAMs.https://www.zbmath.org/1456.940832021-04-16T16:22:00+00:00"Hamlin, Ariel"https://www.zbmath.org/authors/?q=ai:hamlin.ariel"Holmgren, Justin"https://www.zbmath.org/authors/?q=ai:holmgren.justin"Weiss, Mor"https://www.zbmath.org/authors/?q=ai:weiss.mor"Wichs, Daniel"https://www.zbmath.org/authors/?q=ai:wichs.danielSummary: We initiate the study of fully homomorphic encryption for RAMs (RAM-FHE). This is a public-key encryption scheme where, given an encryption of a large database \(D\), anybody can efficiently compute an encryption of \(P(D)\) for an arbitrary RAM program \(P\). The running time over the encrypted data should be as close as possible to the worst case running time of \(P\), which may be sub-linear in the data size.
A central difficulty in constructing a RAM-FHE scheme is hiding the sequence of memory addresses accessed by \(P\). This is particularly problematic because an adversary may homomorphically evaluate many programs over the same ciphertext, therefore effectively ``rewinding'' any mechanism for making memory accesses oblivious.
We identify a necessary prerequisite towards constructing RAM-FHE that we call rewindable oblivious RAM (rewindable ORAM), which provides security even in this strong adversarial setting. We show how to construct rewindable ORAM using symmetric-key doubly efficient PIR (SK-DEPIR) [\textit{R. Canetti} et al., Lect. Notes Comput. Sci. 10678, 694--726 (2017; Zbl 1416.68063); \textit{E. Boyle} et al., ibid. 10678, 662--693 (2017; Zbl 1416.68062)]. We then show how to use rewindable ORAM, along with virtual black-box (VBB) obfuscation for specific circuits, to construct RAM-FHE. The latter primitive can be heuristically instantiated using existing indistinguishability obfuscation candidates. Overall, we obtain a RAM-FHE scheme where the multiplicative overhead in running time is polylogarithmic in the database size \(N\). Our basic scheme is single-hop, but we also extend it to obtain multi-hop RAM-FHE with overhead \(N^\epsilon\) for arbitrarily small \(\epsilon >0\).
We view our work as the first evidence that RAM-FHE is likely to exist.
For the entire collection see [Zbl 1428.94004].Batching techniques for accumulators with applications to IOPs and stateless blockchains.https://www.zbmath.org/1456.940512021-04-16T16:22:00+00:00"Boneh, Dan"https://www.zbmath.org/authors/?q=ai:boneh.dan"Bünz, Benedikt"https://www.zbmath.org/authors/?q=ai:bunz.benedikt"Fisch, Ben"https://www.zbmath.org/authors/?q=ai:fisch.ben-aSummary: We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for distributed settings where no trusted accumulator manager exists and updates to the accumulator are processed in batches. We develop techniques for non-interactively aggregating membership proofs that can be verified with a constant number of group operations. We also provide a constant sized batch non-membership proof for a large number of elements. These proofs can be used to build the first positional vector commitment (VC) with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proof systems in groups of unknown order. These extend a recent construction of a succinct proof of correct exponentiation, and include a succinct proof of knowledge of an integer discrete logarithm between two group elements. We circumvent an impossibility result for Sigma-protocols in these groups by using a short trapdoor-free CRS. We use these new accumulator and vector commitment constructions to design a stateless blockchain, where nodes only need a constant amount of storage in order to participate in consensus. Further, we show how to use these techniques to reduce the size of IOP instantiations, such as STARKs.
For the entire collection see [Zbl 1428.94004].Subvector commitments with application to succinct arguments.https://www.zbmath.org/1456.940952021-04-16T16:22:00+00:00"Lai, Russell W. F."https://www.zbmath.org/authors/?q=ai:lai.russell-w-f"Malavolta, Giulio"https://www.zbmath.org/authors/?q=ai:malavolta.giulioSummary: We put forward the notion of subvector commitments (SVC): an SVC allows one to open a committed vector at a set of positions, where the opening size is independent of length of the committed vector and the number of positions to be opened. We propose two constructions under variants of the root assumption and the CDH assumption, respectively. We further generalize SVC to a notion called linear map commitments (LMC), which allows one to open a committed vector to its images under linear maps with a single short message, and propose a construction over pairing groups.
Equipped with these newly developed tools, we revisit the ``CS proofs'' paradigm [\textit{S. Micali} ``CS proofs'', in: Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA. IEEE Computer Society Press. 436--453 (1994)] which turns any arguments with public-coin verifiers into non-interactive arguments using the Fiat-Shamir transform in the random oracle model. We propose a compiler that turns any (linear, resp.) PCP into a non-interactive argument, using exclusively SVCs (LMCs, resp.). For an approximate 80 bits of soundness, we highlight the following new implications:
1.) There exists a succinct non-interactive argument of knowledge (SNARK) with public-coin setup with proofs of size 5360 bits, under the adaptive root assumption over class groups of imaginary quadratic orders against adversaries with runtime \(2^{128}\). At the time of writing, this is the shortest SNARK with public-coin setup.
2.) There exists a non-interactive argument with private-coin setup, where proofs consist of 2 group elements and 3 field elements, in the generic bilinear group model.
For the entire collection see [Zbl 1428.94004].Synchronous, with a chance of partition tolerance.https://www.zbmath.org/1456.940812021-04-16T16:22:00+00:00"Guo, Yue"https://www.zbmath.org/authors/?q=ai:guo.yue"Pass, Rafael"https://www.zbmath.org/authors/?q=ai:pass.rafael"Shi, Elaine"https://www.zbmath.org/authors/?q=ai:shi.elaineSummary: Murphy, Murky, Mopey, Moody, and Morose decide to write a paper together over the Internet and submit it to the prestigious CRYPTO'19 conference that has the most amazing PC. They encounter a few problems. First, not everyone is online every day: some are lazy and go skiing on Mondays; others cannot use git correctly and they are completely unaware that they are losing messages. Second, a small subset of the co-authors may be secretly plotting to disrupt the project (e.g., because they are writing a competing paper in stealth).
Suppose that each day, sufficiently many honest co-authors are online (and use git correctly); moreover, suppose that messages checked into git on Monday can be correctly received by honest and online co-authors on Tuesday or any future day. Can the honest co-authors successfully finish the paper in a small number of days such that they make the CRYPTO deadline; and perhaps importantly, can all the honest co-authors, including even those who are lazy and those who sometimes use git incorrectly, agree on the final theorem?
For the entire collection see [Zbl 1428.94004].Continuous space-bounded non-malleable codes from stronger proofs-of-space.https://www.zbmath.org/1456.940632021-04-16T16:22:00+00:00"Chen, Binyi"https://www.zbmath.org/authors/?q=ai:chen.binyi"Chen, Yilei"https://www.zbmath.org/authors/?q=ai:chen.yilei"Hostáková, Kristina"https://www.zbmath.org/authors/?q=ai:hostakova.kristina"Mukherjee, Pratyay"https://www.zbmath.org/authors/?q=ai:mukherjee.pratyaySummary: Non-malleable codes are encoding schemes that provide protections against various classes of tampering attacks. Recently \textit{S. Faust} et al. [Lect. Notes Comput. Sci. 10402, 95--126 (2017; Zbl 1409.94871)] initiated the study of space-bounded non-malleable codes that provide such protections against tampering within small-space devices. They put forward a construction based on any non-interactive proof-of-space (NIPoS). However, the scheme only protects against an a priori bounded number of tampering attacks.
We construct non-malleable codes that are resilient to an unbounded polynomial number of space-bounded tamperings. Towards that we introduce a stronger variant of NIPoS called proof-extractable NIPoS (PExt-NIPoS), and propose two approaches of constructing such a primitive. Using a new proof strategy we show that the generic encoding scheme of Faust et al. [loc. cit.] achieves unbounded tamper-resilience when instantiated with a PExt-NIPoS. We show two methods to construct PExt-NIPoS:
1.) The first method uses a special family of ``memory-hard'' graphs, called challenge-hard graphs (CHG), a notion we introduce here. We instantiate such family of graphs based on an extension of stack of localized expanders (first used by \textit{L. Ren} and \textit{S. Devadas} [ibid. 9985, 262--285 (2016; Zbl 1406.94077)] in the context of proof-of-space). In addition, we show that the graph construction used as a building block for the proof-of-space by \textit{S. Dziembowski} et al. [ibid. 9216, 585--605 (2015; Zbl 1369.94531)] satisfies challenge-hardness as well. These two CHG-instantiations lead to continuous space-bounded NMC with different features in the random oracle model.
2.) Our second instantiation relies on a new measurable property, called uniqueness of NIPoS. We show that standard extractability can be upgraded to proof-extractability if the NIPoS also has uniqueness. We propose a simple heuristic construction of NIPoS, that achieves (partial) uniqueness, based on a candidate memory-hard function in the standard model and a publicly verifiable computation with small-space verification. Instantiating the encoding scheme of Faust et al. [loc. cit.] with this NIPoS, we obtain a continuous space-bounded NMC that supports the ``most practical'' parameters, complementing the provably secure but ``relatively impractical'' CHG-based constructions. Additionally, we revisit the construction of Faust et al. and observe that due to the lack of uniqueness of their NIPoS, the resulting encoding schemes yield ``highly impractical'' parameters in the continuous setting.
We conclude the paper with a comparative study of all our non-malleable code constructions with an estimation of concrete parameters.
For the entire collection see [Zbl 1428.94004].Explicit rate-1 non-malleable codes for local tampering.https://www.zbmath.org/1456.940822021-04-16T16:22:00+00:00"Gupta, Divya"https://www.zbmath.org/authors/?q=ai:gupta.divya"Maji, Hemanta K."https://www.zbmath.org/authors/?q=ai:maji.hemanta-k"Wang, Mingyuan"https://www.zbmath.org/authors/?q=ai:wang.mingyuanSummary: This paper constructs high-rate non-malleable codes in the information-theoretic plain model against tampering functions with bounded locality. We consider \(\delta\)-local tampering functions; namely, each output bit of the tampering function is a function of (at most) \(\delta\) input bits. This work presents the first explicit and efficient rate-1 non-malleable code for \(\delta\)-local tampering functions, where \(\delta=\xi\lg n\) and \(\xi<1\) is any positive constant. As a corollary, we construct the first explicit rate-1 non-malleable code against \(\mathrm{NC}^0\) tampering functions.
Before our work, no explicit construction for a constant-rate non-malleable code was known even for the simplest 1-local tampering functions. \textit{M. Ball} et al. [Lect. Notes Comput. Sci. 9666, 881--908 (2016; Zbl 1371.94623)], and \textit{E. Chattopadhyay} and \textit{X. Li} [in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 1171--1184 (2017; Zbl 1370.68083)] provided the first explicit non-malleable codes against \(\delta \)-local tampering functions. However, these constructions are rate-0 even when the tampering functions have 1-locality. In the CRS model, \textit{S. Faust} et al. [ibid. 8441, 111--128 (2014; Zbl 1326.94094)] constructed efficient rate-1 non-malleable codes for \(\delta=O(\log n)\) local tampering functions.
Our main result is a general compiler that bootstraps a rate-0 non-malleable code against leaky input and output local tampering functions to construct a rate-1 non-malleable code against \(\xi \lg n\)-local tampering functions, for any positive constant \(\xi<1\). Our explicit construction instantiates this compiler using an appropriate encoding by M. Ball et al. [loc. cit.].
For the entire collection see [Zbl 1428.94004].Valiant's universal circuits revisited: an overall improvement and a lower bound.https://www.zbmath.org/1456.941242021-04-16T16:22:00+00:00"Zhao, Shuoyao"https://www.zbmath.org/authors/?q=ai:zhao.shuoyao"Yu, Yu"https://www.zbmath.org/authors/?q=ai:yu.yu"Zhang, Jiang"https://www.zbmath.org/authors/?q=ai:zhang.jiang"Liu, Hanlin"https://www.zbmath.org/authors/?q=ai:liu.hanlinSummary: A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size \(n)\). \textit{L. G. Valiant} [in: Proceedings of the eighth annual ACM symposium on theory of computing. Hershey, Pennsylvania May 3--5, 1976. New York, NY: The Association for Computing Machinery (ACM). 196--203 (1976; Zbl 0365.94044)] presented a graph theoretic approach to the construction of UCs, where a UC is represented by an edge universal graph (EUG) and is recursively constructed using a dedicated graph object (referred to as supernode). As a main end result, Valiant constructed a 4-way supernode of size 19 and an EUG of size \(4.75n\log n\) (omitting smaller terms), which remained the most size-efficient even to this day (after more than 4 decades).
Motivated by the emerging applications of UCs in various privacy preserving computation scenarios, we revisit Valiant's universal circuits, and propose a 4-way supernode of size 18, and an EUG of size \(4.5n\log n\). As confirmed by our implementations, we reduce the size of universal circuits (and the number of AND gates) by more than 5\% in general, and thus improve upon the efficiency of UC-based cryptographic applications accordingly. Our approach to the design of optimal supernodes is computer aided (rather than by hand as in previous works), which might be of independent interest. As a complement, we give lower bounds on the size of EUGs and UCs in Valiant's framework, which significantly improves upon the generic lower bound on UC size and therefore reduces the gap between theory and practice of universal circuits.
For the entire collection see [Zbl 1428.94008].On the shortness of vectors to be found by the ideal-SVP quantum algorithm.https://www.zbmath.org/1456.940742021-04-16T16:22:00+00:00"Ducas, Léo"https://www.zbmath.org/authors/?q=ai:ducas.leo"Plançon, Maxime"https://www.zbmath.org/authors/?q=ai:plancon.maxime"Wesolowski, Benjamin"https://www.zbmath.org/authors/?q=ai:wesolowski.benjaminSummary: The hardness of finding short vectors in ideals of cyclotomic number fields (hereafter, Ideal-SVP) can serve as a worst-case assumption for numerous efficient cryptosystems, via the average-case problems Ring-SIS and Ring-LWE. For a while, it could be assumed the Ideal-SVP problem was as hard as the analog problem for general lattices (SVP), even when considering quantum algorithms.
But in the last few years, a series of works has lead to a quantum algorithm for Ideal-SVP that outperforms what can be done for general SVP in certain regimes. More precisely, it was demonstrated (under certain hypotheses) that one can find in quantum polynomial time a vector longer by a factor at most \(\alpha=\exp({\widetilde{O}(n^{1/2})})\) than the shortest non-zero vector in a cyclotomic ideal lattice, where \(n\) is the dimension.
In this work, we explore the constants hidden behind this asymptotic claim. While these algorithms have quantum steps, the steps that impact the approximation factor \(\alpha\) are entirely classical, which allows us to estimate it experimentally using only classical computing. Moreover, we design heuristic improvements for those steps that significantly decrease the hidden factors in practice. Finally, we derive new provable effective lower bounds based on volumetric arguments.
This study allows to predict the crossover point with classical lattice reduction algorithms, and thereby determine the relevance of this quantum algorithm in any cryptanalytic context. For example we predict that this quantum algorithm provides shorter vectors than BKZ-300 (roughly the weakest security level of NIST lattice-based candidates) for cyclotomic rings of rank larger than about 24000.
For the entire collection see [Zbl 1428.94004].Estimation of indirectly observable Langevin states: path integral solution using statistical physics methods.https://www.zbmath.org/1456.827582021-04-16T16:22:00+00:00"Balaji, Bhashyam"https://www.zbmath.org/authors/?q=ai:balaji.bhashyamHow to build pseudorandom functions from public random permutations.https://www.zbmath.org/1456.940642021-04-16T16:22:00+00:00"Chen, Yu Long"https://www.zbmath.org/authors/?q=ai:chen.yu-long"Lambooij, Eran"https://www.zbmath.org/authors/?q=ai:lambooij.eran"Mennink, Bart"https://www.zbmath.org/authors/?q=ai:mennink.bartSummary: Pseudorandom functions are traditionally built upon block ciphers, but with the trend of permutation based cryptography, it is a natural question to investigate the design of pseudorandom functions from random permutations. We present a generic study of how to build beyond birthday bound secure pseudorandom functions from public random permutations. We first show that a pseudorandom function based on a single permutation call cannot be secure beyond the \(2^{n/2}\) birthday bound, where \(n\) is the state size of the function. We next consider the sum of Even-Mansour (SoEM) construction, that instantiates the sum of permutations with the Even-Mansour construction. We prove that SoEM achieves tight \(2n{/}3\)-bit security if it is constructed from two independent permutations and two randomly drawn keys. We also demonstrate a birthday bound attack if either the permutations or the keys are identical. Finally, we present the sum of key alternating ciphers (SoKAC) construction, a translation of encrypted Davies-Meyer dual to a public permutation based setting, and show that SoKAC achieves tight \(2n{/}3\)-bit security even when a single key is used.
For the entire collection see [Zbl 1428.94004].Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs.https://www.zbmath.org/1456.940542021-04-16T16:22:00+00:00"Bootle, Jonathan"https://www.zbmath.org/authors/?q=ai:bootle.jonathan"Lyubashevsky, Vadim"https://www.zbmath.org/authors/?q=ai:lyubashevsky.vadim"Seiler, Gregor"https://www.zbmath.org/authors/?q=ai:seiler.gregorSummary: A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector \(\vec{s}\) with small coefficients satisfying \(A\vec{s}=\vec{u}\bmod\,q\). While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of \(\vec{s}^\prime\) and \(c\) satisfying\(A\vec{s}^\prime=\vec{u}c\) where \(\Vert\vec{s}^\prime\Vert\gg\Vert\vec{s}\Vert\) and \(c\) is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of \textit{J. Stern}'s protocol [Lect. Notes Comput. Sci. 773, 13--21 (1994; Zbl 0876.94035)], for proving knowledge of nearby codewords, to larger moduli. The scheme is a \(\varSigma\)-protocol, each of whose iterations has soundness error \(2{/}3\), and thus requires over 200 repetitions to obtain soundness error of \(2^{-128}\), which is the main culprit behind the large size of the proofs produced.
In this paper, we propose the first lattice-based proof system that significantly outperforms Stern-type proofs for proving knowledge of a short \(\vec{s}\) satisfying \(A\vec{s}=\vec{u}\bmod\,q\). Unlike Stern's proof, which is combinatorial in nature, our proof is more algebraic and uses various relaxed zero-knowledge proofs as sub-routines. The main savings in our proof system comes from the fact that each round has soundness error of \(1{/}n\), where \(n\) is the number of columns of \(A\). For typical applications, \(n\) is a few thousand, and therefore our proof needs to be repeated around 10 times to achieve a soundness error of \(2^{-128} \). For concrete parameters, it produces proofs that are around an order of magnitude smaller than those produced using Stern's approach.
For the entire collection see [Zbl 1428.94004].Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications.https://www.zbmath.org/1456.941222021-04-16T16:22:00+00:00"Yang, Rupeng"https://www.zbmath.org/authors/?q=ai:yang.rupeng"Au, Man Ho"https://www.zbmath.org/authors/?q=ai:au.man-ho"Zhang, Zhenfei"https://www.zbmath.org/authors/?q=ai:zhang.zhenfei"Xu, Qiuliang"https://www.zbmath.org/authors/?q=ai:xu.qiuliang"Yu, Zuoxia"https://www.zbmath.org/authors/?q=ai:yu.zuoxia"Whyte, William"https://www.zbmath.org/authors/?q=ai:whyte.williamSummary: We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error \((2/3)\), or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that ``approximates'' the actual witness. Our systems do not suffer from these limitations.
The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error \((1/\mathrm{poly})\), and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.
Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.
For the entire collection see [Zbl 1428.94004].On a class of constacyclic codes of length \(4p^s\) over \(\frac{\mathbb{F}_pm[u]}{\langle u^a\rangle}\).https://www.zbmath.org/1456.941342021-04-16T16:22:00+00:00"Dinh, Hai Q."https://www.zbmath.org/authors/?q=ai:dinh.hai-quang"Nguyen, Bac T."https://www.zbmath.org/authors/?q=ai:nguyen.bac-trong"Sriboonchitta, Songsak"https://www.zbmath.org/authors/?q=ai:sriboonchitta.songsakNoninteractive zero knowledge for NP from (Plain) Learning With Errors.https://www.zbmath.org/1456.941062021-04-16T16:22:00+00:00"Peikert, Chris"https://www.zbmath.org/authors/?q=ai:peikert.chris"Shiehian, Sina"https://www.zbmath.org/authors/?q=ai:shiehian.sinaSummary: We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the Plain Learning with Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by \textit{R. Canetti} et al. [Lect. Notes Comput. Sci. 10820, 91--122 (2018; Zbl 1423.94058)], \textit{J. Holmgren} and \textit{A. Lombardi} [``Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications)'', in: Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France, 06.10--09.10, 2018. 850-858 (2018)], and \textit{R. Canetti} et al. [J. ACM 51, No. 4, 557--594 (2004; Zbl 1204.94063)] for soundly applying the Fiat-Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on ``exotic'' assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness.
Our main technical contribution is a hash family that is correlation intractable for arbitrary size-\(S\) circuits, for any polynomially bounded \(S\), based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes'', yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.
For the entire collection see [Zbl 1428.94004].Fully secure attribute-based encryption for \(t\)-CNF from LWE.https://www.zbmath.org/1456.941172021-04-16T16:22:00+00:00"Tsabary, Rotem"https://www.zbmath.org/authors/?q=ai:tsabary.rotemSummary: Attribute-based encryption (ABE), first introduced by \textit{A. Sahai} and \textit{B. Waters} [Lect. Notes Comput. Sci. 3494, 457--473 (2005; Zbl 1137.94355)], and \textit{V. Goyal} [``Attribute-based encryption for fine-grained access control of encrypted data'', in: Proceedings of the 13th ACM conference on computer and communications security, CCS'06, Alexandria, VA, USA, October 30--November 3, 2006. New York, NY: Association for Computing Machinery (ACM). 89--98 (2006; \url{doi:10.1145/1180405.1180418})], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).
In this work we construct for the first time a lattice-based (ciphertext-policy) ABE scheme for the function class \(t\)-CNF, which consists of CNF formulas where each clause depends on at most \(t\) bits of the input, for any constant \(t\). This class includes NP-verification policies, bit-fixing policies and \(t\)-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest.
For the entire collection see [Zbl 1428.94004].Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE.https://www.zbmath.org/1456.940902021-04-16T16:22:00+00:00"Jaques, Samuel"https://www.zbmath.org/authors/?q=ai:jaques.samuel"Schanck, John M."https://www.zbmath.org/authors/?q=ai:schanck.john-mSummary: We introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the supersingular isogeny Diffie-Hellman (SIDH) and supersingular isogeny key encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms.
For the entire collection see [Zbl 1428.94004].Cryptanalysis of OCB2: attacks on authenticity and confidentiality.https://www.zbmath.org/1456.940892021-04-16T16:22:00+00:00"Inoue, Akiko"https://www.zbmath.org/authors/?q=ai:inoue.akiko"Iwata, Tetsu"https://www.zbmath.org/authors/?q=ai:iwata.tetsu"Minematsu, Kazuhiko"https://www.zbmath.org/authors/?q=ai:minematsu.kazuhiko"Poettering, Bertram"https://www.zbmath.org/authors/?q=ai:poettering.bertramSummary: We present practical attacks on OCB2. This mode of operation of a blockcipher was designed with the aim to provide particularly efficient and provably-secure authenticated encryption services, and since its proposal about 15 years ago it belongs to the top performers in this realm. OCB2 was included in an ISO standard in 2009.
An internal building block of OCB2 is the tweakable blockcipher obtained by operating a regular blockcipher in \(\mathrm{XEX}^\ast\) mode. The latter provides security only when evaluated in accordance with certain technical restrictions that, as we note, are not always respected by OCB2. This leads to devastating attacks against OCB2's security promises: We develop a range of very practical attacks that, amongst others, demonstrate universal forgeries and full plaintext recovery. We complete our report with proposals for (provably) repairing OCB2. To our understanding, as a direct consequence of our findings, OCB2 is currently in a process of removal from ISO standards. Our attacks do not apply to OCB1 and OCB3, and our privacy attacks on OCB2 require an active adversary.
For the entire collection see [Zbl 1428.94004].Circuit theory and communication.https://www.zbmath.org/1456.940012021-04-16T16:22:00+00:00"Ivrlač, Michel"https://www.zbmath.org/authors/?q=ai:ivrlac.michel-tPublisher's description: The high level of abstraction makes information theory a versatile and powerful tool for the analysis and optimization of a wide variety of communication systems. On the other hand, information theory has no concept of the flow of energy that accompanies the flow of information. Consequently, some important aspects of communication, like transmit power or noise covariance are by no means straight forward. In this book, we introduce effective methods which overcome this inherent limitation of information theory. We deal with this problem from a classic circuit theory point of view. This allows correct assessment of the energy flow in communication systems and thereby enables an information theoretic analysis and optimization which is consistent with the underlying physics of the communication system under investigation.Smoothing inertial projection neural network for minimization \(L_{p-q}\) in sparse signal reconstruction.https://www.zbmath.org/1456.940242021-04-16T16:22:00+00:00"Zhao, You"https://www.zbmath.org/authors/?q=ai:zhao.you"He, Xing"https://www.zbmath.org/authors/?q=ai:he.xing"Huang, Tingwen"https://www.zbmath.org/authors/?q=ai:huang.tingwen"Huang, Junjian"https://www.zbmath.org/authors/?q=ai:huang.junjianSummary: In this paper, we investigate a more general sparse signal recovery minimization model and a smoothing neural network optimal method for compress sensing problem, where the objective function is a \(L_{p-q}\) minimization model which includes nonsmooth, nonconvex, and non-Lipschitz quasi-norm \(L_p\) norms \((1\geq p>0)\) and nonsmooth \(L_q\) norms \((2\geq p>1)\), and its feasible set is a closed convex subset of \(\mathbb{R}^n\). Firstly, under the restricted isometry property (RIP) condition, the uniqueness of solution for the minimization model with a given sparsity \(s\) is obtained through the theoretical analysis. With a mild condition, we get that the larger of the \(q\), the more effective of the sparse recovery model under sensing matrix satisfies RIP conditions at fixed \(p\). Secondly, using a smoothing approximate method, we propose the smoothing inertial projection neural network (SIPNN) algorithm for solving the proposed general model. Under certain conditions, the proposed algorithm can converge to a stationary point. Finally, convergence behavior and successful recover performance experiments and a comparison experiment confirm the effectiveness of the proposed SIPNN algorithm.Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications.https://www.zbmath.org/1456.940752021-04-16T16:22:00+00:00"Esgin, Muhammed F."https://www.zbmath.org/authors/?q=ai:esgin.muhammed-f"Steinfeld, Ron"https://www.zbmath.org/authors/?q=ai:steinfeld.ron"Liu, Joseph K."https://www.zbmath.org/authors/?q=ai:liu.joseph-k-k"Liu, Dongxi"https://www.zbmath.org/authors/?q=ai:liu.dongxiSummary: We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree \(k\ge 2\), where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree \(k\ge 2\) have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs and arithmetic circuit arguments. In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case \((k=1)\) and a very specific quadratic case \((k=2)\), which are obtained as a special case of our technique.
Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting ``inter-slot'' operations, and ``NTT-friendly'' tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.
To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.
Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.
For the entire collection see [Zbl 1428.94004].Cross-layer modeling and optimization of multi-channel cognitive radio networks under imperfect channel sensing.https://www.zbmath.org/1456.940052021-04-16T16:22:00+00:00"Kim, Jae Deok"https://www.zbmath.org/authors/?q=ai:kim.jaedeok"Hwang, Ganguk"https://www.zbmath.org/authors/?q=ai:hwang.gangukSummary: In this paper, we consider a multi-channel cognitive radio network with multiple secondary users (SUs) and analyze the performance of users in the network. We assume primary users (PUs) adopt the automatic repeat request (ARQ) protocol at the medium access control layer. We have two main goals. Our first goal is to develop a cross-layer performance model of the cognitive radio network by considering the retransmission characteristics of the ARQ protocol and the interference between PUs and SUs due to imperfect channel sensing. Using the cross-layer performance model we analyze the throughput performance of SUs and the delay performance of PUs.
Our second goal is to propose an optimal channel sensing method that maximizes the throughput performance of SUs while a given delay requirement of PUs is guaranteed. To this end, using our cross-layer performance model, we formulate an optimization problem and solve it to get an optimal channel sensing method that satisfies the design objectives. Numerical and simulation results are provided to validate our analysis and to investigate the performance of the optimal channel sensing method.Analysis of the strict avalanche criterion in variants of arbiter-based physically unclonable functions.https://www.zbmath.org/1456.941142021-04-16T16:22:00+00:00"Siddhanti, Akhilesh Anilkumar"https://www.zbmath.org/authors/?q=ai:siddhanti.akhilesh-anilkumar"Bodapati, Srinivasu"https://www.zbmath.org/authors/?q=ai:bodapati.srinivasu"Chattopadhyay, Anupam"https://www.zbmath.org/authors/?q=ai:chattopadhyay.anupam"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoy"Roy, Dibyendu"https://www.zbmath.org/authors/?q=ai:roy.dibyendu"Stănică, Pantelimon"https://www.zbmath.org/authors/?q=ai:stanica.pantelimonSummary: Arbiter-based physically unclonable functions (arbiter PUF) were introduced to generate cryptographically secure secret keys during runtime, rather than storing it in non-volatile memory (NVM) which are vulnerable to physical attacks. However, its construction was a target to several statistical and modeling attacks. One such statistical weakness of the arbiter PUF is that it leaks information to the adversary, if some challenge-response pairs are known. The response is heavily biased towards the effect of flipping certain bits of the input, a widely studied property, known as the strict avalanche criterion (SAC). Several variants of arbiter PUFs have been proposed since then, with varying degrees of success against SAC. In this paper, we provide a generalized framework to analyze any arbiter PUF variant against SAC. Building on this analysis, we propose a new arbiter PUF variant which is not only highly resistant to SAC but also has very good reliability.
For the entire collection see [Zbl 1428.94012].Exploring lightweight efficiency of ForkAES.https://www.zbmath.org/1456.940442021-04-16T16:22:00+00:00"Balli, Fatih"https://www.zbmath.org/authors/?q=ai:balli.fatih"Banik, Subhadeep"https://www.zbmath.org/authors/?q=ai:banik.subhadeepSummary: Recently the ForkAES construction was proposed by \textit{E. Andreeva} et al. [``Forking a blockcipher for authenticated encryption of very short messages'', IACR Cryptology ePrint Archive: Report 2018/916 (2018)] for efficiently performing authenticated encryption of very short messages on next generation IoT devices. The ForkAES tweakable block cipher uses around one and a half AES encryption calls to produce a pair of ciphertexts for any given plaintext. However the only downside of the construction is that it needs to store an extra state of 128 bits in addition with the storage elements required to perform AES encryption. Thus a hardware implementation of ForkAES would require additional circuit area to accommodate the extra state.
In this paper, we first show that it is possible to implement ForkAES without any additional storage elements other than those required to implement AES, if the AES circuit can additionally perform decryption. Such an implementation naturally requires more clock cycles to perform ForkAES operations. We extend the recently proposed Atomic AES v2.0 architecture to realize ForkAES and compare the area-latency trade-offs incurred with and without an additional storage. The area of the most compact ForkAES design takes about 1.2 times that of AES.
In the second part of the paper we look at another important parameter of lightweight efficiency, i.e. energy. It is well known that round based constructions for AES are the most energy efficient ones. We extend the so-called ``\(S_3K_2\)'' construction of \textit{S. Banik} et al. [``Efficient configurations for block ciphers with unified ENC/DEC paths'', in: Proceedings of the 2017 IEEE international symposium on hardware oriented security and trust (HOST), McLean, VA, USA, May 1--5, 2017. Piscataway, NJ: IEEE. 41--46 (2017; \url{doi:10.1109/HST.2017.7951795})] to realize ForkAES in an energy-preserving manner, and compare the effects of some design choices. The energy consumption of our best ForkAES design takes about 2 times that of AES. From lightweight design perspective, our results hence demonstrate that although ForkAES lives up to its promise (of being roughly 1.5 times that of AES) in terms of its area, the same does not hold for its energy consumption.
For the entire collection see [Zbl 1428.94012].Generalized approach for analysing quantum key distribution experiments.https://www.zbmath.org/1456.940982021-04-16T16:22:00+00:00"Maitra, Arpita"https://www.zbmath.org/authors/?q=ai:maitra.arpita"Das, Suvra Sekhar"https://www.zbmath.org/authors/?q=ai:das.suvra-sekharSummary: In this initiative, a generalized approach towards step by step synthesis of quantum key distribution (QKD) experiments is presented. Schematic diagram of the optical setup of any QKD protocol is easily available in the literature whereas step by step synthesis of the circuit needs further attention. For practical implementation, this understanding is necessary. In the current effort, we describe a disciplined methodology to synthesize the optical experimental setup of QKD protocols. This approach can be extended towards any optical experiment. The beam splitter and phase retarders are described in terms of annihilation and creation operators. We represent the polarization of photon in the Fock state basis. We consider two QKD protocols; Passive BB84 with coherent light [\textit{M. Curty} et al., `` Passive preparation of BB84 signal states with coherent light'', Prog. Inform. 8, 57--63 (2011; \url{doi:10.2201/NiiPi.2011.8.7})] and Reference Frame Independent 6-4 QKD (RFI-QKD) [\textit{R. Tannous} et al., ``Demonstration of a 6 state-4 state reference frame independent channel for quantum key distribution'', Preprint, \url{arXiv:1905.09197}) to test the methodology. We observe that this disciplined methodology can successfully describe the experiments. This can be exploited to build a convenient synthesis tool for modelling any optical arrangement for security analysis.
For the entire collection see [Zbl 1428.94012].Device independent quantum key distribution using three-party pseudo-telepathy.https://www.zbmath.org/1456.940462021-04-16T16:22:00+00:00"Basak, Jyotirmoy"https://www.zbmath.org/authors/?q=ai:basak.jyotirmoy"Maitra, Arpita"https://www.zbmath.org/authors/?q=ai:maitra.arpita"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoySummary: Removing trustworthiness from the devices is the motivation towards device independent quantum key distribution (DI-QKD). The only assumption in this case is that the devices obey the laws of quantum mechanics and are spatially isolated from each other. The security of the protocol can be achieved by certain tests based on various statistical analysis. Recently, \textit{U. Vazirani} and \textit{T. Vidick} (VV) proposed a DI-QKD scheme [``Fully device-independent quantum key distribution'', Phys. Rev. Lett. 113, No. 14, Article ID 140501, 6 p. (2014; \url{doi:10.1103/PhysRevLett.113.140501})] exploiting the CHSH game. In a similar direction, here we present a simple proposal that exploits the idea of multi-party pseudo-telepathy game to certify device independent security. The relative advantages of our protocol are also discussed.
For the entire collection see [Zbl 1428.94012].Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256.https://www.zbmath.org/1456.941012021-04-16T16:22:00+00:00"Ni, Boyu"https://www.zbmath.org/authors/?q=ai:ni.boyu"Ito, Gembu"https://www.zbmath.org/authors/?q=ai:ito.gembu"Dong, Xiaoyang"https://www.zbmath.org/authors/?q=ai:dong.xiaoyang"Iwata, Tetsu"https://www.zbmath.org/authors/?q=ai:iwata.tetsuSummary: Generalized Feistel schemes (GFSs) are important components of symmetric ciphers, which have been extensively studied in the classical setting. However, detailed security evaluations of GFS in the quantum setting still remain to be explored.
In this paper, we give improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give a new quantum polynomial-time distinguisher on \((3d-3)\)-round Type-1 GFS with branches \(d\ge 3\), which gains \((d-2)\) more rounds than the previous distinguishers. This leads us to obtain a better key-recovery attack with reduced time complexities by a factor of \(2^{\frac{(d-2)n}{2}}\), where n is the bit length of the branch. We also show a quantum distinguishing attack against \((d^2-d+1)\)-round version in qCCA setting, and this gives a key-recovery attack with much lower time complexity.
In addition, based on a 14-round quantum distinguisher, we give quantum key-recovery attacks on round-reduced CAST-256 block cipher. For the 256-bit key version, we could attack up to 20-round CAST-256 in time \(2^{111}\), which is faster than the quantum brute-force attack by a factor of \(2^{17}\). For the 128-bit key version, we could attack 17 rounds in time \(2^{55.5}\), while the best previous classical or quantum attacks are no more than 16 rounds.
For the entire collection see [Zbl 1428.94012].Efficient quantum algorithms related to autocorrelation spectrum.https://www.zbmath.org/1456.940482021-04-16T16:22:00+00:00"Bera, Debajyoti"https://www.zbmath.org/authors/?q=ai:bera.debajyoti"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoy"Tharrmashastha, Sapv"https://www.zbmath.org/authors/?q=ai:tharrmashastha.sapvSummary: In this paper, we propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First, we present a quantum algorithm that samples from the Walsh spectrum of any derivative of \(f()\). Informally, the autocorrelation coefficient of a Boolean function \(f()\) at some point a measures the average correlation among the values \(f(x)\) and \(f(x\oplus a)\). The derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of \(f()\). The Walsh spectrum is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem. We extend the idea to ``higher-order Deutsch-Jozsa'' quantum algorithm to obtain points corresponding to large absolute values in the Walsh spectrum of a certain derivative of \(f()\). Further, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Finally we provide a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares.
For the entire collection see [Zbl 1428.94012].Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction.https://www.zbmath.org/1456.941192021-04-16T16:22:00+00:00"Xu, Jun"https://www.zbmath.org/authors/?q=ai:xu.jun"Sarkar, Santanu"https://www.zbmath.org/authors/?q=ai:sarkar.santanu"Hu, Lei"https://www.zbmath.org/authors/?q=ai:hu.leiSummary: In this paper, we present a polynomial lattice method to solve the Approximate Polynomial Common Divisor problem. This problem is the polynomial version of the well known approximate integer common divisor problem introduced by \textit{N. Howgrave-Graham} [Lect. Notes Comput. Sci. 2146, 51--66 (2001; Zbl 1006.94528)]. Our idea can be applied directly to solve the Noisy Multipolynomial Reconstruction problem in the field of error-correcting codes. Compared to the method proposed by \textit{C. Devet}, \textit{I. Goldberg} and \textit{N. Heninger} [``Optimally robust private information retrieval'', in: Proceedings of the 21st USENIX conference on security symposium, Security 2012, Bellevue, WA, USA, 2012. Berkeley, CA: USENIX Association. 15 p. (2012)], our approach is faster.
For the entire collection see [Zbl 1428.94012].The complete cost of cofactor \(h=1\).https://www.zbmath.org/1456.941112021-04-16T16:22:00+00:00"Schwabe, Peter"https://www.zbmath.org/authors/?q=ai:schwabe.peter"Sprenkels, Daan"https://www.zbmath.org/authors/?q=ai:sprenkels.daanSummary: This paper presents optimized software for constant-time variable-base scalar multiplication on prime-order Weierstraß curves using the complete addition and doubling formulas presented by \textit{J. Renes} et al. [Lect. Notes Comput. Sci. 9665, 403--428 (2016; Zbl 1385.14001)]. Our software targets three different microarchitectures: Intel Sandy Bridge, Intel Haswell, and ARM Cortex-M4. We use a 255-bit elliptic curve over \(\mathbb{F}_{2^{255}-19}\) that was proposed by Barreto in 2017. The reason for choosing this curve in our software is that it allows most meaningful comparison of our results with optimized software for Curve25519. The goal of this comparison is to get an understanding of the cost of using cofactor-one curves with complete formulas when compared to widely used Montgomery (or twisted Edwards) curves that inherently have a non-trivial cofactor.
For the entire collection see [Zbl 1428.94012].On the relationship between resilient Boolean functions and linear branch number of S-boxes.https://www.zbmath.org/1456.941102021-04-16T16:22:00+00:00"Sarkar, Sumanta"https://www.zbmath.org/authors/?q=ai:sarkar.sumanta"Mandal, Kalikinkar"https://www.zbmath.org/authors/?q=ai:mandal.kalikinkar"Saha, Dhiman"https://www.zbmath.org/authors/?q=ai:saha.dhimanSummary: Differential branch number and linear branch number are critical for the security of symmetric ciphers. The recent trend in the designs like PRESENT block cipher, ASCON authenticated encryption shows that applying S-boxes that have nontrivial differential and linear branch number can significantly reduce the number of rounds. As we see in the literature that the class of \(4\times 4\) S-boxes have been well-analysed, however, a little is known about the \(n\times n\) S-boxes for \(n\ge 5\). For instance, the complete classification of \(5 \times 5\) affine equivalent S-boxes is still unknown. Therefore, it is challenging to obtain ``the best'' S-boxes with dimension \(\ge 5\) that can be used in symmetric cipher designs. In this article, we present a novel approach to construct S-boxes that identifies classes of \(n\times n \) S-boxes \((n=5,6)\) with differential branch number 3 and linear branch number 3, and ensures other cryptographic properties. To the best of our knowledge, we are the first to report \(6\times 6\) S-boxes with linear branch number 3, differential branch number 3, and with other good cryptographic properties such as nonlinearity 24 and differential uniformity 4.
For the entire collection see [Zbl 1428.94012].Vectorial Boolean functions with very low differential-linear uniformity using Maiorana-McFarland type construction.https://www.zbmath.org/1456.941472021-04-16T16:22:00+00:00"Tang, Deng"https://www.zbmath.org/authors/?q=ai:tang.deng"Mandal, Bimal"https://www.zbmath.org/authors/?q=ai:mandal.bimal"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoySummary: The differential-linear connectivity table (DLCT) of a vectorial Boolean function was recently introduced
by \textit{A. Bar-On} et al. [Lect. Notes Comput. Sci. 11476, 313--342 (2019; Zbl 07162594)].
In this paper we construct a new class of balanced vectorial Boolean functions with very low differential-linear uniformity and provide a combinatorial count of hardware gates which is required to implement such circuits. Here, all the coordinate functions are constructed by modifying the Maiorana-McFarland bent functions. Further, we derive some properties of DLCT and differential-linear uniformity of modified inverse functions.
For the entire collection see [Zbl 1428.94012].Privacy amplification from non-malleable codes.https://www.zbmath.org/1456.940622021-04-16T16:22:00+00:00"Chattopadhyay, Eshan"https://www.zbmath.org/authors/?q=ai:chattopadhyay.eshan"Kanukurthi, Bhavana"https://www.zbmath.org/authors/?q=ai:kanukurthi.bhavana"Obbattu, Sai Lakshmi Bhavana"https://www.zbmath.org/authors/?q=ai:obbattu.sai-lakshmi-bhavana"Sekar, Sruthi"https://www.zbmath.org/authors/?q=ai:sekar.sruthiSummary: Non-malleable codes give us the following property: their codewords cannot be tampered into codewords of related messages. Privacy amplification allows parties to convert their weak shared secret into a fully hidden, uniformly distributed secret key, while communicating on a fully tamperable public channel. In this work, we show how to construct a constant round privacy amplification protocol from any augmented split-state non-malleable code. Existentially, this gives us another primitive (in addition to optimal non-malleable extractors) whose optimal construction would solve the long-standing open problem of building constant round privacy amplification with optimal entropy loss and min-entropy requirement. Instantiating our code with the current best known NMC gives us an 8-round privacy amplification protocol with entropy loss \(O(\log(n)+\kappa\log(\kappa))\) and min-entropy requirement \(\varOmega(\log(n)+\kappa\log(\kappa))\), where \(\kappa\) is the security parameter and \(n\) is the length of the shared weak secret. In fact, for our result, even the weaker primitive of non-malleable randomness encoders suffice.
We view our result as an exciting connection between two of the most fascinating and well-studied information theoretic primitives, non-malleable codes and privacy amplification.
For the entire collection see [Zbl 1428.94012].Public-coin differing-inputs obfuscator for hiding-input point function with multi-bit output and its applications.https://www.zbmath.org/1456.941032021-04-16T16:22:00+00:00"Pan, Dongxue"https://www.zbmath.org/authors/?q=ai:pan.dongxue"Liang, Bei"https://www.zbmath.org/authors/?q=ai:liang.bei"Li, Hongda"https://www.zbmath.org/authors/?q=ai:li.hongda"Ni, Peifang"https://www.zbmath.org/authors/?q=ai:ni.peifangSummary: Differing-inputs obfuscation (diO), first introduced by \textit{B. Barak} et al. [J. ACM 59, No. 2, Article No. 6, 48 p. (2012; Zbl 1281.68118)] and then revisited by \textit{P. Ananth} et al. [``Differing-inputs obfuscation and applications'', Preprint] and \textit{E. Boyle} et al. [Lect. Notes Comput. Sci. 8349, 52--73 (2014; Zbl 1317.94089)], is a natural extension of indistinguishability obfuscation (iO), which captures a security notion that the obfuscations of two efficiently generated programs \(C_0\) and \(C_1\) are indistinguishable if it is hard for an adversary to find an input \(x\) such that \(C_0(x)\ne C_1(x)\), even in the presence of auxiliary information aux that is generated together with \(C_0\) and \(C_1\). A variant notion of diO, called public-coin diO, introduced by \textit{Y. Ishai} et al. [ibid. 9015, 668--697 (2015; Zbl 1336.94054)] relaxes the original definition of diO by requiring that only the actual random coins that were used to sample programs \(C_0\) and \(C_1\) can be used as the auxiliary input. Public-coin diO is indeed of great interest, since it not only allows to evade the implausible results of diO, but also yields several useful applications. However, as far as we know, there was no approach known to build a public-coin differing-input obfuscator neither for general-purpose programs/circuits such as \(\mathrm{NC}^1\) circuits nor for special-purpose function such as some variant of point function.
In this paper, we propose a public-coin differing-inputs obfuscator for a class of function, namely hiding-input point function with multi-bit output (MB-HIPF). We show that the existence of public-coin diO for MB-HIPF can be implied under the existence of auxiliary input point obfuscation for unpredictable distrins (AIPO) which can be instantiated under different assumptions, and the conjecture of the existence of a special-purpose obfuscation for MB-HIPF, which has been considered as a falsifiable assumption. Besides, we show the applications of public-coin diO for MB-HIPF.
We emphasize that even though our result is based on the special-purpose obfuscation conjecture, it at least provides a different mindset on constructing public-coin diO from more concrete building blocks, i.e., a special-purpose obfuscation for MB-HIPF and AIPO. Then we can turn to investigating these specific primitives with a more focused mindset.
For the entire collection see [Zbl 1428.94012].UC priced oblivious transfer with purchase statistics and dynamic pricing.https://www.zbmath.org/1456.940682021-04-16T16:22:00+00:00"Damodaran, Aditya"https://www.zbmath.org/authors/?q=ai:damodaran.aditya"Dubovitskaya, Maria"https://www.zbmath.org/authors/?q=ai:dubovitskaya.maria"Rial, Alfredo"https://www.zbmath.org/authors/?q=ai:rial.alfredoSummary: Priced oblivious transfer (POT) is a cryptographic protocol that can be used to protect customer privacy in e-commerce applications. Namely, it allows a buyer to purchase an item from a seller without disclosing to the latter which item was purchased and at which price. Unfortunately, existing POT schemes have some drawbacks in terms of design and functionality. First, the design of existing POT schemes is not modular. Typically, a POT scheme extends a \(k\)-out-of-N oblivious transfer (OT) scheme by adding prices to the items. However, all POT schemes do not use OT as a black-box building block with certain security guarantees. Consequently, security of the OT scheme needs to be reanalyzed while proving security of the POT scheme, and it is not possible to swap the underlying OT scheme with any other OT scheme. Second, existing POT schemes do not allow the seller to obtain any kind of statistics about the buyer's purchases, which hinders customer and sales management. Moreover, the seller is not able to change the prices of items without restarting the protocol from scratch.
We propose a POT scheme that addresses the aforementioned drawbacks. We prove the security of our POT in the UC framework. We modify a standard POT functionality to allow the seller to receive aggregate statistics about the buyer's purchases and to change prices dynamically. We present a modular construction for POT that realizes our functionality in the hybrid model. One of the building blocks is an ideal functionality for OT. Therefore, our protocol separates the tasks carried out by the underlying OT scheme from the additional tasks needed by a POT scheme. Thanks to that, our protocol is a good example of modular design and can be instantiated with any secure OT scheme as well as other building blocks without reanalyzing security from scratch.
For the entire collection see [Zbl 1428.94012].Optimality of a protocol by Feige-Kilian-Naor for three-party secure computation.https://www.zbmath.org/1456.941072021-04-16T16:22:00+00:00"Pillai, Sibi Raj B."https://www.zbmath.org/authors/?q=ai:pillai.sibi-raj-b"Prabhakaran, Manoj"https://www.zbmath.org/authors/?q=ai:prabhakaran.manoj-m"Prabhakaran, Vinod M."https://www.zbmath.org/authors/?q=ai:prabhakaran.vinod-m"Sridhar, Srivatsan"https://www.zbmath.org/authors/?q=ai:sridhar.srivatsanSummary: In an influential work aimed at understanding the communication requirements of secure computation, \textit{U. Feige} et al. [in: Proceedings of the 26th annual ACM symposium on theory of computing, STOC '94, Montreal, Canada, May 23--25, 1994. New York, NY: Association for Computing Machinery (ACM). 554--563 (1994; Zbl 1344.68030)] introduced a minimal model of secure computation. In that work, among other results, U. Feige et al. presented a simple protocol for the 2 input AND function. It has remained an intriguing question whether the communication and randomness used in this protocol are optimal. While previous work of \textit{D. Data} et al. [Lect. Notes Comput. Sci. 8617, 199--216 (2014; Zbl 1334.94072)] showed that the communication from the two parties with inputs (Alice and Bob) to the third party who gets the output is optimal, the question of optimality for the third message in the protocol -- a common reference string shared between Alice and Bob -- remained open. In this note we show that in fact, this message (and hence all the randomness used in the protocol) is also optimal in the protocol of Feige et al. [loc. cit.]. This improves on a previous result of \textit{S. Rajan S} et al. [``Lower bounds and optimal protocols for three-party secure computation'', in: Proceedings of the IEEE international symposium on information theory, ISIT 2016, Barcelona, Spain, July 10--15, 2016. Piscataway, NJ: IEEE. 1361--1365 (2016; \url{doi:10.1109/ISIT.2016.7541521})], which showed this optimality restricted to protocols where Alice and Bob are deterministic. Further, our result holds even if only a weak secrecy condition is required of the protocol.
For the entire collection see [Zbl 1428.94012].Cryptanalysis of round-reduced KECCAK using non-linear structures.https://www.zbmath.org/1456.941092021-04-16T16:22:00+00:00"Rajasree, Mahesh Sreekumar"https://www.zbmath.org/authors/?q=ai:rajasree.mahesh-sreekumarSummary: In this paper, we present new preimage attacks on KECCAK-384 and KECCAK-512 for 2, 3 and 4 rounds. The attacks are based on non-linear structures (structures that contain quadratic terms). These structures were studied by \textit{J. Guo} et al. [Lect. Notes Comput. Sci. 10031, 249--274 (2016; Zbl 1404.94078)] and \textit{T. Li} and \textit{Y. Sun} [ibid. 11478, 556--584 (2019; Zbl 07162740); \textit{T. Li} et al., ``Preimage attacks on the round-reduced keccak with cross-linear structures'', Trans. Symmetric Cryptol. 2017, No. 4, 39--57 (2017; \url{doi10.13154/tosc.v2017.i4.39-57})] to give preimage attacks on round reduced KECCAK. We carefully construct non-linear structures such that the quadratic terms are not spread across the whole state. This allows us to create more linear equations between the variables and hash values, leading to better preimage attacks. As a result, we present the best theoretical preimage attack on KECCAK-384 and KECCAK-512 for 2 and 3-rounds and also KECCAK-384 for 4-rounds.
For the entire collection see [Zbl 1428.94012].Some cryptanalytic results on TRIAD.https://www.zbmath.org/1456.940912021-04-16T16:22:00+00:00"Kesarwani, Abhishek"https://www.zbmath.org/authors/?q=ai:kesarwani.abhishek"Sarkar, Santanu"https://www.zbmath.org/authors/?q=ai:sarkar.santanu"Venkateswarlu, Ayineedi"https://www.zbmath.org/authors/?q=ai:venkateswarlu.ayineediSummary: In this paper, we study TRIAD-AE, which is submitted in the on-going NIST Lightweight competition. We first estimate an upper bound of the algebraic degree of internal state and key-stream bit seen as multivariate Boolean polynomials. Using this estimation, we find good cubes to analyze reduced round TRIAD-AE. We get a cube of size 32 which gives zero-sum up to 540 rounds, and a cube of size 34 which can distinguish TRIAD-AE up to 550 rounds with a confidence level around 95\%. Further, we also obtained some small size good cubes which distinguishes TRIAD-AE from a random generator. We believe that our analysis can help to understand the security of the cipher better.
For the entire collection see [Zbl 1428.94012].Improved related-tweakey rectangle attacks on reduced-round Deoxys-BC-384 and Deoxys-I-256-128.https://www.zbmath.org/1456.941232021-04-16T16:22:00+00:00"Zhao, Boxin"https://www.zbmath.org/authors/?q=ai:zhao.boxin"Dong, Xiaoyang"https://www.zbmath.org/authors/?q=ai:dong.xiaoyang"Jia, Keting"https://www.zbmath.org/authors/?q=ai:jia.keting"Meier, Willi"https://www.zbmath.org/authors/?q=ai:meier.williSummary: Deoxys-BC is the core internal tweakable block cipher of the authenticated encryption schemes Deoxys-I and Deoxys-II. Deoxys-II is one of the six schemes in the final portfolio of the CAESAR competition, while Deoxys-I is a 3rd round candidate. By well studying the new method proposed by \textit{C. Cid} et al. [``A security analysis of Deoxys and its internal tweakable block ciphers'', IACR Trans. Symmetric Cryptol. 2017, No. 3, 73--107 (2017; \url{doi:10.13154/tosc.v2017.i3.73-107})] and BDT technique proposed by \textit{H. Wang} and \textit{T. Peyrin} [``Boomerang switch in multiple rounds. Application to AES variants and Deoxys'', IACR Trans. Symmetric Cryptol. 2019, No. 1, 142--169 (2019; \url{doi:10.13154/tosc.v2019.i1.142-169})], we find a new 11-round related-tweakey boomerang distinguisher of Deoxys-BC-384 with probability of \(2^{-118.4}\), and give a related-tweakey rectangle attack on 13-round Deoxys-BC-384 with a data complexity of \(2^{125.2}\) and time complexity of \(2^{186.7}\), and then apply it to analyze 13-round Deoxys-I-256-128 in this paper. This is the first time that an attack on 13-round Deoxys-I-256-128 is given, while the previous attack on this version only reaches 12 rounds.
For the entire collection see [Zbl 1428.94012].Automatic tool for searching for differential characteristics in ARX ciphers and applications.https://www.zbmath.org/1456.940872021-04-16T16:22:00+00:00"Huang, Mingjiang"https://www.zbmath.org/authors/?q=ai:huang.mingjiang"Wang, Liming"https://www.zbmath.org/authors/?q=ai:wang.limingSummary: Motivated by the algorithm of differential probability calculation of \textit{H. Lipmaa} and \textit{S. Moriai} [``Efficient algorithms for computing differential properties of addition'', in: Lect. Notes Comput. Sci. 2355, 336--350 (2001; \url{doi:10.1007/3-540-45473-X_28})], we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel concept of combinational DDT and the corresponding construction algorithm are introduced to make it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the optimization strategies with branch and bound search algorithm, we can reduce the search space of the first round and prune the invalid difference branches of the middle rounds. Applying this tool, the provable optimal differential trails covering more rounds for SPECK32/48/64 with tight probabilities can be found, and the differentials with larger probabilities are also obtained. In addition, the optimal differential trails cover more rounds than exisiting results for SPARX variants are obtained. A 12-round differential with a probability of \(2^{-54.83}\) for SPARX-64, and a 11-round differential trail with a probability of \(2^{-53}\) for SPARX-128 are found. For CHAM-\(64/128\) and CHAM-\(128/^\ast\), the \(39/63\)-round differential characteristics we find cover \(3/18\) rounds more than the known results respectively.
For the entire collection see [Zbl 1428.94012].Analogy between gambling and measurement-based work extraction.https://www.zbmath.org/1456.940352021-04-16T16:22:00+00:00"Vinkler, Dror A."https://www.zbmath.org/authors/?q=ai:vinkler.dror-a"Permuter, Haim H."https://www.zbmath.org/authors/?q=ai:permuter.haim-henri"Merhav, Neri"https://www.zbmath.org/authors/?q=ai:merhav.neriImproved filter permutators for efficient FHE: better instances and implementations.https://www.zbmath.org/1456.941002021-04-16T16:22:00+00:00"Méaux, Pierrick"https://www.zbmath.org/authors/?q=ai:meaux.pierrick"Carlet, Claude"https://www.zbmath.org/authors/?q=ai:carlet.claude"Journault, Anthony"https://www.zbmath.org/authors/?q=ai:journault.anthony"Standaert, François-Xavier"https://www.zbmath.org/authors/?q=ai:standaert.francois-xavierSummary: We revisit the design of filter permutators as a general approach to build stream ciphers that can be efficiently evaluated in a fully homomorphic manner. We first introduce improved filter permutators that allow better security analyses, instances and implementations than the previously proposed FLIP family of ciphers. We also put forward the similarities between these improved constructions and a popular PRG design by \textit{O. Goldreich} [Lect. Notes Comput. Sci. 6650, 76--87 (2011; Zbl 1306.94056)]. We then propose a methodology to evaluate the performance of such symmetric cipher designs in a FHE setting, which primarily focuses on the noise level of the symmetric ciphertexts (hence on the amount of operations on these ciphertexts that can be homomorphically evaluated). Evaluations through HElib show that instances of improved filter permutators using direct sums of monomials as filter outperform all existing ciphers in the literature based on this criteria. We also discuss the (limited) overheads of these instances in terms of latency and throughput.
For the entire collection see [Zbl 1428.94012].Rerandomizable signatures under standard assumption.https://www.zbmath.org/1456.940612021-04-16T16:22:00+00:00"Chatterjee, Sanjit"https://www.zbmath.org/authors/?q=ai:chatterjee.sanjit"Kabaleeshwaran, R."https://www.zbmath.org/authors/?q=ai:kabaleeshwaran.rSummary: The Camenisch-Lysyanskaya rerandomizable signature (CL-RRS) scheme is an important tool in the construction of privacy preserving protocols. One of the limitations of CL-RRS is that the signature size is linear in the number of messages to be signed. \textit{D. Pointcheval} and \textit{O. Sanders} [Lect. Notes Comput. Sci. 9610, 111--126 (2016; Zbl 1332.94078)] introduced a variant of rerandomizable signature (PS-RRS) scheme which removes the above limitation. However, the security of PS-RRS scheme was proved under an interactive assumption. \textit{D. Pointcheval} and \textit{O. Sanders} [ibid. 10808, 319--338 (2018; Zbl 07154109)] improved this to give a reduction under a parameterized assumption.
\textit{M. Gerbush} et al. [ibid. 7658, 25--42 (2012; Zbl 1290.94149)] introduced the dual-form signature technique to remove the dependency on interactive/parameterized assumption. They applied this technique on the CL-RRS scheme (for single message) and proved its unforgeability under static assumptions instead of the interactive assumption used in the original work but in the symmetric composite-order pairing setting.
In this work, we realize a fully rerandomizable signature scheme in the prime order setting without random oracle based on the SXDH assumption. The signature structure is derived from Ghadafi's structure-preserving signature. We first apply the dual-form signature technique to obtain a composite-order variant, called RRSc. A signature in RRSc consists of only two group elements and is thus independent of the message block length. The security of the proposed scheme is based on subgroup hiding assumptions. Then we use the dual pairing vector space framework to obtain a prime-order variant called RRS and prove its security under the SXDH assumption.
For the entire collection see [Zbl 1428.94012].Modification tolerant signature schemes: location and correction.https://www.zbmath.org/1456.940882021-04-16T16:22:00+00:00"Idalino, Thaís Bardini"https://www.zbmath.org/authors/?q=ai:bardini-idalino.thais"Moura, Lucia"https://www.zbmath.org/authors/?q=ai:moura.lucia"Adams, Carlisle"https://www.zbmath.org/authors/?q=ai:adams.carlisle-mSummary: This paper considers malleable digital signatures, for situations where data is modified after it is signed. They can be used in applications where either the data can be modified (collaborative work), or the data must be modified (redactable and content extraction signatures) or we need to know which parts of the data have been modified (data forensics). A classical digital signature is valid for a message only if the signature is authentic and not even one bit of the message has been modified. We propose a general framework of modification tolerant signature schemes (MTSS), which can provide either location only or both location and correction, for modifications in a signed message divided into \(n\) blocks. This general scheme uses a set of allowed modifications that must be specified. We present an instantiation of MTSS with a tolerance level of \(d\), indicating modifications can appear in any set of up to \(d\) message blocks. This tolerance level \(d\) is needed in practice for parametrizing and controlling the growth of the signature size with respect to the number \(n\) of blocks; using combinatorial group testing (CGT) the signature has size \(O(d^2 \log n)\) which is close to the best known lower bound of \(\varOmega(\frac{d^2}{\log d}(\log n))\). There has been work in this very same direction using CGT by \textit{M. T. Goodrich} et al. [Lect. Notes Comput. Sci. 3531, 206--221 (2005; Zbl 1126.68395)] and \textit{T. Bardini Idalino} et al. [Inf. Process. Lett. 115, No. 10, 731--737 (2015; Zbl 1338.94062)]. Our work differs from theirs in that in one scheme we extend these ideas to include corrections of modification with provable security, and in another variation of the scheme we go in the opposite direction and guarantee privacy for redactable signatures, in this case preventing any leakage of redacted information.
For the entire collection see [Zbl 1428.94012].PKP-based signature scheme.https://www.zbmath.org/1456.940492021-04-16T16:22:00+00:00"Beullens, Ward"https://www.zbmath.org/authors/?q=ai:beullens.ward"Faugère, Jean-Charles"https://www.zbmath.org/authors/?q=ai:faugere.jean-charles"Koussa, Eliane"https://www.zbmath.org/authors/?q=ai:koussa.eliane"Macario-Rat, Gilles"https://www.zbmath.org/authors/?q=ai:macario-rat.gilles"Patarin, Jacques"https://www.zbmath.org/authors/?q=ai:patarin.jacques"Perret, Ludovic"https://www.zbmath.org/authors/?q=ai:perret.ludovicSummary: In this document, we introduce PKP-DSS: a digital signature scheme based on the Permuted Kernel problem (PKP) [\textit{A. Shamir}, ``An efficient identification scheme based on permuted kernels (extended abstract)'', Lect. Notes Comput. Sci. 435, 606--609 (1989; \url{doi:10.1007/0-387-34805-0_54})]. PKP is a simple NP-hard [\textit{M. Gary} and \textit{D, Johnson}, Computers and intractability. A guide to NP-completenes. New York, NY, USA: W. H. Freeman \& Co (1979)] combinatorial problem that consists of finding a kernel for a publicly known matrix, such that the kernel vector is a permutation of a publicly known vector. This problem was used to develop an identification scheme (IDS) which has a very efficient implementation on low-cost smart cards. From this zero-knowledge identification scheme, we derive PKP-DSS with the traditional Fiat-Shamir transform [\textit{A. Fiat} and \textit{A. Shamir}, Lect. Notes Comput. Sci. 263, 186--194 (1987; Zbl 0636.94012)]. Thus, PKP-DSS has a security that can be provably reduced, in the (classical) random oracle model, to the hardness of random instances of PKP (or, if wanted, to any specific family of PKP instances). We propose parameter sets following the thorough analysis of the state-of-the-art attacks on PKP presented in [\textit{E. Koussa}, \textit{G. Macario-Rat} and \textit{J. Patarin}, ``On the complexity of the permuted kernel problem'', Preprint, \url{https://eprint.iacr.org/2019/412.pdf}]. We show that PKP-DSS is competitive with other signatures derived from zero-knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size of approximately 20 KBytes for 128 bits of classical security, which is approximately 30\% smaller than MQDSS. Moreover, our proof-of-concept implementation shows that PKP-DSS-128 is an order of magnitude faster than MQDSS which in its turn is faster than Picnic2, SPHINCS, \(\dots\).
Since the PKP is NP-hard and since there are no known quantum attacks for solving PKP significantly better than classical attacks, we believe that our scheme is post-quantum secure.
For the entire collection see [Zbl 1428.94012].Locally decodable and updatable non-malleable codes and their applications.https://www.zbmath.org/1456.940672021-04-16T16:22:00+00:00"Dachman-Soled, Dana"https://www.zbmath.org/authors/?q=ai:dachman-soled.dana"Liu, Feng-Hao"https://www.zbmath.org/authors/?q=ai:liu.feng-hao"Shi, Elaine"https://www.zbmath.org/authors/?q=ai:shi.elaine"Zhou, Hong-Sheng"https://www.zbmath.org/authors/?q=ai:zhou.hong-shengThe paper provides the reader with two new constructions regarding locally decodable and updatable non-malleable codes, a notion introduced by the authors of the mentioned work. The proposed concept is showed to be very important in terms of security against physical attacks.
The paper is structured in four sections. The introduction is a very well documented section with respect to non-malleable codes, physical attacks and the connection between these two notions as well as their applications both in coding theory and cryptography. Also, local decodability and updatability are tackled. The introduction includes a set of definitions which are further used by the authors to present their schemes. The recalled references and concepts represent the main ideas on which the article is based. Moreover, subsequent work is presented at the end of the section. In Section 2, entitled Locally decodable and updatable non-malleable codes, some detailed preliminaries regarding leakage-resilient codes are presented, the proposed notion of locally decodable and updatable non-malleable codes is discussed and the security of some closely related concepts is analyzed. Section 3, Our constructions, presents both a one-time secure construction of locally decodable and updatable non-malleable codes and a version which is resistant to continual attacks. Also, the security proofs are very well detailed and other instantiations are given at the end of the section. In Tamper and leakage-resilient RAM, the 4th section of the article, the authors discuss methods of securing RAM computation against memory tampering and leakage attacks from the point of view of their proposed notion. Moreover, the security of their proposed applications is discussed. Relevant references are given at the end of the paper.
The technical concepts and properties introduced throughout the article are described in a clear and formal manner. The results of this work are suitable for specialized graduate students which already have technical background regarding the topic of non-malleable codes and physical attacks and, especially, researchers.
We could not identify aspects which are not in accordance with the scope of the paper or other incorrect details. The work misses a section of conclusions and very few unimportant typos have been spotted.
In conclusion, we believe that the current article is an impressive work especially for researchers interested in technical aspects and new results regarding non-malleable codes and their applications.
Reviewer: Diana Maimut (Bucureşti)Thermodynamic limits to information harvesting by sensory systems.https://www.zbmath.org/1456.940262021-04-16T16:22:00+00:00"Bo, Stefano"https://www.zbmath.org/authors/?q=ai:bo.stefano"Del Giudice, Marco"https://www.zbmath.org/authors/?q=ai:giudice.marco-del"Celani, Antonio"https://www.zbmath.org/authors/?q=ai:celani.antonioCognitive information measurements: a new perspective.https://www.zbmath.org/1456.680372021-04-16T16:22:00+00:00"Chen, Min"https://www.zbmath.org/authors/?q=ai:chen.min|chen.min.2|chen.min.1|chen.min.3"Hao, Yixue"https://www.zbmath.org/authors/?q=ai:hao.yixue"Gharavi, Hamid"https://www.zbmath.org/authors/?q=ai:gharavi.hamid"Leung, Victor C. M."https://www.zbmath.org/authors/?q=ai:leung.victor-c-mSummary: From a traditional point of view, the value of information does not change during transmission. The Shannon information theory considers information transmission as a statistical phenomenon for measuring the communication channel capacity. However, in modern communication systems, information is spontaneously embedded with a cognitive link during the transmission process, which requires a new measurement that can incorporate continuously changing information values. In this paper, we introduce the concept of cognitive information value and a method of measuring such information. We first describe the characteristics of cognitive information followed by an introduction of the concept of cognitive information in measuring information popularity. The new measurement is based on the mailbox principle in the information value chain. This is achieved by encapsulating the information as a mailbox for transmission where the cognition is continuously implemented during the transmission process. Finally, we set up a cognitive communication system based on a combination of the traditional communication system and cognitive computing. Experimental results attest to the impact of incorporating cognitive value in the performance of 5G networks.Quaternion weighted spherical Bessel-Fourier moment and its invariant for color image reconstruction and object recognition.https://www.zbmath.org/1456.682252021-04-16T16:22:00+00:00"Yang, Tengfei"https://www.zbmath.org/authors/?q=ai:yang.tengfei"Ma, Jianfeng"https://www.zbmath.org/authors/?q=ai:ma.jianfeng"Miao, Yinbin"https://www.zbmath.org/authors/?q=ai:miao.yinbin"Wang, Xuan"https://www.zbmath.org/authors/?q=ai:wang.xuan"Xiao, Bin"https://www.zbmath.org/authors/?q=ai:xiao.bin"He, Bing"https://www.zbmath.org/authors/?q=ai:he.bing.1|he.bing|he.bing.2|he.bing.4|he.bing.3"Meng, Qian"https://www.zbmath.org/authors/?q=ai:meng.qianSummary: Moments with capable of representing global features have been widely used in image analysis, pattern recognition and computer vision applications. However, existing image moment theories are still mainly paid close attention to gray-scale images. In this paper, a new quaternion moment termed as Quaternion weighted Spherical Bessel-Fourier Moment (QSBFM) is proposed to address the issue of color image analysis. Moreover, the relationship between QSBFM and the conventional weighted spherical Bessel-Fourier moment has been established so that the computational cost of QSBFM can be efficiently reduced. Furthermore, the natively geometric invariance of QSBFM is presented and discussed in detail. Experimental results show that the proposed QSBFM outperforms frequently-used quaternion moments including quaternion Bessel-Fourier moment, quaternion Radial-Harmonic-Fourier moment, quaternion Chebyshev-Fourier moment and quaternion orthogonal Fourier-Mellin moment in terms of the color image reconstruction capability and invariant recognition accuracy in noise-free, Salt \& Pepper noise and the Gaussian noise conditions.Accountable identity-based encryption with distributed private key generators.https://www.zbmath.org/1456.941252021-04-16T16:22:00+00:00"Zhao, Zhen"https://www.zbmath.org/authors/?q=ai:zhao.zhen"Wu, Ge"https://www.zbmath.org/authors/?q=ai:wu.ge"Susilo, Willy"https://www.zbmath.org/authors/?q=ai:susilo.willy"Guo, Fuchun"https://www.zbmath.org/authors/?q=ai:guo.fuchun"Wang, Baocang"https://www.zbmath.org/authors/?q=ai:wang.baocang"Hu, Yupu"https://www.zbmath.org/authors/?q=ai:hu.yupuSummary: Distributed private key generators (PKGs) in identity-based encryption (IBE) is a viable approach to mitigate the inherent key escrow problem, where the user's private key is generated by multiple PKGs, and hence, there is no single PKG can impersonate the user. Nevertheless, these PKGs can still collude to generate a user's private key and auction it without the risk of being caught. In the traditional IBE setting, accountable IBE can identify the creator of a pirated private key between the user and the PKG. Unfortunately, the similar problem in IBE with distributed PKGs remains an open research problem. To fill this gap, we concentrate on adding accountability to IBE with distributed PKGs. Specifically, we propose the formal definition of A-IBE with distributed PKGs (A-dIBE) and the corresponding security models. Subsequently, we present a concrete construction with the corresponding security proof. This cryptographic primitive enjoys the advantages of both the IBE with distributed PKGs and A-IBE. Specifically, it distributes the power to multiple PKGs, while preserving the traceability that could give a convincing judgment to identify the suspect between the user and the PKGs. Furthermore, our construction could be easily extended to achieve IND-ID-CCA security and the revocation of the PKGs is efficient.Multilevel similarity model for high-resolution remote sensing image registration.https://www.zbmath.org/1456.940122021-04-16T16:22:00+00:00"Wang, Xianmin"https://www.zbmath.org/authors/?q=ai:wang.xianmin"Li, Jing"https://www.zbmath.org/authors/?q=ai:li.jing.4|li.jing.11|li.jing.5|li.jing.3|li.jing.2|li.jing|li.jing.1|li.jing.6|li.jing.12|li.jing.7|li.jing.13|li.jing.10"Li, Jin"https://www.zbmath.org/authors/?q=ai:li.jin.4|li.jin|li.jin.5|li.jin.3|li.jin.2|li.jin.1"Yan, Hongyang"https://www.zbmath.org/authors/?q=ai:yan.hongyangSummary: Image registration is a prerequisite and the basis for many important applications of remote sensing images. Compared with medium-/low-resolution images, high-resolution (HR) remote sensing images exhibit considerable resolution differences, complex distortions and repeatable textures. Most of the existing registration methods are designed for images with medium/low resolutions. However, these methods typically suffer from many false matches of keypoints when working with HR images. This problem often causes automatic registration to fail in applications. To address these problem, we propose a multilevel similarity model for HR remote sensing image registration. The multilevel similarity model includes three progressive levels of elements: the similarity of keypoint physical size (i.e., point-like similarity), the similarity of textures between two keypoints (i.e., line-like similarity) and the similarity of keypoint space relationship (i.e., plane-like similarity). First, a candidate match set of keypoints is identified depending upon the physical sizes of the keypoint blob-like structures, so that many useless keypoints can be significantly excluded. Then, a minimum spanning tree is developed to discover the false matches, where the weights of the tree are estimated based on the similarities of image windows created between two target keypoints and their candidate homologous keypoints. Finally, a spatial relationship matrix is constructed to further refine the matches between images by efficiently coding the relative spatial locations among keypoints. Experiments were conducted on various HR remote sensing images with different resolutions and distortions, and the experimental results demonstrate the effectiveness of our method.Fast hierarchical wavelet-domain motion estimation for arbitrarily shaped visual objects.https://www.zbmath.org/1456.940102021-04-16T16:22:00+00:00"Song, Chuan-Ming"https://www.zbmath.org/authors/?q=ai:song.chuanming"Wang, Xiang-Hai"https://www.zbmath.org/authors/?q=ai:wang.xianghai"Yin, Bao-Cai"https://www.zbmath.org/authors/?q=ai:yin.baocai"Liu, Ding-Kun"https://www.zbmath.org/authors/?q=ai:liu.ding-kunSummary: Motion estimation is widely used for video compression as it reduces the memory requirements of any video file while maintaining high visual quality. But the computational cost consumed by motion estimation/compensation usually accounts for more than 50\%, even to 80\%, of the total cost of the encoder. So researchers try to develop fast motion estimation algorithms to lower the computational complexity. Moreover, few studies have been concentrated on the efficient motion estimation of arbitrarily shaped visual objects, which particularly pays insufficient attention to boundary continuity of the motion-compensated objects as well. In this research, we present a hierarchical wavelet-domain approach to motion estimation of visual objects with arbitrary shapes. We explore the guiding role of binary alpha-plane in assisting motion estimation of visual objects, and bring forward a binary alpha-plane matching scheme. It constrains the intensity-based motion estimation into a small subset of initial candidate vectors in the search window. This both accelerates search speed and helps to produce coherent object boundary. Moreover, we employ the low-band-shift technique to eliminate the wavelet's shift-variance effect. And based on the observation that high frequency subbands of wavelet contribute little to calculating motion vectors, a new matching function is derived for fast wavelet-domain motion estimation. Coupled with the alpha-plane matching and the devised matching function, a hierarchical low-band-based motion estimation approach is further proposed. Through executing a refined search around the initial candidate vectors using only the low frequency subband at each scale, our approach achieves a satisfying balance between prediction accuracy and computational efficiency. Experimental results show that by using the standard accuracy measurements and the benchmark video sequences, the performance of the proposed approach is close to the full search with a matching quality over 99\%, and with 95.80\% reduction in complexity.Computer algebra tales on Goppa codes and McEliece cryptography.https://www.zbmath.org/1456.941392021-04-16T16:22:00+00:00"Sayols, Narcís"https://www.zbmath.org/authors/?q=ai:sayols.narcis"Xambó-Descamps, Sebastià"https://www.zbmath.org/authors/?q=ai:xambo-descamps.sebastianSummary: The 40-year old McEliece public-key cryptosystem is revisited with the help of recently developed resources: an improved Peterson-Gorenstein-Zierler decoder for alternant error-correcting codes; PyECC, a purely Python CAS; a package of PyECC functional utilities for the computations involved in defining, coding and decoding error-correcting codes; and a Web page with free-access to companion materials. The last two tales trace the evolution of the McEliece systems and provide an account about their current security levels.Self-dual codes over chain rings.https://www.zbmath.org/1456.941322021-04-16T16:22:00+00:00"Eisenbarth, Simon"https://www.zbmath.org/authors/?q=ai:eisenbarth.simon"Nebe, Gabriele"https://www.zbmath.org/authors/?q=ai:nebe.gabrieleSummary: In this paper, we study self-dual codes over commutative Artinian chain rings. Let \(R\) be such a ring, \(x\) be a generator of the unique maximal ideal of \(R\) and \(a\in\mathbb{N}_0\) maximal such that \(x^a\ne 0\). A code \(C\) over \(R\) of length \(t\) is an \(R\)-submodule of the free module \(R^t\). Multiplying powers of \(x\) to \(C\) defines the finite chain of subcodes
\[
C \supseteq C^{(1)} := C x \supseteq C^{(2)} := C x^2 \supseteq \dots \supseteq C^{(a)} := Cx^a \supseteq \lbrace 0 \rbrace .
\]
In this paper, we show that if \(C\) is a self-dual code in \(R^t\), then \(C^{(a)}\) is a (hermitian) self-dual code over the residue field \(\mathbb{F}= R / \langle x \rangle\) if and only if \(C\) a free \(R\)-module (thus isomorphic to \(R^{\frac{t}{2}} \)). In this case, all codes \(C^{(i)}\) are self-dual codes in suitable bilinear or Hermitian spaces \(W_i\) over \(\mathbb{F}\) and we describe a method to construct all lifts \(C\) of a given self-dual code \(C^{(a)}\) over \(\mathbb{F}\) that are self-dual, free codes over \(R\). We apply this technique to codes over finite fields of characteristic \(p\) admitting an automorphism whose order is a power of \(p\). For illustration, we show that the well-known Pless code \(P_{36}\) is the only extremal, ternary code of length 36 with an automorphism of order 3, strengthening a result of Huffman, who showed the assertion for all prime orders \(\ge 5\).Minimax rate of testing in sparse linear regression.https://www.zbmath.org/1456.620832021-04-16T16:22:00+00:00"Carpentier, A."https://www.zbmath.org/authors/?q=ai:carpentier.anne-sophie|carpentier.alexandra|carpentier.a-v"Collier, O."https://www.zbmath.org/authors/?q=ai:collier.olivier"Comminges, L."https://www.zbmath.org/authors/?q=ai:comminges.laetitia"Tsybakov, A. B."https://www.zbmath.org/authors/?q=ai:tsybakov.alexandre-b"Wang, Yu."https://www.zbmath.org/authors/?q=ai:wang.yue-lan|wang.yuyao|wang.yu.8|wang.yue.3|wang.yue.2|wang.yue.1|wang.yuren|wang.yuanming.1|wang.yunfan|wang.yuechen|wang.yunxia|wang.yuxuan|wang.yuqiang|wang.yuhan|wang.yu-hsiang|wang.yuejun|wang.yulu|wang.yujuang|wang.yujiao|wang.yuanlun|wang.yunteng|wang.yuqing|wang.yuchen|wang.yulin|wang.yuting|wang.yuanye|wang.yuefei.1|wang.yueh-jir|wang.yunbo|wang.yunping|wang.yunjiao|wang.yueshan|wang.yudong|wang.yuandi|wang.yuanjun|wang.yunqian|wang.yuanzheng|wang.yuanni|wang.yunpen|wang.yuchuang|wang.yuying|wang.yuanhan|wang.yueran|wang.yuanmei|wang.yuanhua|wang.yubing|wang.yuanqing|wang.yun-yu|wang.yuexia|wang.yuannian|wang.yunxiao|wang.yuanhui|wang.yuanyun|wang.yuan-ruo|wang.yufeng|wang.yuanzhen|wang.yu-wu|wang.yu-chung|wang.yuye|wang.yuhai|wang.yuxiao|wang.yun-chao|wang.yuji|wang.yuhang|wang.yukun|wang.yuli|wang.yuntao|wang.yuyi|wang.yuquan|wang.yuejuan|wang.yucang|wang.yunshi|wang.yuanda|wang.yu-fang-helena|wang.yucheng|wang.yunixa|wang.yuan.1|wang.yunjiu|wang.yuchuan|wang.yuanjia|wang.yuanpei|wang.yunliang|wang.yunqing|wang.yuanlong|wang.yuanbin|wang.yusong|wang.yunhan|wang.yuan-jay|wang.yuan.3|wang.yuexuan|wang.yuanyi|wang.yueji|wang.yujue|wang.yu-jie|wang.yulei|wang.yun-tsz|wang.yuanzhang|wang.yumin|wang.yuxing|wang.yuexing|wang.yumei|wang.yuxin|wang.yunyan|wang.yuangong|wang.yuxiong|wang.yuanxun-ethan|wang.yubin|wang.yushun|wang.yuyuan|wang.yuandong|wang.yu-chiun|wang.yunying|wang.yunling|wang.yusheng|wang.yuanhun|wang.yuan-gen|wang.yue-wen|wang.yuxia|wang.yuancen|wang.yuanjiu|wang.yun-po|wang.yunge|wang.yu-kuo|wang.yuanchun|wang.yunlong|wang.yushan|wang.yuanting|wang.yuan|wang.yunkai|wang.yuxi|wang.yueke|wang.yunzeng|wang.yuzhong|wang.yuanchang|wang.yunkui|wang.yuejian|wang.yuchao|wang.yuanjin|wang.yuzhuo|wang.yulong|wang.yuhao|wang.yung-yi|wang.yuchan|wang.yupeng|wang.yuexin|wang.yu-tsung|wang.yuechao|wang.yun-shih|wang.yuqiao|wang.yuefang|wang.yubo|wang.yueyuan|wang.yuncheng|wang.yuzhen|wang.yueyi|wang.yuliang|wang.yuejiao|wang.yunjuan|wang.yuanliang|wang.yuzhou|wang.yuchung-j|wang.yuehong|wang.yue-feng|wang.yueming|wang.yuefen|wang.yunheng|wang.yu-chi|wang.yuanfang|wang.yuanzhan|wang.yuncai|wang.yuejin|wang.yuan-shyon|wang.yunhong|wang.yunji|wang.yupin|wang.yunjiang|wang.yun-bao|wang.yuh-shyang|wang.yujing|wang.yuangdi|wang.yuangang|wang.yue-li|wang.yuewu|wang.yunxiang|wang.yutao|wang.yunong|wang.yufang|wang.yunyi|wang.yuan-ji|wang.yuefei.2|wang.yuzhi|wang.yue-cong|wang.yuanxin|wang.yunjian|wang.yuh-rau|wang.yun-jen|wang.yung-kun|wang.yusu|wang.yueheng|wang.yue-qing|wang.yubei|wang.yuanping|wang.yunfen|wang.yukang|wang.yunlan|wang.yung-terng|wang.yunzhu|wang.yupei|wang.yuanquan|wang.yurong|wang.yuda|wang.yueyun|wang.yun-che|wang.yunbiao|wang.yuxue|wang.yuankun|wang.yu-chiang-frank|wang.yu-ning|wang.yuewei|wang.yuanzhi|wang.yu-zhen|wang.yunming|wang.yungchin|wang.yuyan|wang.yuexun|wang.yuntong|wang.yuzhu|wang.yueyue|wang.yushun.1|wang.yuanyuan|wang.yuedong|wang.yunhua|wang.yuanbo|wang.yuhua|wang.yu-u|wang.yunzhao|wang.yuexian|wang.yuehu|wang.yuling|wang.yung-ming|wang.yuyong|wang.yudou|wang.yuenan|wang.yuangan|wang.yuyun|wang.yuhuan|wang.yuyin|wang.yutian|wang.yugang|wang.yuan.2|wang.yuan-xu|wang.yuanshi|wang.yuming|wang.yuqin|wang.yujin|wang.yuke|wang.yunwen|wang.yung-chung|wang.yucong|wang.yun-chen|wang.yunfeng|wang.yuwen-w|wang.yunhe|wang.yuanfeng|wang.yuyang|wang.yuanqi|wang.yuehui|wang.yuanqin|wang.yuguo|wang.yuee|wang.yuqi|wang.yuhui|wang.yunpeng|wang.yunqiu|wang.yueyong|wang.yue-sheng|wang.yuelin|wang.yuhong|wang.yujun|wang.yuguang|wang.yupan|wang.yujia|wang.yunxin|wang.yuancheng|wang.yuxiang|wang.yunhai|wang.yuehuan|wang.yu-xiang|wang.yufu|wang.yufei|wang.yunjie|wang.yuankwei|wang.yuchun|wang.yunhui|wang.yuepeng|wang.yuzhe|wang.yutong|wang.yuenda|wang.yungxiao|wang.yunhu|wang.yuanzhe|wang.yujuan|wang.yu-sen|wang.yueling|wang.yunfei|wang.yung-hsin|wang.yuemin|wang.yuhe|wang.yucai|wang.yuzhao|wang.yueping|wang.yun|wang.yueying|wang.yuwei|wang.yu-luen|wang.yung-hung|wang.yuyu|wang.yuanzhuo|wang.yusun|wang.yuesheng|wang.yunsheng|wang.yuan-jiun|wang.yuanhang|wang.yuankai|wang.yuru|wang.yuansheng|wang.yufen|wang.yuanguo|wang.yuheng|wang.yuanheng.1|wang.yuanxi|wang.yunyun|wang.yuansong|wang.yukai|wang.yuwen.1|wang.yuer|wang.yuanhong|wang.yue-hua|wang.yupu|wang.yuping.1|wang.yulan.4Summary: We consider the problem of testing the hypothesis that the parameter of linear regression model is 0 against an \(s\)-sparse alternative separated from 0 in the \(\ell_2\)-distance. We show that, in Gaussian linear regression model with \(p < n\), where \(p\) is the dimension of the parameter and \(n\) is the sample size, the non-asymptotic minimax rate of testing has the form \(\sqrt{(s/n)\log (\sqrt{p}/s)}\). We also show that this is the minimax rate of estimation of the \(\ell_2\)-norm of the regression parameter.Some reliability properties of bivariate cumulative residual Tsallis entropy.https://www.zbmath.org/1456.940342021-04-16T16:22:00+00:00"Raju, David Chris"https://www.zbmath.org/authors/?q=ai:raju.david-chris"Sunoj, S. M."https://www.zbmath.org/authors/?q=ai:sunoj.sreenarayanapurath-madhavan"Rajesh, G."https://www.zbmath.org/authors/?q=ai:rajesh.govindan|rajesh.ganapathiSummary: \textit{G. Rajesh} and \textit{S. M. Sunoj} [Stat. Pap. 60, No. 3, 933--943 (2019; Zbl 1419.62015)] have introduced an alternative form of cumulative Tsalli's Entropy for continuous random variables and studied its importance in reliability studies. The present study aims at extending this measure to the bivariate case based on two types of conditioning, viz. conditionally specified and survival models. In a two component system, it measures the uncertainty associated with one component when the other component is either failed or survived a specified period of time. Characterization results are established for important bivariate lifetime models. We also propose an empirical and kernel-based plug-in estimators for conditional cumulative Tsalli's entropy and study its performance using simulated data. A real data analysis is also carried out to evaluate the usefullness of the empirical estimator of a bivariate dynamic cumulative Tsalllis entropy and compared its performance with that of similar estimator due to \textit{M. M. Sati} and \textit{H. Singh} [J. Appl. Math. Inform. 35, No. 1--2, 45--58 (2017; Zbl 1378.65104)].A contention-free parallel access by butterfly networks for turbo interleavers.https://www.zbmath.org/1456.941412021-04-16T16:22:00+00:00"Nieminen, Esko"https://www.zbmath.org/authors/?q=ai:nieminen.eskoNo review copy delivered.Algebraic geometry codes over abelian surfaces containing no absolutely irreducible curves of low genus.https://www.zbmath.org/1456.140562021-04-16T16:22:00+00:00"Aubry, Yves"https://www.zbmath.org/authors/?q=ai:aubry.yves"Berardini, Elena"https://www.zbmath.org/authors/?q=ai:berardini.elena"Herbaut, Fabien"https://www.zbmath.org/authors/?q=ai:herbaut.fabien"Perret, Marc"https://www.zbmath.org/authors/?q=ai:perret.marcIn this paper, a theoretical study of algebrao-geometric codes constructed from abelian surfaces \(A\) defined over finite fields \(F_q\) is provided. Let \(m = \lfloor 2 \sqrt{q}\rfloor\), \(H\) be an ample divisor on \(A\) rational over \(F_q\) and \(r\) be a positive integer such that \(rH\) is very ample. We denote by \(Tr(A)\) the trace of \(A\) and by \(C(A, rH)\) the generalised evaluation code. Then, it is proved that the distance \(d(A, rH)\) of the code \(C(A, rH)\) satisfies the inequality: \[d(A, rH) \geq \# A(F_q) - rH^2(q + 1 -Tr(A) + m) - r^2m \frac{H^2}{2}.\] Furthermore, if \(A\) is simple and contains no absolutely irreducible curves of arithmetic genus \(\leq \ell\), then \[d(A, rH) \geq \# A(F_q)-\max\left( r\left\lfloor \sqrt{\frac{H^2}{2}}\right \rfloor (\ell-1), \varphi(1), \varphi\left(\left\lfloor r \sqrt{\frac{H^2}{2 \ell}}\right\rfloor \right) \right), \] where \[ \varphi(x) := m \left( r \sqrt{\frac{H^2}{2}} - x\sqrt{\ell} \right)^2 +2m\ell \left( r \sqrt{\frac{H^2}{2}} - x\sqrt{\ell} \right)+\] \[ x\Big(q+1-Tr(A)+(\ell-1)(m-\sqrt{\ell})\Big)+r\sqrt{\frac{H^2}{2}}\ (\ell-1).\] The proof of this result is relied on a characterisation of isogeny classes of abelian surfaces containing Jacobians of curves of genus 2 obtained by \textit{E. W. Howe} et al. [Ann. Inst. Fourier 59, No. 1, 239--289 (2009; Zbl 1236.11058)].
Reviewer: Dimitros Poulakis (Thessaloniki)Multipartite information flow for multiple Maxwell demons.https://www.zbmath.org/1456.800102021-04-16T16:22:00+00:00"Horowitz, Jordan M."https://www.zbmath.org/authors/?q=ai:horowitz.jordan-mStrong Kac's chaos in the mean-field Bose-Einstein condensation.https://www.zbmath.org/1456.601972021-04-16T16:22:00+00:00"Albeverio, Sergio"https://www.zbmath.org/authors/?q=ai:albeverio.sergio-a"De Vecchi, Francesco C."https://www.zbmath.org/authors/?q=ai:de-vecchi.francesco-c"Romano, Andrea"https://www.zbmath.org/authors/?q=ai:romano.andrea"Ugolini, Stefania"https://www.zbmath.org/authors/?q=ai:ugolini.stefaniaMicropaying to a distributed payee with instant confirmation.https://www.zbmath.org/1456.911372021-04-16T16:22:00+00:00"Ni, Peifang"https://www.zbmath.org/authors/?q=ai:ni.peifang"Li, Hongda"https://www.zbmath.org/authors/?q=ai:li.hongda"Pan, Dongxue"https://www.zbmath.org/authors/?q=ai:pan.dongxueSummary: Micropayment means the value of transaction is small, i.e., payment worths a few pennies. To achieve instant micropayments,
\textit{M. Hearn} and \textit{S. J. Spilman} [Bitcoin contracts (2012), \url{https://en.bitcoin.it/wiki/Contract}]
introduced a notion of payment channel. In this paper, we formally discuss the robustness requirements of a scheme that is suitable for micropayments, consider the explicit value of penalty and user privacy leakage. More precisely, we propose a micropayments scheme for decentralized blockchain-based payment system based on the notion of payment channel, which enables a payee to receive funds at several unsynchronized points of sale and penalize the double-spenders, with instant confirmation.
For the entire collection see [Zbl 1398.68037].A note on the properties of associated Boolean functions of quadratic APN functions.https://www.zbmath.org/1456.941452021-04-16T16:22:00+00:00"Gorodilova, A. A."https://www.zbmath.org/authors/?q=ai:gorodilova.anastasiya-aSummary: Let \(F\) be a quadratic APN function in \(n\) variables. The associated Boolean function \(\gamma_F\) in \(2n\) variables \(( \gamma_F(a,b)=1\) if \(a\neq\mathbf{0}\) and equation \(F(x)+F(x+a)=b\) has solutions) has the form \(\gamma_F(a,b) = \Phi_F(a) \cdot b + \varphi_F(a) + 1\) for appropriate functions \(\Phi_F:\mathbb{F}_2^n\to \mathbb{F}_2^n\) and \(\varphi_F:\mathbb{F}_2^n\to \mathbb{F}_2\). We summarize the known results and prove new ones regarding properties of \(\Phi_F\) and \(\varphi_F\). For instance, we prove that degree of \(\Phi_F\) is either \(n\) or less or equal to \(n-2\). Based on computation experiments, we formulate a conjecture that degree of any component function of \(\Phi_F\) is \(n-2\). We show that this conjecture is based on two other conjectures of independent interest.Local entropy as a measure for sampling solutions in constraint satisfaction problems.https://www.zbmath.org/1456.940292021-04-16T16:22:00+00:00"Baldassi, Carlo"https://www.zbmath.org/authors/?q=ai:baldassi.carlo"Ingrosso, Alessandro"https://www.zbmath.org/authors/?q=ai:ingrosso.alessandro"Lucibello, Carlo"https://www.zbmath.org/authors/?q=ai:lucibello.carlo"Saglietti, Luca"https://www.zbmath.org/authors/?q=ai:saglietti.luca"Zecchina, Riccardo"https://www.zbmath.org/authors/?q=ai:zecchina.riccardoInvertibility of Laurent operators and shift invariant spaces with finitely many generators.https://www.zbmath.org/1456.420442021-04-16T16:22:00+00:00"Radha, R."https://www.zbmath.org/authors/?q=ai:radha.ramakrishnan"Sarvesh, K."https://www.zbmath.org/authors/?q=ai:sarvesh.k"Sivananthan, S."https://www.zbmath.org/authors/?q=ai:sivananthan.sivalingamThe authors study the sampling and reconstruction in shift invariant spaces with finitely many generators by using a block Laurent operator associated with the sample set. They provide a necessary and sufficient condition for obtaining such stable sampling set in terms of the invertibility of Laurent and block Laurent operators. They show that for a fixed \(m\in \mathbb N,\) \(\mathbb Z/m\) is a stable set of sampling for \(V(\phi^1,\dots,\phi^s)\) (the shift invariant space generated by \(\phi^1,\dots,\phi^s\) ) if and only if there exists a \( \gamma > 0\) such that \(|\mathrm{det}\Phi^{\#}(x)|\geq \gamma\) a.e on \(\mathbb T,\) where \(\Phi^{\#}\) is a symbol matrix of a block Laurent polynomial associated with the sampling set \(\phi^1, \dots, \phi^s\) \(s\geq 2.\) A similar result is proved when \(r\mathbb Z,\) where \(r=\frac{p}{q}\), \(p,q\in\mathbb N,\) and \(\gcd(p,q)=1,\) is a stable set of sampling for the single generator space \(V(\phi)\) or the multiple generator space \(V(\phi^1,\dots, \phi^s).\)
Reviewer: Ghanshyam Bhatt (Nashville)Equichordal tight fusion frames.https://www.zbmath.org/1456.420432021-04-16T16:22:00+00:00"Mohammadpour, Mozhgan"https://www.zbmath.org/authors/?q=ai:mohammadpour.mozhgan"Kamyabi-Gol, Rajab Ali"https://www.zbmath.org/authors/?q=ai:kamyabi-gol.rajab-ali"Hodtani, Ghosheh Abed"https://www.zbmath.org/authors/?q=ai:hodtani.ghosheh-abedSummary: A Grassmannian fusion frame is an optimal configuration of subspaces of a given vector space, that are useful in some applications related to representing data in signal processing. Grassmannian fusion frames are robust against noise and erasures when the signal is reconstructed. In this paper, we present an approach to construct optimal Grassmannian fusion frames based on a given Grassmannian frame. We also analyse an algorithm for sparse fusion frames which was introduced by \textit{R. Calderbank} et al. [Adv. Comput. Math. 35, No. 1, 1--31 (2011; Zbl 1264.94042)] and present necessary and sufficient conditions for the output of that algorithm to be an optimal Grassmannian fusion frame.Equivalence of 2-rotation symmetric quartic Boolean functions.https://www.zbmath.org/1456.941432021-04-16T16:22:00+00:00"Cusick, Thomas W."https://www.zbmath.org/authors/?q=ai:cusick.thomas-w"Cheon, Younhwan"https://www.zbmath.org/authors/?q=ai:cheon.younhwan"Dougan, Kelly"https://www.zbmath.org/authors/?q=ai:dougan.kellySummary: A Boolean function in \(n\) variables is 2-rotation symmetric if it is invariant under even powers of \(\rho(x_1, \dots \dots, x_n) = (x_2, \dots, x_n, x_1)\), but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of \(\rho^2\) to a single monomial. If the quartic MRS 2-function in \(2n\) variables has a monomial \(x_1 x_q x_rx_s \), then we use the notation \(2-(1, q, r, s)_{2n}\) for the function. This paper gives a detailed theory of equivalence of quartic MRS 2-functions in \(2n\) variables. Such a theory was provided for the cubic MRS 2-functions in two 2015 papers of Cusick and Johns. As in the earlier papers, the two main topics in the theory are describing the affine equivalence classes of the functions under certain groups of permutations; and giving details of the linear recursions that the Hamming weights of any sequence of functions \(2-(1,q,r,s)_{2n}\) (with \(q<r<s\), say), \(n=s\), \(s+1,\dots\) can be shown to satisfy. The discussion for both of these topics uses new ideas because the quartic theory naturally divides into two cases.Geometrical organization of solutions to random linear Boolean equations.https://www.zbmath.org/1456.941462021-04-16T16:22:00+00:00"Mora, Thierry"https://www.zbmath.org/authors/?q=ai:mora.thierry"Mézard, Marc"https://www.zbmath.org/authors/?q=ai:mezard.marcRapid compressed sensing reconstruction: a semi-tensor product approach.https://www.zbmath.org/1456.940112021-04-16T16:22:00+00:00"Wang, Jinming"https://www.zbmath.org/authors/?q=ai:wang.jinming"Xu, Zhenyu"https://www.zbmath.org/authors/?q=ai:xu.zhenyu"Wang, Zhangquan"https://www.zbmath.org/authors/?q=ai:wang.zhangquan"Xu, Sen"https://www.zbmath.org/authors/?q=ai:xu.sen"Jiang, Jun"https://www.zbmath.org/authors/?q=ai:jiang.junSummary: In large-scale applications of compressed sensing (CS), the time cost to reconstruct the original signal is too high. To accelerate the reconstruction and reduce the space cost of the measurement matrix, a novel parallel reconstruction approach based on a semi-tensor product (STP) is proposed. A low-dimensional random matrix where the dimensions are 1/4 (or 1/16, 1/64, 1/256, 1/1024 or even 1/4096) that of conventional CS is generated to sample the original data, and then a parallel reconstruction method is proposed to obtain the solution with the iteratively re-weighted least-squares (IRLS) algorithm. The peak signal-to-noise ratio (PSNR), structural similarity index (SSIM), and time cost of reconstruction were evaluated and compared with matrices of different dimensions, and comparisons were also conducted with other state-of-the-art methods. Numerical results show that the speed can be effectively improved \((10 \times\), or \(100 \times\), even \(1000 \times)\) and the storage space of the matrix can also be remarkably reduced; that is, the matrix can be 1/4096 of conventional CS. Furthermore, the numerical results show that our formulation outperforms conventional CS in speed of reconstruction and in its comparable quality, which is important for real-time and physical implementation of applications.Statistical criticality arises in most informative representations.https://www.zbmath.org/1456.620112021-04-16T16:22:00+00:00"Cubero, Ryan John"https://www.zbmath.org/authors/?q=ai:cubero.ryan-john"Jo, Junghyo"https://www.zbmath.org/authors/?q=ai:jo.junghyo"Marsili, Matteo"https://www.zbmath.org/authors/?q=ai:marsili.matteo"Roudi, Yasser"https://www.zbmath.org/authors/?q=ai:roudi.yasser"Song, Juyong"https://www.zbmath.org/authors/?q=ai:song.juyongMeasurement of network complexity and capability in command and control system.https://www.zbmath.org/1456.900362021-04-16T16:22:00+00:00"Song, Xiao"https://www.zbmath.org/authors/?q=ai:song.xiao"Zhang, Shaoyun"https://www.zbmath.org/authors/?q=ai:zhang.shaoyun"Shi, Xuecheng"https://www.zbmath.org/authors/?q=ai:shi.xuechengSummary: A concept of complexity of the Command and Control (C2) information system is introduced and an innovative approach of measuring network complexity is proposed compared with traditional network complexity computation methods. Complexity measurements, including connectivity, collaboration and redundancy, are proposed and computed. Then the complexity-based capability is discussed and studied. Finally, two case studies of an anti-aircraft defence C2 network and partial tank division network are carried out to illustrate the computation processes of the proposed network complexity and capability.Efficient digital signatures from RSA without random oracles.https://www.zbmath.org/1456.941122021-04-16T16:22:00+00:00"Seo, Jae Hong"https://www.zbmath.org/authors/?q=ai:seo.jae-hongSummary: Improving efficiency of digital signature scheme is important since digital signature scheme is a core building block for many privacy protocols. There are some proposals regarding efficient digital signatures whose security arguments are guaranteed by the standard assumption such as RSA assumption. Although several RSA-based digital signature schemes achieve a short signature size, many of them essentially rely on random oracle heuristics. In 2009, \textit{S. Hohenberger} and \textit{B. Waters} proposed an excellent approach to the design of a short RSA-based signature scheme \textit{without} random oracles [Lect. Notes Comput. Sci. 5677, 654--670 (2009; Zbl 1252.94074)]. However, their scheme requires signers to execute an expensive prime-number generation several times, and leaves the reduction in signing and verifying costs as important open problems. In this paper, we propose an efficient digital signature scheme from the above category. That is, we propose a short RSA signature scheme in the standard model, which requires less prime-number generations than those in the previous best scheme of \textit{F. Böhl} et al. [J. Cryptology 28, No. 1, 176--208 (2015; Zbl 1308.94060)]. More precisely, the BHJKS scheme requires signers to generate \(O(\log\lambda)\) prime-numbers for each signature; however, our scheme requires almost a constant time (e.g., log log \(\lambda)\) of prime-number generation in the signing algorithm, where \(\lambda\) is the security parameter.Amorphous packings of hard spheres for large space dimension.https://www.zbmath.org/1456.825302021-04-16T16:22:00+00:00"Parisi, Giorgio"https://www.zbmath.org/authors/?q=ai:parisi.giorgio"Zamponi, Francesco"https://www.zbmath.org/authors/?q=ai:zamponi.francescoInformation flow in secret sharing protocols.https://www.zbmath.org/1456.811582021-04-16T16:22:00+00:00"Kashefi, Elham"https://www.zbmath.org/authors/?q=ai:kashefi.elham"Markham, Damian"https://www.zbmath.org/authors/?q=ai:markham.damian"Mhalla, Mehdi"https://www.zbmath.org/authors/?q=ai:mhalla.mehdi"Perdrix, Simon"https://www.zbmath.org/authors/?q=ai:perdrix.simonSummary: The entangled graph states have emerged as an elegant and powerful quantum resource, indeed almost all multiparty protocols can be written in terms of graph states including measurement based quantum computation (MBQC), error correction and secret sharing amongst others. In addition they are at the forefront in terms of implementations. As such they represent an excellent opportunity to move towards integrated protocols involving many of these elements. In this paper we look at expressing and extending graph state secret sharing and MBQC in a common framework and graphical language related to flow. We do so with two main contributions.
First we express in entirely graphical terms which set of players can access which information in graph state secret sharing protocols. These succinct graphical descriptions of access allow us to take known results from graph theory to make statements on the generalisation of the previous schemes to present new secret sharing protocols.
Second, we give a set of necessary conditions as to when a graph with flow, i.e. capable of performing a class of unitary operations, can be extended to include vertices which can be ignored, pointless measurements, and hence considered as unauthorised players in terms of secret sharing, or error qubits in terms of fault tolerance. This offers a way to extend existing MBQC patterns to secret sharing protocols. Our characterisation of pointless measurements is believed also to be a useful tool for further integrated measurement based schemes, for example in constructing fault tolerant MBQC schemes.
For the entire collection see [Zbl 1392.68013].Fast rebalanced RSA signature scheme with typical prime generation.https://www.zbmath.org/1456.941262021-04-16T16:22:00+00:00"Gyu-Chol, Kim"https://www.zbmath.org/authors/?q=ai:gyu-chol.kim"Su-Chol, Li"https://www.zbmath.org/authors/?q=ai:su-chol.li"Hak-Chol, Hwang"https://www.zbmath.org/authors/?q=ai:hak-chol.hwangSummary: In RSA, private exponent is usually obtained from the preselected public exponent by extended Euclid algorithm and is roughly the same bit size as a modulus number. If the private exponent is preselected as in rebalanced RSA, then the public exponent obtained by extended Euclid algorithm is roughly the same bit size as a modulus number. Hence, it is not easy to reduce both public exponent and private exponent (or CRT private exponents) in RSA key generation.
In order to reduce both public exponent and CRT private exponents, the methods to search the modulus number after selecting proper public exponent and private exponent have been proposed in recent researches. However, these methods all have complicated key generation because prime generation module developed for RSA cannot be used.
In this paper, we present a method to reduce both public exponent and CRT private exponents after selecting the prime numbers and propose a fast rebalanced RSA signature scheme with small public exponent.
Our scheme is advantageous than other schemes in the aspect of using typical prime generation. That is, key generation is not complicated in our scheme.Scalings and fractals in information geometry: Ornstein-Uhlenbeck processes.https://www.zbmath.org/1456.601282021-04-16T16:22:00+00:00"Oxley, William"https://www.zbmath.org/authors/?q=ai:oxley.william"Kim, Eun-Jin"https://www.zbmath.org/authors/?q=ai:kim.eunjinQuantum algorithms for testing Boolean functions.https://www.zbmath.org/1456.680552021-04-16T16:22:00+00:00"Floess, Dominik F."https://www.zbmath.org/authors/?q=ai:floess.dominik-f"Andersson, Erika"https://www.zbmath.org/authors/?q=ai:andersson.erika"Hillery, Mark"https://www.zbmath.org/authors/?q=ai:hillery.markSummary: We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are \(2^n\) possible linear Boolean functions of \(n\) variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
For the entire collection see [Zbl 1445.68010].Security theorems via model theory.https://www.zbmath.org/1456.680222021-04-16T16:22:00+00:00"Guttman, Joshua"https://www.zbmath.org/authors/?q=ai:guttman.joshua-dSummary: A model-theoretic approach can establish security theorems, which are formulas expressing authentication and non-disclosure properties of protocols. Security theorems have a special form, namely quantified implications \(\forall\vec x . (\phi\supset\exists\vec y . \psi\)).
Models (interpretations) for these formulas are skeletons, partially ordered structures consisting of a number of local protocol behaviors. Realized skeletons contain enough local sessions to explain all the behavior, when combined with some possible adversary behaviors.
We show two results. (1) If \(\phi\) is the antecedent of a security goal, then there is a skeleton \(\mathbb{A}_\phi\) such that, for every skeleton \(\mathbb{B}\), \(\phi\) is satisfied in \(\mathbb{B}\) iff there is a homomorphism from \(\mathbb{A}_\phi\) to \(\mathbb{B}\). (2) A protocol enforces \(\forall\vec x . (\phi\supset\exists\vec y . \psi\)) iff every realized homomorphic image of \(\mathbb{A}_\phi\) satisfies \(\psi\).
Since the program \textsc{cpsa} finds the minimal realized skeletons, or ``shapes'', that are homomorphic images of \(\mathbb{A}_\phi\), if \(\psi\) holds in each of these shapes, then the goal holds.
For the entire collection see [Zbl 1415.68026].Optimal locally repairable and secure codes for distributed storage systems.https://www.zbmath.org/1456.941372021-04-16T16:22:00+00:00"Rawat, Ankit Singh"https://www.zbmath.org/authors/?q=ai:rawat.ankit-singh"Koyluoglu, Onur Ozan"https://www.zbmath.org/authors/?q=ai:koyluoglu.onur-ozan"Silberstein, Natalia"https://www.zbmath.org/authors/?q=ai:silberstein.natalia"Vishwanath, Sriram"https://www.zbmath.org/authors/?q=ai:vishwanath.sriramEditorial remark: No review copy delivered.LCD codes and self-orthogonal codes in generalized dihedral group algebras.https://www.zbmath.org/1456.140332021-04-16T16:22:00+00:00"Gao, Yanyan"https://www.zbmath.org/authors/?q=ai:gao.yanyan"Yue, Qin"https://www.zbmath.org/authors/?q=ai:yue.qin"Wu, Yansheng"https://www.zbmath.org/authors/?q=ai:wu.yanshengA group code is a right ideal in a group ring \(R[G]\) where \(R\) is a commutative ring and \(G\) a finite group. In this paper, the authors consider a finite field \(\mathbb{F}_q\) and a generalized dihedral group \(D_{2n,r}\), \(\gcd(2n,q)=1\). As a first main result, they explicitly describe the primitive idempotents of the group algebra \(\mathbb{F}_q[D_{2n,r}]\). Given a code \(C\), it is named LCD whenever \(C \cap C^\perp = \{0\}\) and it is self-orthogonal iff \(C \subseteq C^\perp\), where \(C^\perp\) means dual of \(C\). LCD codes have cryptographic applications and self-orthogonal codes provide quantum codes. The second main result of the paper describes and counts LCD and self-orthogonal group codes in \(\mathbb{F}_q[D_{2n,r}]\).
Reviewer: Carlos Galindo (Castellón)Flexible attribute-based proxy re-encryption for efficient data sharing.https://www.zbmath.org/1456.680302021-04-16T16:22:00+00:00"Deng, Hua"https://www.zbmath.org/authors/?q=ai:deng.hua"Qin, Zheng"https://www.zbmath.org/authors/?q=ai:qin.zheng"Wu, Qianhong"https://www.zbmath.org/authors/?q=ai:wu.qianhong"Guan, Zhenyu"https://www.zbmath.org/authors/?q=ai:guan.zhenyu"Zhou, Yunya"https://www.zbmath.org/authors/?q=ai:zhou.yunyaSummary: An increasing number of people are sharing their data through third-party platforms. Attribute-based encryption (ABE) is a promising primitive that allows enforcing fine-grained access control on the data to be shared. An issue in ABE is that \textit{a priori} access policies should be determined during the system setup or encryption phase, but these policies will become obsolete over time. Another issue is that the decryption of ABE generally requires complicated and expensive computations, which may be unaffordable for resource-limited users (e.g., mobile-device users). To address these issues, we propose a new paradigm called hybrid attribute-based proxy re-encryption (HAPRE). In HAPRE, a semitrusted proxy can be authorized to convert ciphertexts of an ABE scheme into ciphertexts of an identity-based encryption (IBE) scheme without letting the proxy know the underlying messages. With these features, HAPRE enables resource-limited users to efficiently access the data previously encrypted by ABE. We construct two HAPRE schemes by utilizing a compact IBE scheme and a key rerandomization technique, and then we prove that the schemes are semantically secure and collusion resistant. Theoretical and experimental analyses demonstrate the efficiency of the HAPRE schemes.Sponges resist leakage: the case of authenticated encryption.https://www.zbmath.org/1456.940712021-04-16T16:22:00+00:00"Degabriele, Jean Paul"https://www.zbmath.org/authors/?q=ai:degabriele.jean-paul"Janson, Christian"https://www.zbmath.org/authors/?q=ai:janson.christian"Struck, Patrick"https://www.zbmath.org/authors/?q=ai:struck.patrickSummary: In this work we advance the study of leakage-resilient authenticated encryption with associated data (AEAD) and lay the theoretical groundwork for building such schemes from sponges. Building on the work of \textit{G. Barwell} et al. [Lect. Notes Comput. Sci. 10624, 693--723 (2017; Zbl 1420.94038)], we reduce the problem of constructing leakage-resilient AEAD schemes to that of building fixed-input-length function families that retain pseudorandomness and unpredictability in the presence of leakage. Notably, neither property is implied by the other in the leakage-resilient setting. We then show that such a function family can be combined with standard primitives, namely a pseudorandom generator and a collision-resistant hash, to yield a nonce-based AEAD scheme. In addition, our construction is quite efficient in that it requires only two calls to this leakage-resilient function per encryption or decryption call. This construction can be instantiated entirely from the T-sponge to yield a concrete AEAD scheme which we call SLAE. We prove this sponge-based instantiation secure in the non-adaptive leakage setting. SLAE bears many similarities and is indeed inspired by ISAP, which was proposed by \textit{C. Dobraunig} et al. [``ISAP -- towards side-channel secure authenticated encryption'', IACR Trans. Symm. Cryptol. 2017, No. 1, 80--105 (2017; \url{doi:10.13154/tosc.v2017.i1.80-105})]. However, while retaining most of the practical advantages of ISAP, SLAE additionally benefits from a formal security treatment.
For the entire collection see [Zbl 1428.94009].Finding the maximal adversary structure from any given access structure.https://www.zbmath.org/1456.941162021-04-16T16:22:00+00:00"Tang, Chunming"https://www.zbmath.org/authors/?q=ai:tang.chunming"Xu, Qiuxia"https://www.zbmath.org/authors/?q=ai:xu.qiuxia"Hu, Gengran"https://www.zbmath.org/authors/?q=ai:hu.gengranSummary: Secure multi-party computation is an important research area in cryptography, and the secret sharing scheme (SSS) is one of the main tools for constructing multi-party computation protocols. The access structure and the adversary structure are two important subsets of participants in an SSS. In general, the collection of all qualified subsets that can reconstruct the secret \(s\), is known as an access structure, while no information regarding this secret is available to any unqualified subsets, and the collection of unqualified subsets is described as an adversary structure. The maximal adversary, which will become a qualified subset if any one participant not in this unqualified subset is added. At present, there is no effective algorithm to determine the maximal adversary structure for any given access structure. In this paper, we propose two algorithms to determine the maximal adversary structure from any given access structure, in which a binary tree is introduced to construct such algorithms. Moreover, a special type of access structure is established, from which the maximal adversary structure can be directly characterized, and the maximal adversary structure in this case is shown to be the largest when the number of participants of each qualified polynomial in the access structure is three.Despeckling method of ultrasound images using closed-form shrinkage function based on Cauchy distribution in wavelet domain.https://www.zbmath.org/1456.940072021-04-16T16:22:00+00:00"Kim, Kyong-Il"https://www.zbmath.org/authors/?q=ai:kim.kyong-il"Bahng, Soon-Ic"https://www.zbmath.org/authors/?q=ai:bahng.soon-ic"Choe, Ryong-Nam"https://www.zbmath.org/authors/?q=ai:choe.ryong-namDenoising speckle noise is significant to improve visual quality of ultrasound images, and an effective technique of image denoising is in the wavelet domain, where noise-free wavelet coefficients and noise are statistically modeled, and the noise-free wavelet coefficients are estimated using an MAP estimator. For speckle noisy ultrasound image, M. I. H. Bhuiyan and S. Sahu (see [\textit{M. I. H. Bhuiyan} et al., ``Spatially adaptive wavelet-based method using the Cauchy prior for denoising the SAR images'', IEEE Trans.Circuits Syst. Video Technol. 17, No. 4, 500--507 (2007); \textit{S. Sahu}, ``De-noising of ultrasound image using Bayesian approached heavy-tailed Cauchy distribution'', Multimed. Tools Appl. 78, 4089--4106 (2019)]) have used Cauchy PDF (probability density function) and Gaussian PDF to model the true wavelet coefficients and noisy coefficients for the logarithmically transformed ultrasound image, respectively, but they do not find the analytical solution of a Bayesian MAP estimator. The main contribution of this paper is that the authors obtain an analytical solution of the MAP estimator derived by Bhuiyan and Sahu by solving a cubic equation for MAP estimation of noise free wavelet coefficients. They get a closed-form shrinkage function (CauchyShrinkGMAP) and estimate parameters of MAP estimators, which greatly facilitates practical application. The despeckling performance of wavelet image denoising method using the CauchyShrinkGMAP is evaluated and its effectiveness proved by comparing to other methods such as median and Wiener filters, hard and soft thresholding and GaussShrinkGMAP and MCMAP3N shrinkage function. It would be better if the analytic denoising method would be also compared with the non-analytic denoising method proposed by Bhuiyan and Sahu.
Reviewer: Yankui Sun (Beijing)A generalized measure of dispersion.https://www.zbmath.org/1456.620122021-04-16T16:22:00+00:00"Guerrero, Victor M."https://www.zbmath.org/authors/?q=ai:guerrero.victor-m"Solis-Lemus, Claudia"https://www.zbmath.org/authors/?q=ai:solis-lemus.claudiaSummary: A new measure of dispersion is presented here that generalizes entropy for positive data. It is intrinsically linked to a measure of central tendency and is determined by the data through a power transformation that best symmetrizes the observations.Quisquis: a new design for anonymous cryptocurrencies.https://www.zbmath.org/1456.940762021-04-16T16:22:00+00:00"Fauzi, Prastudy"https://www.zbmath.org/authors/?q=ai:fauzi.prastudy-mungkas"Meiklejohn, Sarah"https://www.zbmath.org/authors/?q=ai:meiklejohn.sarah"Mercer, Rebekah"https://www.zbmath.org/authors/?q=ai:mercer.rebekah"Orlandi, Claudio"https://www.zbmath.org/authors/?q=ai:orlandi.claudioSummary: Despite their usage of pseudonyms rather than persistent identifiers, most existing cryptocurrencies do not provide users with any meaningful levels of privacy. This has prompted the creation of privacy-enhanced cryptocurrencies such as Monero and Zcash, which are specifically designed to counteract the tracking analysis possible in currencies like Bitcoin. These cryptocurrencies, however, also suffer from some drawbacks: in both Monero and Zcash, the set of potential unspent coins is always growing, which means users cannot store a concise representation of the blockchain. Additionally, Zcash requires a common reference string and the fact that addresses are reused multiple times in Monero has led to attacks to its anonymity.
In this paper we propose a new design for anonymous cryptocurrencies, Quisquis, that achieves provably secure notions of anonymity. Quisquis stores a relatively small amount of data, does not require trusted setup, and in Quisquis each address appears on the blockchain at most twice: once when it is generated as output of a transaction, and once when it is spent as input to a transaction. Our result is achieved by combining a DDH-based tool (that we call updatable keys) with efficient zero-knowledge arguments.
For the entire collection see [Zbl 1428.94008].Leakage-resilient group signature: definitions and constructions.https://www.zbmath.org/1456.941272021-04-16T16:22:00+00:00"Huang, Jianye"https://www.zbmath.org/authors/?q=ai:huang.jianye"Huang, Qiong"https://www.zbmath.org/authors/?q=ai:huang.qiong"Susilo, Willy"https://www.zbmath.org/authors/?q=ai:susilo.willySummary: Group signature scheme provides a way to sign messages without revealing identities of the authentic signers. To achieve such functionality and to avoid the abuse of its power, \textit{anonymity} and \textit{traceability} are two essential properties for group signature scheme. In traditional group signature schemes, however, these two security properties are based on the perfectly-secure storage of secret information. Unfortunately, defective implementation of a cryptosystem always exists, and therefore unexpected information leakage is inevitable. In reality, \textit{side-channel attacks} allow an adversary breaks the security of the whole system by eavesdropping a portion of secret information. To tackle this issue, in our work we present the security models of leakage-resilient group signature in bounded leakage setting and furthermore, propose three new black-box constructions of leakage-resilient group signature based on the proposed security models.Shorter pairing-based arguments under standard assumptions.https://www.zbmath.org/1456.940792021-04-16T16:22:00+00:00"González, Alonso"https://www.zbmath.org/authors/?q=ai:gonzalez.alonso"Ràfols, Carla"https://www.zbmath.org/authors/?q=ai:rafols.carlaSummary: This paper constructs efficient non-interactive arguments for correct evaluation of arithmetic and Boolean circuits with proof size \(O(d)\) group elements, where \(d\) is the multiplicative depth of the circuit, under falsifiable assumptions. This is achieved by combining techniques from SNARKs and QA-NIZK arguments of membership in linear spaces. The first construction is very efficient (the proof size is \(\approx 4d\) group elements and the verification cost is \(\approx 4d\) pairings and \(O(n+n^\prime+d)\) exponentiations, where \(n\) is the size of the input and \(n^\prime\) of the output) but one type of attack can only be ruled out assuming the knowledge soundness of QA-NIZK arguments of membership in linear spaces. We give an alternative construction which replaces this assumption with a decisional assumption in bilinear groups at the cost of approximately doubling the proof size. The construction for boolean circuits can be made zero-knowledge with Groth-Sahai proofs, resulting in a NIZK argument for circuit satisfiability based on falsifiable assumptions in bilinear groups of proof size \(O(n+d)\).
Our main technical tool is what we call an ``argument of knowledge transfer''. Given a commitment \(C_1\) and an opening \(x\), such an argument allows to prove that some other commitment \(C_2\) opens to \(f(x)\), for some function \(f\), even if \(C_2\) is not extractable. We construct very short, constant-size, pairing-based arguments of knowledge transfer with constant-time verification for any linear function and also for Hadamard products. These allow to transfer the knowledge of the input to lower levels of the circuit.
For the entire collection see [Zbl 1428.94010].Efficient noninteractive certification of RSA moduli and beyond.https://www.zbmath.org/1456.940782021-04-16T16:22:00+00:00"Goldberg, Sharon"https://www.zbmath.org/authors/?q=ai:goldberg.sharon"Reyzin, Leonid"https://www.zbmath.org/authors/?q=ai:reyzin.leonid"Sagga, Omar"https://www.zbmath.org/authors/?q=ai:sagga.omar"Baldimtsi, Foteini"https://www.zbmath.org/authors/?q=ai:baldimtsi.foteiniSummary: In many applications, it is important to verify that an RSA public key \((N, e)\) specifies a permutation over the entire space \(\mathbb{Z}_N\), in order to prevent attacks due to adversarially-generated public keys. We design and implement a simple and efficient noninteractive zero-knowledge protocol (in the random oracle model) for this task. Applications concerned about adversarial key generation can just append our proof to the RSA public key without any other modifications to existing code or cryptographic libraries. Users need only perform a one-time verification of the proof to ensure that raising to the power \(e\) is a permutation of the integers modulo \(N\). For typical parameter settings, the proof consists of nine integers modulo \(N\); generating the proof and verifying it both require about nine modular exponentiations.
We extend our results beyond RSA keys and also provide efficient noninteractive zero-knowledge proofs for other properties of \(N\), which can be used to certify that \(N\) is suitable for the Paillier cryptosystem, is a product of two primes, or is a Blum integer. As compared to the recent work of \textit{B. Auerbach} and \textit{B. Poettering} [Lect. Notes Comput. Sci. 10770, 403--430 (2018; Zbl 1420.94035)], who provide two-message protocols for similar languages, our protocols are more efficient and do not require interaction, which enables a broader class of applications.
For the entire collection see [Zbl 1428.94010].Shorter QA-NIZK and SPS with tighter security.https://www.zbmath.org/1456.940402021-04-16T16:22:00+00:00"Abe, Masayuki"https://www.zbmath.org/authors/?q=ai:abe.masayuki"Jutla, Charanjit S."https://www.zbmath.org/authors/?q=ai:jutla.charanjit-s"Ohkubo, Miyako"https://www.zbmath.org/authors/?q=ai:ohkubo.miyako"Pan, Jiaxin"https://www.zbmath.org/authors/?q=ai:pan.jiaxin"Roy, Arnab"https://www.zbmath.org/authors/?q=ai:roy.arnab"Wang, Yuyu"https://www.zbmath.org/authors/?q=ai:wang.yuyuSummary: Quasi-adaptive non-interactive zero-knowledge proof (QA-NIZK) systems and structure-preserving signature (SPS) schemes are two powerful tools for constructing practical pairing-based cryptographic schemes. Their efficiency directly affects the efficiency of the derived advanced protocols.
We construct more efficient QA-NIZK and SPS schemes with tight security reductions. Our QA-NIZK scheme is the first one that achieves both tight simulation soundness and constant proof size (in terms of number of group elements) at the same time, while the recent scheme from \textit{M. Abe} et al. [Lect. Notes Comput. Sci. 11272, 627--656 (2018; Zbl 1446.94093)] achieved tight security with proof size linearly depending on the size of the language and the witness. Assuming the hardness of the Symmetric External Diffie-Hellman (SXDH) problem, our scheme contains only 14 elements in the proof and remains independent of the size of the language and the witness. Moreover, our scheme has tighter simulation soundness than the previous schemes.
Technically, we refine and extend a partitioning technique from a recent SPS scheme [\textit{R. Gay} et al., ibid. 10821, 230--258 (2018; Zbl 1428.94104)]. Furthermore, we improve the efficiency of the tightly secure SPS schemes by using a relaxation of NIZK proof system for OR languages, called designated-prover NIZK system. Under the SXDH assumption, our SPS scheme contains 11 group elements in the signature, which is shortest among the tight schemes and is the same as an early non-tight scheme [\textit{M. Abe} et al., ibid. 7658, 4--24 (2012; Zbl 1292.94016)]. Compared to the shortest known non-tight scheme [\textit{C. S. Jutla} and \textit{A. Roy}, ibid. 10175, 183--209 (2017; Zbl 1400.94155)], our scheme achieves tight security at the cost of 5 additional elements.
All the schemes in this paper are proven secure based on the Matrix Diffie-Hellman assumptions [\textit{A. Escala} et al., ibid. 8043, 129--147 (2013; Zbl 1316.94070)]. These are a class of assumptions which include the well-known SXDH and DLIN assumptions and provide clean algebraic insights to our constructions. To the best of our knowledge, our schemes achieve the best efficiency among schemes with the same functionality and security properties. This naturally leads to improvement of the efficiency of cryptosystems based on simulation-sound QA-NIZK and SPS.
For the entire collection see [Zbl 1428.94010].The local forking lemma and its application to deterministic encryption.https://www.zbmath.org/1456.940472021-04-16T16:22:00+00:00"Bellare, Mihir"https://www.zbmath.org/authors/?q=ai:bellare.mihir"Dai, Wei"https://www.zbmath.org/authors/?q=ai:dai.wei.7"Li, Lucy"https://www.zbmath.org/authors/?q=ai:li.lucySummary: We bypass impossibility results for the deterministic encryption of public-key-dependent messages, showing that, in this setting, the classical encrypt with hash scheme provides message-recovery security, across a broad range of message distributions. The proof relies on a new variant of the forking lemma in which the random oracle is reprogrammed on just a single fork point rather than on all points past the fork.
For the entire collection see [Zbl 1428.94010].Rate-1 trapdoor functions from the Diffie-Hellman problem.https://www.zbmath.org/1456.940732021-04-16T16:22:00+00:00"Döttling, Nico"https://www.zbmath.org/authors/?q=ai:dottling.nico"Garg, Sanjam"https://www.zbmath.org/authors/?q=ai:garg.sanjam"Hajiabadi, Mohammad"https://www.zbmath.org/authors/?q=ai:hajiabadi.mohammad"Liu, Kevin"https://www.zbmath.org/authors/?q=ai:liu.kevin-fong-rey"Malavolta, Giulio"https://www.zbmath.org/authors/?q=ai:malavolta.giulioSummary: Trapdoor functions (TDFs) are one of the fundamental building blocks in cryptography. Studying the underlying assumptions and the efficiency of the resulting instantiations is therefore of both theoretical and practical interest. In this work we improve the input-to-image rate of TDFs based on the Diffie-Hellman problem. Specifically, we present:
(a) A rate-1 TDF from the Computational Diffie-Hellman (CDH) assumption, improving the result of \textit{S. Garg} et al. [Lect. Notes Comput. Sci. 11478, 33--63 (2019; Zbl 07162723)], which achieved linear-size outputs but with large constants. Our techniques combine non-binary alphabets and high-rate error-correcting codes over large fields.
(b) A rate-1 deterministic public-key encryption satisfying block-source security from the decisional Diffie-Hellman (DDH) assumption. While this question was recently settled by \textit{N. Döttling} et al. [ibid. 11694, 3--32 (2019; Zbl 1436.94054)], our scheme is conceptually simpler and concretely more efficient. We demonstrate this fact by implementing our construction.
For the entire collection see [Zbl 1428.94010].From single-input to multi-client inner-product functional encryption.https://www.zbmath.org/1456.940392021-04-16T16:22:00+00:00"Abdalla, Michel"https://www.zbmath.org/authors/?q=ai:abdalla.michel"Benhamouda, Fabrice"https://www.zbmath.org/authors/?q=ai:benhamouda.fabrice"Gay, Romain"https://www.zbmath.org/authors/?q=ai:gay.romainSummary: We present a new generic construction of multi-client functional encryption (MCFE) for inner products from single-input functional inner-product encryption and standard pseudorandom functions. In spite of its simplicity, the new construction supports labels, achieves security in the standard model under adaptive corruptions, and can be instantiated from the plain DDH, LWE, and Paillier assumptions. Prior to our work, the only known constructions required discrete-log-based assumptions and the random-oracle model. Since our new scheme is not compatible with the compiler from \textit{M. Abdalla} et al. [Lect. Notes Comput. Sci. 11443, 128--157 (2019; Zbl 1453.94056)] that decentralizes the generation of the functional decryption keys, we also show how to modify the latter transformation to obtain a decentralized version of our scheme with similar features.
For the entire collection see [Zbl 1428.94010].Multi-client functional encryption for linear functions in the standard model from LWE.https://www.zbmath.org/1456.940962021-04-16T16:22:00+00:00"Libert, Benoît"https://www.zbmath.org/authors/?q=ai:libert.benoit"Ţiţiu, Radu"https://www.zbmath.org/authors/?q=ai:titiu.raduSummary: Multi-client functional encryption (MCFE) allows \(\ell\) clients to encrypt ciphertexts \((C_{t,1},C_{t,2},\ldots,C_{t,\ell})\) under some label. Each client can encrypt his own data \(X_i\) for a label \(t\) using a private encryption key \(\mathsf{ek}_i\) issued by a trusted authority in such a way that, as long as all \(C_{t,i}\) share the same label \(t\), an evaluator endowed with a functional key \(\mathsf{dk}_f\) can evaluate \(f(X_1,X_2,\ldots,X_\ell)\) without learning anything else on the underlying plaintexts \(X_i\). Functional decryption keys can be derived by the central authority using the master secret key. Under the Decision Diffie-Hellman assumption, \textit{J. Chotard} et al. [Lect. Notes Comput. Sci. 11273, 703--732 (2018; Zbl 1446.94119)] recently described an adaptively secure MCFE scheme for the evaluation of linear functions over the integers. They also gave a decentralized variant (DMCFE) of their scheme which does not rely on a centralized authority, but rather allows encryptors to issue functional secret keys in a distributed manner. While efficient, their constructions both rely on random oracles in their security analysis. In this paper, we build a standard-model MCFE scheme for the same functionality and prove it fully secure under adaptive corruptions. Our proof relies on the Learning with Errors (LWE) assumption and does not require the random oracle model. We also provide a decentralized variant of our scheme, which we prove secure in the static corruption setting (but for adaptively chosen messages) under the LWE assumption.
For the entire collection see [Zbl 1428.94010].Public-key function-private hidden vector encryption (and more).https://www.zbmath.org/1456.940452021-04-16T16:22:00+00:00"Bartusek, James"https://www.zbmath.org/authors/?q=ai:bartusek.james"Carmer, Brent"https://www.zbmath.org/authors/?q=ai:carmer.brent"Jain, Abhishek"https://www.zbmath.org/authors/?q=ai:jain.abhishek"Jin, Zhengzhong"https://www.zbmath.org/authors/?q=ai:jin.zhengzhong"Lepoint, Tancrède"https://www.zbmath.org/authors/?q=ai:lepoint.tancrede"Ma, Fermi"https://www.zbmath.org/authors/?q=ai:ma.fermi"Malkin, Tal"https://www.zbmath.org/authors/?q=ai:malkin.tal-g"Malozemoff, Alex J."https://www.zbmath.org/authors/?q=ai:malozemoff.alex-j"Raykova, Mariana"https://www.zbmath.org/authors/?q=ai:raykova.marianaSummary: We construct public-key function-private predicate encryption for the ``small superset functionality'', recently introduced by \textit{W. Beullens} and \textit{H. Wee} [Lect. Notes Comput. Sci. 11443, 254--283 (2019; Zbl 07159408)]. This functionality captures several important classes of predicates:
i) Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.
ii) Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by \textit{D. Boneh} et al. [ibid. 8269, 255--275 (2013; Zbl 1327.94036)].
iii) \(d\)-CNFs and read-once conjunctions of \(d\)-disjunctions for constant-size \(d\).
Our construction extends the group-based obfuscation schemes of \textit{A. Bishop} et al. [ibid. 10993, 731--752 (2018; Zbl 1457.94100)], Beullens and Wee [loc. cit.], and \textit{J. Bartusek} et al. [ibid. 11478, 636--666 (2019; Zbl 07162743)] to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key \(\mathsf{sk}_f\) reveals nothing about \(f\) as long as \(f\) is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh et al. [loc. cit.]. Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.
For the entire collection see [Zbl 1428.94010].Differential fault attack on hardware stream ciphers -- a technical survey.https://www.zbmath.org/1456.941152021-04-16T16:22:00+00:00"Siddhanti, Akhilesh Anilkumar"https://www.zbmath.org/authors/?q=ai:siddhanti.akhilesh-anilkumar"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoySummary: Stream ciphers are often employed to provide fast and secure operations under resource-constrained environments. However, when it comes towards implementing the same cipher in hardware, the main question is whether the cipher continues to hold the same security level. Allowing faults to be injected into a cipher can seriously compromise its security. In this work, we discuss the Differential Fault Attack (DFA) against several stream ciphers. The list includes hardware eSTREAM candidates namely Grain, MICKEY, Trivium; lightweight stream ciphers like Sprout, Plantlet, Lizard; and a CAESAR finalist ACORN. We conclude that by injecting few faults, one can cryptanalyze all the ciphers referred above. We revisit these attacks with considerable details in this technical survey. Thus the designers should seriously consider the impact of such fault attacks on their hardware stream ciphers. We conclude with a proposal for a software where one can input the design of a stream cipher and the tool will evaluate its resistance against DFA.
For the entire collection see [Zbl 1420.00048].How to securely outsource the extended Euclidean algorithm for large-scale polynomials over finite fields.https://www.zbmath.org/1456.680162021-04-16T16:22:00+00:00"Zhou, Qiang"https://www.zbmath.org/authors/?q=ai:zhou.qiang"Tian, Chengliang"https://www.zbmath.org/authors/?q=ai:tian.chengliang"Zhang, Hanlin"https://www.zbmath.org/authors/?q=ai:zhang.hanlin"Yu, Jia"https://www.zbmath.org/authors/?q=ai:yu.jia"Li, Fengjun"https://www.zbmath.org/authors/?q=ai:li.fengjunSummary: Cloud computing gives resource-constrained clients great conveniences to outsource exorbitant computations to a public cloud. The extended Euclidean algorithm with large-scale polynomials over finite fields is fundamental and widespread in computer science and cryptography, yet it is computationally overloaded for quantities of lightweight devices emerged with the dawn of internet of things (IoT). In this respect, we design an efficient outsourcing algorithm that enables a lightweight client to achieve this heavy computation with the assistance of a remote cloud server. By comprehensively employing the variable substitution, random polynomial-based blind technique and unimodular matrix transformation, our algorithm achieves the goals of cheating resistance, privacy preservation, and high efficiency. Concretely, our algorithm is based on single untrusted program model which avoids the too strong security assumption between multiple servers, and it enables the client to detect the cloud's misbehaviors with (optimal) probability 1. Also, Thorough theoretical analysis indicates that the algorithm provides robust input/output privacy. Moreover, the algorithm only needs one round interaction between the client and the cloud. Strict theoretical analysis and extensive experimental evaluations demonstrate our algorithm's practical efficiency and effectiveness. Finally, an important application of our algorithm on securely outsourcing the expensive key generation step of NTRU cryptosystem is given.RC4: non-randomness in the index \(j\) and some results on its cycles.https://www.zbmath.org/1456.940602021-04-16T16:22:00+00:00"Chakraborty, Chandratop"https://www.zbmath.org/authors/?q=ai:chakraborty.chandratop"Chakraborty, Pranab"https://www.zbmath.org/authors/?q=ai:chakraborty.pranab"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoySummary: In this paper we provide several theoretical evidences that the pseudo-random index \(j\) of RC4 is indeed not pseudo-random. First we show that in long term \(\Pr(j=i+1)=\frac{1}{N}-\frac{1}{N^2} \), instead of the random association \(\frac{1}{N}\) and this happens for the non-existence of the condition \(S[i]=1\) and \(j=i+1\) that is mandatory for the non-existence of the Finney cycle. Further we also identify several results on non-existence of certain sequences of \(j\). We further discuss the cycle structure in RC4 and provide several theoretical results. The results are supported by experimental observations with reduced versions of RC4. In this direction we point out that certain non-randomness in \(j\) is closely related to the short cycles in RC4.
For the entire collection see [Zbl 1428.94012].Multi-point codes from the GGS curves.https://www.zbmath.org/1456.941362021-04-16T16:22:00+00:00"Hu, Chuangqiang"https://www.zbmath.org/authors/?q=ai:hu.chuangqiang"Yang, Shudi"https://www.zbmath.org/authors/?q=ai:yang.shudiAlgebraic curves over finite fields can be used to obtain error correcting codes since the seminal work of Goppa in the early 1980s. Algebraic geometric (AG) codes have ``good'' parameters when the underlying curve has many rational points with respect to its genus. For this reason, maximal curves (i.e. curves attaining the upper bound in the Hasse-Weil bound) have been widely investigated. Recently, AG codes from Hermitian, Suzuki, Klein quartic, GK, and GGS curves and their quotients attracted a lot of attention. Most of the constructions of AG codes are one-point. In the case of multi-point AG codes, the main problem is a suitable description of Riemann-Roch spaces associated with divisors having a large support.
This paper deals with the construction of AG codes defined from GGS curves, a generalization of the GK curve. In particular, the authors describe bases for the Riemann-Roch spaces associated with some rational places, and characterize explicitly the Weierstrass semigroups and pure gaps (a generalization of gaps) by an exhaustive computation for the basis of Riemann-Roch spaces from GGS curves. As a byproduct, multi-point codes with parameters achieving new records are obtained.
Reviewer: Daniele Bartoli (Perugia)Sifting attacks in finite-size quantum key distribution.https://www.zbmath.org/1456.811602021-04-16T16:22:00+00:00"Pfister, Corsin"https://www.zbmath.org/authors/?q=ai:pfister.corsin"Lütkenhaus, Norbert"https://www.zbmath.org/authors/?q=ai:lutkenhaus.norbert"Wehner, Stephanie"https://www.zbmath.org/authors/?q=ai:wehner.stephanie"Coles, Patrick J."https://www.zbmath.org/authors/?q=ai:coles.patrick-jOptimal bounds for parity-oblivious random access codes.https://www.zbmath.org/1456.940592021-04-16T16:22:00+00:00"Chailloux, André"https://www.zbmath.org/authors/?q=ai:chailloux.andre"Kerenidis, Iordanis"https://www.zbmath.org/authors/?q=ai:kerenidis.iordanis"Kundu, Srijita"https://www.zbmath.org/authors/?q=ai:kundu.srijita"Sikora, Jamie"https://www.zbmath.org/authors/?q=ai:sikora.jamieEffective bandwidth of non-Markovian packet traffic.https://www.zbmath.org/1456.940032021-04-16T16:22:00+00:00"Cavallaro, Massimo"https://www.zbmath.org/authors/?q=ai:cavallaro.massimo"Harris, Rosemary J."https://www.zbmath.org/authors/?q=ai:harris.rosemary-jGeometry of Gaussian signals.https://www.zbmath.org/1456.940162021-04-16T16:22:00+00:00"Rosso, Alberto"https://www.zbmath.org/authors/?q=ai:rosso.alberto"Santachiara, Raoul"https://www.zbmath.org/authors/?q=ai:santachiara.raoul"Krauth, Werner"https://www.zbmath.org/authors/?q=ai:krauth.wernerMobile access and flexible search over encrypted cloud data in heterogeneous systems.https://www.zbmath.org/1456.680332021-04-16T16:22:00+00:00"Sun, Jianfei"https://www.zbmath.org/authors/?q=ai:sun.jianfei"Xiong, Hu"https://www.zbmath.org/authors/?q=ai:xiong.hu"Zhang, Hao"https://www.zbmath.org/authors/?q=ai:zhang.hao.4|zhang.hao.3|zhang.hao.1|zhang.hao.2|zhang.hao"Peng, Li"https://www.zbmath.org/authors/?q=ai:peng.liSummary: Never before has data sharing been more convenient with the rapid popularity and wide adoption of cloud computing. However, mobile access and flexible search with security for outsourced data in heterogeneous systems are two major obstacles prior to practical deployment of cloud computing. To meet the requirements in secure mobile access and flexible search to sensitive data, this paper, for the first time, proposes a versatile primitive referred to as an identity based proxy re-encryption system with outsourced equality test (IBPRE-ET). This primitive allows a data owner in an identity based broadcast encryption system (IBBE) seamlessly to share his/her data with a data sharer in an identity based encryption system (IBE). Moreover, it supports a data sharer in an IBBE system to perform search functionality on ciphertexts related to a data sharer in an IBE system. We also formally prove that the proposed IBPRE-ET system is selective secure using a random oracle model. Meanwhile, the theoretic evaluation and experimental result demonstrate our scheme is practical in the heterogeneous system. Finally, we show an application of our IBPRE-ET to the collaborative office automation system.MRD codes with maximum idealizers.https://www.zbmath.org/1456.941312021-04-16T16:22:00+00:00"Csajbók, Bence"https://www.zbmath.org/authors/?q=ai:csajbok.bence"Marino, Giuseppe"https://www.zbmath.org/authors/?q=ai:marino.giuseppe.1"Polverino, Olga"https://www.zbmath.org/authors/?q=ai:polverino.olga"Zhou, Yue"https://www.zbmath.org/authors/?q=ai:zhou.yue.1|zhou.yueRank-metric codes are a class of codes consisting of matrices with entries in a finite field, with the distance between two matrices being the rank of their difference. Codes with maximum size for a fixed minimum distance are called Maximum Rank Distance (MRD) codes, which are an analog of MDS codes for the Hamming metric. Rank-metric codes have important applications in random linear network coding, and MRD codes also have connections to other topics such as semifields, finite geometry, linearized polynomials, and cryptography.
In this context, it is important to say that only a few classes of MRD codes are known, and among them, Gabidulin codes were the only known class of MRD codes with maximum left and right idealizers.
In this paper, the authors classify MRD codes in \(\mathbb{F}_q^{n\times n}\) for \(n\le 9\) with maximum left and right idealizers, and find out new MRD codes with maximum idealizers for \(n=7\), \(q\) odd and for \(n=8\), \(q\equiv 1 \pmod{3}\). Some interesting open problems are also provided.
Reviewer: Matteo Bonini (Dublin)On determining absolute entropy without quantum theory or the third law of thermodynamics.https://www.zbmath.org/1456.800062021-04-16T16:22:00+00:00"Steane, Andrew M."https://www.zbmath.org/authors/?q=ai:steane.andrew-mWhat we learn from the learning rate.https://www.zbmath.org/1456.940142021-04-16T16:22:00+00:00"Brittain, Rory A."https://www.zbmath.org/authors/?q=ai:brittain.rory-a"Jones, Nick S."https://www.zbmath.org/authors/?q=ai:jones.nick-s"Ouldridge, Thomas E."https://www.zbmath.org/authors/?q=ai:ouldridge.thomas-eUpper energy bounds for spherical designs of relatively small cardinalities.https://www.zbmath.org/1456.050272021-04-16T16:22:00+00:00"Boyvalenkov, Peter"https://www.zbmath.org/authors/?q=ai:boyvalenkov.peter-g"Delchev, Konstantin"https://www.zbmath.org/authors/?q=ai:delchev.konstantin"Jourdain, Matthieu"https://www.zbmath.org/authors/?q=ai:jourdain.matthieuSummary: We derive upper bounds for the potential energy of spherical designs of cardinality close to the Delsarte-Goethals-Seidel bound. These bounds are obtained by linear programming with use of the Hermite interpolating polynomial of the potential function in suitable nodes. Numerical computations show that the results are quite close to certain lower energy bounds confirming that spherical designs are, in a sense, energy efficient.The homogeneous pseudo-embeddings and hyperovals of the generalized quadrangle \(H(3,4)\).https://www.zbmath.org/1456.510032021-04-16T16:22:00+00:00"De Bruyn, Bart"https://www.zbmath.org/authors/?q=ai:de-bruyn.bart"Gao, Mou"https://www.zbmath.org/authors/?q=ai:gao.mouLet \(\mathcal{S}=(\mathcal{P},\mathcal{L})\) be a generalized quadrangle and denote by \(\varepsilon:\mathcal{S} \longrightarrow \mathrm{PG}(V)\) the universal pseudo-embedding \(\mathcal{S}.\) The vector dimension of the subspace \(\langle \varepsilon(\mathcal{P})\rangle\) of \(V\) is called the \textit{pseudo-embedding rank} of \(\mathcal{S}.\)
If \(|\mathcal{P}|\) is finite, denote by \(C=C(\mathcal{S})\) the binary code of length \(|\mathcal{P}|\) generated by the characteristic vectors of the lines of \(\mathcal{S}.\) It has been proved in [the first author, Adv. Geom. 13, No. 1, 71--95 (2013; Zbl 1267.51002)] that the pseudo-embedding rank of \(\mathcal{S}\) is \(|\mathcal{P}|- \dim(C).\)
In this paper, the authors prove that the pseudo-embedding rank of the Hermitian quadrangle \(H(3,4)\) is equal to \(24.\) As a consequence, the binary code \(C(H(3,4))\) has dimension \(45-24=21,\) because the generalized quadrangle \(H(3,4)\) has \(45\) points.
They also show that there are, up to isomorphism, four homogeneous pseudo-embeddings of \(H(3,4),\) with respective vector dimensions \(14,\) \(15,\) \(23\) and \(24.\)
Reviewer: Guglielmo Lunardon (Napoli)Reconstruction of convex bodies from moments.https://www.zbmath.org/1456.520052021-04-16T16:22:00+00:00"Kousholt, Astrid"https://www.zbmath.org/authors/?q=ai:kousholt.astrid"Schulte, Julia"https://www.zbmath.org/authors/?q=ai:schulte.juliaSummary: We investigate how much information about a convex body can be retrieved from a finite number of its geometric moments. We give a sufficient condition for a convex body to be uniquely determined by a finite number of its geometric moments, and we show that among all convex bodies, those which are uniquely determined by a finite number of moments form a dense set. Further, we derive a stability result for convex bodies based on geometric moments. It turns out that the stability result is improved considerably by using another set of moments, namely Legendre moments. We present a reconstruction algorithm that approximates a convex body using a finite number of its Legendre moments. The consistency of the algorithm is established using the stability result for Legendre moments. When only noisy measurements of Legendre moments are available, the consistency of the algorithm is established under certain assumptions on the variance of the noise variables.Artificial sequences and complexity measures.https://www.zbmath.org/1456.940302021-04-16T16:22:00+00:00"Baronchelli, Andrea"https://www.zbmath.org/authors/?q=ai:baronchelli.andrea"Caglioti, Emanuele"https://www.zbmath.org/authors/?q=ai:caglioti.emanuele"Loreto, Vittorio"https://www.zbmath.org/authors/?q=ai:loreto.vittorioBayesian signal reconstruction for 1-bit compressed sensing.https://www.zbmath.org/1456.940232021-04-16T16:22:00+00:00"Xu, Yingying"https://www.zbmath.org/authors/?q=ai:xu.yingying"Kabashima, Yoshiyuki"https://www.zbmath.org/authors/?q=ai:kabashima.yoshiyuki"Zdeborová, Lenka"https://www.zbmath.org/authors/?q=ai:zdeborova.lenkaMultidimensional sparse super-resolution.https://www.zbmath.org/1456.940092021-04-16T16:22:00+00:00"Poon, Clarice"https://www.zbmath.org/authors/?q=ai:poon.clarice"Peyré, Gabriel"https://www.zbmath.org/authors/?q=ai:peyre.gabrielThe authors consider the computation of the positions and amplitudes of pointwise sources from linear measurements affected by additive noise. A regularized version of this problem is obtained by a minimization problem where the total variation of the solution is used as regularization term. The convergence of the regularized solution to the solution of the original problem is ensured under the nondegeneracy condition of minimum norm dual certificate. This last condition is usually replaced by a condition on precertificates requiring only linear relations, that, in the case of positive spikes, can be also used for an asymptotic analysis on the spikes distance to study super-resolution. The main contribution of the paper is a characterization of the certificate for super-resolution in the multidimensional space. Another contribution is a detailed analysis of the structure of the regularized solution in the particular case of the two spikes problem in the two-dimensional space. The paper concludes with some numerical examples.
Reviewer: Pierluigi Maponi (Camerino)Research on high-sensitive precise logic gates based on DNA strand replacement.https://www.zbmath.org/1456.680502021-04-16T16:22:00+00:00"Zhao, Jiwei"https://www.zbmath.org/authors/?q=ai:zhao.jiwei"Shi, Xiaolong"https://www.zbmath.org/authors/?q=ai:shi.xiaolongSummary: With the development of biochemical technology, new computing models that use DNA molecules as storage data and computing media have attracted widespread attention from researchers. One of the basic tasks of programmable DNA computing is to build logic gates with coded DNA. Previous works have implemented a seesaw gate to achieve step function, however this approach changes relatively gentle near threshold and its output is difficult to stabilize on expected value when input increases. In this article, a step function gate based on DNA strand displacement was proposed, of which the output signal has high mutation sensitivity and accuracy near threshold, and ability to maintain stability on expected value. Its threshold is set by annihilation, its reaction order is controlled by degree of toehold complementarity and it uses ``four-domain'' encoding as universal DNA signal strand form. Then based on step function gate, the AND, OR, NOT and XOR gate capable of distinguishing between ``no input signal'' and ``input signal is low'' were proposed, which solves the problem that NOT gates are difficult to implement using direct representations and usually indirectly represented by dual-rail logic.Lowering the error floor of Gallager codes: a statistical-mechanical view.https://www.zbmath.org/1456.941332021-04-16T16:22:00+00:00"Pretti, Marco"https://www.zbmath.org/authors/?q=ai:pretti.marcoIntersections between the norm-trace curve and some low degree curves.https://www.zbmath.org/1456.140322021-04-16T16:22:00+00:00"Bonini, Matteo"https://www.zbmath.org/authors/?q=ai:bonini.matteo"Sala, Massimiliano"https://www.zbmath.org/authors/?q=ai:sala.massimilianoThe affine plane curve \(\mathcal{X}\) defined over the finite field \(\mathbb{F}_{q^r}\) by the equation \[x^{\frac{q^r-1}{q-1}}= y^{q^{r-1}}+y^{q^{r-2}}+\cdots +y^q+y\] is called {\em norm-trace curve}. The norm-trace curve is a natural generalization of the Hermitian curve to any extension field \(\mathbb{F}_{q^r}\). The determination of the intersection of a given curve \(\mathcal{X}\) and low degree curves is often useful for the determination of the weight distribution of the AG code arising from \(\mathcal{X}\).
In this paper, the intersection of \(\mathcal{X}\) with cubics defined by equations of the form \(y = ax^3 + bx^2 + cx + d\), where \(a, b, c, d \in \mathbb{F}_{q^3}\), is studied. Especially, the intersection between the norm-trace curve and parabolas is characterised, and tools are provided in order to get sharp bounds for the number of intersections in the other cases. For this purpose specific irreducible surfaces over finite fields are studied. Furthermore, the weight distribution of the corresponding one-point codes are obtained.
Reviewer: Dimitros Poulakis (Thessaloniki)Exact recovery of multichannel sparse blind deconvolution via gradient descent.https://www.zbmath.org/1456.650432021-04-16T16:22:00+00:00"Qu, Qing"https://www.zbmath.org/authors/?q=ai:qu.qing"Li, Xiao"https://www.zbmath.org/authors/?q=ai:li.xiao"Zhu, Zhihui"https://www.zbmath.org/authors/?q=ai:zhu.zhihuiOn the role of composition entropies in the statistical mechanics of polydisperse systems.https://www.zbmath.org/1456.824262021-04-16T16:22:00+00:00"Paillusson, Fabien"https://www.zbmath.org/authors/?q=ai:paillusson.fabien"Pagonabarraga, Ignacio"https://www.zbmath.org/authors/?q=ai:pagonabarraga.ignacioStochastic resonance in a non-Poissonian dichotomous process: a new analytical approach.https://www.zbmath.org/1456.600912021-04-16T16:22:00+00:00"Bologna, Mauro"https://www.zbmath.org/authors/?q=ai:bologna.mauro"Chandía, Kristopher J."https://www.zbmath.org/authors/?q=ai:chandia.kristopher-j"Tellini, Bernardo"https://www.zbmath.org/authors/?q=ai:tellini.bernardoNETT: solving inverse problems with deep neural networks.https://www.zbmath.org/1456.650382021-04-16T16:22:00+00:00"Li, Housen"https://www.zbmath.org/authors/?q=ai:li.housen"Schwab, Johannes"https://www.zbmath.org/authors/?q=ai:schwab.johannes"Antholzer, Stephan"https://www.zbmath.org/authors/?q=ai:antholzer.stephan"Haltmeier, Markus"https://www.zbmath.org/authors/?q=ai:haltmeier.markus