WO2016048775A1 - Xor-homomorphic cryptosystems with fast key generation - Google Patents

Abstract

The present principles relate to cryptography, and more specifically, to homomorphic public-key encryption systems. 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. The present principles provide practical XOR homomorphic cryptosystems enjoying a fast key generation.

Description

XOR-HOMOMORPHIC CRYPTOSYSTEMS WITH

FAST KEY GENERATION

RELATED APPLICATION

This patent application claims the benefit of U.S. Provisional Application No.

62/055716 filed on September 26, 2014 and U.S. Provisional Application No. 62/098,378 filed on December 31, 2014, with the same title, 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 homomorphic public -key encryption systems. 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. The present principles provide practical XOR homomorphic cryptosystems enjoying a fast key generation.

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.

Public-key encryption

In order to better capture the property that users may share some common parameters in a homogeneous environment, the key generation algorithm is divided in two sub-algorithms: the common-key generation algorithm and the key generation algorithm.

Following the syntax of two articles: 1) Mihir Bellare, Alexandra Boldyreva, Anand Desai, and David Pointcheval. Key-privacy in public -key encryption. In C. Boyd, editor, Advances in Cryptology - ASIACRYPT 2001 , volume 2248 of Lecture Notes in Computer Science, pages 566-582. Springer, 2001, and 2) Shafi Goldwasser and Silvio Micali. Probabilistic encryption. /. Comput. Syst. Sci. , 28(2):270-299, 1984, we define a public-key encryption scheme as a tuple of four algorithms (SETUP, KEYGEN, ENCRYPT, DECRYPT). The generalized flow diagram of the process is illustrated as process 300 in Figure 3. Functions of blocks in Figure 3 are described below.

Common-key generation The common-key generation algorithm SETUP 310 takes on input some security parameter κ and outputs some common parameters

PP t- SETUP(1^K).

Key generation The key generation algorithm KEYGEN 320 is a randomized algorithm that takes on input PP and returns a matching pair of public key and secret

R

key for some user: (upk, usk) <- KEYGEN(PP).

Encryption Let M denote the message space. The encryption algorithm

ENCRYPT 330 is a randomized algorithm that takes on input a public key upk and a plaintext m G M , and returns a ciphertext C. We write C <- ENCRYPT_upk(m).

Decryption The decryption algorithm DECRYPT 340 takes on input secret key usk (matching upk) 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_upk(m)) = m for all messages m G M. The keys generated in process step 320 are provided as necessary for the encryption 330 and decryption 340. The specific processes associated with each of these steps as they relate to the present principles are described in further detail below.

Security notions

The notion of indistinguishability of encryptions (as described in Goldwasser and Micali article) 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. We view an adversary <A as a pair (c Z₁, c Z₂) of probabilistic algorithms. This corresponds to adversary Λ running in two stages. In the "find" stage, algorithm ·Λ₁ takes on input public parameters PP and a public key upk and outputs 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 under upk and where b is chosen at random in {0,1}· The goal of ·Λ₂ is to recover the value of b from s and C.

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

PP <- SETUP(1^K), (upk, usk) <- KEYGEN(PP),

Pr (mo. m-L. s) - c/Zi CPP, upk), : Jl₂ (s, C = b

b <- {0,1}, C <- ENCRYPT_upk(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 KEYGEN and over the random coins of the adversary.

As we are in the public -key setting, the adversary Λ = (<A₁, <A₂) is given the public key upk and so can encrypt any message of its choice. In other words, the adversary can mount chosen-plaintext attacks (CPA). Hence, we write I N D-CPA the security notion achieved by a semantically secure 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

. 7 <- , , ^ _upk

Complexity assumptions

It is useful to introduce some notation. 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(a) . The set of integers whose Jacobi symbol is 1 is denoted by _N, _N = {a G ¾ l/iv (^a) ⁼ 1); the set of quadratic residues is denoted by QM_W , QM_W = {a G ¾ I ^a) = Jq (^a) = 1}· Note that Q _N is a subset of J_N.

Definition 1 (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

R R

Pr [ V(x, N) = l \x ^ QR_N] - 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 QR_N and x G J_N \ QR_N.

As noted before, 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 ^-L) and C₂ = ENCRYPT(m₂) , there exists a non- private operation d such that dC₂ = ENCRYPT ^! * 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 two XOR homomorphic cryptosystems are known to date: the Goldwasser-Micali cryptosystem, (see Goldwasser and Micali article above) and a recent cryptosystem by Clear, Hughes, and Tewari (see 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). Both cryptosystems rely on the quadratic residuosity assumption. The Goldwasser-Micali cryptosystem is practical but incurs an expensive key generation, which is computationally intensive. The cryptosystem by Clear et al. has ciphertexts four times longer than Goldwasser- Micali' s— but can be made only twice longer in the usual public-key setting (as described in the article, the scheme is an identity-based cryptosystem).

In addition, another article in the field is Compression in finite fields and torus-based cryptography. SIAM J. Comput., 37(5): 1401-1428, 2008 by Karl Rubin and Alice Silverberg.

SUMMARY OF THE INVENTION

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

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 public key u pk_j = (ff_j) for user i, where R_t = r_t ² mod N, G (Έ/ΝΈ)^Χ, and N is a composite integer;

generating a ciphertext C = {ε, c], where ε = -l)^mJ_N t) and c = t + ^ mod N, and t G (Z/NZ)^X ; and

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

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 public key u pkj = {ff;} for user i, where ffj = mod N, r_t G (Έ/ΝΈ)^Χ, and N is a composite integer;

an encryptor configured to generate ciphertext C = {ε, c], where ε = -l)^mJ_N t) and c = t + ^ mod N, and t G (Z/NZ)^X ; and

a communication interface, coupled to a communication channel, configured to transmit the ciphertext 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] via the communication channel; and

a processor configured to access the ciphertext C = {ε, c], where _ε = (-l)^mJ_N (t) and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer; and

the processor generates a plaintext message m by accessing a private key uskj = (rj) for user i, where G (Έ/ΝΈ)^Χ and determining τ = J_N(c + 2r ) and

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

receiving the ciphertext C = {ε, c] via the communication channel; and accessing the ciphertext C = {ε, c], where _ε = (-l)^mJ_N (t) and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer; and

generating a plaintext message m by accessing a private key usk_j = {>;} for user i, where r_t G (Έ/ΝΈ)^Χ and determining τ = J_N (c + 2r ) and m =—— .

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

accessing the message m;

accessing a public key u pk_j = (ff_j) for user i, where R_t = r_t ² mod N, Ti G (Έ/ΝΈ)^Χ, and N is a composite integer;

generating a ciphertext C = {ε, c], where ε = (-l)^m and c = t + mod N, and t G (Z/NZ)^X ; and

transmitting the ciphertext 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 comprising computer-executable instructions is presented for:

receiving the ciphertext C = {ε, c] via the communication channel; and accessing the ciphertext C = {ε, c), where _ε = (-l)^mJ_N (t) and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer; and

generating a plaintext message m by accessing a private key usk_j = {>;} for user i, where r_t G (Έ/ΝΈ)^Χ and determining τ = J_N (c + 2r ) and 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 shows an exemplary apparatus according to the present principles;

Figure 2 shows another exemplary apparatus according to the present principles;

Figure 3 shows exemplary system according to the present principles; and

Figures 4 and 5 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

The present principles provide practical XOR homomorphic cryptosystems enjoying a fast key generation. In our case, the key generation involves a mere modular squaring. Moreover, the ciphertext size is the same as in the Goldwasser- Micali cryptosystem. Extra useful properties offered by the proposed cryptosystems include:

• very fast key generation;

• homomorphic property with regards to the XOR operation (or equivalently addition modulo 2);

· almost free encryption of the complementary value;

• strong security guarantees. Main ideas

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

G_p = {x + Sy\x, y E_p and x² -Ay² = 1).

Where it is defined, consider the map

u + δ

ψ W_p→ G_p,u i→

u— δ^' ease the notation, we augment W_p with a special symbol∞ and define ψ ∞ = 1. There are two cases to distinguish:

1. If δ £ W_p then G_p = [ip(u)\u G IF_p U {∞}}—see [4, Section 2];

2. If δ G IFp 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 ^x 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_x,u₂ G T_p. This implies (i½ + δ) (u₂— δ) = (u₂ + δ)(Μ_Χ— δ) and in turn u = u₂. The inverse map is given

δ(ν+1)

by ψ : G_p → Τρ,ν i→

v-1

Furthermore, map ψ yields a homomorphism from T_v to G_p. We have ^(oo) = 1. Let u_Xl u₂ ETp\ {∞}. We have:

and, if u_x≠—u₂,

where 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∞:

!i 0∞ =∞ 0 ii = u for all u G T_p; the inverse of u G T_p \ {∞) is— u:

u © (— u) = (— u) © u given u₁, u₂ G T_p \ {∞), their multiplication is given

oo ot erw se.

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:

( ² = {u ® u\u G T_p}

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

Let u_lt u₂ G T_p. Define w₁ = u₁ ® and w₂ = u₂ © u₂. Then letting u₃ : = u © u₂ we get:

w₃ : = w₁ © w₂

= (ι½ © U-L) © (u₂ © u₂) = (u © u₂) © (U-L © u₂) = u₃ © u₃.

Further, for any 1 < i < 3, if W_j≠ oo then

The previous setting naturally extends through Chinese remaindering. Let N = pq be an RSA (Rivest-Shamir-Adleman) modulus. Then (T_p)² x (T_q)² is a group and has order φ(Ν). Our idea is to see ciphertexts as elements of this group and to exploit the underlying algebraic structure. Note that the application of Eq. (1) requires gcd ( t, N) = gcd ( t² — ff;, N) = 1 , where gcd stands for greatest common divisor.

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. The factorization of N is erased. The public parameters are PP = {N}.

KEYGEN(PP) For user i, key generation algorithm KEYGEN picks at random G (Έ/ΝΈ) ^Χ and sets ff; = r ² mod N. It outputs the public key u pk; = {ff;} and matching private key uskj = {r¾}.

ENCRYPT_upk. (m) To encrypt a message m G {0,1} for user i, ENCRYPT chooses at random t G (Έ/ΝΈ) ^Χ with gcd ( t² — R_t, N) = 1 and computes

Ri

ε = (- l)^m J_N (t) and c = t + - mod N.

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

DECRYPT_usk. (C) From ciphertext C = { , c], DECRYPT first computes τ = J_N (c + 2r_t) using secret key r_t . If τ £ {±1} it returns 1; otherwise it returns plaintext m as

1— ε · τ

m = .

2 An alternative, we see from Eq. (1) that the decryption algorithm can evaluate τ as T = J_N (c - 2η) .

In a practical implementation, for better efficiency, the encryption algorithm can randomly draw t G Έ/ΝΈ. Similarly, the key generation algorithm can randomly draw G Έ/ΝΈ.

Homomorphic property

Let C₁ = (s₁, c₁) and C₂ = (£₂, c₂) be the respective encryption of messages m_x and m₂ under the public key of user i. Then C₃ = (ε₃, c₃) with

£₃ = ₁- ₂-J_N(c₁ + c₂) and

is the encryption of message m₃ = m m₂ (under the public key of user i).

Proof. Using the © operator, observe that 7 = 7 ® 7·

From Eq. (2), we get:

ε₃ - ± 2η) = ε₁·ε₂ ^■ ]_N(c c₂ + R_t ± 2 (¾ +

= ε₁·ε₂ ± 2η) (c₂ ± 2η))

= ε-_ί -JN(CI ± 2η)^■ ε₂ -J_N(c₂ ± 2η)

as desired.

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

Security analysis

Proposition 1. The scheme is IND-CPA under the quadratic residuosity assumption.

Proof. Assume there exists an IND-CPA adversary Λ that can break the scheme with probability e. We will use Λ to decide whether a random element w in _N is a quadratic residue modulo N or not.

Consider the following distinguisher T(w,N) for solving the QR problem:

1. Define ff; = w, set upkj = (ffj), and give (N, upkj) to Λ

Choose a random bit b G {0,1} and compute the encryption of b under public key upkj as C_b = {¾, c_b] where ¾ = (— 1)⁶/J(0 and c_b = t + RJt mod N for some random element t G (Έ/ΝΈ)^Χ with gcd ( t²—

Give C_& = {e_b, c_b) to c Z and obtain its guess

4. li b' = b return 1; otherwise return 0.

There are two cases to consider.

Case 1 Suppose first that w is a quadratic residue modulo N. Clearly, D returns 1 exactly when Λ wins in the IN D-CPA game. We thus have Pr [ D(w, N) l |w G QR_N] = e.

Case 2 Suppose now that w G \ QIR^. We have c_b— t -\- Ri/t mod with R_t = w G J_N \ Q _N. Consider also t₁₍ t₂, t₃ G (Έ/ΝΈ)^Χ such that

t₁ = t (mod p), t₁ = RJt (mod q);

t₂≡ RJt (mod p), t₂≡t (mod q);

t₃≡ RJt (mod p), t₃≡ RJt (mod q).

(Note that the condition gcd ( t² - ffj, N) = 1 implies gcd ( ^² - ffj, N) = gcd ( t₂ ² - R_u N) = gcd ( t₃ ² - R₀ N) = 1.)

In c Z's view, from c_b, the four possible values t, t_{l 5} t₂, and t₃ are equally likely since c_b≡t + Ri/t≡ t_x + Rilt_x≡t₂ + R_t/t₂≡t₃ + R_t/t₃ (mod N). At the same time, since R_t G J_N \ QR_N we also have J_N(t) = J_N(t₃)≠ /«(ίχ) = J_N(t₂). The probability of JL recovers ]_N(t) from c_b is therefore -— note that _b carries no information on J_N(t) since b is random in {0,1}. As a result, D will return 1 with probability

We

which must be negligible by the QR assumption. Hence, the scheme is I N D-CPA secure under the QR assumption.

Second exemplary embodiment

It is easy to see that if C = {ε, c] with ε = (—l)^mJ_N(t) and c = t + R t mod N is the encryption of a message m G {0,1} then so is C: = {ε', c'} where ε' = ε · J_N (— 1) have

_Ε' = (-ΙΓ = (-i)^m;_w(- = ε^■;*(-!)■

One of the two equivalent ciphertexts C = {ε, c] and C = {ε' , c'} is (at least) one bit shorter than the other one. Let £ represent the bit- length of RSA modulus N. This means that one of C or C needs at most £ bits for its representation.

Proof. If c≥ 2^i_1 (i.e., if c is exactly an £-bit integer) then

c' = N - c≤ {2^{ - 1) - 2'-¹ = 2'-¹ - 1 < 2*-

As a result, c or c' is at most an ( — l)-bit integer. The result follows by noting that the Jacobi symbol (1 or—1) can be represented with a single bit (e.g., the sign bit).

Here is an implementation of the resulting cryptosystem.

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

KEYGEN (PP) For user i, key generation algorithm KEYGEN picks at random G Έ/ΝΈ and sets R_t = r_t ² mod N. It outputs the public key upk_j = (ff_j) and matching private key usk_j = ( ).

ENCRYPT_upk. (m) To encrypt a message m G {0,1} for user i, ENCRYPT chooses at random t G Έ/ΝΈ and computes ε = (-l)^mJ_N(t) and δ = ί + mod N.

Define c = min ( c, N— c). If c = c then define ε = έ; otherwise define ε = έ · JN (— 1). The returned ciphertext is C = {ε, c}. DECRYPT_usk. (C) From ciphertext C = { , c}, DECRYPT first computes ^{Τ =} J_N(^C + 2 ) using secret key η. If τ £ {±1} it returns 1; otherwise it returns plaintext m as

Remark that as an alternative, the decryption algorithm can evaluate τ as τ = J_N(c - 2η).

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). The factorization of N is erased. The public parameters are PP = {N}.

KEYGEN(PP) For user i, key generation algorithm KEYGEN picks at random r_t G Έ/ΝΈ and sets R_t = r_t ² mod N. It outputs the public key u pk_j = (ff_j) and matching private key usk_j = ( ).

ENCRYPT_upk. (m) To encrypt a message m G {0,1} for user i, ENCRYPT chooses at random t G Έ/ΝΈ and computes

Ri

ε = (-l)^m;_w(t) and c = t + - mod N.

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

DECRYPT_usk. (C) From ciphertext C = { , c], DECRYPT first computes τ = J_N(c + 2 ) using secret key . If τ £ {±1} it returns 1; otherwise it returns plaintext m as

Remark that as an alternative, the decryption algorithm can evaluate τ as τ = 7«(£ - 2 ). As noted before, there are several advantages for the proposed cryptosystems: very fast key generation;

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 public-key encryption provably secure in the standard model when the homomorphism property with respect to the XOR operation is needed. The homomorphism property is a central ingredient in a number of applications, including, but not limited to, electronic voting, private information retrieval, or secure multiparty computation. In essence, it allows a third party to obtain the decryption of a ciphertext encrypted under some user's public key in a way that this user learns nothing about the corresponding plaintext.

Here is an illustration for an XOR-homomorphic encryption scheme E. Suppose that C is the encryption of some secret bit b under Alice's public key upk^: C = £_Upk_A (b). The goal of Bob is to obtain the value of b.

Bob Alice . Let C = £_upkA (b

. Choose a random bit β £ {0,1}

. Compute C = Cd£_upkA ( )

c

1. Decrypt C and obtain b' = b 0 β b . Recover b as b = b' © β

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 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 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 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) 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.

Figures 4 and 5 show exemplary flow charts according to the present principles. The flow charts illustrate the homomorphic crypto processes discussed above. The processes of Figures 4 and 5 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.

Claims

1. A method for communicating a message m, comprising:

accessing the message m;

accessing a public key upk_j = (ff_j) for user i, where R_t = r_t ² mod N, r_t G

(Έ/ΝΈ)^Χ, and N is a composite integer;

generating a ciphertext C = {ε, c], where

ε = (-l)^m;_w(t) and c = t + ^ mod N, and t G (Έ/ΝΈ ^Χ ; and

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

2. The method of claim 1 , wherein N = pq, and p and q are prime.

3. The method of claim 1 , wherein the message m G {0,1}·

4. The method of claim 1 , further comprising a step of substituting t with - 1, and therefore C = , c} with e = (-l)^mJ_N(-t) and c = -t + mod N.

5. The method of claim 1 , wherein c is instead chosen to be min ( + mod N,—t +

-^ mod jv) = min((t + mod N), N - (t + ^ mod N)) ; and if c = t + ^ mod N, then ε = (-l)^mJ_N (t), otherwise ε = (-l)^m/_w(-t) = (-l)^m/_w(t)

6. The method of claim 5, wherein N is such that J_N(—1 = 1 and ε = (— l)^m J_N(t).

7. The method of claim 6, wherein N = pq and p≡ q (mod 4).

8. An apparatus for communicating a message m, comprising:

a processor configured to access the message m, the processor further configured to accessing a public key u pk_j = (ff_j) for user i, where R_t = r_t ² mod N, r_t G (Έ/ΝΈ)^Χ, and N is a composite integer;

an encryptor configured to generate ciphertext C = {ε, c], where

ε = (-l)^m;_w(t) and c = t + ^ mod N, and t G (Έ/ΝΈ) ; and

a communication interface, coupled to a communication channel, configured to transmit the ciphertext C = {ε, c] via the communication channel.

9. The apparatus of claim 8, wherein N = pq, and p and q are prime.

10. The apparatus of claim 8, wherein the message m G {0,1}·

11. The apparatus of claim 8, wherein t is substituted with - t, and therefore C = {ε, c] with e = (-l)^m;_w(-t) and c = -t + ^ mod N.

12. The apparatus of claim 8, wherein c is instead chosen to be min ( t +— mod N,—t +

then ε = (-l)^m/_w (t); otherwise ε = (-l)^m/_w(-t) = (-l)^m/_w( ^■ /«(-!)·

13. The apparatus of claim 12, wherein N is such that J_N(—1 = 1 and ε = (— l)^m J_N(t).

14. The apparatus of claim 13, wherein N

15. An apparatus for processing a ciphertext, comprising:

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

a processor configured to access the ciphertext C = {ε, c], where

ε = (-l)^mJ_N(t) and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer, and

the processor generates a plaintext message m by accessing a private key uskj =

1— ε·τ

(r_j) for user i, where r_i G (Έ/ΝΈ)^Χ and determining τ = J_N (c + 2r_;) and m =—— .

16. The apparatus of claim 15, wherein N = pq, and p and q are prime.

17. The apparatus of claim 15, wherein the message m G {0,1}·

18. The apparatus of claim 15, wherein t is substituted with - t, and therefore C = {ε, c] with e = (-l)^m -t) and c = -t +—_t mod N.

19. The apparatus of claim 18, wherein c is instead chosen to be

min (t + ^ mod N -t + ^ mod jv) = min((t + γ mod N), N - (t + ^ mod N)), and if c = t + ^ mod N, then ε = (-l ^mJ_N (t , otherwise ε = (-l)^m/_w(-t) =

(-i)^m;_w( · ;«(-!)·

20. The apparatus of claim 19, wherein N is such that J_N(—1 = 1 and ε = (— l)^m J_N(t).

21. The apparatus of claim 20, wherein N = pq and p≡ q (mod 4).

22. The apparatus of claim 15, wherein τ is evaluated as τ = J_N(c— 2r_t) instead.

23. A method for processing a ciphertext, comprising:

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

accessing the ciphertext C = {ε, c], where

ε = (-l)^mJ_N(t) and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer; and

generating a plaintext message m by accessing a private key usk_j = {r for user i, where r_i G (Έ/ΝΈ)^Χ and determining τ = J_N (c + 2r_;) and m =—— .

24. The method of claim 23, wherein τ is evaluated as τ = J_N (c— 2r_t) instead.

25. A computer program product stored in non-transitory computer-readable storage media comprising computer-executable instructions for:

accessing the message m;

accessing a public key upk_j = (ff_j) for user i, where R_t = r_t ² mod N, r_t G

(Έ/ΝΈ)^Χ, and N is a composite integer;

generating a ciphertext C = {ε, c], where

ε = (-l)^m;_w(t) and c = t + ^ mod N, and t G (Έ/ΝΈ ^Χ ; and

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

26. A computer program product stored in non-transitory computer-readable storage media comprising computer-executable instructions for:

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

accessing the ciphertext C = {ε, c], where

ε = (-l)^m and c = t + mod N, and t G (Έ/ΝΈ)^Χ, and N is a composite integer; and

generating a plaintext message m by accessing a private key uskj = {r;} for user i,

1— ε·τ

where r¾ G (Έ/ΝΈ)^Χ and determining τ = J_N (c + 2η) and m = .