Score:1

Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption?

ng flag

We have DCRA and ECSQRT assumptions.

  1. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all points P ∈ E(Z/nZ) such that 2P = Q.
  2. DCRA : DCR: Decisional Composite Residuosity problem Definition: Given a composite n and an integer z, decide if z is a n-residue modulo n² or not, namely if there exists y such that z = $y^n(mod n^²)$.

It is known that the Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption are related to factoring problem. I need to know if there is a method or a mathematical theorems that can provide ways to map from DCRA to ECSQRT and if the mapping between the two assumptions is possible.

Geoffroy Couteau avatar
cn flag
Can you formally state what the ECSQRT assumption is?
enimert avatar
ng flag
Thank you. The question is edited.
poncho avatar
my flag
I had thought that ECSQRT (more commonly known as "point halving") was an easy problem. Is $n$ a composite, that is, are you actually trying to perform the operation on a pseudocurve (which isn't actually a group)?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.