*21:17* [Pub][ePrint]
New Transference Theorems on Lattices Possessing n^\\epsilon-unique Shortest Vectors, by Wei Wei and Chengliang Tian and Xiaoyun Wang
We prove three optimal transference theorems on lattices possessing $n^{\\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length ofgenerating vectors respectively. The theorems result in reductions

between GapSVP$_{\\gamma\'}$ and GapSIVP$_\\gamma$ for this class of

lattices. Furthermore, we prove a new transference theorem giving an

optimal lower bound relating the successive minima of a lattice with

its dual. As an application, we compare the respective advantages of

current upper bounds on the smoothing parameter of discrete Gaussian

measures over lattices and show a more appropriate bound for lattices whose duals possess $\\sqrt{n}$-unique shortest vectors.

*21:17* [Pub][ePrint]
Two grumpy giants and a baby, by Daniel J. Bernstein and Tanja Lange
Pollard\'s rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups.This paper presents two reasons that Pollard\'s rho algorithm

is farther from optimality than generally believed.

First, ``higher-degree local anti-collisions\'\'

make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic.

Second, even a truly random walk is suboptimal,

because it suffers from ``global anti-collisions\'\' that can at least partially be avoided.

For example, after (1.5+o(1))\\sqrt(l) additions in a group of order l (without fast negation),

the baby-step-giant-step method has probability 0.5625+o(1)

of finding a uniform random discrete logarithm;

a truly random walk would have probability 0.6753\\ldots+o(1);

and this paper\'s new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).

*21:17* [Pub][ePrint]
Broadcast-enhanced Key Predistribution Schemes, by Michelle Kendall and Keith M. Martin and Siaw-Lynn Ng and Maura B. Paterson and Douglas R. Stinson
We present a formalisation of a category of schemes which we call \\emph{Broadcast-enhanced Key Predistribution Schemes}.These schemes can be used instead of a key predistribution scheme in any network which has access to a trusted base station and broadcast channel.

In such networks, broadcast-enhanced key predistribution schemes can provide advantages over key predistribution schemes including flexibility and more efficient revocation.

There are many possible applications and ways to implement broadcast-enhanced key predistribution schemes, and we propose a framework for describing, comparing and analysing them.

In their paper `From key predistribution to key redistribution\', Cicho\\\'{n}, Go{\\l}\\c{e}biewski and Kuty{\\l}owski propose a scheme for `redistributing\' keys to a wireless sensor network using a broadcast channel after an initial key predistribution.

We classify this as a broadcast-enhanced key predistribution scheme and analyse it in that context.

We provide simpler proofs of some results from their paper, give a precise analysis of the resilience of their scheme, and discuss modifications based on defining a suitable keyring intersection threshold.

In the latter half of the paper we suggest two particular scenarios where broadcast-enhanced key predistribution schemes may be particularly desirable and the relevant design goals to prioritise in each case.

For each scenario we propose a suitable family of broadcast-enhanced key predistribution schemes and our analysis demonstrates their effectiveness in achieving their aims in resource-constrained networks.

*21:17* [Pub][ePrint]
Tamper and Leakage Resilience in the Split-State Model, by Feng-Hao Liu and Anna Lysyanskaya
It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered \\emph{algorithmic} defenses from such attacks. In this paper, we show how to algorithmically secure any cryptographic functionality from continual split-state leakage and tampering attacks. A split-state attack on cryptographic hardware is one that targets separate parts of the hardware separately. Our construction does not require the hardware to have access to randomness. In contrast, prior work on protecting from continual combined leakage and tampering required true randomness for each update. Our construction is in the common reference string (CRS) model; the CRS must be hard-wired into the device. We note that prior negative results show that it is impossible to algorithmically secure a cryptographic functionality against a combination of arbitrary continual leakage and tampering attacks without true randomness; therefore restricting our attention to the split-state model is justified.

Our construction is simple and modular, and relies on a new construction, in the CRS model, of non-malleable codes with respect to split-state tampering functions, which may be of independent interest.

*21:17* [Pub][ePrint]
Anonymous Credentials Light , by Foteini Baldimtsi and Anna Lysyanskaya
We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement ofanonymous credentials. Our new notion in contrast is a convenient building block for anonymous

credential systems. The construction we propose is efficient: it requires just a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard. Thus, for

the ﬁrst time, we give a provably secure construction of anonymous credentials that can work in

the elliptic group setting without bilinear pairings. In contrast, prior provably secure constructions were based on the RSA group or on groups with pairings, which made them prohibitively

inefficient for mobile devices, RFIDs and smartcards. The only prior efficient construction that

could work in such elliptic curve groups, due to Brands, does not have a proof of security.

*21:17* [Pub][ePrint]
Threshold Implementations of all 3x3 and 4x4 S-boxes, by B. Bilgin and S.Nikova and V.Nikov and V.Rijmen and G.St\\\"{u}tz
Side-channel attacks have proven many hardware implementations of cryptographic algorithms to be vulnerable.A recently proposed masking method, based on secret sharing and multi-party computation methods, introduces a set of sufficient requirements for implementations to be provably resistant against first-order DPA with minimal assumptions on the hardware.

The original paper doesn\'t describe how to construct the Boolean functions that are to be used in the implementation. In this paper, we derive the functions for all invertible $3 \\times 3$, $4 \\times 4$ S-boxes and the $6 \\times 4$ DES S-boxes. Our methods and observations can also be used to accelerate the search for sharings of larger (e.g. $8 \\times 8$) S-boxes. Finally, we investigate the cost of such protection.