Lattices in constructions of dense sphere packings and certain cryptographic schemes

• Main Author: Cheng, Shantian
• Other Authors: Ling San
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Science
• Online Access: https://hdl.handle.net/10356/66449
• Institution: Nanyang Technological University

In this thesis we concentrate on the usage of lattices to construct explicit sphere packings with high density, packing families with good asymptotic properties, and cryptographic schemes with special functionalities, including (delegatable) policybased signature and revocable identity-based encryption. First we introduce new methods using codes and lattices from number fields to construct dense packings in Euclidean spaces. Let ω = (−1 + √−3)/2. For any lattice P ⊆ Z^n, P = P + ωP is a subgroup of On K, where OK = Z[ω] ⊆ C. As C is naturally isomorphic to R^2, P can be regarded as a lattice in R 2n. Let P be a multiplicative lattice (principal lattice or congruence lattice) introduced by Rosenbloom and Tsfasman. We concatenate a family of special codes with t`P·(P + ωP), where tP is a generator of a non-zero prime ideal P of OK. Applying this concatenation to a family of principal lattices, we obtain a new family with asymptotic density exponent λ > −1.26532182283, which is better than −1.87 given by Rosenbloom and Tsfasman by considering only principal lattice families. For a new family based on congruence lattices, the result is λ > −1.26532181404, which is better than −1.39 obtained by considering only congruence lattice families. More generally, via the canonical Q-embedding of arbitrary number field K into R^[K:Q], both the prime ideal p and its residue field κ can be embedded as discrete subsets in R^[K:Q]. Thus we can concatenate the embedding image of the Cartesian product of n copies of p together with the image of a length n code over κ. This concatenation leads to a packing in the Euclidean space R^n[K:Q]. Moreover, we extend the single concatenation to multiple concatenations to obtain dense packings and asymptotically good packing families. For instance, with the help of Magma, we construct a 256-dimensional packing denser than the Barnes-Wall lattice BW256. Next we develop the recent techniques in lattice-based cryptography to construct a (delegatable) policy-based signature scheme and a revocable identity-based encryption scheme from lattice assumptions. Policy-based signature, introduced by Bellare and Fuchsbauer at PKC 2014, is a new type of digital signature in which a signer is only allowed to sign messages satisfying certain policy specified by the authority, but the signatures should not reveal the underlying policy. We adapt Langlois et al.’s zero-knowledge argument system (PKC 2014) for the Bonsai tree signature scheme (Eurocrypt 2010) to enable the prover to convince the verifier that its secret witness satisfies an additional condition. Making the protocol non-interactive via the Fiat-Shamir transformation, we obtain a policy-based signature scheme supporting polynomially many policies, which satisfies the two security requirements (simulatability and extractability) in the random oracle model. Furthermore, our construction can be efficiently extended to a delegatable policy-based signature, thanks to the hierarchical structure of the Bonsai tree. In view of the expiration or revelation of the user’s private credential (or private key) in a realistic scenario, identity-based encryption (IBE) schemes with an efficient key revocation mechanism, or for short, revocable identity-based encryption (RIBE) schemes, become prominently significant. We present an RIBE scheme from lattices by combining two Agrawal et al.’s IBE schemes (Eurocrypt 2010) with the subset difference method. In particular, our scheme may serve as a solution to a question posed by Chen et al. (ACISP 2012).