*21:17* [Pub][ePrint]
A Provably Secure Group Signature Scheme from Code-Based Assumptions, by Martianus Frederic Ezerman and Hyung Tae Lee and San Ling and Khoa Nguyen and Huaxiong Wang
We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than all of the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ($\\approx 2^{24}$ users).The feasibility of the scheme is supported by implementation results.

Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

*21:17* [Pub][ePrint]
Fully Homomorphic Encryption without bootstrapping, by Masahiro Yagisawa
Gentry\'s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In this paper I propose a new fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. The security of the proposed fully homomorphic encryption scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on. The key size of this system and complexity for enciphering/deciphering become to be small enough to handle.

*21:17* [Pub][ePrint]
Randomizing Scalar Multiplication Using Exact Covering Systems of Congruences, by Eleonora Guerrini and Laurent Imbert and Théo Winterhalter
In this paper we present a generic, uniformly randomized scalar multiplication algorithm based on covering systems of congruences, with built-in protections against various side-channel attacks. It has been tailored to resist a recent class of attacks called horizontal attacks. These very powerful attacks exploit some unsuspected weaknesses hidden in most, if not all, highly regular and constant time algorithms.We provide a thorough complexity analysis, several arguments to support its robustness and some encouraging numerical experiments.

*21:17* [Pub][ePrint]
XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees, by Bart Mennink
We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in mathcal{T} and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space mathcal{T} is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in mathcal{T}). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of XPX under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that XPX achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of mathcal{T}. For instance, if t_{12},t_{22} neq 0 and (t_{21},t_{22}) neq (0,1) for all tweaks, XPX is XOR-related-key secure.XPX generalizes Even-Mansour (EM), but also Rogaway\'s XEX based on EM, and tweakable EM used in Minalpher. As such, XPX finds a wide range of applications. We show how our results on XPX directly imply related-key security of the authenticated encryption schemes Pr{\\o}st-COPA and Minalpher, and how a straightforward adjustment to the MAC function Chaskey and to keyed Sponges makes them provably related-key secure.

*21:17* [Pub][ePrint]
How to Build Time-Lock Encryption, by Tibor Jager
Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. A computationally powerful adversary should not be able to learn the message before the deadline. However, even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party.We show how to realize this strong notion of secure encryption by making the additional, very realistic assumption that intermediate results of an iterative, public, large-scale computation --- like the computations performed by users of the popular cryptocurrency Bitcoin --- are publicly available. We use these computations as a \"computational reference clock\", which mimics a physical clock in a computational setting, and show how the computations performed by the reference clock can be \"reused\" to build secure time-lock encryption. A nice feature of this approach is that it can be based on a public computation which is performed \"anyway\" and independent of the time-lock encryption scheme.

We provide the first formal definitions of computational reference clocks and time-lock encryption, and give a proof-of-concept construction which combines a computational reference clock with witness encryption (Garg et al., STOC 2013). We also explain how to construct a computational reference clock based on Bitcoins.

*09:17* [Pub][ePrint]
Shadow-Bitcoin: Scalable Simulation via Direct Execution of Multi-threaded Applications, by Andrew Miller and Rob Jansen
We describe a new methodology that enables the di-rect execution of multi-threaded applications inside of

Shadow, an existing parallel discrete-event network sim-

ulation framework. Our methodology utilizes function

interposition and an application-layer thread library to

emulate the ordinary thread interface to the application.

Using this methodology, we implement a new Shadow

plug-in that directly executes the Bitcoin reference client

software. We describe optimizations that enable scalable

execution of thousands of Bitcoin nodes on a single ma-

chine, and discuss how to model the Bitcoin network for

experimental purposes. Finally, we present novel denial-

of-service attacks against the Bitcoin software, which

exploit low-level implementation artifacts in the Bitcoin

reference client. We demonstrate these attacks using our

methodology, tools, and models.

*09:17* [Pub][ePrint]
On the power of Public-key Functional Encryption with Function Privacy, by Vincenzo Iovino and Qiang Tang and Karol Zebrowski
In CRYPTO 2014 Bitansky et al. introduced a natural strengthening of indistinguishability obfuscation (iO) called strong iO (siO) and showed candidate constructions of such primitive from reasonable assumptions. In this paper, assuming quasi-siO, a natural weakening of siO, for a class of circuits C we construct a public-key functional encryption (FE) scheme with function privacy (FPFE) for the same class C. In the public-key setting known constructions of FPFE were limited to very restricted classes of functionalities like inner-product [Agrawal et al. - PKC 2015] whereas ours can be instantiated for general functionalities. Then, inspired by the Naor\'s transformation from IBE to signature schemes, we construct from FPFE a natural generalization of a signature scheme endowed with functional properties, that we call functional anonymous signature (FAS) scheme. In a FAS (that we show to be equivalent to quasi-siO and FPFE), Alice can sign a circuit C chosen from some distribution D to get a signature $\\sigma$ and can publish a verification key that allows anybody holding a message m to verify that (1) $\\sigma$ is a valid signature of Alice for some (possibly unknown to him) circuit C and (2) C(m) = 1. Beyond unforgeability the security of FAS guarantees that the signature hide as much information as possible about C except what can be inferred from knowledge of D.

As other application of FPFE, we show that it can be used to construct in a black-box way (without using obfuscation directly) FE for randomized functionalities (RFE). Previous constructions of (public-key) RFE relied on iO [Goyal et al. - TCC 2015]. Combining properties of RFE and FAS, we obtain what we call signed probabilistic programs, in which Bob can verify that a (possibly hidden to him) probabilistic program P was signed by Alice and run P on any input but can not maliciously choose its random coins. Furthermore, our constructions of FPFE and RFE naturally generalize to the multi-inputs setting. Finally, we present a general picture of the relations among all these related primitives. One of the key points that such implications draw is that Attribute-based Encryption with function privacy implies FE, a notable fact that sheds light on the importance and power of function privacy for FE.