D.W.
Reputation
23,898
Top tag
Next privilege 25,000 Rep.
 Feb 6 comment Homomorphic encryption for vector addition @uosɐſ, as you correctly anticipated, the integer arithmetic is going to wrap around eventually: keep incrementing, and eventually you'll get back to zero. This is pretty much inevitable, especially since we're working with modular arithmetic. $p$ is the number where wrap-around happens for the first component. Take $\langle 1,0,0 \rangle$ and keep adding it to itself. You'll get $\langle 2,0,0 \rangle$, $\langle 3,0,0 \rangle$, etc. until $\langle p-1,0,0 \rangle$: then when you add one, it wraps around to $\langle 0,0,0 \rangle$. Similarly, $q,r$ are the modulus for the 2nd/3rd component. Feb 5 comment Practical (and secure) PRGs Good point, @user4982! Thank you -- I have edited my answer accordingly. Feb 4 comment Hill cipher is not perfectly secure @Valtteri, well done! Feb 4 comment Game with symmetric key What do you think? What have you tried? We prefer you to make an effort on your own before asking. This is a nice exercise, but we're not here to solve your exercises for you -- on the other hand, if you have a specific question about a specific aspect of your attempt at a solution, that might be more suitable for this site. Jan 31 comment Addition-only PHE in F# @uosɐſ, that's a different question, so it should be posted separately as a separate question. One question per question, please: this is not a discussion forum, so it's important to keep things focused. I think I might be able to propose some candidate solutions, but I don't want to post it here. Jan 30 comment Efficient Robust Private Set Intersection Questions user11706, The etiquette on this site is to edit the question to include this information into the question. When asked for clarification, don't just add a comment; edit the question to make it self-contained. People shouldn't need to read the comment thread to understand everything needed to understand the question. Looks like figlesquidge has done that for you, but you should do it yourself in the future. Jan 30 comment Efficient Robust Private Set Intersection Questions Section 3.4 of what? Step 7 of what? I have no idea what you are referring to. What have you tried? Do you understand what it means to work in a finite field? I suggest you go back and review the basics, like finite fields and modular arithmetics. Jan 29 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? @Angela, ahh, good question! Probably the answer will depend on the formulas or how they were generated; in some cases, yes, knowing the explicit formulas will allow you to invert them -- but not always. I don't know if it is possible to give a general answer. Jan 29 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 29 comment Predicting Java's PRNG using partial output You say algorithms that involve 30,000 steps are not feasible. Frankly: I'm super-skeptical about that claim. Have you tried implementing such a thing? Such a computation will probably finish in microseconds. I find it hard to imagine that this is too slow. Jan 21 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ? 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 15 comment Oracle DBMS_RANDOM algorithm? What research have you done? There's lots written in textbooks and on the Internet (and on this site) about the criteria for a PRNG to be fit for cryptography. Also, please, one question per question; you've crammed two different questions into one post. Jan 13 comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable? @fgrieu, yup, it doesn't allow you to verify that a LFSR given to you by someone else is maximal-length. However, as I suspect you already know, if you want to generate a LFSR that others can verify is probably maximal-length, you could seed a deterministic PRNG (DRBG) with a "nothing-up-my-sleeve number", and then use the output of that PRNG as the random numbers for my algorithm. That'll allow anyone else to verify that you've generated the LFSR polynomial in a way that you can't easily bias. The security level will depend on the value of $n$. Jan 13 comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable? @fgrieu, OK, those are good points. I've added those to the algorithm. Setting the constant term and requiring an odd number of taps is just an optimization. (If you choose a polynomial that doesn't have the low bit set, then it'll fail the check that its period divides $2^n-1$ and will be rejected in step 3 of my algorithm.) Jan 10 comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable? For instance, the Unix factor commands factors $2^{320}-1$ in 1.5 seconds, yielding the factorization $2^{320}-1 = 3 \times 5 \times 5 \times 11 \times 17 \times 31 \times 41 \times 257 \times 641 \times 61681 \times 65537 \times 414721 \times 3602561 \times 6700417 \times 4278255361 \times 44479210368001 \times 94455684953484563055991838558081$.