Salîm Yüce · Journal of Science and Arts · 2023
Let be the vector spaces and V_i^* be their dual spaces for 1≤i≤r . In this paper, (V_1×V_2×…×V_r )^*≅V_1^*×V_2^*×…×V_r^* is examined. Furthermore, the dual map F^* and the adjoint map F^' of the r-linear map F:V_1×V_2×…×V_r→W are defined and for their matrices, the equality [F^* ]=[F^' ]=[F ̅ ]^T is found. Analog, the dual map F^* of the r-variable vector valued linear map F:V_1×V_2×…×V_r→W_1×W_2×…×W_r is defined and for their matrices, the equality [F^* ]=[F ̅ ]^T is true, for the vector spaces V_i and W_i .
Cited by 0Open access
Alice Pellet-Mary, Damien Stehlé · 2016
multilinear map allows to perform as many multiplications as desired, while in κ-multilinear maps like GGH [5] or CLT [3,4] one we can perform at most a predetermined number κ of multiplications. In this note, we show that the extraction Multilinear Computational Diffie-Hellman problem (ext-MCDH) associated to Gu’s map can be solved in polynomial-time: this candidate ideal multilinear map is insecure. We also give intuition on why we think that the two other ideal multilinear maps proposed by Gu in [9] are not secure either. 1
Cited by 3
Chunsheng Gu · International Journal of Information Technology and Web Engineering · 2015
Cryptographic multilinear maps have extensive applications. However, current constructions of multilinear maps suffer from the zeroizing attacks. For a candidate construction of multilinear maps described by Garg, Gentry, and Halevi (GGH13), Hu & Jia recently presented an efficient attack, which broke the GGH13-based applications of multipartite key exchange (MPKE) and witness encryption (WE) based on the hardness of 3-exact cover problem. By introducing random matrix, the author presents an improvement of the GGH13 map, which supports the applications for public tools of encoding in the GGH13 map, such as MPKE and WE. The security of the construction depends upon new hardness assumption. Moreover, the author's improvement destroys the structure of the ring element in the principal ideal lattice problem, and avoids potential attacks using algorithm of solving short principal ideal lattice generator.
Cited by 3
Majid Salimi · arXiv (Cornell University) · 2021
Though the multilinear maps have many cryptographic applications, secure and efficient construction of such maps is an open problem. Many multilinear maps like GGH, GGH15, CLT, and CLT15 have been and are being proposed, while none of them is both secure and efficient. The construction of some multilinear maps is based on the Graded Encoding Scheme (GES), where, the necessity of announcing zero-testing parameter and encoding of zero has destroyed the security of the multilinear map. Attempt is made to propose a new GES, where, instead of encoding an element, the users can obtain the encoding of an associated but unknown random element. In this new setting, there is no need to publish the encodings of zero and one. This new GES provides the actual functionality of the usual GES and can be applied in constructing a secure and efficient multilinear map and a multi-party non-interactive key exchange (MP-NIKE) scheme. We also improve the MP-NIKE scheme of \cite{Access20} and turn it into an ID-based MP-NIKE scheme.
Cited by 0Open access
PEREIRA, Vitor, Hilder V. L. Pereira · Open Repository and Bibliography (University of Luxembourg) · 2019
Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian's randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian's randomization after encoding, the complexity of the best attacks is significantly increased for CLT13 multilinear maps. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude. As an application, we describe the first concrete implementation of multiparty non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange that is resistant against known attacks, based on CLT13 multilinear maps. For $$N=4$$ users and a medium level of security, our implementation requires 18 GB of public parameters, and a few minutes for the derivation of a shared key.
Cited by 7
Shuchang Zhou, Yuxin Wu · arXiv (Cornell University) · 2015
In this paper we propose and study a technique to impose structural constraints on the output of a neural network, which can reduce amount of computation and number of parameters besides improving prediction accuracy when the output is known to approximately conform to the low-rankness prior. The technique proceeds by replacing the output layer of neural network with the so-called MLM layers, which forces the output to be the result of some Multilinear Map, like a hybrid-Kronecker-dot product or Kronecker Tensor Product. In particular, given an "autoencoder" model trained on SVHN dataset, we can construct a new model with MLM layer achieving 62\% reduction in total number of parameters and reduction of $\ell_2$ reconstruction error from 0.088 to 0.004. Further experiments on other autoencoder model variants trained on SVHN datasets also demonstrate the efficacy of MLM layers.
Cited by 0Open access
Sanjam Garg, Eric Miles, Pratyay Mukherjee et al. · Lecture notes in computer science · 2016
Cited by 74
Jianhong Zhang, Yuwei Xu, Yuanbo Cui et al. · The Journal of China Universities of Posts and Telecommunications · 2012
Cited by 1
Brice Minaud, Pierre-alain Fouque · 2016
Abstract. This article describes a polynomial attack on the new multi-linear map over the integers presented by Coron, Lepoint and Tibouchi at Crypto 2015 (CLT15). This version is a fix of the first multilinear map over the integers presented by the same authors at Crypto 2013 (CLT13) and broken by Cheon et al. at Eurocrypt 2015. The attack essentially downgrades CLT15 to its original version CLT13, and leads to a full break of the multilinear map for virtually all applications. In addition to the main attack, we present an alternate probabilistic attack underpinned by a different technique, as well as an instant-time attack on the optimized variant of the scheme.
Cited by 0
Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee et al. · Lecture notes in computer science · 2016
Cited by 76Open access
Jung Hee Cheon, Changmin Lee · 2016
Abstract. We improve the zeroizing attack on the multilinear map of Garg, Gentry and Halevi (GGH). Our algorithm can solve the Graded Decisional Diffie-Hellman (GDDH) problem on the GGH scheme when the dimension n of the ideal lattice Z[X]/(Xn+1) is O(κλ2) as suggested for the κ-linear GGH scheme. The zeroizing attack is to recover a basis of an ideal generated by a secret element g ∈ Z[X]/(Xn + 1) from the zero testing parameter and several encodings in public. It can solve the DLIN and subgroup decision prob-lems, but not the GDDH problem on the GGH scheme for the suggested dimension n due to the hardness of the smallest basis problem and the shortest vector problem on the ideal lattice. In this paper, we propose an algorithm to find a short vector in the ideal lattice 〈g 〉 by applying a lattice reduction to a sublattice obtained from the Hermit Normal Form of 〈g〉. This attack utilizes that the determinant of the lattice 〈g 〉 is not large. We further show that if g has a large residual degree, one can find a short element of g in polynomial time of n. In order to resist the pro-posed attacks, it is required that n = Ω̃(κ2λ3) and the positive generator of 〈g 〉 ∩ Z is large enough.
Cited by 0
Jiseung Kim, Changmin Lee · IET Information Security · 2021
Abstract The authors present a classical polynomial‐time attack against the branching program obfuscator of Fernando–Rasmussen–Sahai (for short FRS, Asiacrypt’17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators when instantiated with the CLT13 multilinear map. The first step is to recover a plaintext modulus of the CLT13 multilinear map. To achieve the goal, the Coron and Notarnicola (Asiacrypt’19) algorithm is applied. However, because of parameter issues, the algorithm cannot be used directly. In order to detour the issue, the authors convert an FRS obfuscator into a new programme containing a small message space. Through the conversion, the authors obtain two zerotest parameters and encodings of zero except for two non‐zero slots. Then, they are used to mitigate parameter constraints of the message space recovering algorithm. Then, a cryptanalysis of the FRS obfuscation based on the recovered message space is proposed. The authors show that there exist two functionally equivalent programmes such that their obfuscated programmes are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.
Cited by 0Open access
Risil Chhatrala, Shailaja Patil, Dattatray V. Jadhav · Lecture notes in computational vision and biomechanics · 2019
Cited by 0
Chun‐I Fan, Yi‐Fan Tseng, Yen‐Lin Huang · 2020
With the growing accessibility of the internet, many people store files in the cloud storage. In consideration of privacy preserving, users tent to encrypt their files before uploading them to the cloud. Under certain conditions, a file owner may want to share the encrypted files directly on the cloud. In such cases, the file owner will delegate the re-encryption ability to a proxy with re-encryption keys. However, Chen et al. found that the size of the re-encryption key (or condition key) would increase with the number of the conditions, which motivated them in proposing the concept of key-aggregate proxy re-encryption. Unfortunately, we found that the conditions cannot be changed arbitrarily once we set the conditions at the beginning. To solve the problem, we apply the multilinear maps to the key-aggregate proxy re-encryption to extend the number of conditions to be exponentially large, while keeping the size of public parameters small and practical.
Cited by 2
Léo Ducas, Alice Pellet-Mary · HAL (Le Centre pour la Communication Scientifique Directe) · 2018
International audience
Cited by 0Open access
Jaeseong Heo · Rocky Mountain Journal of Mathematics · 2001
In this paper the notion of a covariant multilinear map from a C * -algebra to another is introduced. Covariant completely bounded symmetric multilinear maps are decomposed into covariant completely bounded and completely positive multilinear maps, and each covariant completely bounded map is covariantly representable in terms of covariant representations and bridging operators. We show that a covariant completely bounded multilinear map extends to a completely bounded multilinear map on the crossed product C * -algebra.
Cited by 3Open access
W. T. Gowers, Luka Milićević · arXiv (Cornell University) · 2019
Let $G_1, \dots, G_k$ be finite-dimensional vector spaces over a finite field $\mathbb{F}$. A multilinear variety of codimension $d$ is a subset of $G_1 \times \dots \times G_k$ defined as the zero set of $d$ forms, each of which is multilinear on some subset of the coordinates. A map $ϕ$ defined on a multilinear variety $B$ is multilinear if for each coordinate $d$ and all choices of $x_i \in G_i$, $i\not=d$, the restriction map $y \mapsto ϕ(x_1, \dots, x_{d-1}, y, x_{d+1}, \dots, x_k)$ is linear where defined. In this note, we show that a multilinear map defined on a multilinear variety of codimension $d$ coincides on a multilinear variety of codimension $d^{O(1)}$ with a multilinear map defined on the whole of $G_1\times\dots\times G_k$.
Cited by 1Open access
Alice Pellet-Mary · Lecture notes in computer science · 2018
Cited by 9Open access
W. T. Gowers, Luka Milićević · Proceedings of the Edinburgh Mathematical Society · 2021
Abstract Let $G_1, \ldots , G_k$ be finite-dimensional vector spaces over a prime field $\mathbb {F}_p$ . A multilinear variety of codimension at most $d$ is a subset of $G_1 \times \cdots \times G_k$ defined as the zero set of $d$ forms, each of which is multilinear on some subset of the coordinates. A map $\phi$ defined on a multilinear variety $B$ is multilinear if for each coordinate $c$ and all choices of $x_i \in G_i$ , $i\not =c$ , the restriction map $y \mapsto \phi (x_1, \ldots , x_{c-1}, y, x_{c+1}, \ldots , x_k)$ is linear where defined. In this note, we show that a multilinear map defined on a multilinear variety of codimension at most $d$ coincides on a multilinear variety of codimension $O_{k}(d^{O_{k}(1)})$ with a multilinear map defined on the whole of $G_1\times \cdots \times G_k$ . Additionally, in the case of general finite fields, we deduce similar (but slightly weaker) results.
Cited by 2Open access
César Massri · Americanae (AECID Library) · 2011
We provide an algorithm to compute the 2-norm maximum of a multilinear map over a product of spheres. As a corollary we give a method to compute the first singular value of a linear map and an application to the theory of entangled states in quantum physics. Also, we give an application to find the closest rank-one tensor of a given one.
Cited by 3Open access