RELATED APPLICATION

This patent application claims the benefit of U.S. Provisional Application No. 62/055,733 filed on September 26, 2014, titled "Computing over Cocks ciphertexts," and the disclosure of which is incorporated by reference herein in its entirety.

Field of the Invention

The present principles relate to cryptography, and more specifically, to a cryptosystem directed to an identity-based encryption (IBE) scheme described by Clifford Cocks in his article "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. 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.

Cocks ' scheme

The first efficient identity-based encryption scheme that does not rely on pairings over elliptic curves is due to Cocks (in his article mentioned above). It works in standard Rivest- Shamir-Adleman (RSA) groups and its security relies on the quadratic residuosity (QR) assumption (in the random oracle model).

Generally, identity-based encryption can be used in any application requiring encryption. Compared to (regular) public-key encryption, it has the advantage of greatly simplifying the key management. A typical application is email encryption for confidentiality — the email address can serve as the public key (identity). Another application of identity-based encryption is that it provides means to decrypt in the future (or in a given time period). The advantage of Cocks over other identity-based encryption schemes is that its security relies on standard assumption (in this case, the quadratic residuosity).

For a positive integer N, we let J _N (d) denote the Jacobi symbol modulo N of an integer a and _N denote the subset of elements in (Έ/ΝΈ) ^Χ whose Jacobi symbol is +1, wherein TL/NTL is the ring of integers modulo N and (Έ/ΝΈ) ^Χ denotes its multiplicative group. Specifically, TL/NTL ={0,1,2,..., N-l} and (Έ/ΝΈ) ^Χ = {x in TL/NTL such that gcd(x,N) = 1}. For example,

- if N=6 then Έ/ΝΈ = {0,1,2,3,4,5} and (Z/NZ) ^X ={1,5);

- if N=7 then Έ/ΝΈ = {0,1,2,3,4,5,6} and (Z/NZ) ^X ={1,2,3,4,5,6}.

We use Q _W to denote the set of quadratic residues in JJ _W . The quadratic residuosity assumption says that, for some security parameter κ, the distribution of PQR(K) =

{(N, V) I (p, q) RSAgen (κ),Ν *- pq,V Q _W ) and of P _NQR (κ = {(N V)\(p, q

R R

<- RSAgen ( κ), N <- pq, V <- _N \ Q _W ) are computationally indistinguishable, where RSAgen is a probabilistic polynomial-time algorithm that generates two equal-size primes p

R

and q, and "<-" indicates a probabilistic process.

The (generalized) Cocks' scheme proceeds as follows. The generalized flow diagram of the process is illustrated as process 300 in Figure 3.

SETUP(1 ^K ) Given a security parameter κ, SETUP 310 generates an RSA modulus N = pq where p and q are prime. It also selects an element u G _N \ QM _W . The system parameters are mpk = {N,u,J } where Ή is a cryptographic hash function mapping bit- strings to _N . The master secret key is msk = (p, q}.

EXTRACT _msk (id) Using hash function H, EXTRACT 320 first sets R = Ή (id). If R G Q _W it computes r = R ¹ ^ ² mod N; otherwise it computes r = (uR) ¹ ^ ² mod N. EXTRACT returns user's private key d _id = (r). ENCRYPT(id, m) To encrypt a message m G {0,1} for user with identity id,

ENCRYPT 330 chooses at random t,i G TL/NTL such that J _N (t) = J _N (t) = (-l) ^m . It then computes R _ uR

c = t Λ— mod N and c = t + ^- mod N

t t

where R = Ή (id). The returned ciphertext is C = {c, c}.

DECRYPT _d . _d (C) From d _id = {r} and C = {c, c), if r ² ≡ Ή (id) (mod N),

DECRYPT 340 sets γ = c; otherwise it sets γ = c. Plaintext m is then recovered as

l - y + 2r)

m = .

2

Note that the above description generalizes the original scheme. In the article, Cocks considers Blum integers; namely, RSA moduli N = pq with p, q≡ 3 (mod 4). Doing so, it follows that J _p (—1) = J _q (—1) =—1 and therefore— 1 G _N \ Q _W . The original scheme corresponds to the case u =— 1.

In addition, other prior publications in the field include: 1) 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; and 2) Kun Peng, Colin Boyd, and Ed Dawson. A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption. In J. Zhou et al., editors, Information Security (ISC 2005), volume 3650 of Lecture Notes in Computer Science, pages 374-388. Springer, 2005.

SUMMARY OF THE INVENTION

The present invention recognizes the need to improve the existing systems and methods for implementing crytosystems, especially homomorphic crytosystems systems.

In accordance with an aspect of the present invention, a method for generating a ciphertext is presented, comprising:

providing a procedure HOM(x ₁ , x ₂ , Γ) comprising:

selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = t D + (t ² + T) U mod N, wherein

D = + 4Γ mod N and U = x ₁ + x ₂ mod N; outputting HOM(x ₁ , x ₂ , Γ) = '— mod N ;

Θ

for a ciphertext C ₁ = {c ₁₍ that is an encryption of a messages m ₁ for an identity id ; and

generating a third ciphertext C ₃ = {c ₃ , c ₃ ] based on an additional ciphertext C ₂ = {c ₂ , c ₂ } which is an encryption of a message m ₂ for the identity id, where c ₃ = HOM ( c ₁ , c ₂ , Ή. (id)) and c ₃ = HOM ( c ₁₍ c ₂ , uJf (id)), wherein C ₃ is an encryption of m ₃ = m ₁ © m ₂ for the identity id and system parameters m pk = {N, u, J ] where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of _N .

In accordance with another aspect of the present invention, an apparatus is presented, comprising:

an interface configured to receive a ciphertext C ₁ = {c _lt wherein C ₁ is an encryption of a message m ₁ for an identity id ; and

a processor configured to compute a procedure HOM(¾, ¾, Γ) for the ciphertext C ₁ = {c^ c^, wherein the procedure ΗΟΜ(χ ₁₍ x ₂ , Γ) is defined as:

selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = t D + (t ² + T) U mod N, wherein

D = x x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

. . , , . _π (t ² +r)D+4rtU .

outputting ΗΟΜ(χ ₁₍ x ₂ , Γ) = — mod N ;

Θ

wherein the processor is further configured to generate a third ciphertext C ₃ = {c ₃ , c ₃ ] based on an additional ciphertext C ₂ = {c ₂ , c ₂ ] which is an encryption of a message m ₂ for the identity id , where c ₃ = HOM ( c ₁₍ c ₂ , Ή (id)) and c ₃ = HOM ( c ₁ , c ₂ , uJ (id)), and wherein C ₃ is an encryption of m ₃ = 7η _χ φ m ₂ for the identity id and system parameters mpk = {N, u, Ή } where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit- strings to elements of _N .

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

providing a procedure ΗΟΜ(χ ₁₍ x ₂ , Γ) comprising: selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = t D + (t ² + T)U mod N, wherein

D = x x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

„„,., _ (t ² +r)D+4rtu ,

outputting HOM(x ₁ ,x ₂ , Γ) = '— mod N ;

Θ

for a ciphertext C ₁ = {c ₁₍ that is an encryption of a messages m ₁ for an identity id; and

generating a third ciphertext C ₃ = {c ₃ , c ₃ ] based on an additional ciphertext C ₂ = {c ₂ ,c ₂ ] which is an encryption of message m ₂ for the identity id, where c ₃ = HOM (ci,c _2< H (id)) and c ₃ = HOM (c ₁ ,c ₂ ,uJ-C (id)), wherein C ₃ is an encryption of m ₃ =m ₁ ^m ₂ for the identity id and system parameters mpk =

{N, u, J ] where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of _N .

In accordance with an aspect of the present invention, a method for decrypting a ciphertext is presented, comprising:

accessing the ciphertext and a private key, the ciphertext including a first portion c ₃ and a second portion c ₃ , wherein c ₃ = HOM (q, c ₂ ,J (\d)) and c ₃ = HOM (c ₁₍ c ₂ ,uK" (id)) for two ciphertexts C ₁ = {c ₁ ,c ₁ } and C ₂ = {c ₂ ,c ₂ } that are respective encryption of two messages m ₁ and m ₂ for a same identity id, and wherein the procedure HOM(¾, x ₂ , Γ) is defined as:

selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = tD + (t ² + T)U mod N, wherein

D = x x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

„„,., _ (t ² +r)D+4rtu ,

outputting HOM(x ₁ ,x ₂ , Γ) = '— mod N ;

Θ

wherein system parameters mpk = {N,u,J } where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of J _N ; and

decrypting the ciphertext responsive to the private key to obtain a corresponding decrypted message m ₃ , wherein the decrypted message m ₃ = 7η _χ φ m ₂ . In accordance with another aspect of the present invention, an apparatus for processing a ciphertext is presented, comprising:

a communication interface configured to receive the ciphertext, the ciphertext including a first portion c ₃ and a second portion c ₃ , wherein c ₃ = HOM (c ₁ ,c ₂ , H (id)) and c ₃ = HOM (c ₁₍ c ₂ ,WK (id)) for two ciphertexts

C ₁ = {c _lt C-L) and C ₂ = {c ₂ , c ₂ ] that are respective encryption of two messages m ₁ and m ₂ for a same identity id, and wherein the procedure ΗΟΜ(χ ₁₍ x ₂ , Γ) is defined as:

selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = tD + (t ² + T)U mod N, wherein

D = x _x x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

„„,., _ (t ² +r)D+4rtU ,

outputting HOM(x ₁ ,x ₂ , Γ) = '— mod N ;

Θ

wherein system parameters mpk = {N,u,J } where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of J _N ; and

a processor configured to decrypt the ciphertext in responsive to a private key to obtain a corresponding decrypted message m ₃ , wherein the decrypted message m ₃ =m ₁ 0m ₂ .

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

accessing the ciphertext and a private key, the ciphertext including a first portion c ₃ and a second portion c ₃ , wherein c ₃ = HOM (q, c ₂ ,J (\d)) and c ₃ = HOM (c ₁₍ c ₂ ,uK" (id)) for two ciphertexts C ₁ = {c^c-^ and C ₂ = {c ₂ ,c ₂ } that are respective encryption of two messages m ₁ and m ₂ for a same identity id, and wherein the procedure HOM(¾, x ₂ , Γ) is defined as:

selecting t G Έ/ΝΈ such that J _N (9) = 1 where

Θ = t D + (t ² + T)U mod N, wherein

D = x x ₂ + 4Γ mod N and U = x +x mod N;

outputting ΗΟΜ(χ ₁₍ x ₂ , Γ) = ( ^t2+r ^ ^+4rw _{mod N} .

wherein system parameters mpk = {N,u,J } where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of ] _N ; and

decrypting the ciphertext responsive to the private key to obtain a corresponding decrypted message m ₃ , wherein the decrypted message 7713 = 77^ © m ₂ .

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:

Figure 1 illustrates a block diagram of an exemplary system in which various aspects of the exemplary embodiments of the present principles may be implemented.

Figure 2 illustrates an arrangement wherein data is exchanged between two terminals, according to an embodiment of the present principles.

Figure 3 illustrates the generalized Cocks' scheme.

Figure 4 illustrates an exemplary apparatus for performing a HOM procedure, which may compute over Cocks ciphertexts, according to an embodiment of the present principles.

Figure 5 illustrates an exemplary apparatus for performing homomorphic encryption, according to an embodiment of the present principles.

Figure 6 illustrates an exemplary process for performing homomorphic encryption, according to an embodiment of the present principles.

Figure 7 illustrates an exemplary process for performing homomorphic decryption, according to an embodiment of the present principles.

The examples set out herein are not to be construed as limiting the scope of the claims in any manner.

DETAILED DESCRIPTION

Companion public-key system

1 Cocks' IBE scheme can be turned into a public-key cryptosystem by seeing the identity— or more precisely, the hashed value thereof: R = Ή (id)— as the public key. Since the encryption key is made public in public -key cryptosystems (and so need not to be extracted from an identity), one can choose R as a quadratic residue modulo N. This reduces the size of ciphertexts by a factor of 2. On the downside, the so-obtained system is no longer identity-based.

In more detail, we have the following public-key cryptosystem.

SETUP(1 ^K ) Given a security parameter κ, SETUP generates an RSA modulus N = pq where p and q are prime. Modulus N is shared among users and serves as a common reference string. The factorization of N is erased. The public parameters are PP = {N}.

KEYGEN(PP) Key generation algorithm KEYGEN picks at random r G Έ/ΝΈ and sets ff = r ² mod N. It outputs the public key upk = {R} and matching private key usk = {r}.

ENCRYPT _upk (m) To encrypt a message m G {0,1}, ENCRYPT chooses at random t G Έ/ΝΈ such that J _N t) = (-l) ^m and computes

R

c = t +— mod N.

t

The returned ciphertext is c.

DECRYPT _usk (C) From ciphertext C = {c}, DECRYPT recovers plaintext m as

l - J _N (c + 2r)

m = .

2

Technical problems to solve

Homomorphic encryption is a form of encryption which allows one 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 ₁ dC ₂ = ENCRYPT^ _! * m ₂ ) for some specific operation *. Examples of known operations * include the modular addition and the modular multiplication. Cocks' scheme is seemingly non-homomorphic (see e.g., article Homomorphic encryption with access policies: Characterization and new constructions by Michael Clear, Arthur Hughes, and Hitesh Tewari mentioned above). Given two Cocks ciphertexts, it is unknown whether or not it is possible to compute over them. This application answers this question in the affirmative and proposes a constructive method for computing the Cocks encryption of m ₃ : = φ m ₂ from the Cocks encryption of a message m ₁ and of a message m ₂ . The same method readily applies to Cocks' companion public-key cryptosystem.

We use the previous notation. Let m ₁ , m ₂ G {0,1} be two plaintext messages and let C ₁₍ C ₂ denote the corresponding ciphertexts. Specifically, for some random integers t _\ , t _\ , t ₂ , t ₂ satisfying

and t ₂ ) = ;«(¾) = (-1)

R uR R c ₁ = t ₁ -\— mod N , c ₁ = t ₁ + -^— mod N , c ₂ = t ₂ Λ— mod N , ti ti ^2

uR

c ₂ = t ₂ +— mod N

^2

with /? = Jf(id).

In one embodiment, a HOM procedure is provided to allow for computing over Cocks ciphertexts.

HOM procedure

Consider the following procedure HOM, illustrated in block diagram form in Figure 4. It takes on input two elements x ₁ , x ₂ G Έ/ΝΈ and an element Γ G _N , and outputs an element z G Έ/ΝΈ. We write z = HOM ( x , x ₂ , Γ).

1: procedure HOM(x ₁ ,x ₂ , 0

2: Define D = x ₁ x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

3: Select t G TLjNTL such that ] _Ν (Θ) = 1 where

Θ = tD + (t ² + Γ)ϋ mod N ;

4 Evaluate

(t ² + T)D + 4rti/

z = mod N;

0

5 Return z.

6: end procedure

Note that when JN(U = ] _Ν χ + x ₂ = 1, we can take t = 0 (in Procedure HOM, Line 3). This yields Θ = TU mod N (G J _N ) and in turn z = D/U mod N.

Let m ₃ = m ₁ © m ₂ . We now show that if we define C ₃ = {c ₃ , c ₃ ] where

c ₃ = HOM(c ₁ ,c ₂ ,i?) and c ₃ = HOM (q,c ₂ ,¾fi) then C ₃ is the encryption of m ₃ .

Proof. Suppose first that R G Q _W . Then, letting r = R ¹ ^ ² mod N, we have:

J _N (c ₃ + 2r) =J _N (e)J _N (c ₃ + 2r) =J _N ((t ² + R)D + 4RtU + 2r(tD + (t ² + R)U)) = J _N ((t ² +R + 2rt)D + {2rt + t ² + R)(2rU)) = J _N ((t + r) ² (D + 2rU))

= ] _N {D + 2rU) = ] _N {{ _Cl c ₂ + 4ff) + 2r c + c ₂ ))

= J _N (c ₁ + 2r)J _N (c ₂ + 2r)

as desired.

The case R G _N \ Q _W is similar. Letting r = (ui?) ¹ / ² mod N, we then have J _N (c ₃ + 2r) =J _N (c ₁ + 2r)] _N {c ₂ + 2r).

In the following, we describe several exemplary embodiments for performing homomorphic encryption.

First Exemplary embodiment

The first embodiment, illustrated in Figure 5, is concerned with the generalized Cocks' scheme with system parameters mpk = {N,u,J } where N = pq is an RSA modulus, u is a quadratic non-residue in ] _N , and Ή is a hash function mapping bit-strings to ] _N . Let two ciphertexts C ₁ = {c ₁₍ and C ₂ = {c ₂ , c ₂ ] that are the respective encryption of two messages m ₁ and m ₂ for a same identity, say id. Then two applications of the HOM procedure, 510 and 520, defined as

1 : procedure ΗΟΜ(χ _{1 (} Χ2 _< O

2: Define D = x ₁ x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N;

3: Select t G TL/NTL such that ] _Ν (Θ) = 1 where

Θ = t D + (t ² + T U mod N ;

4: Evaluate

(t ² + T)D + rtU

z = mod N ;

Θ

5: Return z.

6: end procedure yields a ciphertext C ₃ = {c ₃ , c ₃ ] where

c ₃ = HOM ( c , c ₂ , Ή (id)) and c ₃ = HOM ( c _lt c ₂ , uHQd)) which is the encryption of m ₃ = m-L © m ₂ for identity id.

Second exemplary embodiment

The second embodiment is a specialization of the first embodiment to the original Cocks' scheme; namely with system parameters msk = {N, J } where N = pq with p, q≡ 3 (mod 4) and u =—1. Given two ciphertexts C ₁ = {c _lt and C ₂ = {c ₂ , c ₂ ] that are the respective encryption of two messages m ₁ and m ₂ for a same identity id, we have C ₃ = [c ₃ , c ₃ ] where

c ₃ = HOM ( c ₁ , c ₂ , J (\d)) and c ₃ = HOM { c _x , c ₂ , -Ή (id)) which is the encryption of m ₃ = m _x ® m ₂ for identity id. Procedure HOM is the same as the one described in the first embodiment.

Third exemplary embodiment

The third embodiment is an adaptation of the HOM procedure that tests whether JN (U) = 1, in which case the value t = 0 is selected. 1 : procedure HOM(x ₁ , x ₂ , 0

2: Define D = x ₁ x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod

3: If JN (U) = 1 then set z = ^ mod N and go to Step 6;

4: Otherwise select t G Z/NZ such that ] _Ν (β~) = 1 where

0 = t D + t ² + T U mod N ;

5 : Evaluate

(t ² + T)D + 4rtU

z = mod N ;

6: Return z.

7: end procedure

Fourth exemplary embodiment

The fourth exemplary embodiment is to use one of the methods of the first, second, or third exemplary embodiments to randomize a Cocks ciphertext C ₁ = {c _lt of a plaintext message m ₁ G {0,1} by taking the encryption of m ₂ = 0 for ciphertext C ₂ = {c ₂ , c ₂ }.

Fifth exemplary embodiment

The fifth exemplary embodiment is to use one of the methods of the first, second, or third exemplary embodiments to flip the value of a plaintext message m ₁ G {0,1} corresponding to a given Cocks ciphertext C ₁ = {c _lt c _x } by taking the encryption of m ₂ = 1 for ciphertext C ₂ = {c ₂ , c ₂ }.

Procedure HOM is the only known method to compute over Cocks ciphertexts. It efficiently solves an open problem.

The HOM procedure allows for new applications for Cocks' scheme that were previously not possible. Specifically, it can now be used in applications where computing over ciphertexts is required. Typical applications include electronic voting, private information retrieval, or secure multi-party computation. Of particular interest is the sealed- bid auction system described in the article, A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption, mentioned above. Also see the article, Homomorphic encryption with access policies: Characterization and new constructions. Figure 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 circuitries 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 non-volatile 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 encryption key. 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, certify the public keys generated, and/or generate common keys in a manner known to those skilled in the art. 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 the (generalized) Cocks' scheme.

Figures 4 and 5 show exemplary apparatus according to the present principles.

Figures 6 and 7 show exemplary flow charts according to the present principles. The flow charts illustrate the homomorphic crypto-processes discussed above. The processes of Figures 6 and 7 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 e.g., non-transitory computer-readable storage media 120 of Figure 1 as described before.

Specifically, Figure 6 illustrates an exemplary process for performing homomorphic encryption, according to an embodiment of the present principles. At step 610, it provides a procedure ΗΟΜ(χ ₁₍ x ₂ , Γ) comprising:

selecting t £ Έ/ΝΈ such that J _N (9) = 1 where

Θ = t D + (t ² + T) U mod N, wherein

D = x x ₂ + 4Γ mod N and U = x ₁ + x ₂ mod N; t ² +r)D +4rtU

outputting ΗΟΜ(χ ₁₍ x ₂ , Γ) = mod N ;

Θ

for a ciphertext C = {c , that is an encryption of a messages m _x for an identity id. At step 620, it generates a third ciphertext C ₃ = {c ₃ , c ₃ ] based on an additional ciphertext C ₂ = {c ₂ , c ₂ } which is an encryption of a message m ₂ for the identity id, where c ₃ = HOM ( c ₁ , c ₂ , J (\d)) and c ₃ = HOM ( c ₁₍ c ₂ , uJ (\d)), wherein C ₃ is an encryption of ^m 3 ^{= m} i Θ ^m 2 f° ^{r me} identity id and system parameters mpk = {N, u, J } where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit- strings to elements of _N . Figure 7 illustrates an exemplary process for performing homomorphic decryption, according to an embodiment of the present principles. At step 710, it accesses the ciphertext and a private key, the ciphertext including a first portion c ₃ and a second portion c ₃ , wherein c ₃ = HOM ( c ₁ , c ₂ , J-C( d and c ₃ = HOM ( c ₁ , c ₂ , uJ-C (id)) for two ciphertexts C _x = {c ₁₍ and C ₂ = {c ₂ , c ₂ ] that are respective encryption of two messages m ₁ and m ₂ for a same identity id, and wherein the procedure HOM(¾, x ₂ , Γ) is defined as:

wherein system parameters mpk = {N, u, K] where N is a composite integer, u is a quadratic non-residue in _N , and Ή is a hash function mapping bit-strings to elements of _N . At step 720, it decrypts the ciphertext responsive to the private key to obtain a corresponding decrypted message m ₃ , wherein the decrypted message m ₃ = m _x ® m ₂ .

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.