*21:17* [Pub][ePrint]
On Necessary Padding with IO, by Justin Holmgren
We show that the common proof technique of padding a circuit before IO obfuscation is sometimes necessary. That is, assuming indistinguishability obfuscation (IO) and one-way functions exist, we define samplers Sam_0, which outputs (aux_0, C_0), and Sam_1, which outputs (aux_1, C_1) such that: - The distributions (aux_0, iO(C_0)) and (aux_1, iO(C_1)) are perfectly distinguishable.

- For padding s = poly(lambda)$, the distributions (aux_0, iO(C_0||0^s)) and (aux_1, iO(C_1||0^s)) are computationally indistinguishable.

We note this refutes the recent \"Superfluous Padding Assumption\" of Brzuska and Mittelbach.

*21:17* [Pub][ePrint]
An Unconditionally Hiding and Long-Term Binding Post-Quantum Commitment Scheme, by Daniel Cabarcas and Denise Demirel and Florian Göpfert and Jean Lancrenon and Thomas Wunderer
Commitment schemes are among cryptography\'s most important building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes applied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where commitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commitment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approximation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness property of a given commitment, while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construction yields two more interesting features: 1) the ability to \"convert\" a Pedersen commitment into a lattice-based one, and 2) the construction of a hybrid approach whose bindingness relies on the discrete logarithmand approximate shortest vector problems.

*21:17* [Pub][ePrint]
Unconditionally Secure Computation with Reduced Interaction, by Ivan Damgård and Jesper Buus Nielsen
We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a non-trivial function (such as the AND of several input bits), assuming that all players have input and get output. We show that for $n$ players and $t$ corruptions, $n(t+3)/2$ messages is necessary, this holds already for semi-honest and static corruption. Note that for functions that can be securely computed in constant round, this bound is tight up to a constant factor. For the case $t=1$ and semi-honest security, we show that $2 n$ messages is also sufficient to compute a rich class of functions efficiently, showing that the bound is exact for $t=1$.

Next, we consider round complexity.

It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with {\\em unconditional} security. Providing a positive answer seems to require completely new ideas for protocol design. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of {\\em some of} the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termination) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with $n=2t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, i.e., they send 1 message in the first round to each of the $t+1$ remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with $n=3t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, also this is shown to be optimal.

*21:17* [Pub][ePrint]
More on Impossibility of Virtual Black-Box Obfuscation in Idealized Models, by Mohammad Mahmoody and Ameer Mohammed and Soheil Nematihaji
The celebrated work of Barak et al. (Crypto\'01) ruled out the possibility of virtual black-box (VBB) obfuscation for general circuits. The recent work of Canetti, Kalai, and Paneth (TCC\'15) extended this impossibility to the random oracle model as well assuming the existence of trapdoor permutations (TDPs). On the other hand, the works of Barak et al. (Crypto\'14) and Brakerski-Rothblum (TCC\'14) showed that general VBB obfuscation is indeed possible in idealized graded encoding models. The recent work of Pass and Shelat (Cryptology ePrint 2015/383) complemented this result by ruling out general VBB obfuscation in idealized graded encoding models that enable evaluation of constant-degree polynomials in finite fields.In this work extend the above two impossibly results for general VBB obfuscation in idealized models. In particular we prove the following two results both assuming the existence of TDPs:

* There is no general VBB obfuscation in the generic group model of Shoup (Eurocrypt\'97) for {any abelian} group. By applying our techniques to the setting of Pass and Shelat we extend their result to any (even noncommutative) finite {ring}.

* There is no general VBB obfuscation even in the {random trapdoor permutation oracle} model. Our proof extends to any number of levels of hierarchical trapdoors.

*21:17* [Pub][ePrint]
Phasing: Private Set Intersection using Permutation-based Hashing, by Benny Pinkas and Thomas Schneider and Gil Segev and Michael Zohner
Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead.We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance

of PSI protocols whose overhead depends on the length of the representations of input items.

We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et

al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have better communication overhead than the previously best PSI protocol in that respect. The new protocol is only moderately less efficient

than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.

*21:17* [Pub][ePrint]
Microcash: Efficient Off-Line Small Payments, by Chris Pavlovski and Colin Boyd
An off-line electronic cash scheme is proposed that is suitable forsmall payments. The approach is innovative, in that each coin may be

efficiently verified by the same or different merchants during payment. The scheme relies on a batch signature technique to efficiently sign and verify individually spent coins; coins may also be deposited in batch manner. The scheme outlined differs considerably from conventional micropayments schemes by servicing a number of cash-like properties, such as off-line processing, detection of double spent coins, and ability to spend at different merchants. Additionally, the scheme eliminates a number of processing overheads that are apparent to some existing micropayment schemes.

*21:17* [Pub][ePrint]
Analyzing Constructions for key-alternating Pseudorandom Functions with Applications to Stream Cipher Operation Modes, by Matthias Krause
In the last years, much research work has been invested into the security analysis of key alternating ciphers in the random oracle model. These are pseudorandom permutations (PRPs), sometimes also called iterated Even-Mansour ciphers, which are defined by alternatingly adding $n$-bit sub-keys $k_i$ and calling public $n$-bit permutations $P_i$. Besides the fact, that results of this kind concern the fundamental questions of understanding the nature of pseudorandomness, a practical motivation for this study is that many modern block cipher designs correspond exactly to variants of iterated Even-Mansour ciphers. In this paper, we study similar construction for pseudorandom functions (PRFs), where additionally the access to a public $n$-bit (one-way) function $F$ is allowed. In particular, we show a sharp $n/2$-security bound for the simplest possible construction $F(x\\oplus k)$ and a sharp $2/3\\cdot n$-bound for the $FP(1)$-construction $F(P(x\\oplus k)\\oplus k)$, both in the random oracle model. The latter result contrasts with a sharp bound of the same order for $P(P(x\\oplus k)\\oplus \\pi(k))\\oplus k$, recently proved by Chen et. al.

One practical motivation for our research is due to the fact that operation modes of key stream generator based (KSG-based) stream ciphers can be modeled in a very straightforward way by FP-constructions. Our research shows a way to save KSG inner state length by using operation modes, which yield provable security beyond the birthday bound against time-space-data tradeoff attacks. For instance, we demonstrate that a slight change in the operation mode of the Bluetooth cipher (adding the session key twice in the initialization phase) raises the security w.r.t. to generic time-space-data tradeoff attacks from $n/2$ to $2/3\\cdot n$, where $n$ denotes the KSG inner state length.