*16:17* [Pub][ePrint]
Improved Differential Analysis of Block Cipher PRIDE, by Qianqian Yang and Lei Hu and Siwei Sun and Kexin Qiao and Ling Song and Jinyong Shan and Xiaoshuang Ma
In CRYPTO 2014 Albrecht \\emph{et al.} brought in a 20-round iterative lightweight blockcipher PRIDE which is based on a good linear layer for achieving a

tradeoff between security and efficiency. A recent

analysis is presented by Zhao \\emph{et al.}. Inspired by their work, we use an

automatic search method to find out 56 iterative differential characteristics of PRIDE, containing 24

1-round iterative characteristics, based on three of them we construct a 15-round differential and perform a differential attack on the 19-round PRIDE, with data,

time and memory

complexity of $2^{62}$, $2^{63}$ and $2^{71}$ respectively.

*16:17* [Pub][ePrint]
Publicly Verifiable Non-Interactive Arguments for Delegating Computation, by Omer Paneth and Guy N. Rothblum
We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier\'s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis.As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier\'s complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

*16:17* [Pub][ePrint]
Public Verification of Private Effort, by Giulia Alberini and Tal Moran and Alon Rosen
We introduce a new framework for polling responses from a large population. Our framework allows gathering information without violating the responders\' anonymity and at the same time enables public verification of the poll\'s result. In contrast to prior approaches to the problem, we do not require trusting the pollster for faithfully announcing the poll\'s results, nor do we rely on strong identity verification. We propose an ``effort based\'\' polling protocol whose results can be publicly verified by constructing a ``responder certification graph\'\' whose nodes are labeled by responders\' replies to the poll, and whose edges cross-certify that adjacent nodes correspond to honest participants. Cross-certification is achieved using a newly introduced (privately verifiable) ``Private Proof of Effort\'\' (PPE). In effect, our protocol gives a general method for converting privately-verifiable proofs into a publicly-verifiable protocol. The soundness of the transformation relies on expansion properties of the certification graph.

Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes crypto-currencies, political polling, elections, recommendation systems, viewer voting in TV shows, and prediction markets.