As of May 31, 2023, we have updated our Code of Conduct.

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$.

Filter by
Sorted by
Tagged with
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$). ...
gormatron3000's user avatar
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 ...
tonythestark's user avatar
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 ...
gormatron3000's user avatar
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.
alu vaja's user avatar
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-...
Anon's user avatar
  • 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 ...
Angelina's user avatar
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 ...
user93353's user avatar
  • 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 ...
Neil's user avatar
  • 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 ...
Andrew Au's user avatar
  • 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 ...
mike's user avatar
  • 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 ...
yacovm's user avatar
  • 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 ...
soccervvy123's user avatar
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, ...
Tho Mas's user avatar
  • 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.
drtak93's user avatar
  • 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𝑛√))...
aayush Lak's user avatar
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 ...
Georg D's user avatar
  • 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 ...
intingfeeder's user avatar
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 ...
3nondatur's user avatar
  • 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 ...
ais523's user avatar
  • 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$ ...
Antonio Frighetto's user avatar
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 ...
Mike Gallagher's user avatar
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-...
Xiaopeng Zhao's user avatar
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}...
user1868607's user avatar
  • 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 ...
azuresky's user avatar
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 ...
valdo's user avatar
  • 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$ ...
Colin Lee's user avatar
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 ...
user41965's user avatar
  • 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$, $...
lamba's user avatar
  • 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 ...
TheFooBarWay's user avatar
-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$ ...
m s's user avatar
  • 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: ...
Amadeus's user avatar
  • 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 ...
fgrieu's user avatar
  • 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 ...
t4u's user avatar
  • 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 ...
Steve's user avatar
  • 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 ...
RevFlash's user avatar
  • 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$. ...
user13676's user avatar
  • 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 ...
Aditi Rai's user avatar
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 ...
helloworld's user avatar
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{...
neuteich's user avatar
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 ...
hanugm's user avatar
  • 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 ...
Misty's user avatar
  • 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}$?
Arthur B's user avatar
  • 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$ ...
habillqabill's user avatar
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{...
T.B's user avatar
  • 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 ...
Charlie Parker's user avatar
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 ...
user4811's user avatar
  • 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{^...
curious's user avatar
  • 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?
Faith's user avatar
  • 445