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

Springer eBooks

Multi-bit Cryptosystems Based on Lattice Problems

Akinori Kawachi, Keisuke Tanaka, Keita Xagawa

Published Jun 20, 2007• 104 citations
Publisher
DOI
10.1007/978-3-540-71677-8_21

Related papers

Multi-party concurrent signatures scheme from lattice

Shangping Wang, Lihua Liu, Jin Dong Sun +1 more

Concurrent signatures scheme is an effective way to solve the problem of fair exchange without the help of any trusted third party. Until now, all concurrent signatures are based on traditional cryptosystems, but the emergence of quantum computing poses a severe threat to the security of classic public–key cryptosystems. More and more attentions are being paid to lattice–based cryptosystems, which is one of the candidate cryptosystems against the attacks from quantum computing. In this paper, we present a new formal model of multi–party concurrent signatures scheme and a lattice–based multi–party concurrent signatures scheme. The scheme has comparative advantages in both efficiency and security over the existing concurrent signatures schemes based on traditional cryptosystem. In particular, our scheme is constructed based on constant–size ring signatures, and thus we have solved the open problem: how to construct a multi–party concurrent signatures scheme based on constant–size ring signatures, which was proposed by Tonien et al. (2006).

International Journal of Information and Communication Technology•Jan 1, 2015•1 citation

Lattice-Based Cryptosystems: A Design Perspective

Jiang Zhang, Zhenfeng Zhang

Springer eBooks•Jan 1, 2020•17 citations

Reduction-Respecting Parameters for Lattice-Based Cryptosystems

Fletcher Gates

One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.

•Jan 1, 2018•0 citations

A Study on Lattice-Based Public-Key Cryptosystems

Keita Xagawa

•Jan 1, 2007•0 citations

Securities of lattice-based public-key cryptosystems

한대완

•Jan 1, 2007•0 citations

Efficient oblivious transfer construction via multiple bits dual-mode cryptosystem for secure selection in the cloud

Zengpeng Li, Chunguang Ma, Minghao Zhao +1 more

Cloud computing is a promising paradigm to provide flexible and reliable services. Nevertheless, concern and anxiety about data security and tenants’ privacy are still a major barrier for the popularity of cloud computing. Oblivious transfer (OT) is a cryptographic primitive that enables a client to selectively retrieve data in a privacy-preserving manner. It can be used to construct high-level protocols enabling applications in the cloud-computing paradigm. Technically, it has been proven that OT protocols can be constructed using a CPA-secure public-key encryption scheme. Along these lines, Peikert et al. formulated a dual-mode cryptosystem on which they constructed a single-bit OT scheme. Obviously, it has deficiencies in performance, which makes it unqualified for use in cloud-computing scenarios. This paper aims at providing an efficient multi-bit OT scheme for secure cloud applications. We first propose a multi-bit dual-mode cryptosystem based on the learning with errors (LWE) problem. Based on this multi-bit dual-mode cryptosystem, we construct a multi-bit OT. We present details of the OT construction together with security analysis of our scheme, and finally provide an example of how it can be used in specific application scenarios.

Journal of the Chinese Institute of Engineers•Jan 2, 2019•5 citations
Concurrent signatures scheme is an effective way to solve the problem of fair exchange without the help of any trusted third party. Until now, all concurrent signatures are based on traditional cryptosystems, but the emergence of quantum computing poses a severe threat to the security of classic public–key cryptosystems. More and more attentions are being paid to lattice–based cryptosystems, which is one of the candidate cryptosystems against the attacks from quantum computing. In this paper, we present a new formal model of multi–party concurrent signatures scheme and a lattice–based multi–party concurrent signatures scheme. The scheme has comparative advantages in both efficiency and security over the existing concurrent signatures schemes based on traditional cryptosystem. In particular, our scheme is constructed based on constant–size ring signatures, and thus we have solved the open problem: how to construct a multi–party concurrent signatures scheme based on constant–size ring signatures, which was proposed by Tonien et al. (2006).
One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.
Cloud computing is a promising paradigm to provide flexible and reliable services. Nevertheless, concern and anxiety about data security and tenants’ privacy are still a major barrier for the popularity of cloud computing. Oblivious transfer (OT) is a cryptographic primitive that enables a client to selectively retrieve data in a privacy-preserving manner. It can be used to construct high-level protocols enabling applications in the cloud-computing paradigm. Technically, it has been proven that OT protocols can be constructed using a CPA-secure public-key encryption scheme. Along these lines, Peikert et al. formulated a dual-mode cryptosystem on which they constructed a single-bit OT scheme. Obviously, it has deficiencies in performance, which makes it unqualified for use in cloud-computing scenarios. This paper aims at providing an efficient multi-bit OT scheme for secure cloud applications. We first propose a multi-bit dual-mode cryptosystem based on the learning with errors (LWE) problem. Based on this multi-bit dual-mode cryptosystem, we construct a multi-bit OT. We present details of the OT construction together with security analysis of our scheme, and finally provide an example of how it can be used in specific application scenarios.