257 reputation
16
bio website
location http://www.maths.manchester.ac.uk/~burdges/
age 38
visits member for 2 years, 10 months
seen Mar 4 at 13:40

Jan
17
comment Information leakage from the ecryptfs filesystem
Is the only big difference between eCryptFS and EncFS that EncFS is userspace with all that entails, and requires users reserve another directory elsewhere for the encrypted files?
Dec
24
comment How does one design a traffic analysis resistant protocol?
Agreed, making the server useless was the whole point talking about "mailboxes". I think what I'd be most interested in is any rigorous analysis of what makes a server useless for traffic analysis while still making ordinary usage reasonable.
Dec
23
comment How does one design a traffic analysis resistant protocol?
I'd consider that "traffic analysis" refers to any attempt to discern the traffic pattern, but especially contacts/friends lists. I suppose one should view this on-server traffic analysis as a completely separate problem form internet traffic analysis.
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
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
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 Could one prevent double spending in decentralized digital currencies (like Bitcoin) without all transactions being public?
Agreed, digital currency theory should remain inside crypto.SE.
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.
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.
Nov
26
comment How does the wider cryptographic community view non-abelian group based cryptography?
I'll verify further later but I believe the reference should be this article by Artin as well as its predecessor : onlinelibrary.wiley.com/doi/10.1002/cpa.3160080403/abstract
Nov
26
comment How does the wider cryptographic community view non-abelian group based cryptography?
I'll track one down but it's the fact that all finite simple groups has distinct orders except for B_n(q) and C_n(q) with q odd and n>2, and A_3(2) and A_2(4), amusingly even wikipedia states it sans citation : en.wikipedia.org/wiki/List_of_finite_simple_groups
Nov
25
comment How does the wider cryptographic community view non-abelian group based cryptography?
Interesting thank! I'd naively assume any implementation would use only a bounded fragment of the infinite object for computational reasons, which avoids that side channel attack. You wouldn't be creating a finite group by imposing this bound, but maybe the CFSG still worms it's way into the picture somehow.