*18:17* [Pub][ePrint]
Anon-Pass: Practical Anonymous Subscriptions, by Michael Z. Lee and Alan M. Dunn and Jonathan Katz and Brent Waters and Emmett Witchel
We present the design, security proof, and implementation of an anonymous subscription service. Users register for the service by providing some form of identity, which might or might not be linked to a real-world identity such as a credit card, a web login, or a public key. A user logs on to the system by presenting a credential derived from information received at registration. Each credential allows only a single login in any authentication window, or epoch. Logins are anonymous in the sense that the service cannot distinguish which user is logging in any better than random guessing. This implies unlinkability of a user across different logins.We find that a central tension in an anonymous subscription service is the service provider\'s desire for a long epoch (to reduce server-side computation) versus users\' desire for a short epoch (so they can repeatedly \"re-anonymize\" their sessions). We balance this tension by having short epochs, but adding an efficient operation for clients who do not need unlinkability to cheaply re-authenticate themselves for the next time period.

We measure performance of a research prototype of our pro- tocol that allows an independent service to offer anonymous access to existing services. We implement a music service, an Android-based subway-pass application, and a web proxy, and show that adding anonymity adds minimal client latency and only requires 33 KB of server memory per active user.

*18:17* [Pub][ePrint]
Instantaneous Frequency Analysis, by Roman Korkikian and David Naccache and Guilherme Ozari de Almeida
This paper investigated the use of instantaneous frequency (IF)instead of power amplitude and power spectrum in side-channel analysis.

By opposition to the constant frequency used in Fourier Transform, instantaneous frequency reflects local phase differences and allows detecting frequency variations. These variations reflect the processed binary data and are hence cryptanalytically useful. IF exploits the fact that after higher power drops more time is required to restore power back to its nominal value. Whilst our experiments reveal IF does not bring specific benefits over usual power attacks when applied to unprotected designs, IF allows to obtain much better results in the presence of amplitude modification

countermeasures.

*18:17* [Pub][ePrint]
Generic Constructions of Secure-Channel Free Searchable Encryption with Adaptive Security, by Keita Emura and Atsuko Miyaji and Mohammad Shahriar Rahman and Kazumasa Omote
For searching keywords against encrypted data, the public key encryption scheme with keyword search (PEKS), and its an extension called secure-channel free PEKS (SCF-PEKS) have been proposed. In SCF-PEKS, a receiver makes a trapdoor for a keyword, and uploads it on a server. A sender computes an encrypted keyword, and sends it to the server. The server executes the searching procedure (called the test algorithm, which takes as inputs an encrypted keyword, trapdoor, and secret key of the server).

In this paper, we extend the security of SCF-PEKS, calling it adaptive SCF-PEKS, wherein an adversary (modeled as a ``malicious-but-legitimate\" receiver) is allowed to issue test queries \\emph{adaptively}, and show that adaptive SCF-PEKS can be generically constructed by anonymous identity-based encryption (anonymous IBE) only. That is, for constructing adaptive SCF-PEKS we need not require any additional cryptographic primitive when compared to the Abdalla et al. PEKS construction (J. Cryptology 2008), even though adaptive SCF-PEKS requires additional functionalities. Note that our generic construction needs to apply the KEM/DEM framework (a.k.a. hybrid encryption), where KEM stands for key encapsulation mechanism, and DEM stands for data encapsulation mechanism. We also show that there is a class of anonymous IBE that can be applied for constructing adaptive SCF-PEKS without using hybrid encryption, and propose an adaptive SCF-PEKS construction based on this IBE. Although our second construction is not fully generic, it is efficient compared to the first, since we can exclude the DEM part. Finally, we instantiate an adaptive SCF-PEKS scheme (via our second construction) that achieves a similar level of efficiency for the costs of the test procedure and encryption, compared to the (non-adaptive secure) SCF-PEKS scheme by Fang et al. (CANS2009).

*18:17* [Pub][ePrint]
Encryption Schemes with Post-Challenge Auxiliary Inputs, by Tsz Hon Yuen and Ye Zhang and Siu-Ming Yiu
In this paper, we tackle the open problem of proposing a leakage-resilience encryption model that can capture leakage from both the secret key owner and the encryptor, in the auxiliary input model. Existing models usually do not allow adversaries to query more leakageinformation after seeing the challenge ciphertext of the security games. On one hand, side-channel attacks on the random factor (selected by the encryptor) are already shown to be feasible. Leakage from the encryptor should not be overlooked. On the other hand, the technical challenge for allowing queries from the adversary after he sees the ciphertext is to avoid a trivial attack to the system since he can then embed the decryption function as the leakage function (note that we consider the auxiliary input model in which the leakage is modeled as computationally hard-to-invert functions). We solve this problem by defining the post-challenge auxiliary input model in which the family of leakage functions must be defined before the adversary is given the public key. Thus the adversary cannot embed the decryption function as a leakage function after seeing the challenge ciphertext while is allowed to make challenge-dependent queries. This model is able to capture a wider class of real-world side-channel attacks.

To realize our model, we propose a generic transformation from the auxiliary input model to our new post-challenge auxiliary input model for both public key encryption (PKE) and identity-based encryption (IBE). Furthermore, we extend Canetti et al.\'s technique, that converts CPA-secure IBE to CCA-secure PKE, into the leakage-resilient setting. More precisely, we construct a CCA-secure PKE in the post-challenge auxiliary input model, by using strong one-time signatures and strong extractor with hard-to-invert auxiliary inputs, together with a CPA-secure IBE in the auxiliary input model. Moreover, we extend our results to signatures, to obtain fully leakage-resilient signatures with auxiliary inputs using standard signatures and strong extractor with hard-to-invert auxiliary inputs. It is more efficient than the existing fully leakage-resilient signature schemes.

*18:17* [Pub][ePrint]
Elligator: Elliptic-curve points indistinguishable from uniform random strings, by Daniel J. Bernstein and Anna Krasnova and Tanja Lange
Censorship-circumvention tools are in an arms race against censors. The censors study all traffic passing into and out of their controlled sphere, and try to disable censorship-circumvention tools without completely shutting down the Internet. Tools aim to shape their traffic patterns to match unblocked programs, so that simple traffic profiling cannot identify the tools within a reasonable number of traces; the censors respond by deploying firewalls with increasingly sophisticated deep-packet inspection.Cryptography hides patterns in user data but does not evade censorship if the censor can recognize patterns in the cryptography itself. In particular, elliptic-curve cryptography often transmits points on known elliptic curves, and those points are easily distinguishable from uniform random strings of bits.

This paper introduces high-security high-speed elliptic-curve systems in which elliptic-curve points are encoded so as to be indistinguishable from uniform random strings.