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
0 votes
0 answers
29 views

Finding square roots in $QR_{n}$ when its order has a small factor

I am stuck at a homework problem to find the square root of a quadratic residue $b$ in $Z_n$ ($n$ is not a prime). Currently, I have figured out that there exists a number $a \in Z_n$ such that $a^2 \...
ark's user avatar
  • 1
2 votes
1 answer
89 views

Properties of Sums of Legendre Symbols

Context An unknown modulus N with 8 unknown prime factors $p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$ a plaintext $m$ is encrypted with the formula $c = 2^m \mod N$ the only things the attacker know are ...
Cukurukuk's user avatar
1 vote
0 answers
19 views

Does exist an Elliptic analogue of Benaloh encryption scheme?

The definition of Benaloh encryption scheme can be found here. Does exist an elliptic analogue of this scheme? I want to use this scheme but the length of the key ...
Galois group's user avatar
1 vote
1 answer
34 views

Hiding and binding property of Goldwasser-Micali like bit commitment scheme

Let $N=pq$ be an RSA modulus, that is, $p$ and $q$ are large, distinct primes. Let $J_{N}=\{y\in\mathbb{Z}^{*}_{N}:(\frac{y}{N})_{J}=1\}$ denote the set of all integers in $\mathbb{Z}^{*}_{N}$ with ...
user1035648's user avatar
2 votes
1 answer
49 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
23 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
84 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
138 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
49 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
  • 383
2 votes
1 answer
112 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
171 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,169
1 vote
1 answer
178 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
139 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
669 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
481 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
475 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
43 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
477 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
212 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
85 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
85 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
7 votes
1 answer
738 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
  • 191
1 vote
1 answer
154 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
57 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
110 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
339 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,243
1 vote
0 answers
173 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
451 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
822 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
226 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
559 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
510 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
186 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
  • 138k
1 vote
2 answers
597 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
290 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
82 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
332 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
  • 805
3 votes
1 answer
182 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
345 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
343 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
74 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
7 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
  • 255
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
294 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,282
4 votes
2 answers
155 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
172 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