*05:22* [Pub][ePrint]
Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction, by S. Dov Gordon and Tal Malkin and Mike Rosulek and Hoeteck Wee
Halevi, Lindell, and Pinkas (CRYPTO 2011) recently proposed a model for secure computation that captures communication patterns that arisein many practical settings, such as secure computation on the web. In their model, each party interacts only once, with a single centralized server. Parties do not interact with each other; in fact, the parties need not even be online simultaneously.

In this work we present a suite of new, simple and efficient protocols for secure computation in this \"one-pass\" model. We give protocols that obtain optimal privacy for the following general tasks:

-- Evaluating any multivariate polynomial $F(x_1, \\ldots ,x_n)$ (modulo a large RSA modulus N), where the parties each hold an input $x_i$.

-- Evaluating any read once branching program over the parties\' inputs.

As a special case, these function classes include all previous functions for which an optimally private, one-pass computation was known, as well as many new functions, including variance and other statistical functions, string matching, second-price auctions, classification algorithms and some classes of finite automata

and decision trees.

*05:22* [Pub][ePrint]
Chosen Ciphertext Secure (CCS): Stateful Symmetric Key CCA Encryption with Minimal Ciphertext Expansion, by Jonathan Trostle
In some wireless environments, minimizing the size of messages is paramount due to the resulting significant energy savings. Wepresent a new stateful symmetric encryption scheme: CCS or Chosen

Ciphertext Secure scheme. CCS has the property that modifications to

the ciphertext randomizes the resulting plaintext. Using this property,

we prove the scheme is CCA2 secure. Thus we obtain CCA2 encryption

schemes with minimal ciphertext expansion which are applicable to resource constrained wireless environments. For protocols that send short messages, our scheme is similar to Counter with CBC-MAC (CCM) for

computation but has much shorter messages (since we can use much

smaller or no MAC tags) for a similar level of security. A key idea is

that various protocol fields in the underlying plaintext act as an authentication tag given changes to the message ciphertext. To the best of our knowledge, CCS is the first scheme that achieves CCA2 security with only 2-3 bytes of ciphertext expansion.

*05:22* [Pub][ePrint]
Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters, by Yu Yu
We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions: (1) For any known-regular one-way function (on $n$-bit inputs) that is known to be $\\eps$-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length $\\Theta(n)$ by making a single call to the underlying one-way function.

(2) For any unknown-regular one-way function with known $\\eps$-hardness, we give a new construction with seed length $\\Theta(n)$ and $O(n/\\log{(1/\\eps)})$ calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha [FOCS 2012].

Both constructions require the knowledge about $\\eps$, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length $\\tilde{O}(n)$ and $\\tilde{O}(n/\\log{n})$ calls, where $\\tilde{O}$ omits a factor that can be made arbitrarily close to constant (e.g. $\\log\\log\\log{n}$ or even less). This improves the \\emph{randomized iterate} approach by Haitner, Harnik and Reingold [CRYPTO 2006] which requires seed length $O(n{\\log}{n})$ and $O(n/\\log{n})$ calls.

*05:22* [Pub][ePrint]
Cryptography Challenges for Computational Privacy in Public Clouds, by Sashank Dara
Computational privacy is a property of cryptographicsystem that ensures the privacy of data (and/or operations)

while being processed at an untrusted server. Cryptography

has been an indispensable tool for computer security but its

readiness for this new generational shift of computing platform

i.e. Cloud Computing is still questionable.

Theoretical constructions like Fully Homomorphic Encryption,

Functional encryption, Server aided Multiparty Computation,

Verifiable Computation, Instance Hiding etc. are few

directions being pursued. These cryptographic techniques solve

Cloud privacy problems at different levels but most of them dont

fit well in overall scheme of things.

We state the privacy requirements for Cloud offerings in

various delivery methods. We discuss the challenges with current

cryptographic techniques being pursued by researchers and show

that they dont cater to blanket cover these privacy requirements.

We urge the need to find generalizations and connections

among these isolated techniques. As this might give more insights

into the underpinnings of Computational Privacy and lead to

better solutions.

*05:22* [Pub][ePrint]
Computing the Rank of Incidence Matrix and Algebraic Immunity of Boolean Functions, by Deepak Kumar Dalai
The incidence matrix between a set of monomials and a set of vectors in $\\F_2$ has a great importance in the study of coding theory, cryptography, linear algebra, combinatorics. The rank of these matrices are very useful while computing algebraic immunity($\\ai$) of Boolean functions in cryptography literature~\\cite{MPC04,DGM04}.Moreover, these matrices are very sparse and well structured. Thus, for aesthetic reason finding rank of these matrices is also very interesting in mathematics.

In this paper, we have reviewed the existing algorithms with added techniques to speed up the algorithms and have proposed some new efficient algorithms for the computation of the rank of incidence matrix and solving the system of equations where the co-efficient matrix is an incidence matrix.Permuting the rows and columns of the incidence matrix with respect to an ordering, the incidence matrix can be converted to a lower block triangular matrix, which makes the computation in quadratic time complexity and linear space complexity. Same technique is used to check and computing low degree annihilators of an $n$-variable Boolean functions in faster time complexity than the usual algorithms. Moreover, same technique is also exploited on the Dalai-Maitra algorithm in~\\cite{DM06} for faster computation. On the basis of experiments, we conjecture that the $\\ai$ of $n$-variable inverse S-box is $\\lfloor\\sqrt{n}\\rfloor + \\lceil\\frac{n}{\\lfloor\\sqrt{n}\\rfloor}\\rceil-2$.

We have also shown the skepticism on the existing fastest algorithm

in~\\cite{ACGKMR06} to find $\\ai$ and lowest degree annihilators of a Boolean function.

*05:22* [Pub][ePrint]
The Potential of Individualized Trusted Root Stores: Minimizing the Attack Surface in the Light of CA Failures, by Johannes Braun and Gregor Rynkowski
The security of most Internet applications relies on underlying public key infrastructures (PKIs) and thus on an ecosystem of certification authorities (CAs). The pool of PKIs responsible for the issuance and the maintenance of SSL certificates, called the Web PKI, has grown extremely large and complex. Herein, each CA is a single point of failure for the security, leading to an attack surface, the size of which is hardly assessable.This paper approaches the issue if and how the attack surface can be reduced in order to reduce the risk of relying on a malicious certificate. In particular we consider the individualization of the set of trusted CAs. We present a tool called Rootopia, which allows to assess the respective part of the Web PKI relevant for a user.

Our analysis of browser histories of 22 Internet users reveals, that the major part of the PKI is completely irrelevant to a single user. The attack surface can be reduced by more than 90%, which shows the potential of the individualization of the set of trusted CAs. Furthermore, all the relevant CAs reside within a small set of countries. Our findings confirm, that we unnecessarily trust in a

huge number of CAs, exposing ourselves to unnecessary risks.

*05:22* [Pub][ePrint]
Towards a Practical Cryptographic Voting Scheme Based on Malleable Proofs, by David Bernhard and Stephan Neumann and Melanie Volkamer
Mixnets are one of the main approaches to deploy secret and verifiable electronic elections.General-purpose verifiable mixnets however suffer from the drawback that the amount of data to be verified by observers increases linearly with the number of involved mix nodes, the number of decryptors, and the number of voters. Chase et al. proposed a verifiable mixnet at Eurocrypt 2012 based on so-called \\emph{malleable proofs} - proofs that do not increase with the number of mix nodes. In work published at PKC 2013, the same authors adapted malleable proofs to verifiable distributed decryption, resulting in a cryptographic voting scheme. As a result, the amount of data to be verified only increases linearly with the number of voters.

However, their scheme leaves several questions open which we address in this paper:

As a first contribution, we adapt a multi-party computation protocol to build a distributed key generation protocol for the encryption scheme underlying their voting scheme. As a second contribution, we decompress their abstract scheme description, identify elementary operations, and count the number of such operations required for mixing and verification. Based on timings for elementary operations, we extrapolate the running times of the mixing and verification processes, allowing us to assess the feasibility of their scheme. For the German case, we conclude that the replacement of postal voting by cryptographic voting based on malleable proofs is feasible on an electoral district level.