# Questions tagged [arithmetic]

Arithmetic is a branch of mathematics usually concerned with the four operations (adding, subtracting, multiplication and division) of positive numbers.

39 questions
Filter by
Sorted by
Tagged with
187 views

### How to prove the conclusion " linear operation $\mathsf{XOR}$ does not affect the division property"?

Division property is proposed as a generalized integral property at Eurocrypt 2015 by Yosuke Todo in his paper Structural evaluation by generalized integral property, And in paper Integral ...
• 143
96 views

### Finite Field Arithmetic _ Montgomery reduction

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that ...
511 views

### How to map elements from subgroup to larger subgroup of its parent group?

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b. pls read carefully- I am looking for a function/formula/algorithm that can be applied on any curve, say for e....
1 vote
194 views

### Special algorithms for edge cases of binary arithmetic?

I have several mathematical operations on binary numbers that are special cases of more general arithmetic operations. I am wondering whether there exist more specialized algorithms purpose-made for ...
253 views

### Reference for basic secret sharing and MPC arithmetic algorithms

I am looking for references for the most basic secret sharing and MPC arithmetic algorithms for generic rings or prime fields. Problem: Suppose there are $m$ parties $P_1, \ldots, P_m$ which wish to ...
• 143
1 vote
491 views

### Stuck on a cryptanalytical research project [closed]

This is not a technical question, but rather it seeks advice on what to do if cryptanalytical research goes wrong. I've discovered a new attack that works great in theory, but in practice, it fails. I ...
• 11
1 vote
80 views

### Different ways to implement NTT in FHE, confusion about CT/GS butterflies

I'm looking at document of SEAL and openFHE, and they both use $\mathrm{NTT}^{\mathrm{CT}, \psi_{rev}}[\text{no to bo}]$ and $\mathrm{INTT}^{\mathrm{GS}, \psi_{rev}}[\text{bo to no}]$, 2 kinds of ...
• 95
1 vote
142 views

### What arithmetic operations are supported from fully homomorphic encryptions(FHE)?

I'm wondered about what arithmetic operations are supported from FHE. I want to know for 2nd Gen(BGV,BFV), 3rd GEN(GSW,CGGI), 4th GEN(CKKS)! Is 3rd can support more than and/or/not? I heard it is for ...
1 vote
75 views

### Why can't rsa come out with the same cipher?

When $x < N$, there cannot be the same encrypted message with different outgoing messages. But why?
• 11
443 views

### Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?

According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only ...
70 views

### How to get a common coordinate from two different coordinates on Elliptic Curves? [duplicate]

I am trying to write a SageMath script that multiplies two coordinates on Elliptic Curves into one common coordinate. SageMath Elliptic curves over finite fields ...
1 vote
152 views

### MPC arithmetic circuit file and benchmark

For doing MPC over Boolean circuits (typically XOR, AND, INV gates over field of size 2), Boolean circuit files can be found online for a range of interesting functions (e.g. AES, SHA-256). These ...
• 11
461 views

• 143
3k views

### How to avoid side channel attacks when handling large numbers?

For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, ...
• 49.1k
1 vote
101 views

### How to handle points in extended finite field

Following the response to my previous question, I would like to know if you could give me some information or give me a link on how to perform arithmetic operations once I changed a point from the ...
• 165
6k views

### What is bignum-free RSA?

I recently saw a claim that BearSSL has a bignum-free implementation of RSA. What does this mean? I don't see how one could implement RSA without bignum arithmetic.
• 4,933
348 views

### Is there a way of encryption that allows to check what encrypted values are close to their mean?

I am looking for a way to allow parties to publicize encrypted values that can only be decrypted by one or a select few other parties, but that allow everyone to check how close they are to the mean ...
• 91
842 views

### Why is multiplication uncommon in cryptographic primitives?

Modern computers (which crypto programs are usually run on) have a 64-bit multiply, and it only takes one cycle. It's pretty decent mixing at next to no cost. For block ciphers: Multiplication by ...
• 359
1k views

### Endomorphism ring of a Elliptic Curve and $j$ invariant

I am reading Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i). I am trying to understand page 238 (second paragraph) of the proof: if the ...
• 83
1 vote
296 views

### How to implement division using Garbled Circuit

Implementing Addition, Subtraction and even N-bit Multiplication can be done fairly quickly and intuitively using garbled circuit, since no looping, control unit nor state machine is needed. One just ...
• 369
1k views

### Finding sum of two encrypted numbers

Let's consider such process: Two emitents emit two (integer) secret numbers independently They encrypt (encode) these number in such a way that no-one (except emitent) can decode these numbers. ...
• 131
1 vote
400 views

### Bilinear pairing arithmetic

Is this $e(g^x,g^yH^z) = e(g^x,g^y)e(g^x,H^z)$ expression is true? where $g$ is the generator and $H \in G$
• 21
351 views

### How to compute accumulated values in bilinear map accumulators

How to compute $g^{1/(e_1+s)}$, where $g$ is the generator of group $\mathbb G$, and $e_1$ and $s$ are keys? I know only $s$ and $g^{e_1}$, not $e_1$. $\mathbb G$ has prime order for some prime $p$ ...
• 31
94 views

### $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$?

Is there any function $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$ that is invertible? By invertible, I mean it given $y \in \mathbb{Z}^\times_n$, it should be easy to find $x \in \mathbb{Z}_n$ ...
• 26
2k views

According to this document the padded message has the following structure: $EM \;= \; 0x00 \; || \; 0x02 \; || \; PS \; || \; 0x00 \; || \; M$ What is the purpose of this null byte at the beginning ...
1 vote
1k views

### ECC Point Multiplication of Product

I can calculate $Q = a\,b\,G$ in several ways: $Q = a \, (b \, G)$ or $Q = b \, (a \, G)$. These give the same result, as expected. But if I do $c = (a \, b) \bmod n$ where $a \, b$ is much greater ...
960 views

### Chosen ciphertext insecurity in an ElGamal variant

I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'...
• 459
1 vote
389 views

### computing inverses in truncated polynomial rings manually for NTRU encryption [duplicate]

Can someone explain how to find inverses in truncated polynomial rings manually (i.e. on pen and paper)? As an example from the tutorial: Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The ...
3k views

### Timing attack on modular exponentiation

It is known that computing $a^x \bmod N$ takes $O(|x| + \mathrm{pop}(x))$ multiplications modulo $N$, where $|x|$ is the number of bits of $x$ and $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming ...
• 1,701
13k views

### Simple example for CP-ABE (Ciphertext policy attribute-based encryption)

I'm currently working on Ciphertext Policy Attribute-Based Encryption (CP-ABE). So far I'm only using it with a basic understanding how it actually works. Now I want to understand it a bit better, but ...
3k views

### How to best obtain bit sequences from throwing normal dice?

Throwing normal dice, one can get sequences of digits in [0,5]. In practice, which is the best procedure to transform such sequences into a desired number of bit ...
• 1,312
### What exactly is addition modulo $2^{32}$ in cryptography?
EDIT: I've been confusing this the whole time. What I've been wanting to say this whole time is addition modulo $2^{32}$ not addition modulo 32 as the question originally said. Thanks for pointing ...