PIRMAP: Efficient Private Information Retrieval for MapReduce, by Travis Mayberry and Erik-Oliver Blass and Agnes Hui Chan
Private Information Retrieval (PIR) allows for retrieval of bits from a
database in a way that hides a user\'s access pattern from the server. However, its practicality in a cloud computing setting has recently been questioned. In such a
setting, PIR\'s enormous computation and communication overhead is
expected to outweigh any cost saving advantages of cloud computing.
This paper presents PIRMAP, a practical, highly efficient protocol for
PIR in MapReduce, a widely supported cloud computing API. PIRMAP focuses especially on the retrieval of
large files from the cloud, where it achieves optimal communication
complexity ($O(l)$ for retrieval of an $l$ bit file) with query times significantly faster than previous schemes. To achieve this, PIRMAP arranges files so parallel evaluation can be done during the ``Map\'\' phase
of MapReduce and aggregation can be carried out via an efficient additively
homomorphic encryption scheme in the ``Reduce\'\' phase. PIRMAP has been implemented and tested in Amazon\'s public cloud with total database sizes of up to 1~TByte. Our performance evaluations show that
PIRMAP is more than one order of magnitude cheaper and faster than
``trivial PIR\'\' on Amazon and adds only $20\\%$ overhead to a
theoretical optimal PIR.
An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers, by Martin Albrecht and Gregor Leander
We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32, which is 37 rounds more than previous work. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic.
Since our results still cover less than 1/2 of the cipher, they further strengthen our confidence in KATAN-32\'s resistance against differential attacks.
Analysis and Construction of Efficient RFID Authentication Protocol with Backward Privacy, by Shaohui Wang,Sujuan Liu,Danwei Chen
Privacy of RFID systems is receiving increasing attentions in the
RFID community and an important issue required as to the security of RFID system. Backward privacy means the adversary can not trace the tag later even if he reveals the internal states of the tag sometimes before. In this paper, we analyze two recently proposed RFID authentication schemes: Randomized GPS and Randomized Hashed GPS scheme. We show both of them can not provide backward privacy in Juels and Weis privacy model, which allows the adversary to know whether the reader authenticates the tag successfully or not. In addition, we present a new protocol, called Challenge-Hiding GPS, based on the Schnorr identification scheme. The challenge is hidden from the eavesdropping through the technique of Diffie-Hellman key agreement protocol. The new protocol can satisfy backward privacy, and it has less communication overheads and almost the same computation, compared with the two schemes analyzed.