*15:17* [Pub][ePrint]
Relational Hash, by Avradip Mandal and Arnab Roy
Traditional cryptographic hash functions allow one to easily check whether the original plain-texts are equal or not, given a pair of hash values. Probabilistic hash functions extend this concept where given a probabilistic hash of a value and the value itself, one can efficiently check whether the hash corresponds to the given value. However, given distinct probabilistic hashes of the same value it is not possible to check whether they correspond to the same value. In this work we introduce a new cryptographic primitive called \\emph{relational hash} using which, given a pair of (relational) hash values, one can determine whether the original plain-texts were related or not. We formalize various natural security notions for the relational hash primitive - one-wayness, unforgeability and oracle simulatibility. We develop a relational hash scheme for discovering linear relations among bit-vectors (elements of $\\FF_2^n$) and $\\FF_p$-vectors. Using these linear relational hash schemes we develop relational hashes for detecting proximity in terms of hamming distance. These proximity relational hashing scheme can be adapted to a privacy preserving biometric authentication scheme.

We also introduce the notion of \\emph{relational encryption}, which is a regular semantically secure public key encryption for any adversary which only has access to the public key. However, a semi-trusted entity can be given a relational key using which it can discover relations among ciphertexts, but still cannot decrypt and recover the plaintexts.

*15:17* [Pub][ePrint]
Almost Optimal Short Adaptive Non-Interactive Zero Knowledge, by Helger Lipmaa
Several recent short NIZK arguments are constructed in a modular way from a small number of basic arguments like the product argument or the shift argument. The main technical novelty of the current work is a significantly more efficient version of the product argument. Based on this, we propose an adaptive NIZK range argument with almost optimal complexity: constant communication (in group elements), constant verifier\'s computational complexity (in cryptographic operations), and $\\Theta (n \\log n)$ [resp., $\\Theta (n)$] prover\'s computational complexity (in non-cryptographic [resp., cryptographic] operations). The latter can be compared to $n \\log^{\\omega (1)} n$ in the most efficient \\emph{published} short adaptive non-interactive range argument, or $\\Theta (n \\log^2 n)$ [resp., $\\Theta (n \\log n)$] that is achievable when following QAP-based framework from Eurocrypt 2013. Here, $n$ is the logarithm of the range length.

The new product argument can be used to construct efficient adaptive NIZK arguments for many other languages, including several that are $\\mathsf{NP}$-complete like $\\textsc{SubsetSum}$. Importantly, for all such languages, new adaptive arguments achieve better prover\'s computation than the QAP-based framework.

*06:23* [Job][New]
Lecturer/Senior Lecturer in Cyber Security

(equiv. to Assistant/Associate Professor), *Surrey Centre for Cyber Security, Department of Computing, University of Surrey, Guildford, UK*
Department of Computing at University of Surrey is currently seeking to make an appointment at Lecturer (equiv. to Assistant Professor) or Senior Lecturer (equiv. to Associate Professor) level in Cyber Security to support the Departmentâ€™s continued growth by complementing our existing research strengths and contributing to the research leadership within the Department, to play a leading role in the recently established interdisciplinary Surrey Centre for Cyber Security (SCCS) and to contribute to the new MSc Information Security programme. Applications are welcome particularly in the areas of Software Security, Web and Network Security, System Security, Applied Cryptography and Protocols, Privacy and Data Protection, Multimedia Security, Digital Forensics, and Human-Centred Security.

The Department is research-led with around 70 RAs and PhD students, and is attracting growing research support from funding bodies such as the UK Research Councils, UK Technology Strategy Board (TSB), the EU-IST, and also private foundations e.g. The Leverhulme Trust. Major IT, telecommunication, defence and security organisations are sponsoring research in the Department.

Applicants at the Lecturer level should have a relevant PhD, a developing track record in publication with demonstrable high potential in high-quality research and teaching. Applicants at the Senior Lecturer level will have an international research profile, a significant track record of high-quality publications in leading journals and conference proceedings, and experience in a leadership or development role in high quality teaching. A record in attracting research funding would be an advantage.

Closing date for applications is 30 June 2014. The post is to start in September 2014 or as soon as possible thereafter.

*18:17* [Pub][ePrint]
How Secure is Deterministic Encryption?, by Mihir Bellare and Rafael Dowsley and Sriram Keelveedhi
This paper presents three curious findings about deterministic public-key encryption (D-PKE) that further our understanding of its security, in particular because of the contrast with standard, randomized public-key encryption (R-PKE):(1) It would appear to be a triviality, for any primitive, that security in the standard model implies security in the random-oracle model, and it is certainly true, and easily proven, for R-PKE. For D-PKE it is not clear and depends on details of the definition. In particular we can show it in the non-uniform case but not in the uniform case.

(2) The power of selective-opening attacks (SOA) comes from an adversary\'s ability, upon corrupting a sender, to learn not just the message but also the coins used for encryption. For R-PKE, security is achievable. For D-PKE, where there are no coins, one\'s first impression may be that SOAs are vacuous and security should be easily achievable. We show instead that SOA-security is impossible, meaning no D-PKE scheme can achieve it.

(3) For R-PKE, single-user security implies multi-user security, but we show that there are D-PKE schemes secure for a single user and insecure with two users.

*18:17* [Pub][ePrint]
Efficient Adaptively Secure IBBE from Standard Assumptions, by Somindu C. Ramanna and Palash Sarkar
This paper describes the first construction of efficient identity-based broadcast encryption (IBBE) schemes whichcan be proved secure against adaptive-identity attacks based on standard assumptions. The constructions are

obtained by extending the currently known most efficient identity-based encryption scheme proposed by Jutla

and Roy in 2013. Ciphertext size and user storage compare favourably to previously known constructions. The

new constructions fill both a practical and a theoretical gap in the literature on efficient IBBE schemes.