# US 11,451,381 B2 · Reaching agreement on a secret value

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

- Number: US 11,451,381 B2
- Document ID: US11451381B2
- Status: Granted
- Kind: B2
- Application number: 16/347,366
- Filed: 2017-10-31
- Published: 2019-11-14
- Granted: 2022-09-20
- Earliest claimed: 2016-11-04
- Assignees: Koninklijke Philips N.V.
- Applicants: Koninklijke Philips N.V.
- Inventors: Ludovicus Marinus Gerardus Maria Tolhuizen; Ronald Rietman; Oscar Garcia Morchon
- Web page: https://patentgrep.com/patent/US11451381B2

## CPC

- H04L 9/0841: {involving Diffie-Hellman or related key agreement protocols}
- H04L 9/0819: {Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) (network architectures or network communication protocols for key distribution in a packet data network H04L63/062)}
- H04L 9/0838: {Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these (network architectures or network communication protocols for key exchange in a packet data network H04L63/061)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A first device and a second device are disclosed for reaching agreement on a secret value. Herein, the second device comprises a receiver configured to receive information indicative of a reconciliation data h from the first device, a processor configured to compute a common secret s based on an integer value b, an equation, and system parameters. The processor is configured to compute b based on a key exchange protocol. The first device has a number a in approximate agreement with the number b. The first device comprises a processor configured to determine a common secret s based on an integer value a an equation, and system parameters, and determine a reconciliation data h. The first device further comprises a transmitter configured to transmit information indicative of the reconciliation data h to the second device.

## Claims

### Claim 1

A second device, for reaching agreement on a secret value with a first device, comprising:
a receiver configured to receive information indicative of a reconciliation data h from the first device, wherein 0≤h<2δ, wherein δ is an integer greater than 1; and
a processor circuit configured to compute a common secret s based on an integer value b and an equation
s
≡
⌊
b
+
c
-
h
⁢
q
2
B
+
δ
-
q
2
B
+
δ
+
1
+
q
2
B
+
1
q
2
B
⌋
⁢
⁢
mod
⁢
⁢
2
B
,
wherein b satisfies 0≤b<q, B is a positive integer, and q is an integer multiple of 2B+δ+1, wherein q, B, δ, and c are system parameters.

### Claim 2 (depends on 1)

The second device of claim 1, wherein the processor circuit is configured to compute b based on a key exchange protocol.

### Claim 3 (depends on 1)

The second device of claim 1, wherein the first device has a number a in approximate agreement with the number b, in the sense that a≡b+e (mod q), wherein e represents a difference between the numbers a and b, wherein
/
e
/
≤
q
2
B
+
1
-
q
2
B
+
δ
+
1
.

### Claim 4 (depends on 1)

The second device of claim 1, wherein q=2m and δ=m−B−1, wherein m is a positive integer.

### Claim 5 (depends on 1)

The second device of claim 1, wherein the processor circuit is configured to compute the value b based on a value β and an equation b≡wβ (mod q), wherein wN≡1 (mod q), wherein N is an integer greater than 1 and is relatively prime to q.

### Claim 6

A system comprising:
a first device, and
a second device;
wherein the first device comprises:
a first processor circuit configured to:
determine a common secret s based on an integer value a and an equation
s
=
⌊
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
q
2
B
⌋
,
wherein a satisfies 0≤a<q, B is a positive integer, q is an integer multiple of 2B+δ+1 wherein δ is an integer greater than 1, wherein q, B, δ, and c are system parameters, and
determine a reconciliation data h based on an equation
h
=
⌊
(
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
)
⁢
⁢
mod
⁡
(
q
2
B
)
q
2
B
+
δ
⌋
;
and
a transmitter configured to transmit information indicative of the reconciliation data h to the second device,
wherein the number a is in approximate agreement with the number b,
wherein a≡b+e (mod q), wherein e represents a difference between the numbers a and b, wherein

e

≤
q
2
B
+
1
-
q
2
B
+
δ
+
1
;
and
wherein the second device comprises:
a receiver configured to receive information indicative of the reconciliation data h from the first device, wherein 0≤h<2δ; and
a second processor circuit configured to compute the common secret s based on an integer value b and an equation
s
≡
⌊
b
+
c
-
h
⁢
q
2
B
+
δ
-
q
2
B
+
δ
+
1
+
q
2
B
+
1
q
2
B
⌋
⁢
⁢
mod
⁢
⁢
2
B
,
wherein b satisfies 0≤b<q.

### Claim 7

A first device for reaching agreement on a secret value with a second device, comprising:
a processor circuit configured to:
determine a common secret s based on an integer value a and an equation
s
=
⌊
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
q
2
B
⌋
,
wherein a satisfies 0≤a<q, B is a positive integer, q is an integer multiple of 2B+δ+1, wherein δ is an integer greater than 1, wherein q, B, δ, and c are system parameters, and
determine a reconciliation data h based on an equation
h
=
⌊
(
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
)
⁢
⁢
mod
⁡
(
q
2
B
)
q
2
B
+
δ
⌋
;
and
a transmitter configured to transmit information indicative of the reconciliation data h to the second device.

### Claim 8 (depends on 7)

The first device of claim 7, wherein the processor circuit is configured to compute a based on a key exchange protocol.

### Claim 9 (depends on 7)

The first device of claim 7, wherein the second device has a number b in approximate agreement with the number a in the sense that a≡b+e (mod q), wherein e represents a difference between the numbers a and b, wherein

e

≤
q
2
B
+
1
-
q
2
B
+
δ
+
1
.

### Claim 10 (depends on 7)

The first device of claim 7, wherein q=2m, wherein m is a positive integer, the common secret s corresponds to B most significant bits of a binary expansion of (a+c) mod 2m, and the reconciliation data h corresponds to next δ bits of the binary expansion.

### Claim 11 (depends on 10)

The first device of claim 10, wherein δ=m−B−1.

### Claim 12 (depends on 7)

The first device of claim 7, wherein at least one of:
c=0 so that the common secret s equals a quotient of a and
(
q
2
B
)
,
rounded downwards to the closest integer;
c
=
q
2
B
+
1
,
so that the common secret s equals a quotient of a and
(
q
2
B
)
,
rounded to the closest integer, wherein rounding is performed upwards in case of a tie; and
c
=
q
2
B
+
1
-
1
,
so that the common secret s equals a quotient of a and
(
q
2
B
)
,
rounded to the closest integer, wherein rounding is performed downwards in case of a tie.

### Claim 13 (depends on 7)

The first device of claim 7, wherein the processor circuit is configured to compute the value a based on a value α and an equation a≡wα (mod q), wherein wN≡1 (mod q), wherein N is an integer greater than 1, wherein N is relatively prime to q.

### Claim 14

A method to be performed by a second device for reaching agreement on a secret value with a first device, the method comprising:
receiving information indicative of a reconciliation data h from the first device, wherein 0≤h<2δ, wherein δ is an integer greater than 1; and
computing a common secret s based on an integer value b and an equation
s
≡
⌊
b
+
c
-
h
⁢
q
2
B
+
δ
-
q
2
B
+
δ
+
1
+
q
2
B
+
1
q
2
B
⌋
⁢
⁢
mod
⁢
⁢
2
B
,
wherein b satisfies 0≤b<q, B is a positive integer, and q is an integer multiple of 2B+δ+1, wherein q, B, δ, and c are system parameters.

### Claim 15

A method to be performed by a first device for reaching agreement on a secret value with a second device, the method comprising:
determining a common secret s based on an integer value a and an equation
s
=
⌊
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
q
2
B
⌋
,
wherein a satisfies 0≤a<q, B is a positive integer, q is an integer multiple of 2B+δ+1, wherein δ is an integer greater than 1, wherein q, B, δ, and c are system parameters;
determining a reconciliation data h based on an equation
h
=
⌊
(
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
)
⁢
⁢
mod
⁡
(
q
2
B
)
q
2
B
+
δ
⌋
;
and
transmitting information indicative of the reconciliation data h to the second device.

### Claim 16

A non-transitory computer-readable medium comprising a program that, when executed by a processing system, causes the processing system to:
receive information indicative of a reconciliation data h, wherein 0≤h<2δ, wherein δ is an integer greater than 1; and
compute a common secret s based on an integer value b and an equation
s
≡
⌊
b
+
c
-
h
⁢
q
2
B
+
δ
-
q
2
B
+
δ
+
1
+
q
2
B
+
1
q
2
B
⌋
⁢
⁢
mod
⁢
⁢
2
B
,
wherein b satisfies 0≤b<q, B is a positive integer, and q is an integer multiple of 2B+δ+1, wherein q, B, δ, and c are system parameters.

### Claim 17

A non-transitory computer-readable medium comprising a program that, when executed by a processing system, causes the processing system to:
determine a common secret s based on an integer value a and an equation
s
=
⌊
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
q
2
B
⌋
,
wherein a satisfies 0≤a<q, B is a positive integer, q is an integer multiple of 2B+δ+1, wherein δ is an integer greater than 1, wherein q, B, δ, and c are system parameters;
determine a reconciliation data h based on an equation
h
=
⌊
(
(
a
+
c
)
⁢
⁢
mod
⁢
⁢
q
)
⁢
⁢
mod
⁡
(
q
2
B
)
q
2
B
+
δ
⌋
;
and
transmit information indicative of the reconciliation data h.