*06:17* [Pub][ePrint]
Some results on Sprout, by Subhadeep Banik
Sprout is a lightweight stream cipher proposed by Armknecht and Mikhalev at FSE 2015. It has a Grain-like structure with two State Registers of size 40 bits each, which is exactly half the state sizeof Grain v1. In spite of this, the cipher does not appear to lose in security against generic Time-Memory-Data Tradeoff attacks due to the novelty of its design. In this paper, we first present improved results on Key Recovery with partial knowledge of the internal state. We show that if 50 of the 80 bits of the internal state are guessed then the remaining bits along with the Secret Key can be found in a reasonable time using a SAT solver. Thereafter we show that it is possible to perform a distinguishing attack on the full Sprout stream cipher in the multiple IV setting using around $2^{40}$ randomly chosen IVs on an average. The attack requires around $2^{48}$ bits of memory. Thereafter we will show that for every Secret Key, there exist around $2^{30}$ IVs for which the LFSR used in Sprout enters the all zero state during the Keystream generating phase. Using this observation, we will first show that it is possible to enumerate Key-IV pairs that produce keystream bits with period as small as 80. We will then outline a simple Key recovery attack that takes time equivalent to $2^{66.7}$ encryptions with negligible memory requirement. This although is not the best attack reported against this cipher in terms of the Time complexity, it is the best in terms of the memory required to perform the attack.

*06:17* [Pub][ePrint]
Non-malleability under Selective Opening Attacks: Implication and Separation, by Zhengan Huang and Shengli Liu and Xianping Mao and Kefei Chen
We formalize the security notions of non-malleability under selective opening attacks (NM-SO security) in two approaches: the indistinguishability-based approach and the simulationbased approach. We explore the relations between NM-SO security notions and the known selectiveopening security notions, and the relations between NM-SO security notions and the standard non-malleability notions.

*06:17* [Pub][ePrint]
Leakage-Resilient Cryptography over Large Finite Fields: Theory and Practice, by Marcin Andrychowicz and Daniel Masny and Edoardo Persichetti
Information leakage is a major concern in modern day IT-security. In fact, a malicious user is often able to extractinformation about private values from the computation performed on the

devices. In specific settings, such as RFID, where a low computational complexity is required, it is hard to apply standard techniques to achieve resilience against this kind of attacks.

In this paper, we present a framework to make cryptographic

primitives based on large finite fields robust against information leakage

with a bounded computational cost.

The approach makes use

of the inner product extractor and guarantees security in the presence of

leakage in a widely accepted model. Furthermore, we show how to apply the proposed

techniques to the authentication protocol Lapin, and we compare it to existing

solutions.

*06:17* [Pub][ePrint]
Practical Divisible E-Cash, by Patrick Märtens
Divisible e-cash systems allow a user to withdraw a wallet containing K coins and to spend k < K + 1 coins in a single operation, respectively. Independent of the new work of Canard, Pointcheval, Sanders and Traoré (Proceedings of PKC \'15) we present a practical and secure divisible e-cash system in which the bandwidth of each protocol is constant while the system fulfills the standard securityrequirements (especially which is unforgeable and truly anonymous) in the random oracle model. In other existing divisible e-cash systems that are truly anonymous, either the bandwidth of withdrawing

depends on K or the bandwidth of spending depends on k. Moreover, using some techniques of the work of Canard, Pointcheval, Sanders and Traoré we are also able to prove the security in the standard model.

Furthermore, we show an efficient attack against the unforgeability of Canard and Gouget\'s divisible e-cash scheme (FC \'10).

Finally, we extend our scheme to a divisible e-cash system that provides withdrawing and spending of an arbitrary value of coins (not necessarily a power of two) and give an extension to a fair e-cash

scheme.

*06:17* [Pub][ePrint]
Point Decomposition Problem in Binary Elliptic Curves, by Koray Karabina
We analyze the point decomposition problem (PDP) in binary elliptic curves. It is known that PDP in an elliptic curve group can be reduced to solving a particular system of multivariate non-linear system of equations derived from the so called Semaev summation polynomials.We modify the underlying system of equations by introducing some auxiliary variables. We argue that the trade-off between lowering the degree of Semaev polynomials and increasing the number of variables is worth.

*06:17* [Pub][ePrint]
Hybrid Publicly Verifiable Computation, by James Alderman and Christian Janson and Carlos Cid and Jason Crampton
Publicly Verifiable Outsourced Computation (PVC) allows weak devices to delegate computations to more powerful servers, and to verify the correctness of results.Delegation and verification rely only on public parameters, and thus PVC lends itself to large multi-user systems where entities need not be registered, yet in such settings the individual user requirements may be diverse.

In this paper, we introduce Hybrid PVC (HPVC) which, with a single setup stage, provides a flexible solution to outsourced computation supporting standard PVC, the enforcement of access control policies restricting the servers that may evaluate a given computation, and a reversed model of PVC which we call Verifiable Delegable Computation (VDC) where data is held remotely by servers. We provide formal frameworks and constructions for such systems.

*06:17* [Pub][ePrint]
Size-Hiding in Private Set Intersection: what can be done and how to do it without random oracles, by Paolo D\'Arco and Maria Isabel Gonzalez Vasco and Angel L. Perez del Pozo and Clauido Soriente
In this paper we focus our attention on private set intersection protocols, through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage. Considering the (more restricted) size-hiding scenario, we are able to:- prove that it is impossible to realize an unconditionally secure set intersection protocol (size-hiding or not);

- prove that unconditionally secure size-hiding set intersection is possible in a model where a set up authority provides certain information to the two parties and disappears;

- provide several new computationally secure size-hiding set intersection protocols.

Regarding the latter, in particular we provide a new generic construction without random oracles for the unbalanced setting,

where only the client gets the intersection and hides the size of its set of secrets. The main tool behind this design are smooth projective hash functions for languages derived from perfectly-binding commitments. We stand on the seminal ideas of Cramer-Shoup and Gennaro-Lindell, which have already found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer.

*06:17* [Pub][ePrint]
Efficient, Pairing-Free, One Round Attribute-Based Authenticated Key Exchange, by Suvradip Chakraborty and Srinivasan Raghuraman and Pandu Rangan C
In this paper, we present a single round two-party attribute-based authenticated key exchange protocol. Since pairing is a costly operation and the composite order groups must be very large to ensure security, we focus on pairing free protocols in prime order groups. We propose a new protocol that is pairing free, working in prime order group and having tight reduction to Strong Diffie Hellman (SDH) problem under the Attribute-based CK model which is a natural extension of the CK model for the public key setting. Thus, the first major advantage is that smaller key sizes are sufficient to achievecomparable security. Our scheme has several other advantages. The major one being the capability to handle active adversaries. All the previous Attribute-Based authenticated key exchange protocols can offer security only under passive adversaries. Our protocol recognizes the corruption by an active adversary and aborts the process. Ours is the first scheme achieving this property. We also show how to modify our construction to achieve anonymity of access structure of users. Our attribute-based authenticated key exchange is also the first that enjoys this property. In addition to this property, our scheme satisfies other security properties that are not covered by CK model such as forward secrecy, key compromise impersonation attacks and ephemeral key compromise impersonation attacks.

*06:17* [Pub][ePrint]
A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys, by Divesh Aggarwal and Alexander Golovnev
In this note, we prove lower bounds on the amount of entropy of random sources necessary for secure message authentication. We consider the problem of non-interactive c-time message authentication using a weak secret key having min-entropy k. We show that existing constructions using (c+1)-wise independent hash functions are optimal.This result resolves one of the main questions left open by the work of Dodis and Spencer [DS02] who considered this problem for one-time message authentication of one-bit messages.