*09:17* [Pub][ePrint]
McEliece in the world of Escher, by Danilo Gligoroski and Simona Samardjiska and H{\\aa}kon Jacobsen and Sergey Bezzateev
We present a new family of linear binary codes of length $n$ and dimension $k$ accompanied with a fast list decoding algorithm that can correct up to $\\frac{n}{2}$ errors in a bounded channel with an error density $\\rho$. The decisional problem of decoding random codes using these generalized error sets is NP-complete. Next we use the properties of these codes to design both an encryption scheme and a signature scheme. Although in the open literature there have been several proposals how to produce digital signatures from the McEliece public key scheme, as far as we know, this is the first public key scheme based on codes where signatures are produced in a straightforward manner from the decryption procedure of the scheme. The security analysis of our scheme have two main parts:1. An extensive list of attacks using the Information Set Decoding techniques adopted for our codes; 2. An analysis of the cost of a distinguishing attack based on rank attacks on the generator matrix of the code or on its dual code. Based on this security analysis we suggest some concrete parameters for the security levels in the range of $2^{80} - 2^{128}$.

*09:17* [Pub][ePrint]
Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups, by Jean-Charles Faugère and Ayoub Otmani and Ludovic Perret and Frédéric de Portzamparc and Jean-Pierre Tillich
The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. Forinstance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes.

We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold:

the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D¨ur). This enables not only to present a unified view but also to generalize the construction of QC, QD and even quasi-monoidic (QM) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.

*09:17* [Pub][ePrint]
Graph-theoretic design and analysis of key predistribution schemes, by Michelle Kendall and Keith M. Martin
Key predistribution schemes for resource-constrained networks are methods for allocating symmetric keys to devices in such a way as to provide an efficient trade-off between key storage, connectivity and resilience. While there have been many suggested constructions for key predistribution schemes, a general understanding of the design principles on which to base such constructions is somewhat lacking. Indeed even the tools from which to develop such an understanding are currently limited, which results in many relatively ad hoc proposals in the research literature.It has been suggested that a large edge-expansion coefficient in the key graph is desirable for efficient key predistribution schemes. However, attempts to create key predistribution schemes from known expander graph constructions have only provided an extreme in the trade-off between connectivity and resilience: namely, they provide perfect resilience at the expense of substantially lower connectivity than can be achieved with the same key storage.

Our contribution is two-fold. First, we prove that many existing key predistribution schemes produce key graphs with good expansion.

This provides further support and justification for their use, and confirms the validity of expansion as a sound design principle. Second, we propose the use of incidence graphs and concurrence graphs as tools to represent, design and analyse key predistribution schemes. We show that these tools can lead to helpful insights and new constructions.

*09:17* [Pub][ePrint]
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits, by Dan Boneh and Craig Gentry and Sergey Gorbunov and Shai Halevi and Valeria Nikolaenko and Gil Segev and Vinod
We construct the first (key-policy) attribute-based encryption (ABE) system with short secret keys: the size of keys in our system depends only on the depth of the policy circuit, not its size. Our constructions extend naturally to arithmetic circuits with arbitrary fan-in gates thereby further reducing the circuit depth. Building on this ABE system we obtain the first reusable circuit garbling scheme that produces garbled circuits whose size is the same as the original circuit {\\em plus} an additive $\\mathsf{poly}(\\secp,d)$ bits, where $\\secp$ is the security parameter and $d$ is the circuit depth. Save the additive $\\mathsf{poly}(\\secp,d)$ factor, this is the best one could hope for. All previous constructions incurred a {\\em multiplicative} $\\mathsf{poly}(\\secp)$ blowup. As another application, we obtain (single key secure) functional encryption with short secret keys.We construct our attribute-based system using a mechanism we call {\\em fully key-homomorphic encryption} which is a public-key system that lets anyone translate a ciphertext encrypted under a public-key~$\\vx$ into a ciphertext encrypted under the public-key~$(f(\\vx),f)$ of the same plaintext, for any efficiently computable~$f$. We show that this mechanism gives an ABE with short keys. Security is based on the subexponential hardness of the learning with errors problem.

We also present a second (key-policy) ABE, using multilinear maps, with short ciphertexts: an encryption to an attribute vector~$\\vx$ is the size of $\\vx$ plus $\\mathsf{poly}(\\secp,d)$ additional bits. This gives a reusable circuit garbling scheme where the size of the garbled input is short, namely the same as that of the original input, {\\em plus} a $\\mathsf{poly}(\\secp,d)$ factor.