*06:17* [Pub][ePrint]
Deterministic Public-Key Encryption under Continual Leakage, by Venkata Koppula,Omkant Pandey,Yannis Rouselakis,Brent Waters
Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O\'Neill (CRYPTO 2007), is an important database encryption technique which allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of highly sensitive, yet unpredictable, data items such as credit card or social security numbers. Such databases, however, are also the ideal target for hackers since even partial data leaks may reveal significantly damaging information to the attacker.Motivated by the goal of limiting the damage in such scenarios, we apply the ideas from leakage resilient cryptography to deterministic public-key encryption (D-PKE). We formulate appropriate security notions for D-PKE in the presence of leakage, and present constructions that achieve them in the standard model. We work in the *continual* leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerating up to $0.5-o(1)$ fraction of arbitrary leakage. The leakage rate can be improved to $1-o(1)$ by relying on the SXDH assumption.

At a technical level, we propose and construct a ``continual leakage resilient\'\' version of the *all-but-one* lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

*06:17* [Pub][ePrint]
Simple-looking joint decoders for traitor tracing and group testing, by Boris Skoric
The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes.In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible)

into which we feed all the evidence available to the tracer, in particular the codewords of *all* users. As far as we know, until now similar efforts have taken into consideration only the codeword of a single user, namely the user under scrutiny.

The Neyman-Pearson score needs as input the attack strategy of the colluders, which typically is not known to the tracer.

We insert the Interleaving attack, which plays a very special role in the theory of bias-based traitor tracing by virtue of being part of the asymptotic (i.e. large coalition size) saddlepoint solution.

The score system obtained in this way is universal: effective not only against the Interleaving attack, but against all other attack

strategies as well. Our score function for one user depends on the other users\' codewords in a very simple way: through the symbol tallies, which are easily computed.

We present bounds on the False Positive and False Negative error probability, yielding a.o. a prescription for setting the accusation threshold. We investigate the probability distribution of the score.

Finally we apply our construction to the area of (medical) Group Testing, which is related to traitor tracing.

*10:28* [Job][Update]
Lecturer/Senior Lecturer (Chancellor\'s Fellowship), *University of Strathclyde, UK*
The University of Strathclyde recently announced another round of the Chancellor\\\'s Fellowship Scheme. This round aims to appoint up to 20 new early career academic staff members in areas of strategic priority (including computer security). The appointment will be made at lecturer or senior lecturer level. Candidates from all areas of computer security are welcome.The benefits of the Chancellor\\\'s Fellowship include:

* Access to start up research funding, as appropriate for the discipline.

* A reduced teaching and administration load for the first stages of the Fellowship to allow you to concentrate on building your research portfolio.

* The Strathclyde Fellow will benefit from the normal academic probationary process, including completion of the Postgraduate Certificate in Advanced Academic Studies (Academic Practice).

* Bespoke learning and development events tailored for the Fellowship.

* Where appropriate, there will be the opportunity to gain experience working with external partner organisations through secondments and joint projects.

* Where appropriate, there will be an opportunity to participate in funded visits to international partners to further collaborative initiatives.

*10:28* [Job][New]
Lecturer/Senior Lecturer (Chancellor\'s Fellowship), *University of Strathclyde, UK*
The University of Strathclyde recently announced another round of the Chancellor\'s Fellowship Scheme. This round aims to appoint up to 20 new early career academic staff members in areas of strategic priority (including computer security). The appointment will be made at lecturer or senior lecturer level. Candidates from all areas of computer security are welcome.The benefits of the Chancellor\'s Fellowship include:

* Access to start up research funding, as appropriate for the discipline.

* A reduced teaching and administration load for the first stages of the Fellowship to allow you to concentrate on building your research portfolio.

* The Strathclyde Fellow will benefit from the normal academic probationary process, including completion of the Postgraduate Certificate in Advanced Academic Studies (Academic Practice).

* Bespoke learning and development events tailored for the Fellowship.

* Where appropriate, there will be the opportunity to gain experience working with external partner organisations through secondments and joint projects.

* Where appropriate, there will be an opportunity to participate in funded visits to international partners to further collaborative initiatives.

*06:17* [Pub][ePrint]
Obfuscating Low-Rank Matrix Branching Programs, by Amit Sahai and Mark Zhandry
In this work, we seek to extend the capabilities of the \"core obfuscator\" from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot \"forget.\" At a technical level, this limitation arises in previous work because all previous work relies on Kilian\'s statistical simulation theorem, which is false when applied to matrices not of full rank.In our work, we build the first core obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian\'s statistical simulation theorem. Furthermore, our obfuscator achieves two other notable advances over previous work:

- Our construction allows for non-square matrices of arbitrary dimensions. We also show that this flexibility yields concrete efficiency gains.

- Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit of output.

Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains even in applications not directly using obfuscation.

*06:17* [Pub][ePrint]
Automated Analysis and Synthesis of Block-Cipher Modes of Operation, by Alex J. Malozemoff and Jonathan Katz and Matthew D. Green
Block ciphers such as AES are deterministic, keyed functions that operate on small, fixed-size blocks. Block-cipher \\emph{modes of operation} define a mechanism for probabilistic encryption of arbitrary length messages using any underlying block cipher. A mode of operation can be proven secure (say, against chosen-plaintext attacks) based on the assumption that the underlying block cipher is a pseudorandom function. Such proofs are complex and error-prone, however, and must be done from scratch whenever a new mode of operation is developed.We propose an \\emph{automated} approach for the security analysis of block-cipher modes of operation based on a ``local\'\' analysis of the steps carried out by the mode when handling a \\emph{single} message block. We model these steps as a directed, acyclic graph, with nodes corresponding to instructions and edges corresponding to intermediate values. We then introduce a set of \\emph{labels} and \\emph{constraints} on the edges, and prove a meta-theorem showing that any mode for which there exists a labeling of the edges satisfying these constraints is secure (against chosen-plaintext attacks). This allows us to reduce security of a given mode to a constraint-satisfaction problem, which in turn can be handled using an SMT solver. We couple our security-analysis tool with a routine that automatically generates viable modes; together, these allow us to synthesize hundreds of secure modes.

*06:17* [Pub][ePrint]
Lock-free GaussSieve for Linear Speedups in Parallel High Performance SVP Calculation, by Artur Mariano, Shahar Timnat and Christian Bischof
Lattice-based cryptography became a hot-topic in the past years because it seems to be quantum immune, i.e., resistant to attacks operated with quantum computers. The security of lattice-based cryptosystems is determined by the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP). Thus, it is of prime importance to study how efficiently SVP-solvers can be implemented.This paper presents a parallel shared-memory implementation of the GaussSieve algorithm, a well known SVP-solver. Our implementation achieves almost linear and linear speedups with up to 64 cores, depending on the tested scenario, and delivers better sequential performance than any other disclosed GaussSieve implementation. In this paper, we show that it is possible to implement a highly scalable version of GaussSieve on multi-core CPU-chips. The key features of our implementation are a lock-free singly linked list, and hand-tuned, vectorized code. Additionally, we propose an algorithmic optimization that leads to faster convergence.

*06:17* [Pub][ePrint]
How to Obfuscate Programs Directly, by Joe Zimmerman
We propose a new way to obfuscate programs, using composite-order multilinear maps. Our construction operates directly on straight-line programs (arithmetic circuits), rather than converting them to matrix branching programs as in other known approaches. This yields considerable efficiency improvements. For an NC1 circuit of size $s$ and depth $d$, with $\\n$ inputs, we require only $O(d^2s^2 + \\n^2)$ multilinear map operations to evaluate the obfuscated circuit---as compared with other known approaches, for which the number of operations is exponential in $d$. We prove virtual black-box (VBB) security for our construction in a generic model of multilinear maps of hidden composite order, extending previous models for the prime-order setting.Our scheme works either with \"noisy\" multilinear maps, which can only evaluate expressions of degree $\\lambda^c$ for pre-specified constant $c$; or with \"clean\" multilinear maps, which can evaluate arbitrary expressions. The \"noisy\" variant can be instantiated at present with the Coron-Lepoint-Tibouchi scheme, while the existence of \"clean\" maps is still unknown. With known \"noisy\" maps, our new obfuscator applies only to NC1 circuits, requiring the additional assumption of FHE in order to bootstrap to P/poly (as in other obfuscation constructions).

From \"clean\" multilinear maps, on the other hand (whose existence is still open), we present the first approach that would achieve obfuscation for P/poly directly, without FHE. We also introduce the concept of succinct obfuscation, in which the obfuscation overhead size depends only on the length of the input and of the secret part of the circuit. Using our new techniques, along with the assumption that factoring is hard on average, we show that \"clean\" multilinear maps imply succinct obfuscation for P/poly. For the first time, the only remaining obstacle to implementable obfuscation in practice is the noise growth in known, \"noisy\" multilinear maps. Our results demonstrate that the question of \"clean\" multilinear maps is not a technicality, but a central open problem.