*19:17* [Pub][ePrint]
Learning with Rounding, Revisited: New Reduction, Properties and Applications, by Joel Alwen and Stephan Krenn and Krzysztof Pietrzak and Daniel Wichs
The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen [BPR12] at EUROCRYPT \'12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem of [BPR12] and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors.As a tool in the reduction, we show that there is a ``lossy mode\'\' for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple new constructions of deterministic encryption, lossy trapdoor functions and reusable extractors.

Our approach is inspired by a technique of Goldwasser et al. [GKPV10] from ICS \'10, which implicitly showed the existence of a ``lossy mode\'\' for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.

*19:17* [Pub][ePrint]
Notions of Black-Box Reductions, Revisited, by Paul Baecher and Christina Brzuska and Marc Fischlin
Reductions are the common technique to prove security of cryptographic constructions based on a primitive. They take an allegedly successful adversary against the construction and turn it into a successful adversary against the underlying primitive. To a large extent, these reductions are black-box in the sense that they consider the primitive and/or the adversary against the construction only via the input-output behavior, but do not depend on internals like the code of the primitive or of the adversary. Reingold, Trevisan, and Vadhan~(TCC, 2004) provided a widely adopted framework, called the RTV framework from hereon, to classify and relate different notions of black-box reductions.Having precise notions for such reductions is very important when it comes to black-box separations, where one shows that black-box reductions cannot exist. An impossibility result, which clearly specifies the type of reduction it rules out, enables us to identify the potential leverages to bypass the separation. We acknowledge this by extending the RTV framework in several respects using a more fine-grained approach. First, we capture a type of reduction---frequently ruled out by so-called meta-reductions---which escapes the RTV framework so far. Second, we consider notions that are ``almost black-box\'\', i.e., where the reduction receives additional information about the adversary, such as its success probability. Third, we distinguish explicitly between efficient and inefficient primitives and adversaries, allowing us to determine how relativizing reductions in the sense of Impagliazzo and Rudich (STOC, 1989) fit into the picture.

*19:17* [Pub][ePrint]
On the Complexity of Broadcast Setup, by Martin Hirt and Pavel Raykov
Byzantine broadcast is a distributed primitive that allows a specific party (called ``sender\'\') to consistently distribute a value $v$ among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. Broadcast requires that correct parties always agree on the same value and if the sender is correct, then the agreed value is $v$. Broadcast without a setup (i.e., from scratch) is achievable from point-to-point channels if and only if $t < n/3$. In case $t \\ge n/3$ a trusted setup is required. The setup may be assumed to be given initially or generated by the parties in a setup phase.It is known that generating setup for protocols with cryptographic security is relatively simple and only consists of setting up a public-key infrastructure. However, generating setup for information-theoretically secure protocols is much more involved. In this paper we study the complexity of setup generation for information-theoretic protocols using point-to-point channels and temporarily available broadcast channels. We optimize the number of rounds in which the temporary broadcast channels are used while minimizing the number of bits broadcast with them. We give the first information-theoretically secure broadcast protocol tolerating $t < n/2$ that uses the temporary broadcast channels during only 1 round in the setup phase. Furthermore, only $\\cO(n^3)$ bits need to be broadcast with the temporary broadcast channels during that round, independently of the security parameter employed. The broadcast protocol presented in this paper allows to construct the first information-theoretically secure MPC protocol which uses a broadcast channel during only one round. Additionally, the presented broadcast protocol supports refreshing, which allows to broadcast an a priori unknown number of times given a fixed-size setup.

*19:17* [Pub][ePrint]
Lossy Chains and Fractional Secret Sharing, by Yuval Ishai and Eyal Kushilevitz and Omer Strulovich
Motivated by the goal of controlling the amount of work required toaccess a shared resource or to solve a cryptographic puzzle,

we introduce and study the related notions of {\\em lossy chains} and {\\em fractional secret sharing}.

Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty

about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure $f:2^{[n]}\\to [m]$ by guaranteeing that from the point of view of each set $T\\subseteq [n]$ of parties, the secret is {\\em uniformly} distributed over a set of $f(T)$ potential secrets. We show that every (monotone) fractional access structure can be realized. For {\\em symmetric} structures, in which $f(T)$ depends only on the size of $T$, we give an efficient construction with share size $poly(n,\\log m)$.

Our construction of fractional secret sharing schemes is based on the new notion of {\\em lossy chains} which may be of independent interest.

A lossy chain is a Markov chain $(X_0,\\ldots,X_n)$ which starts with a random secret $X_0$ and gradually loses information about it at a rate which is specified by a {\\em loss function} $g$. Concretely, in every step $t$, the distribution of $X_0$ conditioned on the value of $X_t$ should always be uniformly distributed over a set of size $g(t)$.

We show how to construct such lossy chains efficiently for any possible loss function $g$, and prove that our construction achieves an optimal asymptotic information rate.

*19:17* [Pub][ePrint]
URDP: General Framework for Direct CCA2 Security from any Lattice-Based PKE Scheme, by Roohallah Rastaghi
Design efficient Lattice-based cryptosystem secure against adaptive chosen ciphertext attack (IND-CCA2) is a challenge problem. To the date, full CCA2-security of all proposed Lattice-based PKE schemes achieved by using a generic transformations such as either strongly unforgeable one-time signature schemes (SU-OT-SS), or a message authentication code (MAC) and weak form of commitment. The drawback of these schemes is that encryption requires \"separate encryption\". Therefore, the resulting encryption scheme is not sufficiently efficient to be used in practice and it is inappropriate for many applications such as small ubiquitous computing devices with limited resources such as smart cards, active RFID tags, wireless sensor networks and other embedded devices.In this work, for the first time, we introduce an efficient universal random data padding (URDP) scheme, and show how it can be used to construct a \"direct\" CCA2-secure encryption scheme from \"any\" worst-case hardness problems in (ideal) lattice in the standard model, resolving a problem that has remained open till date. This novel approach is a \"black-box\" construction and leads to the elimination of separate encryption, as it avoids using general transformation from CPA-secure scheme to a CCA2-secure one. IND-CCA2 security of this scheme can be tightly reduced in the standard model to the assumption that the underlying primitive is an one-way trapdoor function.

*19:17* [Pub][ePrint]
Unconditionally Secure and Universally Composable Commitments from Physical Assumptions, by Ivan Damgard and Alessandra Scafuro
We present a constant-round unconditional black-box compiler, that transforms any ideal straight- line extractable commitment scheme, into an extractable and equivocal commitment scheme, therefore yielding to UC-security [Can01]. We exemplify the usefulness of our compiler providing two (constant- round) instantiations of ideal straight-line extractable commitment using (malicious) PUFs [OSVW13] and stateless tamper-proof hardware tokens [Kat07]. This allows us to achieve the first unconditionally UC-secure commitment with malicious PUFs and the first unconditionally UC-secure commitment with stateless tokens. Our constructions are secure for adversaries creating arbitrarily malicious stateful PUFs/tokens.Previous results with malicious PUFs used either computational assumptions to achieve UC-secure commitments or were unconditionally secure but only in the indistinguishability sense [OSVW13]. Similarly, with stateless tokens, UC-secure commitments are known only under computational assumptions [CGS08, GIS+10, CKS+11], while the (not UC) unconditional commitment scheme of [GIMS10] is secure only in a weaker model in which the adversary is not allowed to create stateful tokens.

Besides allowing us to prove feasibility of unconditional UC-security with (malicious) PUFs and stateless tokens, our compiler can be instantiated with any ideal straight-line extractable commitment scheme, thus allowing the use of various setup assumptions which may better fit the application or the technology available.