*12:17* [Pub][ePrint]
Practical Secure Logging: Seekable Sequential Key Generators, by Giorgia Azzurra Marson and Bertram Poettering
In computer forensics, log files are indispensable resources that support auditors in identifying and understanding system threats and security breaches. If such logs are recorded locally, i.e., stored on the monitored machine itself, the problem of log authentication arises: if a system intrusion takes place, the intruder might be able to manipulate the log entries and cover her traces. Mechanisms that cryptographically protect collected log messages from manipulation should ideally have two properties: they should be *forward-secure* (the adversary gets no advantage from learning current keys when aiming at forging past log entries), and they should be *seekable* (the auditor can verify the integrity of log entries in any order or access pattern, at virtually no computational cost).We propose a new cryptographic primitive, a *seekable sequential key generator* (SSKG), that combines these two properties and has direct application in secure logging. We rigorously formalize the required security properties and give a provably-secure construction based on the integer factorization problem. We further optimize the scheme in various ways, preparing it for real-world deployment. As a byproduct, we develop the notion of a *shortcut one-way permutation* (SCP), which might be of independent interest.

Our work is highly relevant in practice. Indeed, our SSKG implementation has become part of the logging service of the systemd system manager, a core component of many modern commercial Linux-based operating systems.

*09:17* [Pub][ePrint]
Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption, by Keita Emura and Goichiro Hanaoka and Koji Nuida and Go Ohtake and Takahiro Matsuda and Shota Yamada
In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can \\lq\\lq freely\'\' perform the operation inevitably means that ciphertexts are malleable, and it is well-known that adaptive chosen ciphertext (CCA) security and the homomorphic property can never be achieved simultaneously. In this paper, we show that CCA security and the homomorphic property can be simultaneously handled in situations that the user(s) who can perform homomorphic operations on encrypted data should be controlled/limited, and propose a new concept of homomorphic public-key encryption, which we call \\emph{keyed-homomorphic public-key encryption} (KH-PKE). By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation. To construct KH-PKE schemes, we introduce a new concept, a \\emph{homomorphic transitional universal hash family}, and present a number of KH-PKE schemes through hash proof systems. We also present a practical construction of KH-PKE from the DDH assumption. For $\\ell$-bit security, our DDH-based scheme yields only $\\ell$-bit longer ciphertext size than that of the Cramer-Shoup PKE scheme.

*09:17* [Pub][ePrint]
Key Recovery Attacks on 3-round Even-Mansour, 8-step LED-128, and Full $\\mbox{AES}^{2}$, by Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir
The Even-Mansour (EM) encryption scheme received a lot of attention in the last couple of years due to its exceptional simplicity and tight security proofs.The original $1$-round construction was naturally generalized into $r$-round structures with one key, two alternating keys, and completely independent keys.

In this paper we describe the first key recovery attack on the one-key 3-round version of EM which is asymptotically faster than exhaustive search

(in the sense that its running time is $o(2^n)$ rather than $O(2^n)$ for an $n$-bit key).

We then use the new cryptanalytic techniques in order to improve the best known

attacks on several concrete EM-like schemes. In the case of LED-128, the best previously known attack could only be applied to 6 of its 12 steps. In this paper we develop a new attack which increases the number of attacked steps to 8, is slightly faster than the previous attack on 6 steps, and uses about a thousand times less data.

Finally, we describe the first attack on the full $\\mbox{AES}^{2}$ (which uses two complete AES-128 encryptions and three independent $128$-bit keys, and looks exceptionally strong) which is about 7 times faster than a standard meet-in-the-middle attack, thus violating its security claim.