Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM ASIA Public-Key Cryptography Workshop (APKC)

Two applications of multilinear maps

Seiko Arita, Sari Handa

Published May 30, 2014• 7 citations
Publisher

Abstract

Constructing multilinear maps has been long-standing open problem, before recently the first construction based on ideal lattices has been proposed by Garg et al. After this breakthrough, various new cryptographic systems have been proposed. They introduce the concept of level into the encodings, and the system has a function that extracts a deterministic value at only a specific level, and the encodings are unable to downgrade to the lower levels. These properties are useful for cryptography. We study how this graded encoding system be applied to cryptosystems, and we propose two protocols, group key exchange and witness encryption. In our group key exchange, we achieve the communication size and the computation costs per party are both O(1) with respect to the number of parties by piling the encodings of passed parties in one encoding. A witness encryption is a new type cryptosystem using NP-complete problem. The first construction is based on EXACT-COVER problem. We construct it based on another NP complete Hamilton Cycle problem, and prove its security under the Generic Cyclic Colored Matrix Model.

DOI
10.1145/2600694.2600699

Related papers

Application of Multilinear Forms in Cryptography

Tomáš Rabas

We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.

•Jan 1, 2018•0 citations

Design and Implementation of Lattice-Based Cryptography

Tancrède Lepoint

Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems. In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices and remains as of today a promising primitive for post-quantum cryptography. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.

•Jun 30, 2014•9 citations

New Applications of Homomorphic Cryptography

Sina Shiehian

Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.

•Jan 1, 2019•0 citations

Extensional schemes of multipartite non-interactive key exchange from multilinear maps and their applications

Yupu Hu, Huiwen Jia

The question of generalising the celebrated 2-party non-interactive key exchange (NIKE), Diffie-Hellman protocol, to a multipartite setting was left as an important open problem. In 2003, Boneh and Silverberg put forward a theoretical construction of multipartite NIKE protocol from a new notion called multilinear maps. In their protocol, however, the number of users N and the multilinearity k are related by N = k + 1, resulting in the system initialising another multilinear map when the number of users who want to exchange a session key changes. In this paper, we describe two extensional schemes of multipartite NIKE, which enables any less than or equal to N users derive a common shared key from an (N – 1)-multilinear map. In addition, using our extensional schemes, we show a concrete scenario: the establishment of any discussion group in a user group and its privacy version. Furthermore, we analyse its security.

International Journal of High Performance Computing and Networking•Jan 1, 2018•0 citations

Extensional schemes of multipartite non-interactive key exchange from multilinear maps and their applications

Huiwen Jia, Yupu Hu

The question of generalising the celebrated 2-party non-interactive key exchange (NIKE), Diffie-Hellman protocol, to a multipartite setting was left as an important open problem. In 2003, Boneh and Silverberg put forward a theoretical construction of multipartite NIKE protocol from a new notion called multilinear maps. In their protocol, however, the number of users N and the multilinearity k are related by N = k + 1, resulting in the system initialising another multilinear map when the number of users who want to exchange a session key changes. In this paper, we describe two extensional schemes of multipartite NIKE, which enables any less than or equal to N users derive a common shared key from an (N – 1)-multilinear map. In addition, using our extensional schemes, we show a concrete scenario: the establishment of any discussion group in a user group and its privacy version. Furthermore, we analyse its security.

International Journal of High Performance Computing and Networking•Jan 1, 2018•0 citations

A Verifiable Multi-recipient Encryption Scheme from Multilinear Maps

Zhengjun Jing, Guoping Jiang, Chunsheng Gu

Multi-recipient encryption is an important public key cryptosystem, which can be applied for a variety of purposes, such as broadcasting data. In order to design an secure multi-recipient public key encryption (MRPKE) in post-quantum era, in this paper, we construct a novel MRPKE scheme base on Garg-Gentry-Halevi (GGH) framework which is a graded algebras analogue of multilinear maps from ideal lattice. Under the grade decisional Diffie-Hellman (GDDH) assumption of GGH, the proposed scheme has semantically safety against chosen plaintext attack (CPA). At the same time, each recipient, without first decrypting, can verify whether the message to be received is from a legitimate sender. Furthermore, the encryption and decryption only involves the polynomial modular addition and multiplication in polynomial ring, so the efficiency of the proposed scheme is higher.

International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC)•Nov 1, 2014•1 citation
Constructing multilinear maps has been long-standing open problem, before recently the first construction based on ideal lattices has been proposed by Garg et al. After this breakthrough, various new cryptographic systems have been proposed. They introduce the concept of level into the encodings, and the system has a function that extracts a deterministic value at only a specific level, and the encodings are unable to downgrade to the lower levels. These properties are useful for cryptography. We study how this graded encoding system be applied to cryptosystems, and we propose two protocols, group key exchange and witness encryption. In our group key exchange, we achieve the communication size and the computation costs per party are both O(1) with respect to the number of parties by piling the encodings of passed parties in one encoding. A witness encryption is a new type cryptosystem using NP-complete problem. The first construction is based on EXACT-COVER problem. We construct it based on another NP complete Hamilton Cycle problem, and prove its security under the Generic Cyclic Colored Matrix Model.
Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems. In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices and remains as of today a promising primitive for post-quantum cryptography. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.
Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.
The question of generalising the celebrated 2-party non-interactive key exchange (NIKE), Diffie-Hellman protocol, to a multipartite setting was left as an important open problem. In 2003, Boneh and Silverberg put forward a theoretical construction of multipartite NIKE protocol from a new notion called multilinear maps. In their protocol, however, the number of users N and the multilinearity k are related by N = k + 1, resulting in the system initialising another multilinear map when the number of users who want to exchange a session key changes. In this paper, we describe two extensional schemes of multipartite NIKE, which enables any less than or equal to N users derive a common shared key from an (N – 1)-multilinear map. In addition, using our extensional schemes, we show a concrete scenario: the establishment of any discussion group in a user group and its privacy version. Furthermore, we analyse its security.
The question of generalising the celebrated 2-party non-interactive key exchange (NIKE), Diffie-Hellman protocol, to a multipartite setting was left as an important open problem. In 2003, Boneh and Silverberg put forward a theoretical construction of multipartite NIKE protocol from a new notion called multilinear maps. In their protocol, however, the number of users N and the multilinearity k are related by N = k + 1, resulting in the system initialising another multilinear map when the number of users who want to exchange a session key changes. In this paper, we describe two extensional schemes of multipartite NIKE, which enables any less than or equal to N users derive a common shared key from an (N – 1)-multilinear map. In addition, using our extensional schemes, we show a concrete scenario: the establishment of any discussion group in a user group and its privacy version. Furthermore, we analyse its security.
Multi-recipient encryption is an important public key cryptosystem, which can be applied for a variety of purposes, such as broadcasting data. In order to design an secure multi-recipient public key encryption (MRPKE) in post-quantum era, in this paper, we construct a novel MRPKE scheme base on Garg-Gentry-Halevi (GGH) framework which is a graded algebras analogue of multilinear maps from ideal lattice. Under the grade decisional Diffie-Hellman (GDDH) assumption of GGH, the proposed scheme has semantically safety against chosen plaintext attack (CPA). At the same time, each recipient, without first decrypting, can verify whether the message to be received is from a legitimate sender. Furthermore, the encryption and decryption only involves the polynomial modular addition and multiplication in polynomial ring, so the efficiency of the proposed scheme is higher.