*15:17* [Pub][ePrint]
Quantum algorithm for the discrete logarithm problem for matrices over finite group rings, by A. D. Myasnikov and A. Ushakov
We propose a polynomial time quantum algorithm for solving thediscrete logarithm problem in matrices over finite group rings.

The hardness of this problem was recently employed in the design

of a key-exchange protocol proposed by D. Kahrobaei, C. Koupparis,

and V. Shpilrain. Our result implies that the Kahrobaei et al.

protocol does not belong to the realm of post-quantum cryptography.

*21:17* [Pub][ePrint]
Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing, by Mihir Bellare and Viet Tung Hoang and Phillip Rogaway
Standard constructions of garbled circuits provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some applications--notably one-time programs(Goldwasser, Kalai, and Rothblum 2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)--need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with

regard to adaptive security and suggest the need of a better abstraction boundary. To this end we

investigate the adaptive security of garbling schemes, an abstraction of Yao\'s garbled-circuit technique

that we recently introduced (Bellare, Hoang, Rogaway 2012). Building on that framework, we give definitions encompassing privacy, authenticity, and obliviousness, with either coarse-grained or fine-grained adaptivity. We show how adaptively secure garbling schemes support simple solutions for one-time programs and secure outsourcing, with privacy being the goal in the first case and obliviousness and authenticity the goal in the second. We give transforms that promote static-secure garbling schemes

to adaptive-secure ones. Our work advances the thesis that conceptualizing garbling schemes as a first-class cryptographic primitive can simplify, unify, or improve treatments for higher-level protocols.

*21:17* [Pub][ePrint]
Packed Ciphertexts in LWE-based Homomorphic Encryption, by Zvika Brakerski and Craig Gentry and Shai Halevi
In this short note we observe that the Peikert-Vaikuntanathan-Waters (PVW) method of packing many plaintext elements in a single Regev-type ciphertext, can be used for performing SIMD homomorphic operations on packed ciphertext. This provides an alternative to the Smart-Vercauteren (SV) ciphertext-packing technique that relies on polynomial-CRT. While the SV technique is only applicable to schemes that rely on ring-LWE (or other hardness assumptions in ideal lattices), the PVW method can be used also for cryptosystems whose security is based on standard LWE (or more broadly on the hardness of ``General-LWE\'\').Although using the PVW method with LWE-based schemes leads to worse asymptotic efficiency than using the SV technique with ring-LWE schemes, the simplicity of this method may still offer some practical advantages. Also, the two techniques can be used in tandem with ``general-LWE\'\' schemes, suggesting yet another tradeoff that can be optimized for different settings.

*21:17* [Pub][ePrint]
Information Leakage of Continuous-Source Zero Secrecy Leakage Helper Data Schemes, by Joep de Groot and Boris Skoric and Niels de Vreede and Jean-Paul Linnartz
A Helper Data Scheme is a cryptographic primitive that extracts a high-entropy noise-free string from noisy data. Helper Data Schemes are used for privacy-preserving databases and for Physical Unclonable Functions.We refine the theory of Helper Data schemes with Zero Secrecy Leakage (ZSL), i.e. the mutual information between the helper data and the extracted secret is zero. We prove that ZSL necessitates particular properties of the helper data generating function, which also allows us to show the existence of `Sibling Points\'. In the special case that our generated secret is uniformly distributed (Fuzzy Extractors) our results coincide with the continuum limit of a recent construction by Verbiskiy et al. Yet our results cover secure sketches as well. Moreover we present an optimal reconstruction algorithm for this scheme, that not only provides the lowest possible reconstruction error rate but also yields an attractive, simple implementation of the verification.

Further, we introduce Diagnostic Category Leakage (DCL), which quantifies what an attacker can infer from helper data about a particular medical indication of the enrolled user, or reversely what probabilistic knowledge of a diagnose can leak about the secret. If the attacker has a priori knowledge about the enrolled user (medical indications, race, gender), then the ZSL property does not guarantee that there is no secrecy leakage from the helper data. However, this effect is typically very small.

*21:17* [Pub][ePrint]
Leakage Squeezing of Order Two, by Claude Carlet and Jean-Luc Danger and Sylvain Guilley and Houssem Maghrebi
In masking schemes, \\emph{leakage squeezing} is the study of the optimal shares\' representation, that maximizes the resistance order against high-order side-channel attacks.Squeezing the leakage of first-order Boolean masking has been problematized and solved previously in~\\cite{DBLP:conf/africacrypt/MaghrebiCGD12}.

The solution consists in finding a bijection $F$ that modifies the mask, in such a way that its graph, seen as a code, be of greatest dual distance.

This paper studies second-order leakage squeezing, \\emph{i.e.} leakage squeezing with two independent random masks.

It is proved that, compared to first-order leakage squeezing, second-order leakage squeezing at least increments (by one unit) the resistance against high-order attacks, such as high-order correlation power analyses (HO-CPA).

Now, better improvements over first-order leakage squeezing are possible by relevant constructions of the squeezing bijections pair.

We provide with linear bijections that improve by strictly more than one (instead of one) the resistance order.

Specifically,

when the masking is applied on bytes (which suits AES),

resistance against $1$st-order (resp. $2$nd-order) attacks is possible with one (resp. two) masks.

Optimal leakage squeezing with one mask resists HO-CPA of orders up to $5$.

In this paper, with two masks, we provide resistance against HO-CPA not only of order $5+1=6$, but also of order $7$.

*21:17* [Pub][ePrint]
On Transaction Pseudonyms with Implicit Attributes, by Stefan G. Weber
Transaction pseudonyms with implicit attributes are a novel approach to multilevel linkable transaction pseudonyms. We extend earlier work of Juels and Pappu on reencryption-based transaction pseudonyms, by developing new mechanisms for controlled pseudonym linkability.This includes mechanisms for cooperative, stepwise re-identication

as well as individual authentication of pseudonyms. Our proposal makes

use of efficient techniques from the area of secure multiparty computation and cryptographically secure PRNGs.