# US 12,003,633 B2 · Techniques, devices, and instruction set architecture for balanced and secure ladder computations

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

- Number: US 12,003,633 B2
- Document ID: US12003633B2
- Status: Granted
- Kind: B2
- Application number: 17/707,605
- Filed: 2022-03-29
- Published: 2023-09-07
- Granted: 2024-06-04
- Earliest claimed: 2022-01-28
- Assignees: NVIDIA Corporation
- Applicants: NVIDIA Corporation
- Inventors: Shuai Wang; Chen Yao; Xiao Wu; Rongzhe Zhu; Yuji Qian; Kun Yang; Weiping Pan; Xixi Xie
- Web page: https://patentgrep.com/patent/US12003633B2

## CPC

- H04L 9/003: {for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]}
- H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)}
- G06F 21/554: {involving event detection and direct action}
- G06F 2221/034: Test or assess a computer or a system
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed are apparatuses, systems, and techniques to perform and facilitate secure ladder computational operations whose iterative execution depends on secret values associated with input data. Disclosed embodiments balance execution of various iterations in a way that is balanced for different secret values, significantly reducing vulnerability of ladder computations to adversarial side-channel attacks.

## Claims

### Claim 1

A method to perform a ladder computation using a first number and a second number, the method comprising:
storing a seed number in a first memory location (ML), the first ML identified by a pointer stored in a first register;
storing the first number in a second ML, the second ML identified by a pointer stored in a second register;
performing a plurality of iterations, wherein each of the plurality of iterations comprises:
identifying a respective bit of a plurality of bits of the second number;
executing a conditional operation, wherein the conditional operation comprises:
responsive to identifying that the respective bit of the plurality of bits of the second number has a defined relationship to a reference bit, swapping the pointer stored in the first register and the pointer stored in the second register;
performing a first computational operation on at least one of a first operand identified by the pointer stored in the first register or a second operand identified by the pointer stored in the second register; and
determining an output of the ladder computation based on the performed plurality of iterations.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first computational operation comprises one of:
squaring the first operand or doubling the first operand; and
wherein each of the plurality of iterations further comprises:
performing a second computational operation, wherein the second computational operation comprises one of:
multiplication of the first operand and the second operand or addition of the first operand and the second operand.

### Claim 3 (depends on 2)

The method of claim 2, wherein each of the plurality of iterations further comprises:
storing the output of the first computational operation in an ML identified by the pointer stored in the first register; and
storing the output of the second computational operation in an ML identified by the pointer stored in the second register.

### Claim 4 (depends on 2)

The method of claim 2, wherein the first computational operation and the second computational operation are modular computational operations.

### Claim 5 (depends on 1)

The method of claim 1, wherein determining the output of the ladder computation comprises:
responsive to identifying that a final bit of the plurality of bits of the second number has a first bit value, retrieving the output of the ladder computation from an ML identified by the pointer stored in the first register.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the output of the ladder computation comprises:
responsive to identifying that a final bit of the plurality of bits of the second number does not have a first bit value, retrieving the output of the ladder computation from an ML identified by the pointer stored in the second register.

### Claim 7 (depends on 1)

The method of claim 1, wherein the reference bit has a value that is equal to:
a first bit value, for a first iteration of the plurality of iterations, and
a value of bit of the plurality of bits of the second number that is adjacent to the respective bit, for each subsequent iteration of the plurality of iterations.

### Claim 8 (depends on 1)

The method of claim 1, wherein the ladder computation comprises a Montgomery ladder computation of at least one of: an exponentiation of the first number to a power of the second number or a multiplication product of the first number and the second number.

### Claim 9 (depends on 1)

The method of claim 1, wherein the conditional operation further comprises:
responsive to identifying that the respective bit of the plurality of bits of the second number does not have the defined relationship to the reference bit, swapping a pointer stored in a third register and a pointer stored in a fourth register.

### Claim 10 (depends on 9)

The method of claim 9, wherein the pointer stored in the third register and the pointer stored in the fourth register are dummy pointers, and wherein a hamming distance between the pointer stored in the first register and the pointer stored in the second register is equal to a hamming distance between the pointer stored in the third register and the pointer stored in the fourth register.

### Claim 11

A processor comprising:
a memory device;
a plurality of registers; and
one or more circuits, communicatively coupled to the memory device, to:
store a seed number in a first memory location (ML) of the memory device, the first ML identified by a pointer stored in a first register of the plurality of registers;
store a first number in a second ML, the second ML identified by a pointer stored in a second register of the plurality of registers; and
perform a plurality of iterations, wherein for each of the plurality of iterations the one or more circuits are to:
identify a respective bit of a plurality of bits of a second number;
execute a conditional operation, wherein the conditional operation comprises:
responsive to identifying that the respective bit of the plurality of bits of the second number has a defined relationship to a reference bit, swapping the pointer stored in the first register and the pointer stored in the second register;
perform a first computational operation on at least one of a first operand identify the pointer stored in the first register or a second operand identified by the pointer stored in the second register; and
determine an output of a ladder computation based on the performed plurality of iterations.

### Claim 12 (depends on 11)

The processor of claim 11, wherein to perform the first computational operation, the one or more circuits are to:
square the first operand or double the first operand; and
wherein during each of the plurality of iterations the one or more circuits are further to:
perform a second computational operation, wherein the second computational operation comprises one of:
multiplication of the first operand and the second operand or addition of the first operand and the second operand.

### Claim 13 (depends on 12)

The processor of claim 12, wherein the ladder computation comprises a Montgomery ladder computation of at least one of an exponentiation of the first number to a power of the second number or a multiplication product of the first number and the second number, and wherein the first computational operation and the second computational operation are modular computational operations.

### Claim 14 (depends on 12)

The processor of claim 12, wherein during each of the plurality of iterations the one or more circuits are further to:
store the output of the first computational operation in an ML identified by the pointer stored in the first register; and
store the output of the second computational operation in an ML identified by the pointer stored in the second register.

### Claim 15 (depends on 11)

The processor of claim 11, wherein to determine the output of the ladder computation the one or more circuits are to:
responsive to identifying that a final bit of the plurality of bits of the second number has a first bit value, retrieve the output of the ladder computation from an ML identified by the pointer stored in the first register.

### Claim 16 (depends on 11)

The processor of claim 11, wherein to determine the output of the ladder computation the one or more circuits are to:
responsive to identifying that a final bit of the plurality of bits of the second number does not have a first bit value, retrieve the output of the ladder computation from an ML identified by the pointer stored in the second register.

### Claim 17 (depends on 11)

The processor of claim 11, wherein the reference bit has a value that is equal to:
a first bit value, for a first iteration of the plurality of iterations, and
a value of bit of the plurality of bits of the second number that is adjacent to the respective bit, for each subsequent iteration of the plurality of iterations.

### Claim 18 (depends on 11)

The processor of claim 11, wherein to perform the conditional operation, the one or more circuits are further to:
responsive to identifying that the respective bit of the plurality of bits of the second number does not have the defined relationship to the reference bit, swap a dummy pointer stored in a third register of the plurality of registers and a pointer stored in a fourth register of the plurality of registers.

### Claim 19

An accelerator circuit comprising:
a first register to store a first pointer to a first memory location (ML), wherein the first ML stores a seed number;
a second register to store a second pointer to a second ML, wherein the second ML stores a first number;
a third register to store a first dummy pointer;
a fourth register to store a second dummy pointer;
a decode unit to:
receive an instruction to perform, via a plurality of iterations, a ladder computation using the first number and a second number, wherein during each iteration of the plurality of iterations the instruction is to cause the decode unit to:
identify a respective bit of a plurality of bits of the second number;
perform a swapping operation comprising one of:
responsive to the respective bit having a defined relationship to a reference bit, swapping a pointer stored in the first register with a pointer stored in the second register; or
responsive to the respective bit not having the defined relationship to the reference bit, swapping a pointer stored in the third register with a pointer stored in the fourth register;
identifying a first operand using a pointer currently stored in the first register; and
identifying a second operand using a pointer currently stored in the second register; and
an execution unit, wherein during each iteration of the plurality of iterations, the execution unit is to:
perform a first computational operation on at least the first operand or the second operand; and
generate an output of the ladder computation using the performed plurality of iterations.

### Claim 20 (depends on 19)

The accelerator circuit of claim 19, wherein to perform the first computational operation the execution unit is to:
square the first operand or double the first operand; and
wherein during each of the plurality of iterations the execution unit is further to:
perform a second computational operation, wherein to perform the second computational operation the execution unit is to:
multiply the first operand and the second operand or add the first operand to the second operand.

### Claim 21 (depends on 20)

The accelerator circuit of claim 20, wherein during each of the plurality of iterations the execution unit if further to:
store the output of the first computational operation in an ML identified by the pointer currently stored in the first register; and
store the output of the second computational operation in an ML identified by the pointer currently stored in the second register.

### Claim 22 (depends on 19)

The accelerator circuit of claim 19, wherein to determine the output of the ladder computation, the execution unit is to:
responsive to identifying that a final bit of the plurality of bits of the second number has a first bit value, retrieve the output of the ladder computation from an ML identified by the pointer currently stored in the first register; or
responsive to identifying that the final bit of the plurality of bits of the second number does not have a first bit value, retrieve the output of the ladder computation from an ML identified by the pointer currently stored in the second register.