*09:17* [Pub][ePrint]
Compositions of linear functions and applications to hashing, by Vladimir Shpilrain and Bianca Sosnovski
Cayley hash functions are based on a simple idea of using a pair of(semi)group elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with linear functions of one variable over F_p. The corresponding hash functions are very efficient, in particular, due to the fact that a linear function is determined by its values at two points. Thus, we show that hashing a bit string of length $n$ with our method requires just 2n multiplications in F_p, but with particular pairs of linear functions that we suggest, one does not need to perform any multiplications at all. We also give explicit lower bounds on the

length of collisions for hash functions corresponding to these particular pairs of linear functions over F_p.

*09:17* [Pub][ePrint]
Provable Virus Detection: Using the Uncertainty Principle to Protect Against Malware, by Richard J. Lipton and Rafail Ostrovsky and Vassilis Zikas
Protecting software from malware injection is the holy grail of modern computer security. Despite intensive efforts by the scientific and engineering community, the number of successful attacks continues to increase. We have a breakthrough novel approach to provably detect malware injection. The key idea is to use the very insertion of the malware itself to allow for the systems to detect it. This is, in our opinion, close in spirit to the famous Heisenberg Uncertainty Principle. The attackers, no matter how clever, no matter when or how they insert their malware, change the state of the system they are attacking. This fundamental idea is a game changer. And our system does not rely on heuristics; instead, our scheme enjoys the unique property that it is proved secure in a formal and precise mathematical sense and with minimal and realistic CPU modification achieves strong provable security guarantees. Thus, we anticipate our system and formal mathematical security treatment to open new directions in software protection.

*09:17* [Pub][ePrint]
Linear Cryptanalysis of Reduced-Round SIMECK Variants, by Nasour Bagheri
SIMECK is a family of 3 lightweight block ciphers designed by Yang et al. Theyfollow the framework used by Beaulieu et al. from the United States National Security Agency

(NSA) to design SIMON and SPECK. A cipher in this family with K-bit key and N-bit block is

called SIMECKN=K.We show that the security of this block cipher against linear cryptanalysis

is not as good as its predecessors SIMON. More precisely, while the best known linear attack

for SIMON32/64, using algorithm 1 of Matsui, covers 13 rounds we present a linear attack in

this senario which covers 14 rounds of SIMECK32/64. Similarly, using algorithm 1 of Matsui,

we present attacks on 19 and 22 rounds of SIMECK48/96 and SIMECK64/128 respectively,

compare them with known attacks on 16 and 19 rounds SIMON48/96 and SIMON64/128

respectively. In addition, we use algorithm 2 of Matsui to attack 18, 23 and 27 rounds of

SIMECK32/64, SIMECK48/96 and SIMECK64/128 respectively, compare them with known

attacks on 18, 19 and 21 rounds SIMON32/64, SIMON48/96 and SIMON64/128 respectively.

*09:17* [Pub][ePrint]
Efficient Asynchronous Accumulators for Distributed PKI, by Leonid Reyzin and Sophia Yakoubov
Cryptographic accumulators are a tool for compact set representation and secure set membership proofs. When an element is added to a set by means of an accumulator, a membership witness is generated. This witness can later be used to prove the membership of the element. Typically, the membership witness has to be synchronized with the accumulator value, and to be updated every time another element is added to the accumulator. In this work we propose an accumulator that, unlike any prior scheme, does not require strict synchronization.In our construction a membership witness needs to be updated only a logarithmic number times in the number of subsequent element additions. Thus, an out-of-date witness can be easily made current. Vice versa, a verifier with an out-of-date accumulator value can still verify a current membership witness. These properties make our accumulator construction uniquely suited for use in distributed applications, such as blockchain-based public key infrastructures.

*09:17* [Pub][ePrint]
Output-Compressing Randomized Encodings and Applications, by Huijia Lin and Rafael Pass and Karn Seth and Sidharth Telang
We consider randomized encodings (RE) that enable encoding a Turing machine Pi and input x into its ``randomized encoding\'\' \\hat{Pi}(x) in sublinear, or even polylogarithmic, time in the running-time of Pi(x), independent of its output length. We refer to the former as sublinear RE and the latter as compact RE. For such efficient RE, the standard simulation-based notion of security is impossible, and we thus consider a weaker (distributional) indistinguishability-based notion of security: Roughly speaking, we require indistinguishability of \\hat{Pi}_0(x_0) and \\hat{Pi}_0(x_1) as long as Pi_0,x_0 and Pi_1,x_1 are sampled from some distributions such that Pi_0(x_0),Time(Pi_0(x_0)) and Pi_1(x_1),Time(Pi_1(x_1)) are indistinguishable.We first observe that compact RE is equivalent to a variant of the notion of indistinguishability obfuscation (iO)---which we refer to as puncturable iO---for the class of Turing machines without inputs. For the case of circuits, puncturable iO and iO are equivalent (and this fact is implicitly used in the powerful ``punctured program\'\' paradigm by Sahai and Waters [SW13]).

We next show the following:

- Impossibility in the Plain Model: Assuming the existence of subexponentially secure one-way functions, subexponentially-secure sublinear RE does not exists. (If additionally assuming subexponentially-secure iO for circuits we can also rule out polynomially-secure sublinear RE.) As a consequence, we rule out also puncturable iO for Turing machines (even those without inputs).

- Feasibility in the CRS model and Applications to iO for circuits: Subexponentially-secure sublinear RE in the CRS model and one-way functions imply iO for circuits through a simple construction generalizing GGM\'s PRF construction. Additionally, any compact (even with sublinear compactness) functional encryption essentially directly yields a sublinear RE in the CRS model, and as such we get an alternative, modular, and simpler proof of the results of [AJ15,BV15] showing that subexponentially-secure sublinearly compact FE implies iO.

- Applications to iO for Unbounded-input Turing machines: Subexponentially-secure compact RE for natural restricted classes of distributions over programs and inputs (which are not ruled out by our impossibility result, and for which we can give candidate constructions) imply iO for unbounded-input Turing machines. This yields the first construction of iO for unbounded-input Turing machines that does not rely on (public-coin) differing-input obfuscation.

*15:17* [Pub][ePrint]
A Brief Comparison of Simon and Simeck, by Stefan Kölbl and Arnab Roy
Simeck is a new lightweight block cipher design based oncombining the Simon and Speck block cipher. While the design allows a

smaller and more efficient hardware implementation, its security margins are not well understood. The lack of design rationals of its predecessors further leaves some uncertainty on the security of Simeck.

In this work we give a short analysis of the impact of the design changes by comparing the lower bounds for differential and linear characteristics with Simon. We also give a comparison of the effort of finding those bounds, which surprisingly is significant less for Simeck while covering a larger number of rounds.

Furthermore, we provide new differentials for Simeck which can cover

more rounds compared to previous results on Simon. Based on this we

mount key recovery attacks on 19/26/33 rounds of Simeck32/48/64,

which also give insights on the reduced key guessing effort due to the

different set of rotation constants.