*22:17* [Pub][ePrint]
The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, by Razvan Barbulescu and Cécile Pierrot
In this paper, we study the discrete logarithm problem in medium andhigh characteristic finite fields. We propose a variant of the Number Field Sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3, (128/9)^{1/3})$ to $L_{p^n}(1/3, (2^{13} /3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n} (1/3, (64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26\\sqrt{13})/27))^{1/3})$ in the high characteristic case.

*22:17* [Pub][ePrint]
Outsourcing Private RAM Computation, by Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs
We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client\'s work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server\'s work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database.Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.

*04:17* [Pub][ePrint]
Statistical Concurrent Non-Malleable Zero Knowledge, by Claudio Orlandi and Rafail Ostrovsky and Vanishree Rao and Amit Sahai and Ivan Visconti
The notion of Zero Knowledge introduced by Goldwasser, Micali, and Rackoff in STOC 1985 is fundamental in Cryptography. Motivated by conceptual and practical reasons, this notion has been explored under stronger definitions. We will consider the following two main strengthened notions.-- Statistical Zero Knowledge: here the zero-knowledge property will last forever, even in case in future the adversary will have unlimited power.

-- Concurrent Non-Malleable Zero Knowledge: here the zero-knowledge property is combined with non-transferability and the adversary fails in mounting a concurrent man-in-the-middle attack aiming at transferring zero-knowledge proofs/arguments.

Besides the well-known importance of both notions, it is still unknown whether one can design a zero-knowledge protocol that satisfies both notions simultaneously.

In this work we shed light on this question in a very strong sense. We show a {\\em statistical concurrent non-malleable} zero-knowledge argument system for NP with a {\\em black-box} simulator-extractor.

*04:17* [Pub][ePrint]
Untappable communication channels over optical fibers from quantum-optical noise, by Geraldo A. Barbosa and Jeroen van de Graaf
Coherent light, as produced by lasers, gives rise to an intrinsic noise, known as quantum noise, optical noise or shot noise. AlphaEta is a protocol which exploits this physical phenomenon to obtain secure data encryption or key distribution over a fiber-optic channelin the presence of an eavesdropper. In this paper we focus on the cryptographic aspects of AlphaEta and its variants. Moreover, we propose a new protocol for which we can provide a rigorous proof

that the eavesdropper obtains neglible information. In comparison to single-photon quantum cryptography, AlphaEta provide much higher throughputs combined with a well-known technology.

*16:17* [Pub][ePrint]
On the Phase Space of Block-Hiding Strategies, by Assaf Shomer
We calculate the probability of success of block-hiding mining strategies in bitcoin-like networks.These strategies involve building a secret branch of the block-tree and publishing it opportunistically, aiming to replace the top of the main branch and rip the reward associated with the secretly mined blocks. We identify two types of block-hiding strategies and chart the parameter space where those are more beneficial than the standard mining strategy described in Nakamoto\'s paper.

Our analysis suggests a generalization of the notion of the relative hashing power as a measure for a miner\'s influence on the network. Block-hiding strategies are beneficial only when this measure of influence exceeds a certain threshold.