Skip to main content

Questions tagged [arithmetic]

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

Filter by
Sorted by
Tagged with
4 votes
1 answer
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 ...
L0ngx1ng's user avatar
  • 143
0 votes
1 answer
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 ...
Nawras Hussein's user avatar
-2 votes
2 answers
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....
Homer's user avatar
  • 5
1 vote
1 answer
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 ...
Kevin Stefanov's user avatar
3 votes
1 answer
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 ...
Kolja's user avatar
  • 143
1 vote
2 answers
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 ...
MayDen's user avatar
  • 11
1 vote
0 answers
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 ...
DDD's user avatar
  • 95
1 vote
1 answer
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 ...
user97821's user avatar
1 vote
0 answers
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?
Passi's user avatar
  • 11
2 votes
2 answers
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 ...
Guerlando OCs's user avatar
0 votes
0 answers
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 ...
Dew Debra's user avatar
1 vote
0 answers
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 ...
cmu314's user avatar
  • 11
4 votes
1 answer
461 views

Definition of Circuit Satisfiability In The Context of zk-SNARKs

A standard theorem is that boolean circuit satisfiability is NP-complete (shown in CLRS, for example). I am interested in what these statements formally mean. From CLRS, I can cite that $$\text{...
cadaniluk's user avatar
  • 229
6 votes
1 answer
1k views

Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?

With the risen popularity of Zero-Knowledge Proofs of Knowledge (ZKPoKs) such as Pinocchio, Groth16 and Sonic, to name some ZKPoKs that are popularly known as zk-SNARKs, I got engaged to understand ...
Bean Guy's user avatar
  • 752
0 votes
0 answers
106 views

Why does Montgomery Ladder not work for Brainpool curves

According to SafeCurves, the Brainpool curves mentioned there (P256t1 and P384t1) do not support the Montgomery Ladder for scalar multiplication in constant time. I am wondering why this is the case ...
mat's user avatar
  • 2,528
4 votes
1 answer
672 views

Problem about complexity of Chinese remainder theorem

I have a question about CRT. Assuming, that we have this system (S): x=a0 mod n0 x=a1 mod n1 with N=n0*n1 and n0,n1 are two distinct prime numbers. Then the complexity in terms of binary operation is ...
Altario's user avatar
  • 61
0 votes
1 answer
64 views

Does the following equation hold in bilinear pairings?

$e:G_1 \times G_1 \rightarrow G_2$, where $g$ is a generator of $G_1$. $\text{H}: \lbrace 0,1\rbrace ^* \rightarrow G_1$. Is $e(\text{H}(D)g^a,g) == e(\text{H}(D)g,g)^a$ ? where $D$ is a string
Rabindra Moirangthem's user avatar
3 votes
1 answer
311 views

Solving a system of equations using both arithmetic and bitwise operations

At first I asked this question on Stackoverflow, where I was advised to ask here. So there is the question: I have a system of pretty simple equations: $x + y = A$ $f(x,y) + y = B$ $A, B$ are known....
Long Kong 's user avatar
3 votes
1 answer
132 views

Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?

Let $P$ be a prime and $g$ a value between $2$ and $P$. Let $M$ be the set of numbers which can be generated with $g$: $$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$ If $g$ is a prime root of $...
J. Doe's user avatar
  • 453
1 vote
0 answers
75 views

Complexity of arithmetic in (the integer ring of) a number field?

What is the running time complexity (average or worst case) of common arithmetic operations in number fields? In fact, I'm only interested in the integer ring of the quadratic extension $\mathbb{Q}[\...
gen's user avatar
  • 143
7 votes
2 answers
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, ...
kelalaka's user avatar
  • 49.1k
1 vote
1 answer
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 ...
user1990088's user avatar
34 votes
3 answers
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.
Elias's user avatar
  • 4,933
4 votes
3 answers
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 ...
Qqwy's user avatar
  • 91
12 votes
2 answers
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 ...
EPICI's user avatar
  • 359
7 votes
2 answers
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 ...
student's user avatar
  • 83
1 vote
0 answers
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 ...
xtt's user avatar
  • 369
3 votes
1 answer
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. ...
Solvek's user avatar
  • 131
1 vote
1 answer
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 $
manju's user avatar
  • 21
0 votes
1 answer
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$ ...
manju's user avatar
  • 31
-1 votes
1 answer
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$ ...
sadnoe's user avatar
  • 26
5 votes
1 answer
2k views

Purpose of leading zero in PKCS1-v1_5 padding

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 ...
user avatar
1 vote
1 answer
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 ...
Peter Butler's user avatar
3 votes
1 answer
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'...
user1136342's user avatar
1 vote
0 answers
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 ...
Sunia Raharja's user avatar
8 votes
2 answers
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 ...
Smit Johnth's user avatar
  • 1,701
5 votes
1 answer
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 ...
Baertierchen's user avatar
11 votes
5 answers
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 ...
Mok-Kong Shen's user avatar
10 votes
1 answer
25k views

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 ...
BTent's user avatar
  • 103