Reputation
289
Top tag
Next privilege 300 Rep.
Create new tags
Badges
1 9
Newest
 Curious
Impact
~3k people reached

  • 0 posts edited
  • 0 helpful flags
  • 47 votes cast
Dec
23
comment How does one design a traffic analysis resistant protocol?
I'd implicitly assumed that the IM server cannot be trusted, maybe I should edit the question, but everything you say still applies of course. I suppose you could achieve this extra traffic merely by using Tor hidden services with all nodes configured as Tor relays.
Dec
23
asked How does one design a traffic analysis resistant protocol?
Dec
21
accepted How does the wider cryptographic community view non-abelian group based cryptography?
Dec
21
accepted Is there any serious discussion about using blinding intermediaries in digital currency scenarios?
Dec
21
awarded  Scholar
Dec
21
accepted How close is homomorphic encryption to handling regular expressions?
Dec
21
comment How close is homomorphic encryption to handling regular expressions?
Is homomorphic encryption even the correct term when we aren't talking about the ring structure? It'll work, I suppose.
Dec
21
asked How close is homomorphic encryption to handling regular expressions?
Dec
3
comment How do we find the last two correspondences in an otherwise known even permutation?
You could achieve sublinear space by modifying this algorithm to implement the set as a Bloom filters for the done array, but you must watch that the false positive rate doesn't grow too much, i.e. cycles cannot be too long. en.wikipedia.org/wiki/Bloom_filter
Dec
3
comment Prevent double-spending with decentralized digital currencies without all transactions being public?
Agreed, digital currency theory should remain inside crypto.SE.
Dec
2
awarded  Commentator
Dec
2
comment How do we find the last two correspondences in an otherwise known even permutation?
Yes, you must choose the queries, obviously. Just fyi, online algorithm is the technical term for an algorithm that acts on data arriving in a fixed sequence without any chance for going backwards.
Dec
2
comment How do we find the last two correspondences in an otherwise known even permutation?
Create an object Pmod with two variables a and b such that Pmod(a) = n-1, Pmod(b) = n-2, and Pmod(j) = P(j) otherwise. For i=0..n-3, if done[i]==0 then : Initialize j=i. Loop setting done[j]=1 and j=Pmod(j)$ until done[j]==1. If j==n-1, set a=i. If j==n-2, set b=i. You compute the answer using the final values of a and b.
Dec
2
comment How do we find the last two correspondences in an otherwise known even permutation?
In that case, my second linear time algorithm requires an $n$ bit array plus a few $O(log(n))$ bit counters and integers.
Dec
2
comment How do we find the last two correspondences in an otherwise known even permutation?
If your going for n bits plus O(1), then : Iterate thorough the entries exhausting each elements cycle as far as possible to gradually build out the cycle(s) that end in $n-2$ and $n-1$. You use the n bit array to prevent reprocessing cycles.
Dec
2
comment How do we find the last two correspondences in an otherwise known even permutation?
Inverse : Initialize $inverse[i] = -1$ for $i=1..n$. Set $inverse[P(i)] = i$ for $i=1..n$. If $inverse[n-2] = -1$ or $inverse[n-1] = -1$, then use parity to decide whether it's a fixed point or maps to $n-1$ or $n-2$, respectively.
Dec
2
answered How do we find the last two correspondences in an otherwise known even permutation?
Nov
28
asked Is there any serious discussion about using blinding intermediaries in digital currency scenarios?
Nov
26
comment How does the wider cryptographic community view non-abelian group based cryptography?
There are cases where identifying a hidden subgroup has applications though. These results tell us that non-abelian finite simple groups cannot play the same role as prime numbers in cryptographic applications; hence my motivation for asking this question.
Nov
26
comment How does the wider cryptographic community view non-abelian group based cryptography?
There is an industry of identifying finite groups both simple and non-simple using Monte Carlo methods, called black box group theory. Afaik, non-simple groups are treated using variations on the component analysis techniques from the CFSGs.