IDENTITY-BASED XOR HOMOMORPHIC CRYPTOSYSTEMS

RELATED APPLICATION

This patent application claims the benefit of 1) U.S. Provisional Application No. 62/098386 filed on December 31, 2014, 2) U.S. Provisional Application No. 62/055,729 filed on September 26, 2014 both with the same title, and 3) U.S. Provisional Application No. 62/055716 filed on September 26, 2014, titled "XOR- homomorphic Crypto systems with Fast Key Generation", the disclosures of both are incorporated by reference herein in their entirety.

Field of Invention

The present principles relate to cryptography, and more specifically, to identity-based homomorphic cryptosystems. Background Information

This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.

Referenced Documents

[1] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In st ACM Conference on Computer and Communications Security, pages 62-73. ACM Press, 1993.

[2] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. SIAM J. CompuL , 32(3):586-615, 2003.

[3] Michael Clear, Arthur Hughes, and Hitesh Tewari. Homomorphic encryption with access policies: Characterization and new constructions. In A. Youssef, A. Nitaj, and A. E. Hassanien, editors, Progress in Cryptology — AFRICACRYPT 2013, volume 7918 of Lecture Notes in Computer Science, pages 61- 87. Springer, 2013.

[4] Clifford Cocks. An identity based encryption scheme based on quadratic residues. In B. Honary, editor, Cryptography and Coding, volume 2260 of Lecture Notes in Computer Science, pages 360-363. Springer, 2001.

[5] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. /. Comput. Syst. Sci., 28(2):270-299, 1984.

[6] Marc Joye. U.S. Provisional Application No. 62/055716 filed on

September 26, 2014, titled "XOR-homomorphic Crypto systems with Fast Key Generation."

[7] Marc Joye and Gregory Neven, editors. Identity-Based Cryptography, volume 2 of Cryptology and Information Security Series. IOS Press, 2009.

[8] Karl Rubin and Alice Silverberg. Compression in finite fields and torus- based cryptography. SIAM J. Comput, 37(5): 1401-1428, 2008.

[9] Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and D. Chaum, editors, Advances in Cryptology, Proceedings of CRYPTO '84, volume 196 of Lecture Notes in Computer Science, pages 47-53. Springer, 1985.

Identity-based encryption

Identity-based cryptography is an extension of the public -key paradigm which was put forward by Shamir [9]. A major issue with public -key cryptography is the management of trust. Other issues to be dealt with include recovering the public key and companion certificate, checking them, and then only encrypting and sending the messages. We refer the reader to the excellent introduction [7] by Joux for details. Identity-based cryptography aims at solving these practical issues by simplifying key management.

Formally, we define an identity-based encryption (IBE) scheme [2] as a tuple of four algorithms (SETUP, EXTRACT, ENCRYPT, DECRYPT), where the process 300 is illustrated in Figure 3 :

Setup The setup algorithm SETUP 310 is a randomized algorithm that takes on input some security parameter κ and outputs the system parameters m pk together

R

with the master secret key msk: (m pk, msk) <- SETUP(1 ^K ). Key derivation The key derivation algorithm EXTRACT , or Key Derivation 320, takes on input an identity id and master secret key msk and returns a secret key for the user with identity id : usk <- EXTRACT _msk (id) .

Encryption Let M denote the message space. The encryption algorithm ENCRYPT 330 is a randomized algorithm that takes on input an identity id and a plaintext m G M , and returns a ciphertext C. We write C <- ENCRYPT _mpk (id, m).

Decryption The decryption algorithm DECRYPT 340 takes on input secret key usk (corresponding to identity id) and ciphertext C and returns the corresponding plaintext m or a special symbol 1 indicating that the ciphertext is invalid. We write m - DECRYPT _usk (C) if C is a valid ciphertext and ± - DECRYPT _usk (C) if it is not.

We require that, with non-negligible probability, DECRYPT _usk (ENCRYPT _mpk (id, m)) = m for all messages m E M. The specific processes associated with each of these steps as they relate to the present principles is described in further detail below.

Security notions

The notion of indistinguishability (IND) of encryptions [5] captures a strong notion of data-privacy: The adversary should not learn any information whatsoever about a plaintext given its encryption beyond the length of the plaintext. The definitions for the public -key setting naturally extend to the identity-based paradigm. The standard definition is strengthened by allowing the adversary to issue chosen private-key extraction queries [2].

We view an adversary Λ as a pair (Λ ₁ , Λ ₂ ) of probabilistic algorithms. This corresponds to adversary Λ running in two stages. Upon receiving the system parameters m pk, in the "find" stage, algorithm Λ issues private-key extraction queries id ₁₍ id _ni and receives back the private key uskj corresponding to identity \ά(. usk _j <- EXTRACT _msk (id _j ). The queries may be asked adaptively. Once the adversary decides not to make further oracle queries, it outputs a challenge identity id* (with id*≠ id; , 1 < i < ¾), two (different) equal-size messages m ₀ and m ₁ G M , and some state information s. In the "guess" stage, algorithm ·Λ ₂ receives a challenge ciphertext C which is the encryption of m _b for identity id* and where b is chosen at random in {0,1}· Algorithm ·Λ ₂ can issue more private -key extraction queries id _ni+1 , ... , id _n2 ; the only restriction is that id;≠ id ^* , n < i < n ₂ . The goal of cZ ₂ is to recover the value of b from 5 and C.

A public-key encryption scheme is said semantically secure (or indistinguishable) if

(mpk,msk) <- SETUP(1 ^K ),

r _/ |EXTRACT _msk (-)/- , EXTRACT _msk () _{f Γ} ,

Pr (id ,m ₀ ,m ₁ ,s <- <A ₁ ^msK (mpk),: & ₂ ^msK (s, C) = b

[b ^{0,1},C <- ENCRYPT _mpk (id ^* ,m _¾ )

is negligible in the security parameter for any polynomial-time adversary Λ; the probability is taken over the random coins of the experiment according to the distribution induced by SETUP and over the random coins of the adversary.

Adversary Λ = (·Λ ₁ ,·Λ ₂ ) can encrypt any message of its choice for any identity. In other words, the adversary can mount chosen-Identity, Chosen-Plaintext Attacks (ID-CPA). Hence, we write IND-ID-CPA the security notion achieved by a semantically secure identity-based encryption scheme.

Remark 1. As messages m ₀ and m ₁ are supposed to be different, when the message space is M = {0,1}, the previous relation simplifies to

(mpk,msk) <- SETUP(1 ^K ),

EXTRACT _msk () . EXTRAC _W .) _{(S) C) = &}

Pr (id ^* ,s) <- A (mpk),

b <- {0,1}, C <- ENCRYPT _mpk (id ^* , b) Complexity assumptions

It is useful to introduce some notations. Let N = pq be the product of two (odd) primes p and q. The Jacobi symbol modulo N of an integer a is denoted by 7 _w ( ). The set of integers whose Jacobi symbol is 1 is denoted by _N , _N = {a G ¾l/iv( ) ⁼ 1}; ^tne set of quadratic residues is denoted by Q _W , Q _W = {a G N\J _p (a) = J _q (a) = 1}. Note that QR _N is a subset of J _N .

[Quadratic Residuosity Assumption] Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q and their product N = pq. The Quadratic Residuosity (QR) assumption asserts that the success probability defined as the distance

Pr [D(x,N) = l\x ,]-Pr[V(x,N) = l\x^ _N \QR _N ] is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) <- RSAGen ( 1 ^K ) and choosing at random x G QM _W and x G _N \ QM _W .

Random oracle model

The random oracle model is an idealized model introduced by Bellare and Rogaway [1] to analyze the security of certain cryptographic constructions using hash functions. Informally, the random oracle model assumes that the output of a hash function behaves as the output of a random generator.

The group {Τ _ρ γ x {T _q f

Let p be an odd prime, let Δ G IF _p ^x , and let δ ² = A. Define the multiplicative group

G _p = {x + y\x, y G W _p and x ² — Ay ² = 1). Where it is defined, consider the map

To ease the notation, we augment IF _p with a special symbol∞ and define ψ(∞ ^~ ) = 1. There are two cases to distinguish:

1. Ιΐ δ <£ W _p then G _p = [ip(u) \u G IF _p U {∞}}—see [8, Section 2];

2. If δ G IF _p then G _p = {ip(u) \u G IF _p U {∞}, u≠ ±δ}.

(Observe that 0 ί G _p when δ E W _p .)

We are interested in the second case. From now on, we will suppose that δ G IF _p * and thus that Δ G QR _p . For convenience, we write T _p = W _p \ {±£}) U (oo). We so have G _p = ψ(Τ _ρ ). Clearly, map T _p → G _p is injective and thus defines a bijection. Indeed, suppose τ/>(«ι) = ^{ ₂ ) for some u , u _{2 p} . This implies + δ) (u ₂ — δ) = (u ₂ + δ) u — δ) and in turn u _x = u ₂ . The inverse map is given

Furthermore, map yields a homomorphism from T _p to G _p . We have ψ(∞ = 1. Let u _x , u ₂ G T _p \ {∞). We have:

1 u _x — δ —u _x + δ

τ/Ό½) u + δ — u — δ = ! -Mi) and, if u ≠

u ₁ u ₂ + Δ

(i½ + δ) (u ₂ + δ) u u ₂ + Δ + 8 u ₁ + u ₂ ) u + u ₂

(μ ₁ -δ)(μ ₂ -δ) u u ₂ + Δ - δ(π + u ₂ ) ^u i ^u 2 + ^Δ

u _x + u ₂

U ₁ U ₂ +Δ

where —

u ₁ +u ₂

Consequently, T _p endows a group structure. Its order is #T _p = p— 1. We write T _p multiplicatively and use © to denote its group law. We have:

• the neutral element is∞:

u®∞ =∞®u = u for all u G T _p ; the inverse of u G T _p \ {∞) is— u:

u © (— u) = (—u) © u · given u _x , u ₂ G T _p \ {∞), their multiplication is given by:

oo ot erwse.

Remark that 0 is of order 2 as an element of T _p , namely 0 © 0 = oo. Remark also that for u G T _p , u≠ 0, oo, we have u © 0 = A/u.

Let (T _p ) ² c _p represent the subgroup of squares in T _p .

(T _p ² ={u® u\u G T _p }

The group (T _p ) ² has (p— l)/2 elements.

Let u ₁ ,u ₂ T _p . Define w ₁ =u ₁ ®u ₁ and w ₂ =u ₂ ®u ₂ . Then letting u ₃ : = u _x © u ₂ we get:

w ₃ : = w ₁ © w ₂

= (u ® u ) ® (u ₂ ® u ₂ ) = (u ® u ₂ ) ® (u ® u ₂ ) = u ₃ ® u ₃ .

Further, for any 1 < i < 3, if W _j ≠ oo then 2w; + 28 = , and thus / _T ,C2w _/ + 25)

Ui ^p (1)

The previous setting naturally extends through Chinese remaindering. Let N = pq be an RSA (Rivest-Shamir-Adleman) modulus. Then (T _p ) ² x ( _q ) ² is a group and has order φ(Ν).

SUMMARY OF THE INVENTION

The present invention recognizes the need to improve the existing systems and methods for implementing cryptosystems, especially homomorphic identify -based cryptosystems and methods.

In accordance with an aspect of the present principles, a method for communicating a message m is presented, comprising:

accessing the message m;

accessing a user identity id and public system parameters mpk = {N, u, Ή}, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u G _N \ Q _W , N is a composite integer;

generating a ciphertext C = {ε, c, έ, c] of the message m using the user identity id, where

ε = (-l) ^m , = t + ?f mod N, έ = (-l) ^m J _N (t), and c = t + ^ mod N, where t, i E (Έ/ ΝΈ ^Χ , R _ld = Jf(id) ; and

transmitting the ciphertext C = {ε, c, έ, c] to a device via a communication channel.

In accordance with another aspect of the present principles, a method for processing a ciphertext is presented, comprising:

receiving the ciphertext C = {ε, c, έ, c], via a communication channel;

accessing the ciphertext C = {ε, c, έ, c], where ε = (-l ^m J _N (t , c = t + ^ mod N, έ = (-l ^m J _N (t , and c = t +

^ - mod N; t, i G (Έ/ΝΈ) ^Χ , R _ld = (id), u G J _N \ QR _N , and N is a composite integer; and generating a plaintext message m by accessing a private key usk = {r _id } for a user with an identity id by following steps:

if r _id ² ≡≡ Ή (id) (mod N , setting v = ε and γ = c; otherwise setting v = έ and γ = c;

determining τ = ] _Ν γ + 2r _id ) using the private key r _id ; and if r G {±1} ,

1— v · τ

m

In accordance with another aspect of the present principles, a method is presented for generating a private key for an identity based cryptosystem wherein the private key is used to decrypt a ciphertext C = {ε, c, έ, c], where ε = (-l) ^m ; _w (t), c = t + ^ mod N, έ = (-l ^m J _N (t , and c = t +

^ητ mod N; t, t G (Έ/ΝΈ) ^Χ , R _id = Jf(id), u G J _N \ QR _N , and N is a composite integer, comprising steps of:

setting a master secret key msk; and

generating, using the master secret key msk, the private key usk = {r _id } for a user with an identity id, using public system parameters m pk = {N, u, J }, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u G _N \ Q _W , and N is a composite integer; wherein ff _id = Ή (id) and if ff _id G Q _W , then r _id =

R^ ^{1 2} mod N, otherwise r _id = (uff _id ) 2 mod N.

In accordance with another aspect of the present principles, an apparatus for communicating a message m is presented, comprising:

a processor configured to access the message m, the processor further configured to accessing a user identity id and public system parameters m pk = {N, u, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u G _N \ Q _W , N is a composite integer;

an encryptor configured to generate a ciphertext C = {ε, c, έ, c] of the message m using the user identity id , where

ε = (-1Γ , c = t + ^ mod N, έ = -l) ^m ] _N t), and c = t + ^ mod N, where t, i G (Z/NZ) ^x , ff _id = W (id) ; and a communication interface, coupled to a communication channel, configured to transmit the ciphertext C = {ε, c, έ, c] via the communication channel.

In accordance with another aspect of the present principles, an apparatus for processing a ciphertext is presented, comprising:

a communication interface, coupled to a communication channel, configured to receive the ciphertext C = {ε, c, έ, c] via the communication channel;

a processor configured to access the ciphertext C = {ε, c, έ, c], where ε = (-l) ^m J _N (t), c = t + ^f mod N, έ = (-l) ^m J _N (t), and c = t + ^ητ mod N; t, i G (Έ/ΝΈ) ^Χ , R _ld = (id), u G J _N \ QR _N , and N is a composite integer; and

the processor generates a plaintext message m by accessing a private key usk = {r _id } for a user with an identity id by following steps:

if r _id ² ≡≡ Ή (id) (mod N), setting v = ε and γ = c; otherwise setting v = έ and γ = c;

determining τ = ] _Ν γ + 2r _id ) using the private key r _id ; and if G {±l) ,

1— v · τ

m = .

2

In accordance with another aspect of the present principles, an apparatus is presented for generating a private key for an identity based cryptosystem wherein the private key is used to decrypt a ciphertext C = {ε, c, έ, c], where ε = (-l) ^m ; _w (t), c = t + ^ mod N, έ = (-l ^m J _N (t , and c = t +

^ητ mod N; t, i G (Έ/ΝΈ) ^Χ , R _ld = (id), u G J _N \ QR _N , and N is a composite integer, comprising:

a processor configured to set a master secret key msk, and generate, using the master secret key msk, the private key usk = {r _id } for a user with an identity id , using public system parameters m pk = {N, u, Ή}, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u G _N \ Q _W , and N is a composite integer; wherein ff _id = Ή (id) and if ff _id G Q _W , then r _id = Κ^ ^{1 2} mod N, otherwise r _id = (uff mod N; and a communication interface, coupled to a communication channel, configured to transmit the private key usk = {r _id } via the communication channel.

In accordance with another aspect of the present principles, a computer program product stored in non-transitory computer-readable storage media is presented, comprising computer-executable instructions for:

accessing the message m;

accessing a user identity id and public system parameters m pk = {N, u, Ή}, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u E _N \ Q _W , N is a composite integer;

generating a ciphertext C = {ε, c, έ, c] of the message m using the user identity id , where

ε = (-l) ^m , = t + ?f mod N, έ = (-l) ^m J _N (t), and c = t + ^ mod N, where t, i G (Z/NZ) ^x , i? _id = Jf(id) ; and

transmitting the ciphertext C = {ε, c, έ, c] to a device via a communication channel.

In accordance with another aspect of the present principles, a computer program product stored in non-transitory computer-readable storage media is presented, comprising computer-executable instructions for:

receiving the ciphertext C = {ε, c, έ, c], via a communication channel;

accessing the ciphertext C = {ε, c, έ, c], where ε = (-l) ^m J _N (t), c = t + ^ mod N, έ = (-l) ^m J _N (t), and c = t +

UR

- - mod N; t, i G (Έ/ΝΈ) ^Χ , R _id = (id), u G J _N \ Q _N , and N is a composite integer; and

generating a plaintext message m by accessing a private key usk = {r _id } for a user with an identity id by following steps:

if r _id ² ≡ Ή (id) (mod N), setting v = ε and γ = c; otherwise setting v = έ and γ = c;

determining τ = ] _Ν γ + 2r _id ) using the private key r _id ; and if e {±l} , 1— v · τ

m

In accordance with another aspect of the present principles, a computer program product stored in non-transitory computer-readable storage media is presented, for generating a private key for an identity based cryptosystem wherein the private key is used to decrypt a ciphertext C = {ε, c, έ, c], where ε = (-l ^m J _N (t , c = t + ^ mod N, έ = (-l ^m J _N (t , and c = t +

^ - mod N; t, i G (Έ/ΝΈ) ^Χ , ff _id = (id), u G J _N \ QR _N , and N is a composite integer, comprising computer-executable instructions for:

setting a master secret key msk; and

generating, using the master secret key msk, the private key usk = {r _id } for a user with an identity id, using public system parameters m pk = {N, u, J }, where Ή is a cryptographic hash function mapping bit-strings to elements of _N , u G _N \ Q _W , and N is a composite integer; wherein ff _id = Ή (id) and if ff _id G Q _W , then r _id =

R^ ^{1 2} mod N, otherwise r _id = (uR _ld ) 2 mod N.

DETAILED DESCRIPTION OF THE DRAWINGS

The above-mentioned and other features and advantages of this invention, and the manner of attaining them, will become more apparent and the invention will be better understood by reference to the following description of embodiments of the invention taken in conjunction with the accompanying drawings, wherein:

Figures 1 to 3 show exemplary apparatus according to the present principles; and

Figures 4 to 6 show exemplary processes according to the present principles. The examples set out herein illustrate exemplary embodiments of the invention. Such examples are not to be construed as limiting the scope of the invention in any manner.

DETAILED DESCRIPTION

Homomorphic encryption is a form of encryption which allows for combining two ciphertexts through a non-private operation that results in a third ciphertext which, when decrypted, yields a plaintext that is the combination of the corresponding two plaintexts through a specific operation. Mathematically, for two ciphertexts C = ENCRYPT^i) and C ₂ = ENCRYPT(m ₂ ) , there exists a non-private operation d such that C _x dC ₂ = ENCRYPT (m-L * m ₂ ) for some specific operation *. Examples of known operations * include the modular addition and the modular multiplication. This application is concerned with the XOR operation, or equivalently, the addition modulo 2.

Only one XOR-homomorphic identity-based cryptosystem is known to date: a recent cryptosystem by Clear, Hughes, and Tewari [3]. Its security relies on the quadratic residuosity assumption in the random oracle model. However, the cryptosystem by Clear et al. has ciphertexts twice longer than Cocks' IBE [4] (also semantically secure under the quadratic residuosity assumption in the random oracle model).

The present principles provide XOR-homomorphic identity-based cryptosystems with short ciphertexts. As will be seen, the resulting ciphertexts are as short as in the Cocks' IBE scheme. Extra useful properties offered by the proposed cryptosystems are listed later.

Main ideas

Let N = pq be an RSA modulus. As shown in [6], the algebraic structure behind T _p x T _q gives rise to XOR-homomorphic public-key encryption schemes. If the user' s public key therein is defined as the output of a hash function (modeled as a random oracle), they can be turned into XOR-homomorphic IBE schemes. The complication is that the user' s public key in the schemes of [6] are required to be quadratic residues modulo N; i.e., elements of Q _W .

To address this issue, we assume a hash function Ή mapping arbitrary identities to a superset of Q _W (note that in the current state of affairs, it is unknown how to output an element of Q _W without the knowledge of prime factors p and q.)

As in Cocks' IBE scheme [4], we suppose that this superset is J _w ; namely, the set of integers modulo N whose Jacobi symbol is 1 :

Ή : {0),\γ→ _N , d H> Jf(id).

The probability that a random element in (Έ/ΝΈ) ^Χ (where (Έ/ΝΈ) ^Χ denotes the multiplicative group of Έ/ΝΈ, as well known in the art) is also in _N is 1/2. Hence, it is easy to build an efficient hash function mapping to _N on top of a "regular" cryptographic hash function, say h, mapping bit-strings to Έ/ΝΈ (or a subset thereof). See e.g. [1] for examples of such "regular" cryptographic hash functions (sometimes referred to as full-domain hash functions).

Back to our case, we can for example define Ή(χ) as h(i, x) where i is the smallest nonnegative integer such that h(i, x) G J _w . Yet another possibility is to successively apply h until the output is an element in _N : define Ή(χ) as Ή(χ) = Qi o h o · · · o h)(x) = h ^l (x) where i is the smallest positive integer such that h ^l (x) G

The user's secret key is then defined as Ή (id) ¹ / ² mod N. Of course, this is only defined when Ή (id) G Q _N . When Ή (id) G J _N \ Q _N , the user's secret key is defined as (uJ (id)) ¹ / ² mod N where u is a predetermined element in _N \ Q _W — note that in this case u · Ή (id) G Q _W , as desired.

Remark 2. The above technique slightly generalizes Cocks' technique. In [4], Cocks considers Blum integers; namely, RSA moduli N = pq with p, q≡ 3 (mod 4). Doing so, his original scheme corresponds to the case u =— 1. Remember that when p, q≡ 3 (mod 4), we have J _p (—1) = J _q (—1) =—1 and therefore -1 G J _N \ QR _N .

Now when someone wishes to encrypt a message for a user with identity id, s/he cannot know whether Ή (id) G Q _W . Again, as in [4], this can be solved by encrypting twice: once with ff _id : = Ή (id) and once with ff _id : = u · Ή (id) mod N. As the recipient knows either a square -root modulo N of ff _id or of ff _id , the recipient will be able to decrypt.

Remark 3. Where defined, square-roots modulo N are not unique. For security reasons, it is important that, given some input, key derivation algorithm always returns the same square root. The notation (-) ¹ / ² mod N is used to refer to a well- identified square-root modulo N (for example as the output of a deterministic algorithm, as the smallest square root among the possible square roots, or as a value in a history list).

Exemplary embodiments

First exemplary embodiment

The exemplary embodiments are now described in the framework of the flow diagram of Figure 3. Our first cryptosystem is defined as follows. SETUP(1 ^K ) Given a security parameter κ, SETUP generates an RSA modulus N = pq where p and q are prime. It also selects an element u G _N \ QM _W . The public system parameters are m pk = {N, u, where Ή is a cryptographic hash function mapping bit-strings to J _w ; i.e., J : {0,1} ^* → _N . The master secret key is msk = {p, q}.

EXTRACT _msk (id) Given identity id, key derivation algorithm EXTRACT first sets ff _id = Ή (id). If ff _id G Q _W it computes r _id = R^ ² mod N; otherwise it computes r _id = (uR^) ¹ ^ ² mod N. EXTRACT returns user's private key usk = {r _id }.

ENCRYPT _mpk (id, m) To encrypt a message m G {0,1} for a user with identity id, ENCRYPT first defines ff _id = Ή (id). It chooses at random t, i G (Έ/ΝΈ) ^Χ satisfying gcd ( t ² — ff _jd , N) = gcd ( t ² — uR _ld , N) = 1 and computes ε = (-l) ^m , c = t + -^ mod N, έ = (-l) ^m J _N (i), and c

= t + ^2- mod N.

t

The returned ciphertext is C = {ε, c, έ, c}.

DECRYPT _usk (C) From usk = {r _id } and C = {ε, c, έ, c], if r _id ² ≡ Ή (id) (mod N), DECRYPT sets v = ε and γ = c; otherwise it sets v = έ and γ = c. Next it computes τ = ] _Ν γ + 2r _id ) using secret key r _id . If τ £ {±1} it returns 1; otherwise it returns plaintext m as m

Remark 4. As an alternative, we see from Eq. (1) that the decryption algorithm can evaluate τ as τ = ] _Ν γ— 2r _id ). Also the test r _id ² ≡ ^? Ή (id) (mod N can be precomputed.

Remark 5. In a practical implementation, for better efficiency, the encryption algorithm can randomly draw t, i G Έ/ΝΈ.

Correctness

Correctness is straightforward and follows from [6]. Homomorphic property

Let C ₁ = (ε ₁₍ c ₁₍ έ ₁₍ c _x ) and C ₂ = (ε ₂ , c ₂ , έ ₂ , c ₂ ) be the respective encryption of ges m ₁ and m ₂ for a user with identity id. Then, letting ff _id = Ή (id) and u · Ή (id) mod N, we get from [6, § 2.2.3] that C ₃ = (ε ₃ , c ₃ , έ ₃ , c ₃ ) with

^C 1 ^C 2 +

ε ₃ = ε _ί - ₂ - J _N (c ₁ + c ₂ , c ₃ = ^■ mod N, ε ₃

Ci + c ₂

= £ ₁ - £ ₂ - J _N c ₁ + c ₂ ), and

c ₂ + R _jd

c ₃ =— ; ;— mod N

Cl + C ₂

is the encryption of message m ₃ = © m ₂ (for the user with identity id).

Note that given the encryption of a message m G {0,1}, it is easy to get the encryption of the complementary value. If C = (ε, c, ε, c) is the encryption of m G {0,1} then C = (— ε, c,— ε, c) is the encryption of—an.

Security analysis

We start with a useful lemma. It shows that, given a ciphertext C = {ε, c, ε, c}, among its two components (ε, c) and (έ, c) , one carries no information whatsoever about the corresponding plaintext.

Lemma 1. Using the previous notations, ifJi d ^{^} ) Q _W then the pair (ε, c) corresponds with the same probability to the encryption of message m = 0 or of m = 1. Conversely, ifu J{(jd Q _W then the pair (ε, c) corresponds with the same probability to the encryption of message m = 0 or of m = 1.

Proof Suppose that Ή (id) £ QR _N (i.e., Ή (id) G J _N \ QR _N ). Let ff _id = Jf(id). We have ε = (— l) ^m / _w (t) and c = t + -^ mod N for some random t G (Έ/ΝΈ) ^Χ . Consider also t ₁₍ t ₂ , t ₃ G (Έ/ΝΈ) ^Χ such that

• t ₁ ≡ t (mod p), t ₁ ≡ ffj _d /t (mod q) ;

• ¾ ≡ ^ff id A (mod p), t ₂ ≡ t (mod q) ;

• t ₃ ≡ ffi _d /t (mod p), t ₃ ≡ ffi _d /t (mod q).

(Note that the condition gcd ( t ² - ff _id , N) = 1 implies gcd ( ^ ² - ff _id , N) = gcd ( t ₂ ² - R _id , N) = gcd ( t ₃ ² - R _id , N) = 1.) The four possible values t, t _l5 t ₂ , and t ₃ are equally likely since c≡ t + ff _id /t≡ t ₁ + ffj _d /ti = t ₂ + (mod N). At the same time, since ^ff i _d ^G Jw \ QH&j ^{we a} l ^so have J _N t) = J _N t ₃ )≠ ] _Ν {ί ) = J _N (t ₂ ). Hence component c leaks no information about J _N (t); it has the same probability to be 1 or — 1.

The case u Ή (id) £ Q _W is proved similarly.

Proposition 1. The scheme is I N D-ID-CPA under the quadratic residuosity assumption in the random oracle model.

Proof. Let Λ = (·Λ ₁ , ·Λ ₂ ) be an I N D-I D-CPA adversary against the scheme that can break the scheme with probability e. We will use Λ to decide whether a random element w in _N is quadratic residue modulo N or not.

Let Ή : {0,1} ^* → JJ be a hash function viewed as a random oracle. Consider the following distinguisher D(w, N) for solving the QR problem:

1. Select u G J _W ;

2. Set mpk = [N, u, JC), and give m pk to ^EXTRACT^O O _HA§ oracle access to EXTRACT _msk (-) and Ή (·), it may issue a number of extraction and hash queries, after what it returns a pair (id*, s);

3. Depending on id* :

(a) If Jf(icT) = w then i. Choose a random bit b G {0,1}, let ff _id * = Ή (id*) , and compute the encryption of b as C _b = {s _b , c _b , i _b , c _b ] where

R *

¾ = (-i O, c _b = t + ^- mod N,

uR *

s _b = (-l) ¹ - ^b J _N (i), c¾ = t +— mod N, for some random elements t, i G (Έ/ΝΈ) ^Χ such that gcd ( t ² — ff _{i d} * , N) = gcd ( t ² - uR _id ., N) = 1;

_/ G-.i·ve C r _& = { r¾, c¾, ¾ - , c-¾- j> * t.o Λi ₂ EXTRACT _msk (-),3f

11. ( — Λ _Λ2 may issue more extraction and hash queries, after what it returns its guess b' iii. If b' = b return 1; otherwise return 0.

(b) If Jf(icT)≠ w then

i. Choose a random bit b' £ {0,1};

ii. Return b' .

It remains to detail how T) simulates answers to oracle queries. D maintains a history list HistfJf] composed of triplets. The list is initialized to 0. It also maintains a counter k initialized to 0. Let q _Hi denote the number of hash queries that are not followed by extract queries and let q _Ei denote the number of extract queries, made by Λ _χ . Without loss of generality, we assume that Λ _χ issues a hash query on id ^* . Finally, we let / denote a random integer in {1, ... , q _Hi + q _Ei ] chosen by D.

Hash queries When Λ queries oracle Ή on some id, D checks whether there is an entry of the form (id, h, r) in Hist[Jf] ; i.e., a triplet with id as the first component. If so, it returns h. Otherwise, it does the following:

1. Increment k ;

2. Depending on k:

(a) If k = /q, define h = w and append (id, h, 1) to Hist[Jf] ;

(b) Else (if k≠ /q), define h = u ^~ i r ² mod N with r <- (Έ/ΝΈ) ^Χ

R

and ; - {0,1} and append (id, h, r) to H ist[Jf ] ;

3. Return h.

Extraction queries When Λ queries oracle EXTRACT on some id, D checks whether there is an entry of the form (id, h, r) in HistfJf ]. If not, it calls Ή (id) so that there is an entry. Let (id, h, r) denote the entry in HistfJf] corresponding to id. Depending on it, D does the following:

1. If r≠± then return r;

2. If r =1 then abort. We now analyze the success probability of D in solving the QR challenge. If u is chosen at random in _N , with a probability of 1/2, u is an element in _N \ Q _W , and so the resulting mpk appear as valid system parameters (note that when more information is known about N, for example that N is a Blum integer, then one can select u =— 1 and mpk then always represent valid system parameters). Provided that u G _N \ QM _W , three cases can be distinguished.

Case 1 The first case supposes w = Ή (id ^* ) G Q _W . The condition w = Jf(id ^* ) requires that id ^* is the / -th query to Ή. Further, since Ή (id ^* ) G Q _W , Lemma 1 teaches that C _b = {£ _b ,c _b ,i _b ,c _b } is a valid ciphertext for b. Namely, component (¾, c _b ) correctly decrypts to b and component (s _b ,c _b ) is of no use. Hence, D returns 1 exactly when Λ wins in the I ND- ID- CPA game, provided that there is no abort. But since Λ is not allowed to submit id ^* to EXTRACT (and so there is no abort when id ^* is the / -th query), we get Pr [D(w, N) = l|w G Q _W Aw = K (id ^* )] = e.

Case 2 The second case supposes w = Ή (id ^* ) G j _N \ Q _W . Since Ή (id ^* ) G N \ Q _W , Lemma 1 teaches that C _b = {s _b , c _b , l _b , c _b ] is a valid ciphertext for (1— b) — it is worth noticing that ¾ = (— l) ^1~b J _N (t). Hence, D returns 1 exactly when Λ looses in the I ND- ID-CPA game. We therefore get Pr [T>(w,N) = l\w G QR _N Aw = KQd ^* )] = l-e.

Case 3 The last case supposes w≠ Ή (id ^* ). In this case D returns a random bit, regardless of w. Therefore, we have Pr [ ⁾ (w, N) = l\w G Q _W Aw≠ Jf(id ^* )] = Pr[D(w,N) = Aw≠ Jf(id ^* )] = 1/2.

We so obtain:

Pr [D(w,N) = l|w G QR _N ]

= Pr [w = (id ^* )] · Pr [O w,N = l\w G QM _W Λ w = Jf(id ^* )]

+ Pr [w≠ Jf(id ^* )] · Pr [D(w,N) = l|w G QM _W Aw≠ Jf(id ^* )]

and similarly,

Pr[2)(w,N) =

Putting all together, we get:

|Pr[2)(w,N) = l|wG QM _w ]-Pr[2)(w,N) = l|w G _N \ QR _N ]\

2 1 which must be negligible by the QR assumption. As a consequence, \ e— - \ must be negligible, which means that the scheme is I N D- I D-CPA secure under the QR assumption. Second exemplary embodiment

Suppose that ff _id = J-C \d G QR _N . As shown in [6], if {ε, c) with ε = (— l) ^m / _w (t) and c = t + ff _id /t mod N is a valid encryption for message m G {0,1} then so is C : = {ε', c'} where ε' = ε 1) and c' = N— c. The case Ή (id) G N \ Q _W is similar.

As a result, if £ represents the bit-length of RSA modulus N this allows us to reduce to size a ciphertext to at most 2£ bits. Here is an implementation of a so- obtained cryptosystem.

SETUP(1 ^K ) Given a security parameter κ, SETUP generates an RSA modulus N = pq where p and q are prime. It also selects an element u G _N \ Q _W . The public system parameters are m pk = {N, u, where Ή is a cryptographic hash function mapping bit-strings to J _w ; i.e., J : {0,1}*→ _N . The master secret key is msk = {p, q}.

EXTRACT _msk (id) Given identity id, key derivation algorithm EXTRACT first sets ff _id = Ή (id) . If ff _id G Q _W it computes r _id = ffjd ¹ '' ² mod N; otherwise it computes r _id = (uR^) ¹ ^ ² mod N. EXTRACT returns user's private key usk = {Yjd}-

ENCRYPT _mpk (id, m) To encrypt a message m G {0,1} for a user with identity id , ENCRYPT first defines ff _id = Ή (id). It chooses at random t, t E TL/NTL and computes ε' = (-ΓΤ , c' = t + ^ mod N, έ' = (-l) ^m J _N (t), and

uRj _f i

c' = i + mod N.

t

Define c = min ( c', N— c') and c = min ( c', N— c') . If c = c' then define ε = ε' ; otherwise define ε = ε' · J _N (—1). Similarly, if c = c' then define έ = έ'; otherwise define έ = έ' · J _N (—1) . The returned ciphertext is C = {ε, c, έ, c}.

DECRYPT _usk (C) From usk = {r _id } and C = {ε, c, έ, c], if r _id ² ≡ Ή (id) (mod N), DECRYPT sets v = ε and γ = c; otherwise it sets v = έ and γ = c. Next it computes τ = ] _N (j + 2r _id ) using secret key r _id . If τ <t {±1} it returns 1; otherwise it returns plaintext m as

1— v · τ

m =

Remark 6. As an alternative, the decryption algorithm can evaluate τ as τ = ] _Ν {γ— 2r _id ). Also the test r _ld ² ≡K (\d) (mod N)

can be precomputed.

Third exemplary embodiment

Assume now primes p and q satisfy the extra condition p≡ q (mod 4). In this case, we know that J _p (—1) = J _q (—1) and therefore J _N (— 1) = 1. Note that it is easily verified that N is the product of two primes that are congruent modulo 4 by checking that N≡ 1 (mod 4).

SETUP(1 ^K ) Given a security parameter κ, SETUP generates an RSA modulus N = pq where p and q are prime and p≡ q (mod 4). It also selects an element ii £ j _w \ Q _W . The public system parameters are mpk = {N, u, J } where Ή is a cryptographic hash function mapping bit-strings to J _w ; i.e., J : {0,1} ^* → _N . The master secret key is msk = {p, q}.

EXTRACT _msk (id) Given identity id, key derivation algorithm EXTRACT first sets ff _id = Ή (id) . If ff _id G Q _W it computes r _id = Κ^ ^{1 2} mod N; otherwise it computes r _id = (uR^) ¹ ^ ² mod N. EXTRACT returns user's private key usk = {r _id }.

ENCRYPT _mpk (id, m) To encrypt a message m G {0,1} for a user with identity id , ENCRYPT first defines ff _id = Ή (id). It chooses at random t, i E TL/NTL and computes

£ = (-l) ^m J _N (t), ' = t + ^ mod N, i = (-l) ^m J _N (t), and

uRiri

c' = _t + mod N.

t

Define c = min ( c', N— c') and c = min ( c\ N— c'). The returned ciphertext is C = {ε, c, έ, c}.

DECRYPT _usk (C) From usk = {r _id } and C = {ε, c, έ, c], if r _id ² ≡ Ή (id) (mod N , DECRYPT sets v = ε and γ = c; otherwise it sets v = έ and γ = c. Next it computes τ = ] _N (j + 2r _id ) using secret key r _id . If τ <t {±1} it returns 1; otherwise it returns plaintext m as

1— v · τ

m =

Remark 7. As an alternative, the decryption algorithm can evaluate τ as τ = ] _Ν {γ— 2r _id ). Also the test

r _id ² = Jf (id) (mod N)

can be precomputed.

Fourth exemplary embodiment

Assume further that RSA modulus N is a so-called Blum integer. Namely, N is the product of two primes p and q such that p≡ q≡ 3 (mod 4). In this case,— 1 is an element of _N \ Q _W . The choice u =— 1 is therefore valid for the system parameters. As the value can be global (and thus implicit in the description) there is no need to explicitly include it in mpk. The choice u =— 1 also slightly improves the performance of the key derivation algorithm and of the encryption algorithm.

SETUP(1 ^K ) Given a security parameter κ, SETUP generates an RSA modulus

N = pq where p and q are prime and p≡ q≡ 3 (mod 4). The public system parameters are m pk = {N, J } where Ή is a cryptographic hash function mapping bit- strings to J _w ; i.e., Ή : {0,1} ^*→ Jw Th ^e master secret key is msk = {p, q}.

EXTRACT _msk (id) Given identity id, key derivation algorithm EXTRACT first sets ff _id = H " (id) . If ff _id G Q _N it computes r _id = ff _id ^1/2 mod N; otherwise it computes r _id = (— R^) ¹ ^ ² mod N. EXTRACT returns user's private key usk = {r _id }.

ENCRYPT _mpk (id, m) To encrypt a message m G {0,1} for a user with identity id , ENCRYPT first defines ff _id = Ή (id). It chooses at random t, i E TL/NTL and computes = (-l) ^m J _N (t), c' = t + ! - mod N, i = (-l) ^m J _N (i), and

R- c' = i mod N.

t

Define c = min ( c', N— c') and c = min ( c', N— c'). The returned ciphertext is C = {ε, c, έ, c}. DECRYPT _usk (C) From usk = {r _id } and C = {ε, c, έ, c], if r _id ² ≡ Ή (id) (mod N), DECRYPT sets v = ε and γ = c; otherwise it sets v = έ and γ = c. Next it computes τ = ] _Ν γ + 2r _id ) using secret key r _id . If τ £ {±1} it returns 1; otherwise it returns plaintext m as

1— v · τ

Remark 8. When N = pq is a Blum integer, if R £ Q _W then a square-root of R is given by R(N+5- _P -q)/8 _{mod N} _ _{notice that} ^Ν +* ^~ ν-<ι _{≡ z}

8

Remark 9. As an alternative, the decryption algorithm can evaluate τ as τ = JN(Y— 2r _id ). Also the test

r _id ² = Jf (id) (mod N)

can be precomputed.

There are several advantages for the proposed cryptosystems:

• identity-based paradigm;

• homomorphic property w.r.t. the XOR operation (or equivalently addition modulo 2 ) ;

• almost free encryption of the complementary value;

• strong security guarantees.

The proposed encryption schemes can be used in any application requiring efficient identity-based encryption when the homomorphism property w.r.t. the XOR operation is needed. The homomorphism property is a central ingredient in a number of applications, including, to name a few, electronic voting, private information retrieval, or secure multi-party computation.

Compared with [6], the new cryptosystems proposed in this application present the advantage of being identity-based. This solves a number of practical issues in real systems. On the downside, the ciphertexts are twice longer.

FIG. 1 illustrates a block diagram of an exemplary system in which various aspects of the exemplary embodiments of the present principles may be implemented. System 100 may be embodied as a device including the various components described below and is configured to perform the processes described above. Examples of such devices, include, but are not limited to, personal computers, laptop computers, smartphones, tablet computers, digital multimedia set top boxes, digital television receivers, personal video recording systems, connected home appliances, and servers. System 100 may be communicatively coupled to other similar systems, and to trusted third parties via a communication channel as shown in Figure 2 and as known by those skilled in the art to implement the exemplary cryptosystems described above.

The system 100 may include at least one processor 110 configured to execute instructions loaded therein for implementing the various processes as discussed above. Processor 110 may include embedded memory, input output interface and various other circuitry as known in the art. The system 100 may also include at least one memory 120 (e.g., a volatile memory device, a non-volatile memory device). System 100 may additionally include a storage device 140, which may include nonvolatile memory, including, but not limited to, EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, magnetic disk drive, and/or optical disk drive. The storage device 140 may comprise an internal storage device, an attached storage device and/or a network accessible storage device, as non-limiting examples. System 100 may also include an encryption/decryption module 130 configured to process data to provide an encrypted message or decrypted message.

Encryption/decryption module 130 represents the module(s) that may be included in a device to perform the encryption and/or decryption functions. As is known, a device may include one or both of the encryption and decryption modules, for example, encryption may be done on a regular PC since encryption does not involve secret key so that the PC need not include secure memory for storing the input parameters (i.e., the public system parameters and the user's identity). Decryption however, requires secret keys (i.e., the decryption key) and is done in a secure device, for example a smart card. As memory is expensive on smart card, the encryption functionality may not always be provided on a smart card. The encryption and/or decryption may be performed using shared resources as known to those skilled in the art. Additionally, encryption/decryption module 130 may be implemented as a separate element of system 100 or may be incorporated within processors 110 as a combination of hardware and software as known to those skilled in the art.

Program code to be loaded onto processors 110 to perform the various processes described hereinabove may be stored in storage device 140 and

subsequently loaded onto memory 120 for execution by processors 110. In accordance with the exemplary embodiments of the present principles, one or more of the processor(s) 110, memory 120, storage device 140 and encryption/decryption module 130 may store one or more of the various items during the performance of the processes discussed herein above, including, but not limited to a public key, a private keys, encrypted messages, equations, formula, matrices, variables, operations, and operational logic.

The system 100 may also include communication interface 150 that enables communication with other devices via communication channel 160. The

communication interface 150 may include, but is not limited to a transceiver configured to transmit and receive data from communication channel 160. The communication interface may include, but is not limited to, a modem or network card and the communication channel may be implemented within a wired and/or wireless medium. The various components of system 100 may be connected or

communicatively coupled together using various suitable connections, including, but not limited to internal buses, wires, and printed circuit boards.

As a non- limiting example, one or more of the above-identified components may receive and/or store the information (e.g., to be encrypted, resulting from decryption) and/or the ciphertext (e.g., to be decrypted, to be operated on

homomorphically, resulting from encryption). As a further non-limiting example, one or more of the above-identified components may receive and/or store the encryption function(s) and/or the decryption function(s), as described herein above.

The exemplary embodiments of this invention may be carried out by computer software implemented by the processor 110 or by hardware, or by a combination of hardware and software. As a non-limiting example, the exemplary embodiments of this invention may be implemented by one or more integrated circuits. The memory 120 may be of any type appropriate to the technical environment and may be implemented using any appropriate data storage technology, such as optical memory devices, magnetic memory devices, semiconductor-based memory devices, fixed memory and removable memory, as non-limiting examples. The processor 110 may be of any type appropriate to the technical environment, and may encompass one or more of microprocessors, general purpose computers, special purpose computers and processors based on a multi-core architecture, as non-limiting examples.

Figure 2 illustrates an arrangement wherein data is exchanged between two terminals 210 and 220 in accordance with the present principles. Each of the terminals 210 and 220 include encryptor/decryptor modules 230 and 240,

respectively, and may additionally include each of the other components of system 100 described above, as appropriate. Terminals 210 and 220 are communicatively coupled to each other via communication channel 250, which may be implemented via wired and/or wireless medium. Additionally, arrangement 200 may include a trusted third party 260 communicatively coupled to terminals 210 and 220, wherein third party 260 may in some cases, among other things, generate common parameters and the keys, distribute them to the terminals in a manner known to those skilled in the art. For example, in identity based encryption, the setup algorithm is performed by the trusted third party to generate, among other things, the master secret key.

Following key generation, a message can be encrypted and decrypted by the terminals as described above, and transmitted and received via communication channel 250.

Figure 3 illustrates a generalized flow diagram of an identity-based cryptosystem.

Figures 4 to 6 show exemplary flow charts according to the present principles.

The flow charts illustrate the homomorphic crypto-processes discussed above. The processes of Figures 4 - 6 may be executed by e.g., a processor 110 of Figure 1. The processes may represent, e.g., computer program products having the computer- executable instructions which may be stored in non-transitory computer-readable storage media 120 of Figure 1 as described before.

The foregoing has provided by way of exemplary embodiments and non- limiting examples a description of the method and systems contemplated by the inventor. It is clear that various modifications and adaptations may become apparent to those skilled in the art in view of the description. However, such various modifications and adaptations fall within the scope of the teachings of the various embodiments described above.

The embodiments described herein may be implemented in, for example, a method or a process, an apparatus, a software program, a data stream, or a signal. Even if only discussed in the context of a single form of implementation (for example, discussed only as a method), the implementation of features discussed above may also be implemented in other forms (for example, an apparatus or program). An apparatus may be implemented in, for example, appropriate hardware, software, and firmware. The methods may be implemented in, for example, an apparatus such as, for example, a processor, which refers to processing devices in general, including, for example, a computer, a microprocessor, an integrated circuit, or a programmable logic device. Processors also include communication devices, such as, for example, computers, cell phones, portable/personal digital assistants ("PDAs"), and other devices that facilitate communication of information between end-users.

Reference to "one embodiment" or "an embodiment" or "one implementation" or "an implementation" of the present principles, as well as other variations thereof, mean that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase "in one embodiment" or "in an embodiment" or "in one implementation" or "in an implementation", as well any other variations, appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

Additionally, this application or its claims may refer to "determining" various pieces of information. Determining the information may include one or more of, for example, estimating the information, calculating the information, predicting the information, or retrieving the information from memory.

Further, this application or its claims may refer to "accessing" various pieces of information. Accessing the information may include one or more of, for example, receiving the information, retrieving the information (for example, from memory), storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

Additionally, this application or its claims may refer to "receiving" various pieces of information. Receiving is, as with "accessing", intended to be a broad term. Receiving the information may include one or more of, for example, accessing the information, or retrieving the information (for example, from memory). Further, "receiving" is typically involved, in one way or another, during operations such as, for example, storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

As will be evident to one of skill in the art, implementations may produce a variety of signals formatted to carry information that may be, for example, stored or transmitted. The information may include, for example, instructions for performing a method, or data produced by one of the described embodiments. For example, a signal may be formatted to carry the bitstream of a described embodiment. Such a signal may be formatted, for example, as an electromagnetic wave (for example, using a radio frequency portion of spectrum) or as a baseband signal. The formatting may include, for example, encoding a data stream and modulating a carrier with the encoded data stream. The information that the signal carries may be, for example, analog or digital information. The signal may be transmitted over a variety of different wired and/or wireless links, as is known. The signal may be stored on a processor-readable medium.

While several embodiments have been described and illustrated herein, those of ordinary skill in the art will readily envision a variety of other means and/or structures for performing the functions and/or obtaining the results and/or one or more of the advantages described herein, and each of such variations and/or modifications is deemed to be within the scope of the present embodiments. More generally, those skilled in the art will readily appreciate that all parameters, dimensions, materials, and configurations described herein are meant to be exemplary and that the actual parameters, dimensions, materials, and/or configurations will depend upon the specific application or applications for which the teachings herein is/are used. Those skilled in the art will recognize, or be able to ascertain using no more than routine experimentation, many equivalents to the specific embodiments described herein. It is, therefore, to be understood that the foregoing embodiments are presented by way of example only and that, within the scope of the appended claims and equivalents thereof, the embodiments disclosed may be practiced otherwise than as specifically described and claimed. The present embodiments are directed to each individual feature, system, article, material and/or method described herein. In addition, any combination of two or more such features, systems, articles, materials and/or methods, if such features, systems, articles, materials and/or methods are not mutually inconsistent, is included within the scope of the present embodiments.