Relational encryption

Patent metadata

Field	Value
Publication number	US-9749138-B2
Application number	US-201615287717-A
Country	US
Kind code	B2
Filing date	Oct 6, 2016
Priority date	May 25, 2014
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

A method includes encrypting a first plaintext vector using a relational linearity encryption scheme to generate a first linearity ciphertext and using a relational proximity encryption scheme to generate a first proximity ciphertext. The method includes communicating the first linearity and the first proximity ciphertexts to a server. The method includes encrypting a second plaintext vector using the relational linearity encryption scheme to generate a second linearity ciphertext and using the relational proximity encryption scheme to generate a second proximity ciphertext. The method includes communicating the second linearity and second proximity ciphertexts, a relational linearity key, and a relational proximity key to the server. The method includes receiving an authentication signal indicative of a linearity relationship between the first and the second linearity ciphertexts discovered using the relational linearity key and of a proximity between the first and the second proximity ciphertexts detected using the relational proximity key.

First claim

What is claimed is:

1. A method comprising:
encrypting a first plaintext vector using a relational linearity encryption scheme to generate a first linearity ciphertext representative of the first plaintext vector;
encrypting the first plaintext vector using a relational proximity encryption scheme to generate a first proximity ciphertext representative of the first plaintext vector;
communicating the first linearity ciphertext and the first proximity ciphertext to an authentication server;
encrypting a second plaintext vector using the relational linearity encryption scheme to generate a second linearity ciphertext representative of the second plaintext vector;
encrypting the second plaintext vector using the relational proximity encryption scheme to generate a second proximity ciphertext representative of the second plaintext vector;
communicating the second linearity ciphertext and the second proximity ciphertext to the authentication server;
communicating a relational linearity key of the relational linearity encryption scheme and a relational proximity key of the relational proximity encryption scheme to the authentication server; and
receiving from the authentication server an authentication signal indicative of a linearity relationship between the first linearity ciphertext and the second linearity ciphertext discovered using the relational linearity key and of a proximity between the first proximity ciphertext and the second proximity ciphertext detected using the relational proximity key.

2. The method of claim 1 , wherein:
the first plaintext vector includes a first biometric template received as registration input from a user;
the second plaintext vector includes a second biometric template received as challenge input; and
the authentication signal indicates that the second biometric template originated at the user.

3. The method of claim 1 , further comprising generating keys of the relational linearity encryption scheme, wherein the generating includes:
generating three bilinear groups of a prime order, wherein the prime order is exponential in a security parameter;
sampling a first generator of a first bilinear group of the three bilinear groups;
sampling a second generator of a second bilinear group of the three bilinear groups;
generating a first linearity secret key by randomly sampling a particular number of elements from a set of integers, the set of integers including zero to one less than the prime order;
generating a second linearity secret key by randomly sampling the particular number of elements from the set of integers;
defining a first linearity public key that includes an element that is the first generator and one or more other elements that are the first generator raised to the power of a corresponding element of the first linearity secret key;
defining a second linearity public key that includes an element that is the second generator and one or more other elements that are the second generator raised to the power of a corresponding element of the second linearity secret key; and
defining a linearity relational secret key, wherein each element of the linearity relational secret key is a sum of a corresponding element of the second linearity secret key and a corresponding element of the first linearity secret key.

4. The method of claim 3 , wherein:
the first plaintext vector includes a p-ary vector and is a member of a second field including elements of zero to one less than the base-number (p) and a dimension of the particular number;
the three bilinear groups are generated of the prime order exponential in the security parameter and equal to one modulo the base-number (p);
the first linearity public key includes another element that is an arbitrary generator of a subgroup of the set of integers with zero omitted;
the second linearity public key includes another element that is the arbitrary generator; and
the encrypting the first plaintext vector using the relational linearity encryption scheme includes:
sampling a random number from the set of integers; and
constructing the first linearity ciphertext that includes:
a first element that is the first generator raised to the power of the random number, and
one or more other elements including a corresponding element of the first linearity public key raised to a linearity encryption power, wherein the linearity encryption power includes a product of the random number and the arbitrary generator raised to the power of a corresponding element of the first plaintext vector.

5. The method of claim 3 , wherein:
the first plaintext vector includes bit vectors and is a member of a first field, the first field including elements of zero and one and a dimension of the particular number; and
the encrypting using the relational linearity encryption scheme includes:
sampling a random number from the set of integers; and
constructing the first linearity ciphertext to include:
a first element that is the first generator raised to the power of the random number, and
one or more other elements that are a corresponding element of the first linearity public key raised to a linearity encryption power, wherein the linearity encryption power includes a product of the random number and negative one raised to the power of a corresponding element of the first plaintext vector.

6. The method of claim 1 , further comprising generating keys of the relational proximity encryption scheme for a security parameter, wherein the generating includes:
choosing a linear error correcting code (ECC), wherein the linear error correcting code includes a length, a rank in the same order of the security parameter, and a selected minimum distance;
running a key generator algorithm of a chosen-plaintext attack (CPA) secure encryption scheme, wherein the CPA secure encryption scheme outputs a CPA public key and a CPA secret key;
running a relational linearity key generation algorithm that outputs a first linear public key, a second linear public key, a first linear secret key, a second linear secret key, and a relational linear secret key;
defining a first proximity public key as an ECC encoding operator, an ECC decoding operator, the CPA public key, and the first linear public key;
defining a second proximity public key as the ECC encoding operator, the ECC decoding operator, the CPA public key, and the second linear public key;
defining a first proximity secret key as the CPA secret key and the first linear secret key;
defining a second proximity secret key as the CPA secret key and the second linear secret key; and
defining a proximity relational secret key as the CPA secret key and the relational linear secret key.

7. The method of claim 6 , wherein the encrypting using the relational proximity encryption scheme includes:
sampling a proximity random number from a third field, wherein the third field includes a base-number and a dimension that is the rank of the ECC;
defining a first part of a first proximity ciphertext as a CPA encryption algorithm receiving as inputs the CPA public key and a sum of the first plaintext vector and the ECC encoding operator receiving the proximity random number as an input; and
defining a second part of the first proximity ciphertext as a first linearity encryption algorithm that receives the first linearity public key and the proximity random number as inputs.

8. The method of claim 1 , further comprising decrypting the first linearity ciphertext using the relational linearity encryption scheme, wherein the decrypting includes for each element of the first plaintext vector:
determining whether a corresponding element in the first linearity ciphertext is equal to a first element of the first linearity ciphertext raised t

Assignees

• Fujitsu Ltd

Inventors

• Mandal Avradip
• Roy Arnab

Classifications

• H04L9/0869

  involving random numbers or seeds · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L9/3231 Primary

  Biological data, e.g. fingerprint, voice or retina (network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861) · CPC title

• H04L9/3271

  using challenge-response · CPC title