*00:17* [Pub][ePrint]
One-Sided Adaptively Secure Two-Party Computation, by Carmit Hazay and Arpita Patra
Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures scenarios in which the attacker chooses which party to corrupt based on the protocol communication. It further captures real-world scenarios where ``hackers\'\' actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. The former is because the theoretical understanding of this setting is not yet profound and important questions are still unresolved; a notable example is the question regarding the feasibility of constant round adaptively secure protocols. From practical viewpoint, generic adaptively secure protocols are far more complicated and less efficient than static protocols.A primary building block in designing adaptively secure protocols is a non-committing encryption or NCE that implements secure communication channels in the presence of adaptive corruptions. Current NCE constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that is linear in the circuit size (or otherwise the protocol is not round efficient). As a result the number of public key operations is inflated and depends on the circuit size as well.

In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, which we believe is the right security notion in the two-party setting. We study the feasibility of (1) NCE with constant number of public key operations for any message space. (2) Oblivious transfer with constant number of public key operations for any sender\'s input space, and (3) constant round secure computation protocols with a number of NCE calls, and an overall number of public key operations, that are independent of the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions, while this is not the case for fully adaptive security (where both parties may get corrupted).

*03:17* [Pub][ePrint]
Random Projections, Graph Sparsification, and Differential Privacy, by Jalaj Upadhyay
This paper initiates the study of preserving {\\em differential privacy} ({\\sf DP}) when the data-set is sparse. We study the problem of constructing efficient sanitizer that preserves {\\sf DP} and guarantees high utility for answering cut-queries on graphs. The main motivation for studying sparse graphs arises from the empirical evidences that social networking sites are sparse graphs. We also motivate and advocate the necessity to include the efficiency of sanitizers, in addition to the utility guarantee, if one wishes to have a practical deployment of privacy preserving sanitizers. We show that the technique of Blocki et al. (FOCS2012) ({\\sf BBDS}) can be adapted to preserve {\\sf DP} for answering cut-queries on sparse graphs, with an asymptotically efficient sanitizer than~{\\sf BBDS}. We use this as the base technique to construct an efficient sanitizer for arbitrary graphs. In particular, we use a preconditioning step that preserves the spectral properties (and therefore, size of any cut is preserved), and then apply our basic sanitizer. We first prove that our sanitizer preserves {\\sf DP} for graphs with high conductance. We then carefully compose our basic technique with the modified sanitizer to prove the result for arbitrary graphs. In certain sense, our approach is complementary to the Randomized sanitization for answering cut queries (Gupta, Roth, and Ullman, TCC 2012): we use graph sparsification, while Randomized sanitization uses graph densification.

Our sanitizers almost achieves the best of both the worlds with the same privacy guarantee, i.e., it is almost as efficient as the most efficient sanitizer and it has utility guarantee almost as strong as the utility guarantee of the best sanitization algorithm.

We also make some progress in answering few open problems by {\\sf BBDS}. We make a combinatorial observation that allows us to argue that the sanitized graph can also answer $(S,T)$-cut queries with same asymptotic efficiency, utility, and {\\sf DP} guarantee as our sanitization algorithm for $S, \\bar{S}$-cuts. Moreover, we achieve a better utility guarantee than Gupta, Roth, and Ullman (TCC 2012). We give further optimization by showing that fast Johnson-Lindenstrauss transform of Ailon and Chazelle~\\cite{AC09} also preserves {\\sf DP}.

*03:17* [Pub][ePrint]
The Special Number Field Sieve in $\\F _{p^{n}}$, Application to Pairing-Friendly Constructions, by Antoine Joux and Cécile Pierrot
In this paper, we study thediscrete logarithm problem in finite fields related to pairing-based

curves. We start with a precise analysis of the

state-of-the-art algorithms for computing discrete logarithms that

are suitable for finite fields related to pairing-friendly

constructions. To improve upon these algorithms, we extend the

Special Number Field Sieve to compute discrete logarithms in

$\\F_{p^{n}}$, where $p$ has an adequate sparse representation. Our

improved algorithm works for the whole range of applicability of the

Number Field Sieve.

*03:17* [Pub][ePrint]
Cryptanalysis of GOST R Hash Function, by Zongyue Wang, Hongbo Yu, Xiaoyun Wang
GOST R is the hash function standard of Russia. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2^{176} and the memory requirement is 2^{128} bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. Moreover, a method to construct k collisions on 512-bit version of GOST R is given which show the weakness of the structure used in GOST R. To the best of our knowledge, these are the first results on GOST R.