*16:17* [Pub][ePrint]
Prover Anonymous and Deniable Distance-Bounding Authentication, by Sebastien Gambs and Cristina Onete and Jean-Marc Robert
In distance-bounding authentication protocols, a verifier confirms that a prover is (1) legitimate and (2) in the verifier\'s proximity. Proximity checking is done by running time-critical exchanges between both parties. This enables the verifier to detect relay attacks (a.k.a. mafia fraud). While most distance-bounding protocolsoffer resistance to mafia and distance fraud as well as to impersonation attacks, only few protect the privacy of the authenticating prover.

One exception is the protocol due to Hermans, Peeters, and Onete developed in 2013, which offers strong privacy guarantees with respect to a Man-in-the-Middle adversary. However, this protocol provides no privacy guarantees for the prover with respect to a malicious verifier, who can fully identify the prover. Having in

mind possible verifier corruption or data leakage from verifiers to a centralized server, we suggest that stronger privacy properties are needed.

In this paper, we propose an efficient distance-bounding protocol that gives strong prover privacy guarantees even with respect to the verifier or to a centralized back-end server, storing prover information and managing revocation and registration. Specifically, we formally model and define prover anonymity, a property guaranteeing that verifiers infer only the legitimacy of the prover but not his identity, and deniability, which ensures that the back-end server cannot distinguish prover behavior from malicious verifier behavior (i.e., provers can deny that they authenticated). Finally, we present an efficient protocol that achieves these strong guarantees, give exact bounds for each of its security properties, and prove these statements formally.

*16:17* [Pub][ePrint]
Optimal Algebraic Manipulation Detection Codes, by Ronald Cramer and Carles Padr{\\\'o} and Chaoping Xing
Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as {\\em keyless} combinatorial authentication codes that provide security in the presence of an {\\em oblivious}, {\\em algebraic} attacker.Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing.

In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive constant error probability $\\epsilon$ in combination with unbounded cardinality $M$ of the message space. Adapting a known bound to this regime, it follows that the binary length $\\rho$ of the tag satisfies $\\rho\\geq \\log \\log M + \\Omega_{\\epsilon}(1)$. We shall call AMD codes meeting this lower bound {\\em optimal}. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor~2 {\\em off} from being optimal. Bridging the gap to optimality efficiently turns out to be surprisingly nontrivial. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. This leads to an explicit construction of almost-optimal AMD codes and to an efficient randomized construction of optimal AMD codes, as we show in our main results. In all our results, the error probability $\\epsilon$ can be chosen as an arbitrarily small positive real number.

*22:17* [Pub][ePrint]
Key-Indistinguishable Message Authentication Codes, by Joel Alwen and Martin Hirt and Ueli Maurer and Arpita Patra and Pavel Raykov
While standard message authentication codes (MACs) guarantee authenticity of messages, they do not, in general, guarantee the anonymity of the sender and recipient. For example it may be easy for an observer to determine whether or not two authenticated messages were sent by the same party even without any information about the secret key used. However preserving any uncertainty an attacker may have about the identities of honest parties engaged in authenticated communication is an important goal of many cryptographic applications. For example this is stated as an explicit goal of modern cellphone authentication protocols~\\cite{3GPP} and RFID based authentication systems\\cite{Vaudenay10}.In this work we introduce and construct a new fundamental cryptographic primitive called \\emph{key indistinguishable} (KI) MACs. These can be used to realize many of the most important higher-level applications requiring some form of anonymity and authenticity~\\cite{AHMPR14}. We show that much (though not all) of the modular MAC construction framework of~\\cite{DodisKPW12} gives rise to several variants of KI MACs. On the one hand, we show that KI MACs can be built from hash proof systems and certain weak PRFs allowing us to base security on such assumption as DDH, CDH and LWE. Next we show that the two direct constructions from the LPN assumption of~\\cite{DodisKPW12} are KI, resulting in particularly efficient constructions based on structured assumptions. On the other hand, we also give a very simple and efficient construction based on a PRF which allows us to base KI MACs on some ideal primitives such as an ideal compression function (using HMAC) or block-cipher (using say CBC-MAC). In particular, by using our PRF construction, many real-world implementations of MACs can be easily and cheaply modified to obtain a KI MAC. Finally we show that the transformations of~\\cite{DodisKPW12} for increasing the domain size of a MAC as well as for strengthening the type of unforgeability it provides also preserve (or even strengthen) the type of KI enjoyed by the MAC. All together these results provide a wide range of assumptions and construction paths for building various flavors of this new primitive.

*22:17* [Pub][ePrint]
MJH: A Faster Alternative to MDC-2, by Jooyoung Lee and Martijn Stam
In this paper, we introduce a new class of double-block-length hash functions. Using the ideal cipher model, we prove that these hash functions, dubbed \\MJH, are asymptotically collision resistant up to $O(2^{n(1-\\epsilon)})$ query complexity for any $\\epsilon>0$ in the iteration, where $n$ is the block size of the underlying blockcipher.When based on $n$-bit key blockciphers, our construction, being of rate 1/2, provides better provable security than MDC-2, the only known construction of a rate-1/2 double-length hash function based on an $n$-bit key blockcipher with non-trivial provable security.

Moreover, since key scheduling is performed only once per message block for MJH, our proposal significantly outperforms MDC-2 in efficiency.

When based on a $2n$-bit key blockcipher, we can use the extra $n$ bits of key to increase the amount of payload accordingly. Thus we get a rate-1 hash function that is much faster than existing proposals, such as Tandem-DM with comparable provable security. The proceedings version of this paper appeared in CT-RSA 2011.

*20:12* [Job][New]
PhD Position in Lattice-Based Cryptography, *Technische Universität Darmstadt, Germany, Middle-Europe*
The group for Cryptography and Computer Algebra at the Technische Universität Darmstadt chaired by Prof. Dr. Johannes Buchmann is looking for a Ph.D. student. Candidates should have a superior Master\\\'s degree in mathematics, computer science, or related disciplines. The opportunity to work in the area of cryptography --- more precisely, in lattice-based cryptography --- is given to the prospective Ph.D. student. Any prior experience in lattice-based cryprography is certainly an asset.

*19:17* [Pub][ePrint]
Improved Slender-set Linear Cryptanalysis, by Guo-Qiang Liu and Chen-Hui Jin and Chuan-Da Qi
In 2013, Borghoff \\emph{et al}. introduced a slender-set linearcryptanalysis on PRESENT-like ciphers with key-dependent secret

S-boxes. In this paper, we propose an improved slender-set linear

attack to PRESENT-like ciphers with secret S-boxes. We investigate

three new cryptanalytic techniques, and use them to recover the

secret S-boxes efficiently. Our first new idea is that we propose a

new technique to support consistency of partitions of the input to

the secret S-boxes. Our second new technique is that we present a

more efficient method to recover the coordinate functions of secret

S-boxes based on more information than that of Borghoff\'s attack.

The third new technique is that we propose a method of constructing

all correct coordinate function of secret S-boxes by pruning search

algorithm. In particular, we implemented a successful linear attack

on the full round Maya in practice. In our experiments, the correct

S-box can be recovered with $2^{36}$ known plaintexts, $2^{18.9}$

time complexity and negligible memory complexity at a success rate

of 87.5\\%. Our attack is the improvement and sequel of Borghoff\'s

work on PRESENT-like cipher with secret S-boxes.

*19:17* [Pub][ePrint]
Actively Secure Private Function Evaluation, by Payman Mohassel and Saeed Sadeghian and Nigel P. Smart
We propose the first general framework for designing actively secure private function evaluation (PFE), not based on universal circuits. Our framework is naturally divided into pre-processing and online stages and can be instantiated using any generic actively secure multiparty computation (MPC) protocol.Our framework helps address the main open questions about efficiency of actively secure PFE. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with $O(g \\cdot \\log g)$ complexity where $g$ is the circuit size. The best previous construction (of practical interest) is based on an arithmetic universal circuit and has complexity $O(g^5)$.

We also introduce the first linear Zero-Knowledge proof of correctness of ``extended permutation\" of ciphertexts (a generalization of ZK proof of correct shuffles) which maybe of independent interest.