This work continues the search for viable intractability assumptions over infinite groups. In particular, we study the possibility of phrasing random self-reducibility properties for infinite groups in an analogous manner to the case of finite groups with the uniform distribution. As a first step, it is natural to look for distributions which are translation-invariant, i.e., the probability of an event and its translate by a group element are the same (as is the case for the uniform distribution). Indeed, this approach has been considered in cryptographic literature by Lee [18], who introduced the concept of right invariance. However, we argue a number of shortcomings for its applicability to cryptography, showing in particular that any computational problem defined on a right-invariant distribution will not yield a better (weaker) intractability assumption than some problem defined over a finite group with the uniform distribution. Perhaps the problem is simply that translation invariance is too strong of a property to ask of a distribution over an infinite group. Any such distribution is necessarily non-atomic, and the atomic approximations introduced by [18] (universally right invariant distributions) are still insufficient to deliver the desired complexity reductions. However, if a family of distributions is randomizable via translation, this may in fact suffice: one could translate an arbitrary instance by a sample from a known distribution, and obtain a related instance distributed according to a desired base distribution (or something statistically close) - highly analogous to the mode of operation of many random self reductions in cryptography. Using a novel approach based on random walks, we construct families of such distributions, which are translation-randomizable over infinite groups. The main ingredients in our construction are recurrence (meaning a random walk will invariably return to its origin), and shortcut sampling, which asserts the existence of an efficient method for sampling a long (super-polynomial length) walk. Given a suitable group with these properties (ℤ), we demonstrate how one may formulate problems with random self reducibility properties akin to the familiar setting of finite groups and the uniform distribution. © 2013 Springer-Verlag.