Questions tagged [quadratic-residuosity]
A residue of order 2. A number $a$ for which the congruence $x^2 ≡ a \pmod m$ has a solution is called a quadratic residue modulo $m$.
48
questions
2
votes
1
answer
46
views
exponent bit-length for hard DL (128-bit security)
Following up on my previous post, I thought I might get a more concrete answer if I gave a more concrete question.
I require 128-bit security so I choose a 3072-bit RSA modulus ($\ell_n=3072$). ...
1
vote
0
answers
18
views
Honest verifier zero knowledge property for this protocol
This is zero-knowledge proof that show x is not a quadratic residue.
I am trying to verify Honest verifier zero knowledge property.
My steps were these:
Let S be a simulator that does not know how to ...
- 173
2
votes
1
answer
79
views
Hardness of DL in group of Quadratic Residues (product of safe primes)
A protocol I am working with requires $\ell_n$-bit RSA modulus and $\ell_\Lambda$ such that computing $\ell_\Lambda$-bit discrete logs is hard in $QR_n$ (technically $n$ is $\ell_n+2$ bits in the ...
0
votes
1
answer
81
views
Take n = 4633 and B = {−1, 2, 3}. Note the b-smooth numbers as {67, 68, 69}. Find the factor of n
This question is from Quadratic Sieve Factorization Method. Didn't find the solution on the web also. And not aware of how to solve such questions.
- 1
0
votes
1
answer
41
views
QR-PKE not CCA secure
Due to a comment stating "... QR-PKE is secure (CPA)..." I've been thinking of how to prove that it's not CCA secure, and would like to understand whether my proof is correct.
Here's the QR-...
- 373
2
votes
1
answer
84
views
Can functional encryption encrypt and decrypt negative integers?
I want to use DCR-based functional encryption for encryption and decryption purpose. However, I'm unsure whether DCR-based functional encryption can support negative integers.
Is there any ...
- 21
3
votes
1
answer
142
views
Quadratic Sieve: Sieving with prime powers
I am trying to understand the Quadratic Sieve algorithm.
Currently I am stuck at the sieving part.
Let's say the number to be factored is 9788111. I decide to look for 50-smooth factors.
My initial ...
- 2,290
1
vote
1
answer
138
views
How to prove correct decryption in Goldwasser-Micali cryptosystem
In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext ...
- 11
3
votes
2
answers
132
views
How the coin flipping protocol prevent Alice from generating $ n $ from many primes?
This is a question from reading the paper 'Coin Flipping by Telephone - a protocol for solving impossible problems'.
The fact that the coin is unbiased is based on the fact that if n is a product of ...
- 131
1
vote
2
answers
595
views
Adversary for attack on one variant of ElGamal
I came by the following question:
Consider the following variant of ElGamal encryption. Let $p= 2q+ 1$,
let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of
$Z_p^*$ of order $q$, and ...
- 41
1
vote
2
answers
375
views
ZKP for product of two primes
I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper.
The proof is a 2 round where the verifier asks the prover to extract square roots of ...
- 209
1
vote
1
answer
385
views
How do Quadratic Residues work and how do they relate to Diffie Hellman?
Can someone explain Quadratic residues to me in english? I keep reading forums with all the math symbols and it's hard to follow. And how are they incorporated in Diffie-Hellman? Is there a difference ...
- 13
1
vote
1
answer
40
views
Is there a quick method of listing certain elements of a cyclic group?
I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc.
"List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$
Okay, ...
- 13
1
vote
1
answer
444
views
Is it possible to perfom quadratic residues attack on elgamal cryptosystem?
I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.
- 13
1
vote
0
answers
31
views
Help with next step in the Quadratic Sieve
So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here:
Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
- 111
1
vote
2
answers
209
views
Identify the cryptosystem where $\ m = c^2 \bmod n$?
I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n $. It's exact opposite of Rabin's, where's the same formula is used for encryption.
What is the name of this ...
- 25
0
votes
0
answers
82
views
Given a deterministic oracle that calculates square roots modulo n, factor n
When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
0
votes
1
answer
82
views
Question on the Quadratic Residuosity Assumption
I am reading the Handbook of Applied Cryptography and on page 99 the authors write
, after showing that $QRP \le_P FACTORING$:
It is believed that the $QRP$ is as difficult as the problem of ...
- 617
6
votes
1
answer
608
views
What makes the quadratic residuosity problem hard?
The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$.
This problem's believed to be hard to solve in general (e.g. an efficient ...
- 181
1
vote
1
answer
152
views
Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG
In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ ...
0
votes
1
answer
56
views
Difficulty understanding 'random square root' in enhancement to fiat-shamir
This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically ...
4
votes
0
answers
108
views
About Cocks IBE
Why doesn't Cocks IBE use the hash function H from ID space to quadratic residue set $\mathbb{QR}_N$ in $\mathbb{Z}/N\mathbb{Z}$ to reduce the ciphertext expansion by half?
I think it is also IND-ID-...
- 101
3
votes
1
answer
318
views
Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime
I need some orientation to solve the following problem:
Let $p = 2q+1$ be a safe prime and $s(x)$ the smallest of the two square roots of $x$ modulo $p$. Then:
Determine the distribution of $s(g^{ab}...
- 1,233
1
vote
0
answers
171
views
Cryptographic Counter
Good morning,
I state that I am not an expert in cryptography.
I'm studying the feasibility of a project which looks like requires a kind of cryptographic counter that behave similarly to the one in ...
- 11
0
votes
0
answers
424
views
Compact encoding of an elliptic curve point
I'm working on a project with elliptic curve cryptography (ECC), I'm using the secp256k1 library (the one that's used in bitcoin).
My goal is to create the most compact platform-independent ...
- 339
3
votes
1
answer
72
views
Is a composition of computational hardness problems still hard?
It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard?
Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ ...
- 31
2
votes
1
answer
790
views
why doesn't quadratic residue attack work with Elgamal encryption with decisional diffie Hellman assumption?
I was reading this notes http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf
It's given that discrete log assumption is not enough for semantic security, I'm assuming there maybe chance of ...
- 123
3
votes
1
answer
221
views
Why work in a subgroup for Naor and Pinkas oblivious transfer?
In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
- 1,365
3
votes
1
answer
527
views
Quadratic residue zero knowledge proof - simulator with identical distribution
I am looking at the zero knowledge proof for quadratic residues and am confused when it comes to showing a simulator that can give a transcript of the proof with the same distribution as the proof ...
- 225
-1
votes
1
answer
475
views
Elliptic Curve Cryptography calculation of $y^2 \equiv x^3 + x + 1 \pmod{23}$
Learning the basics of elliptic curve cryptography. The question is a mathematical one.
While finding the points in the elliptic group $E_{23}(1,1)$,this is how one proceeds :
How is $y^2= 7$ ...
- 3
1
vote
0
answers
182
views
Issue Factorization Quadratic Sieve
Good evening,
I'm about to write my own quadratic sieve implementation in C using GMP library for large numbers. I'm facing an issue while attempting to do the last factorization step for the number: ...
- 11
12
votes
3
answers
2k
views
In the Quadratic Sieve, why restrict the factor base?
In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...
- 134k
1
vote
2
answers
579
views
Get $a$ such that quadratic residue has a solution (Rabin)
My task is to implement Rabin signature. I have trouble with choosing padding a such that
$$x^2 \equiv a \pmod n$$
has a solution.
In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are ...
- 121
-2
votes
1
answer
267
views
Decrypting an RSA message given $a^2 \equiv 1 \pmod n$
I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated.
Suppose that the ...
- 1
1
vote
0
answers
80
views
Using quadratic residue to learn the sign of a field element
Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to ...
- 101
0
votes
1
answer
312
views
Working on subgroup of $\mathbb{Z}^*_p$ in practice
It is said that, given a group $\mathbb{Z}^*_p$, we can always have a subgroup whose order is prime. To this end, for a safe prime $p=2q+1$, compute $x_i^2 \bmod p$ for all $x_i \in \mathbb{Z}^*_p$.
...
- 785
3
votes
1
answer
181
views
How to prove the hardness of Rabin's function?
I am unable to prove the following theorem:
If for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$ one could find a square root of $q$, then one could factor $n$ in random polynomial ...
- 31
3
votes
1
answer
143
views
For which RSA moduli, precisely, is $e=d$ for all $e$?
This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$
Reading the linked ...
- 31
1
vote
1
answer
341
views
Cocks IBE Scheme: why is -a a quadratic residue mod n?
In the Cocks IBE scheme it is required for the hash function, that the Jacobi symbol of its output and the universally available moduls $n = p*q$ is $+1$, so:
$\Big(\frac{H(ID)}{n}\Big) = \Big(\frac{...
- 13
3
votes
2
answers
331
views
Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently
I have to randomly generate a number $u$ such that $u \in J(N)-Q(N)$
where $J(N)$ denotes the set of elements less than $N$, whose Jacobi symbol value is equal to 1; and $Q(N)$ denotes the set of ...
- 499
5
votes
0
answers
70
views
What is the restriction on $k$, for the $k$th composite residuosity problem to be hard?
The paper “Residuosity Problem and Its Applications to Cryptography” considers the exponent to be an odd integer.
When $k = 2$, it is called the quadratic residuosity problem (mod $n$, where $n$ is ...
- 51
6
votes
4
answers
2k
views
Algorithm for computing square roots in $GF(2^n)$
Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?
- 245
4
votes
2
answers
449
views
Exactly two of the four roots must be greater than N/2
Theorem: Let $y$ be a quadratic residue in $\mathbb{Z}_N$* where $N=pq$.
There are exactly four integers $x_1, x_2, x_3, x_4$ where $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$ ...
- 163
2
votes
1
answer
283
views
Computational Diffie-Hellman problem over the group of quadratic residues
Suppose that $N=pq$ where $p$ and $q$ are safe primes. $\mathbb{QR}_N$ is the group of quadratic residues which is a cyclic group with order $\frac{\phi(N)}{4}$. Let $g$ be the generator of $\mathbb{...
- 1,272
4
votes
2
answers
148
views
What does it mean that $BW_N$ is a permutation over the squares mod N?
Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am ...
- 265
3
votes
2
answers
168
views
Possible to check if $a \in \mathrm{QR}_n$?
It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.
$n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the ...
- 579
1
vote
1
answer
166
views
Are those two distributions indistinguishable?
The Decision composite residuosity problem problem states that is impossible to distinguish between those two ensembles:
$\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r \in \mathbb{Z^*_{N{^...
- 6,092
8
votes
3
answers
2k
views
Quadratic residuosity problem reduction to integer factorization
How can one show how to reduce the quadratic residuosity problem to an integer factorization?
- 445