*16:17* [Pub][ePrint]
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation, by Alexandra Boldyreva and Jean Paul Degabriele and Kenneth G. Paterson and Martijn Stam
In recent years, a number of standardized symmetric encryption schemes have fallen foul of attacks exploiting the fact that in some real world scenarios ciphertexts can be delivered in a fragmented fashion. We initiate the first general and formal study of the security of symmetric encryption against such attacks. We extend the SSH-specific work of Paterson and Watson (Eurocrypt 2010) to develop security models for the fragmented setting. We also develop security models to formalize the additional desirable properties of ciphertext boundary hiding and robustness against Denial-of-Service (DoS) attacks for schemes in this setting. We illustrate the utility of each of our models via efficient constructions for schemes using only standard cryptographic components, including constructions that simultaneously achieve confidentiality, ciphertext boundary hiding and DoS robustness.

*02:17* [Job][New]
2 x Lectureships (equivalent to assistant professor) in Security of Cyber-Physical Systems, *Security Lancaster Research Centre, Lancaster University, UK*
Cyber-physical systems (CPS) present the new frontier for security. The number of connected devices is expected to grow to 50 billion by the year 2020. This growth is being driven by innovations in the areas of smart cities, internet of things, body-area networks (in healthcare), smart grids and wearable sensors. With digital technologies becoming embedded in everyday objects and infrastructures, CPS offer both great opportunities and great problems of security for modern society. They raise major research challenges with regards to security of the data and information, the systems and infrastructures and the users interacting with them on a daily basis. The research agendas raised by these questions are interdisciplinary and can be tackled from a range of technical, behavioural and socio-economic perspectives. The proposed position will, therefore, be based in Security Lancaster, our inter-disciplinary research centre on Security and Protection Science.Security Lancaster is one of only four flagship Lancaster Research Centres and was amongst the first 8 Academic Centres of Excellence in Cyber Security Research recognised by the UK government. With over 70 researchers, it is one of the few multi-disciplinary centres to tackle human and technological challenges to cyber security by integrating computer science researchers with expertise from social and behavioural sciences. The centre has a thriving PhD programme with over 30 current graduate students engaged in security research.

For these posts (equivalent to Assistant Professor) we are seeking a ‘rising star’ in security of cyber-physical systems, with a strong and growing international reputation, evidenced by excellent international publications in leading security journals and conferences.

*16:17* [Pub][ePrint]
Non-committing encryption from $\\Phi$-hiding, by Brett Hemenway and Rafail Ostrovsky and Alon Rosen
A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants

to corrupt before the protocol begins.

A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC \'96). The

original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the

best known constructions had ciphertext expansion that was linear in the security parameter.

In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length.

Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key

of size $\\tilde{\\bigoh}(n \\secpar)$ where $n$ is the message length and $\\secpar$ is the security parameter. The second message consists

of a ciphertext of size $\\bigoh( n \\log n + \\secpar )$. The security of our scheme is proved based on the $\\Phi$-hiding problem.

*16:17* [Pub][ePrint]
Richer Efficiency/Security Trade-offs in 2PC, by Vladimir Kolesnikov and Payman Mohassel and Ben Riva and Mike Rosulek
The dual-execution protocol of Mohassel \\& Franklin (PKC 2006) is a highly efficient (each party garbling only one circuit) 2PC protocol that achieves malicious security apart from leaking an {\\em arbitrary, adversarially-chosen} predicate about the honest party\'s input. We present two practical and orthogonal approaches to improve the security of the dual-execution technique.First, we show how to greatly restrict the predicate that an adversary can learn in the protocol, to a natural notion of ``only computation leaks\'\'-style leakage. Along the way, we identify a natural security property of garbled circuits called {\\em property-enforcing} that may be of independent interest.

Second, we address a complementary direction of reducing the probability that the leakage occurs. We propose a new dual-execution protocol --- with a very light cheating-detection phase and each party garbling $s+1$ circuits --- in which a cheating party learns a bit with probability only $2^{-s}$. Our concrete measurements show approximately $35\\%$ reduction in communication for the AES circuit, compared to the best combination of state of the art techniques for achieving the same security notion.

Combining the two results, we achieve a rich continuum of practical trade-offs between efficiency \\& security, connecting the covert, dual-execution and full-malicious guarantees.

*16:17* [Pub][ePrint]
Better Algorithms for LWE and LWR, by Alexandre Duc and Florian Tramèr and Serge Vaudenay
The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al. In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.

Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime q, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.

*19:17* [Pub][ePrint]
On Obfuscation with Random Oracles, by Ran Canetti and Yael Tauman Kalai and Omer Paneth
Assuming trapdoor permutations, we show that there exist function families that cannot be VBB-obfuscated even if both the obfuscator and the obfuscated program have access to a random oracle. Specifically, these families are the robust unobfuscatable families of [Bitansky-Paneth, STOC 13].Our result stands in contrast to the general VBB obfuscation algorithms in more structured idealized models where the oracle preserves certain algebraic homomorphisms [Canetti-Vaikuntanathan, ePrint 13; Brakerski-Rothblum, TCC 14; Barak et al., Eurocrypt 14].

*19:17* [Pub][ePrint]
Stretching Groth-Sahai: NIZK Proofs of Partial Satisfiability, by Carla Ràfols
Groth, Ostrovsky and Sahai constructed a non-interactive Zap for NP-languages by observing that the common reference string of their proof system for circuit satisfiability admits what they call correlated key generation.

The latter means that it is possible to create from scratch two common reference strings in such a way that it can be publicly verified that at least one of them guarantees perfect soundness while

it is computationally infeasible to tell which one. Their technique also implies that it is possible to have NIWI Groth-Sahai proofs for certain types of equations over bilinear groups in the plain model. We extend the result of Groth, Ostrovsky and Sahai in several directions. Given as input some predicate $P$ computable by some monotone span program over a finite field, we show how to generate a set of common reference strings in such a way that it can be publicly verified that the subset of them which guarantees perfect soundness is accepted by the span program. We give several different flavors of the technique suitable for different applications scenarios and different equation types. We use this to stretch the expressivity of Groth-Sahai proofs and construct NIZK proofs of partial satisfiability of sets of equations in a bilinear group and more efficient Groth-Sahai NIWI proofs without common reference string for a larger class of equation types. Finally, we apply our results to significantly reduce the size of the signatures of the ring signature scheme of Chandran, Groth and Sahai or to have a more efficient proof in the standard model that a commitment opens to an element of a public list.