*09:17* [Pub][ePrint]
The Feasibility of Outsourced Database Search in the Plain Model, by Carmit Hazay and Hila Zarosim
The problem of securely outsourcing computation to an untrusted server gained momentum with the recent penetration of cloud computing services. The ultimate goal in this setting is to design efficient protocols that minimize the computational overhead of the clients and instead rely on the extended resources of the server. In this paper, we focus on the outsourced database search problem which is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases, that may contain confidential data. This functionality is described in two phases: (1) setup phase and (2) query phase. The main goal is to minimize the parties workload in the query phase so that it is proportional to the query size and its corresponding response.Our starting point is the semi-honest protocol from FaustHV13 (ICALP 2013) that offers a simulation based secure protocol for outsourced pattern matching in the random oracle setting with optimal workload. In this work we study whether the random oracle is necessary for protocols with minimal interaction that meet the optimal communication/computation bounds in the query phase. We answer this question negatively and demonstrate a lower bound on the communication or the computational overhead in this phase. We further abstract the security properties of the underlying cryptographic primitive that enables to obtain private outsourced database search with minimal interaction. For a large class of search functionalities the communication complexity of our protocol meets the above lower bound.

*09:17* [Pub][ePrint]
A Note on Quantum Security for Post-Quantum Cryptography, by Fang Song
Shor\'s quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against \\emph{quantum} attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are ``quantum-friendly\'\'. We characterize sufficient conditions such that a classical reduction can be ``lifted\'\' to the quantum setting.

We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in~\\cite{BDH11} carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in~\\cite{BDH11} is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model~\\cite{Zha12ibe} and the simple hybrid arguments framework in~\\cite{HSS11}) can be reformulated under our unified framework.

*03:15* [Job][New]
Ph.D. student in Theoretical Computer Science, *CWI / University of Amsterdam*
The Institute for Logic, Language & Computation (ILLC) at the University of Amsterdam, and the Centrum Wiskunde & Informatica (CWI) are looking for a PhD candidate in the area of quantum cryptography.

The aim of the PhD project is to develop new quantum-cryptographic protocols (beyond the task of key distribution) and explore their limitations. An example of an active research is position-based quantum cryptography. Another aspect is to investigate the security of classical cryptographic schemes against quantum adversaries (post-quantum cryptography).

Full-time appointment is on a temporary basis for a period of four years. For the first two years the PhD candidate will be appointed at the ILLC, University of Amsterdam, initially for a period of 18 months and then, on positive evaluation, for a further six months. During the final two years, the PhD candidate will be employed by the Centrum Wiskunde and Informatica (CWI). On the basis of a full-time appointment (38 hours per week), the gross monthly salary amounts to €2,083 during the first year, rising to €2,664 during the fourth year.

Requirements:

- a Master\'s degree with excellent grades in computer science, mathematics or physics with outstanding results or a comparable degree;
- candidates with a strong background in cryptography or quantum information are preferred;
- demonstrated research abilities by completion of an (undergraduate) research project;
- good academic writing and presentation skills;
- good social and organisational skills.

*21:17* [Pub][ePrint]
HIMMO security, by Oscar Garcia-Morchon and Ronald Rietman and Ludo Tolhuizen and Domingo Gomez-Perez and Jaime Gutierrez
This paper describes HIMMO, an identity-based pairwise symmetric key establishment method. The acronym \"HIMMO\" is derived from two interpolation problems that are essential for thesecurity of the scheme: the HI problem, which is related to the

well-known noisy interpolation problem, and the apparently novel MMO problem, presented at ISSAC\'14.

HIMMO is non-interactive: nodes in a network can directly generate a common key without exchanging messages. Each node in the network has an identifier, and a trusted third pay (TTP) provides it with secret keying material---linked to the node identifier---in a secure way.

A node that wishes to communicate with another node uses its own secret keying material and the identity of the other node to generate a common pairwise key.

HIMMO allows for efficient operation with respect to both the amount of stored keying material and the key computation time, which is especially relevant for resource-constrained devices.

It has similar operational characteristics as previous ID-based symmetric key establishment methods, but has superior resistance against attacks in which multiple colluding or compromised nodes co-operate to obtain information on keys between other non-colluding or non-compromised nodes.

*21:17* [Pub][ePrint]
Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures, by Ahto Buldas and Risto Laanoja and Peeter Laud and Ahto Truu
We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \\emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\\EXT$ that is bounded in the sense that for any efficiently computable query string $\\alpha$, the number of outputs $y$ for which $\\EXT(y,\\alpha)$ succeeds does not exceed the number of queries in $\\alpha$. We show that blockcipher based MD-hash functions with rate-1 compression functions (such as Davies-Meyer and Miyaguchi-Preneel) of both type I and type II are BPrA. We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \\log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C=2^{50}$, the previous proofs require $n=302$ output bits, while the new proof requires $n=204$ output bits.