Timeline for Efficiently computing the neutral element in a ring isomorphic to Z/NZ?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2014 at 4:35 | history | tweeted | twitter.com/#!/StackCrypto/status/432734423562612736 | ||
| Jan 30, 2014 at 8:58 | vote | accept | Angela | ||
| Jan 29, 2014 at 9:04 | history | edited | Angela | CC BY-SA 3.0 |
deleted 142 characters in body
|
| Jan 29, 2014 at 4:06 | answer | added | D.W. | timeline score: 3 | |
| Jan 29, 2014 at 3:36 | comment | added | D.W. | Oh, also: you're going to need to give us some way to get some element(s) of $S$ to get started, otherwise we have no way to do anything in $S$ (we don't have anything we can apply the $\Delta$ or $*$ operations to). So what can we do? Can we generate a random element of $S$? If yes, are we told what element of $R$ it corresponds to? | |
| Jan 29, 2014 at 3:34 | comment | added | D.W. | Finally, I'll comment that a ring is an algebraic structure that has more than just addition and multiplication as operations. It also has negation (the inverse for addition) and inversion (the inverse for multiplication) maps, i.e., the maps $x \mapsto -x$ and $x \mapsto x^{-1}$. Are we given the ability to apply these maps to elements of $S$ of our choice? The natural answer would be "yes" (but in that case the question becomes trivial). If the answer in your situation is "no", why not? What is the motivation for the question? | |
| Jan 29, 2014 at 3:32 | comment | added | D.W. | Also I think you need to be more careful about how elements of $S$ are represented, and what it means to be given an element of $S$. Presumably what you mean is that there is some way of representing an element of $S$, and when we are given an element of $S$, you mean we are given the corresponding bit string. OK, fine. So, what do we know about the representation? What are we given? Do we know the map from elements of $S$ to bit strings, or the reverse map? I suggest you take more care in your question to distinguish an element from the representation of that element. | |
| Jan 29, 2014 at 3:31 | comment | added | D.W. | Angela, what does it mean to say you are "given the elements of $S$"? There are exponentially many elements of $S$, so we cannot be literally given a list of all elements of $S$ (represented somehow) -- that wouldn't make sense. So what do you mean? P.S. Make sure you edit your question to make it self-contained and comprehensible without reading the comment thread. This is not a discussion forum. We expect you to spend serious effort to craft a well-posed, well-explained problem statement. | |
| Jan 27, 2014 at 9:37 | comment | added | Angela | Ah yes the latter comment is my question exactly - can we really assume that when given the formula for $*$, we can compute the neutral element? I'm having a hard time finding a good example here, but generally isn't it one thing to be able to compute $f(x)$ efficiently and another to solve $f(x)=a$? Like I can easily compute $f(x) = g^x$ in $\mathbb Z/N\mathbb Z$, but solving $g^x = a$ for $x$ is generally hard... | |
| Jan 27, 2014 at 9:27 | history | edited | Angela | CC BY-SA 3.0 |
edited title
|
| Jan 23, 2014 at 17:23 | comment | added | tylo | anyway: In order to get a really useful answer, you might want to edit the topic to reflect your given situation more clearly. You asked for a general ring, and now it is isomorphic to $\mathbb{Z}/N\mathbb{Z}$ (your given example fulfilled this property, but not the original statement). Btw, if you are given the "formula" for $*$, you can just use standard algebra to calculate the neutral element, and you don't need the multiplicative group order at all. | |
| Jan 23, 2014 at 17:11 | comment | added | tylo | That's exactly what he wrote. Factoring with the general number sieve is subexponential, and then it's just a matter of solving BBFP in fields instead of a ring. His statements is: if you can factor, you can break it (deterministic fully homomorphic encryption). He does not look at the case, when you can't factor. | |
| Jan 22, 2014 at 15:16 | comment | added | Angela | Hmm I looked at the paper. But theorem 5 confuses me - isn't he assuming we can factor n? And I don't get the corollary on the top of the next page: He says that if we have a sub-exponential algorithm for solving the problem in fields, we can break any algebraically homomorphic scheme in subexponential time, and he does this by chinese remaindering. But wouldn't factoring be the bottleneck here? The paper he cites only has that runtime for n that have a certain form, not all n... Am I missing something, or does this go wrong when we can't factor n? | |
| Jan 22, 2014 at 8:44 | comment | added | Angela | Even better would be if we could indeed invert the isomorphism :) But I don't want to make any assumptions about the complexity of said isomorphism or $\triangle$ and $*$, except that the latter two are poly-time. But now I will go retrieve Boneh's paper from the printer, maybe that will already solve the issue ;) | |
| Jan 22, 2014 at 8:41 | comment | added | Angela | D.W. - Thank you very much, that paper sounds very promising. I will read it in the course of the day. As to "What's given?": I'm given the elements of $S$, which is isomorphic to $\mathbb Z/ N \mathbb Z$ (so we know $N$), along with the two operations $\triangle$ and $*$ that make the ring structure. We can easily compute the image of $0$, and our goal is to find the image of $1$. I already mentioned the possibility of using the group order if we can factor $N$, but if $N$ is e.g. an RSA-modulus, that doesn't help. I'm looking for a way to do this that doesn't rely on factoring $N$. | |
| Jan 21, 2014 at 23:29 | comment | added | D.W. | Finally, are you familiar with the concept of black-box fields, and Dan Boneh's seminal result on this topic? crypto.stanford.edu/~dabo/pubs/abstracts/bbf.html If I understood your question, I could probably give you a better explanation of exactly how that is relevant; but as it stands, I'll just say that I suspect it to be closely related to what you're asking about. It shows how to invert any field homomorphism in subexponential time. You're asking about a ring homomorphism, which is closely related. | |
| Jan 21, 2014 at 23:27 | comment | added | D.W. | If you can select a random element of $S$, and you can multiply in $S$, then a simple algorithm is: factor $N$, then let $x$ be a random element in $S$, and compute $x^{\varphi(N)}$. This is a subexponential time algorithm to compute the element $1$ in $S$. If this isn't allowed in your model, you need to clarify your model. (If $N=\infty$, your problem is not well-defined. For instance, how were you planning to represent ring elements? It's also unlikely to be relevant to crypto. So I suggest you throw that one out.) | |
| Jan 21, 2014 at 23:24 | comment | added | D.W. | I'm having a hard time understanding the question. What's given? What are you trying to compute? Am I given an integer $N$, and told that there is some ring $S$ that is isomorphic to the ring $\mathbb{Z}/N\mathbb{Z}$, but I'm given no other information about $S$, and my job is to find the image of $1$ in $S$? That is obviously not solvable. Did you mean to supply some additional side information? For instance, do you have some way of representing elements in $S$, and some black box that can perform addition, multiplication, inversion in $S$, and that can apply the isomorphism function? | |
| Jan 21, 2014 at 18:20 | review | Close votes | |||
| Jan 30, 2014 at 10:32 | |||||
| Jan 21, 2014 at 16:22 | history | edited | Angela | CC BY-SA 3.0 |
added 177 characters in body
|
| Jan 21, 2014 at 14:42 | comment | added | tylo | Well, it really depends on your group structures, there is probably no standard way for arbitrary rings. For example, the multiplicative structure in general is not needed to be a group (only a monoid), and neither is it required to be abelian. Additionally, knowledge of the additive order of the group does not automatically help you with the multiplicative order: E.g. $\mathbb{Z}/16\mathbb{Z}$ has multiplicative order 8, while $\mathbb{F}_{2^4}$ has multiplicative order 15 (all elements except $0$ are invertible), while both have 16 elements in the additive structure | |
| Jan 21, 2014 at 14:27 | comment | added | fgrieu♦ | You are of course right about the need for several tries, my mistake, oups! | |
| Jan 21, 2014 at 14:02 | comment | added | Angela | I don't think so - e.g. if $S = \mathbb Z/15\mathbb Z$, we have $|S| = 15$, i.e. $\varphi (|S|) = 8$. But, for example, $5^8 \bmod 15 = 10$. Euler's Theorem only holds for elements coprime to $|S|$, when $S = \mathbb Z/ n \mathbb Z$. As for the "coprime": I see your point. I really don't know how to answer this at the moment, but I will think about it. | |
| Jan 21, 2014 at 11:52 | review | First posts | |||
| Jan 21, 2014 at 12:20 | |||||
| Jan 21, 2014 at 11:33 | history | asked | Angela | CC BY-SA 3.0 |