# US 2026/0254610 A1 · Method for homomorphically determining the sign of a message by dilation, associated methods and devices

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0254610 A1
- Document ID: US20260254610A1
- Status: Published application
- Kind: A1
- Application number: 18/875,864
- Filed: 2023-06-16
- Published: 2026-08-27
- Earliest claimed: 2022-06-17
- Applicants: Ravel Technologies
- Inventors: Philippe CHARTIER; Michel KOSKAS; Mohammed LEMOU; Florian MEHATS
- Web page: https://patentgrep.com/patent/US20260254610A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- H04L 9/3033: {details relating to pseudo-prime or prime number generation, e.g. primality test}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for homomorphically determining the positive or negative character of a message μ from a corresponding encrypted message c, encrypted by a learning-with-errors type method, the message μ belonging to the discrete torus Tp or to a space in bijection with Tp, with formula (p), the integers pi being mutually prime, the encrypted message c being made up of q components Ci, with formula (c), vi being the Bézout coefficient associated with the integer pi. The method comprises at least one dilation of the encrypted message c in accordance with formula (c[1]), where p is an odd number greater than or equal to 3. The method also includes merging quantities representative of the sign of c and the sign of c[1].

## Claims

### Claim 1

A method for homomorphically determining the positive or negative character of a message μ from a corresponding encrypted message c, without decrypting the encrypted message c, the encrypted message c corresponding to the message μ being encrypted by a learning-with-error type method, the message μ belonging to the discrete torus
T
p
=
1
p
⁢
{
-
p
-
1
2
,
-
p
-
1
2
+
1
,
…
,
p
-
1
2
-
1
,
p
-
1
2
}
or to a space in bijection with Tp, with
p
=
∏
i
=
1
i
=
q
⁢
p
i
,
the integers pi being mutually prime, the encrypted message c being formed of q components ci, with
c
=
∑
i
=
1
i
=
q
⁢
ν
i
⁢
c
i
⁢
mod
⁢
(
1
)
,
vi being the Bézout coefficient associated with the integer pi, defined by ui pi+vi p/pi=1, the method comprising:
a scaling step, comprising determining a dilated encrypted message c[1] in accordance with the following formula
c
[
1
]
=
∑
i
=
1
i
=
q
[
p
_
⁢
v
i
⁢
mod
⁢
(
p
i
)
]
⁢
c
i
⁢
mod
⁢
(
1
)
,
where p is an odd number greater than or equal to 3, and
a merging step, comprising calculating the sum F0(c)+F1(c[1]) where F0 and F1 respectively designate an operation of homomorphically calculating a quantity att[0]·gε, and a quantity att[1]·gε, gε being a staircase function which is zero on a central interval]−ε/2,ε/2[ and which has two distinct values on either side of this central interval, the coefficient att[1] being less than the coefficient att[0].

### Claim 2 (depends on 1)

The method according to claim 1, wherein the scaling step comprises determinations of several dilated encrypted messages c[k], the integer k varying from 1 to K−1, each dilated encrypted message being determined in accordance with the following formula
c
[
k
]
=
∑
i
=
1
i
=
q
[
p
_
k
⁢
v
i
⁢
mod
⁢
(
p
i
)
]
⁢
c
i
⁢
mod
⁢
(
1
)
,
and wherein the positive or negative character of the message μ is determined as a function of c and as a function of the different dilated encrypted messages c[k], k=1 . . . K−1.

### Claim 3 (depends on 2)

The method according to claim 2, wherein the merging step comprises a step of merging a packet during which the following sum is calculated: F0(c)+F1(c[1])+ . . . +Fk(c[k])+ . . . +Fm(c[m]), where Fk designates an operation of homomorphically calculating the quantity att[k]·gε, where att[k] is an attenuation coefficient less than 1, the series of coefficients att[k], k=0 . . . m being decreasing and such that: the sum of the attenuation coefficients, successively to one of the given attenuation coefficients of the series, is less than said given attenuation coefficient.

### Claim 4 (depends on 3)

The method according to claim 3, wherein m is less than K, and wherein the merging step comprises the following steps:
S1: merging by packets, each packet grouping m terms, each merging of a packet corresponding to calculating the intermediate result resi=F0(c[(i-1)·m])+F1(c[(i-1)·m+1])+ . . . +Fk(c[(i-1)·m+k])+ . . . +Fm-1(c[i·m-1]), with i being the packet number
S2: merging by packets of intermediate results resi, each merging of a packet of m′ intermediate results corresponding to calculating a new intermediate result res′j={tilde over (F)}0(resm′·(j-1))+{tilde over (F)}1(resm′·(j-1)+1)+ . . . +{tilde over (F)}k(resm′·(j-1)+k)+ . . . +{tilde over (F)}m′-1(resm′·j-1), with j being the packet number, {tilde over (F)}k designating an operation of homomorphically calculating a quantity att[k]·g{tilde over (ε)},
step S2 being repeated until only a single result is obtained, to which the operation {tilde over (F)}0 is applied, which provides a final result which is an encrypted version of the sign of the message μ.

### Claim 5 (depends on 2)

The method according to claim 2, wherein the number K−1 of dilated encrypted messages taken into account is such that pK-1>p/(p+1).

### Claim 6 (depends on 1)

The method according to claim 1, wherein the width ε of the central interval is less than 1/(2p+1).

### Claim 7 (depends on 1)

A method for homomorphically applying the Heaviside function H, which is zero for negative values and equal to 1 otherwise, the method comprising executing the method for determining the positive or negative character of the message μ according to claim 1, the function gε being selected to be zero for negative values and equal to 1 for positive values.

### Claim 8 (depends on 7)

A method for homomorphically applying a piecewise constant function f to a message μ, the function f having t distinct pieces, the method comprising:
decomposing the function f as a linear combination of translated Heaviside functions, i.e.
f
⁡
(
μ
)
=
∑
j
=
1
j
=
𝔱
⁢
α
j
⁢
H
⁢
(
μ
-
β
j
)
,
where the coefficients αj are integers and the abscissas βj of the discontinuity points belong to the interval [−¼, ¼],
calculating the quantity
∑
j
=
1
j
=
𝔱
⁢
α
j
⁢
H
⁢
(
μ
-
β
j
)
,
each term H(μ−βj) having been homomorphically determined in accordance with the method of claim 7.

### Claim 9 (depends on 7)

A method for homomorphically determining the maximum of two messages μa and μb, from the corresponding encrypted messages ca and cb, without decrypting the encrypted messages ca and cb, the method comprising:
homomorphically determining the quantity H(μa−μb), in accordance with the method for homomorphically applying the Heaviside function H according to claim 7, the encrypted version of H(μa−μb) thus determined being noted h, and calculating the quantity Maxh=h·ca+(1−h)·cb,
or, homomorphically determining the quantity H(μb−μa), in accordance with the method for homomorphically applying the Heaviside function H, the encrypted version of H(μb−μa) thus determined being noted h′, and calculating the quantity h′·cb+(1−h′)·ca.

### Claim 10 (depends on 7)

A method for homomorphically determining the minimum of two messages μa and μb, from the corresponding encrypted messages ca and cb, without decrypting the encrypted messages ca and cb, the method comprising:
homomorphically determining the quantity H(μa−μb), in accordance with the method for homomorphically applying the Heaviside function H according to claim 7, the encrypted version of H(μa−μb) thus determined being noted h, and calculating the quantity Minh=h·cb+(1−h)·ca,
or, homomorphically determining the quantity H(μb−μa), in accordance with the method for homomorphically applying the Heaviside function H, the encrypted version of H(μb−μa) thus determined being noted h′, and calculating the quantity h′·ca+(1−h′)·cb.

### Claim 11 (depends on 9)

A method for sorting a database, the database comprising at least, in a first location of the database, a first encrypted message ca, and in a second location of the database, a second encrypted message cb, the method comprising writing at least once, in the first location, the quantity Maxh, determined in accordance with the method of claim 9.

### Claim 12 (depends on 11)

An encrypted communication and processing method, comprising the following steps of:
encrypting at least one message μ, with a private key s, by a client, in the form of an encrypted message c, by a learning-with-error type method, the message μ belonging to the discrete torus
T
p
=
1
p
⁢
{
-
p
-
1
2
,
-
p
-
1
2
+
1
,
…
,
p
-
1
2
-
1
,
p
-
1
2
}
or to a space in bijection with Tp, with
p
=
∏
i
=
1
i
=
q
⁢
p
i
,
the integers pi being mutually prime, the encrypted message c=(c1, . . . ci, . . . , cq) being formed of q components ci, with
c
=
∑
i
=
1
i
=
q
⁢
ν
i
⁢
c
i
⁢
mod
⁢
(
1
)
,
vi being the Bézout coefficient associated with the integer pi, defined by ui pi+vi p/pi=1,
transmitting the encrypted message c, or an encrypted database containing the encrypted message c, by the client, to a server distinct from the client and not having the private key s, via a communication channel,
homomorphically processing the encrypted message c, or a difference between the encrypted message c and another encrypted message, or the encrypted database containing the encrypted message c, by the server, in accordance with the method according to claim 11,
emitting the result of said homomorphic processing by the server.

### Claim 13 (depends on 1)

A cryptographic processing server comprising at least a communication module and a calculation module:
the communication module being configured to receive, from an entity external to the server, an encrypted message c or an encrypted database containing the encrypted message c, the encrypted message c corresponding to a message μ encrypted by a learning-with-error type method, the message μ belonging to the discrete torus
T
p
=
1
p
⁢
{
-
p
-
1
2
,
-
p
-
1
2
+
1
,
…
,
p
-
1
2
-
1
,
p
-
1
2
}
or to a space in bijection with Tp, with
p
=
∏
i
=
1
i
=
q
⁢
p
i
,
the integers pi being mutually prime, the encrypted message c=(c1, . . . ci, . . . cq) being formed of q components ci, with
c
=
∑
i
=
1
i
=
q
⁢
ν
i
⁢
c
i
⁢
mod
⁢
(
1
)
,
vi being the Bézout coefficient associated with the integer pi, defined by ui pi+vi p/pi=1,
the calculation module being programmed to homomorphically process the encrypted message c, or a difference between the encrypted message c and another encrypted message, or the encrypted database containing the encrypted message c, without decrypting the message c, in accordance with the method according to claim 1,
the communication module being also configured to emit the result of said homomorphic processing.

### Claim 14 (depends on 13)

A cryptographic system (1) comprising:
the cryptographic processing server according to claim 13,
a client, configured to encrypt at least one message μ, in the form of the encrypted message c, and to communicate the encrypted message c, or an encrypted database containing the encrypted message c, to the server via a communication channel.

### Claim 15 (depends on 10)

A method for sorting a database, the database comprising at least, in a first location of the database, a first encrypted message ca, and in a second location of the database, a second encrypted message cb, the method comprising writing at least once, in the first location, the quantity Minh, determined in accordance with the method of claim 10.
