*13:17* [Pub][ePrint]
On the Non-malleability of the Fiat-Shamir Transform, by Sebastian Faust and Markulf Kohlweiss and Giorgia Azzurra Marson and Daniele Venturi
The Fiat-Shamir transform is a well studied paradigm for removing interaction from public-coin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions.A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.

*13:17* [Pub][ePrint]
Why \"Fiat-Shamir for Proofs\" Lacks a Proof, by Nir Bitansky and Sanjam Garg and Daniel Wichs
The Fiat-Shamir heuristic (CRYPTO \'86) is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover\'s first message to select the verifier\'s challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai (FOCS \'03) shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function.This leaves us with the following interesting possibility: perhaps there exists a hash function that securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if it can fail for some computationally sound arguments. Indeed, the existence of such hash functions has been conjectured by Barak, Lindell and Vadhan (FOCS \'03), who also gave a seemingly reasonable and sufficient condition under which such hash functions exist. However, we do not have any provably secure construction of such hash functions, under any standard assumption such as the hardness of DDH, RSA, QR, LWE, etc.

In this work we give a broad black-box separation result, showing that the security of such hash functions cannot be proved under virtually any standard cryptographic assumption via a black-box reduction.

*13:17* [Pub][ePrint]
On the (In)security of the Fiat-Shamir Paradigm, Revisited, by Dana Dachman-Soled and Abhishek Jain and Yael Tauman Kalai and Adriana Lopez-Alt
The Fiat-Shamir paradigm [CRYPTO\'86] is a heuristic for converting 3-round identification schemes into signature schemes, and more generally, for collapsing rounds in public-coin interactive protocols. This heuristic is very popular both in theory and in practice, and many researchers have studied its security (and insecurity).In this work, we continue this study. As our main result, we show that for many well studied interactive *proofs* (and arguments) the soundness of the Fiat-Shamir heuristic cannot be proven via a black-box reduction to any falsifiable assumption. Previously, the insecurity of this paradigm was exemplified only when applied to interactive arguments (as opposed to proofs).

Using similar techniques, we also show a black-box impossibility result for Micali\'s CS-proofs [FOCS\'94]. Namely, we prove that there exist PCPs such that for \"sufficiently hard\'\' NP languages, Micali\'s CS-proof cannot be proven sound via black-box reduction to any falsifiable assumption.

These results are obtained by extending the impossibility of two-message zero knowledge protocols due to Goldreich and Oren [J. Cryptology\'94].

*13:17* [Pub][ePrint]
Cryptanalysis of WIDEA, by Gaëtan Leurent
WIDEA is a family of block ciphers designed by Junod and Macchetti in2009 as an extension of IDEA to larger block sizes (256 and 512 bits for

the main instances WIDEA-4 and WIDEA-8) and key sizes (512 and 1024

bits), with a focus on using them to design a hash function. WIDEA is

based on the trusted IDEA design, and was expected to inherit its good

security properties. WIDEA-w is composed of w parallel copies of the

IDEA block cipher, with an MDS matrix to provide diffusion between them.

In this paper we present low complexity attacks on WIDEA based on

truncated differentials. We show a distinguisher for the full WIDEA

with complexity only 2^65, and we use the distinguisher in a

key-recovery attack with complexity w·2^68. We also show a collision

attack on WIDEA-8 if it is used to build a hash function using the

Merkle-Damgård mode of operation.

The attacks exploit the parallel structure of WIDEA and the limited

diffusion between the IDEA instances, using differential trails where

the MDS diffusion layer is never active. In addition, we use structures

of plaintext to reduce the data complexity.

*13:17* [Pub][ePrint]
Calling out Cheaters: Covert Security With Public Verifiability, by Gilad Asharov and Claudio Orlandi
We introduce the notion of covert security with public verifiability, building on the covert security model introduced by Aumann and Lindell (TCC 2007). Protocols that satisfy covert security guarantee that the honest parties involved in the protocol will notice any cheating attempt with some constant probability $\\epsilon$. The idea behind the model is that the fear of being caught cheating will be enough of a deterrent to prevent any cheating attempt. However, in the basic covert security model, the honest parties are not able to persuade any third party (say, a judge) that a cheating occurred.We propose (and formally define) an extension of the model where, when an honest party detects cheating, it also receives a certificate that can be published and used to persuade other parties, without revealing any information about the honest party\'s input. In addition, malicious parties cannot create fake certificates in the attempt of framing innocents.

Finally, we construct a secure two-party computation protocol for any functionality $f$ that satisfies our definition, and our protocol is almost as efficient as the one of Aumann and Lindell. We believe that the fear of a public humiliation or even legal consequences vastly exceeds the deterrent given by standard covert security. Therefore, even a small value of the deterrent factor $\\epsilon$ will suffice in discouraging any cheating attempt.

As the overall complexity of covert security and the parameter $\\epsilon$ are inversely proportional to each other, we believe that the small price to pay to get the public verifiability property on top of covert security will be dominated by the efficiency gain obtained by using a smaller value $\\epsilon$.

*14:09* [Job][New]
PostDoc Position in Lightweight Cryptography for the Internet of Things, *Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg*
*LACS* at the University of Luxembourg is looking for a post-doctoral researcher in the area of lightweight cryptography. The successful candidate will contribute to a research project entitled *Applied Cryptography for the Internet of Things (ACRYPT)*, which is funded by the Fonds National de la Recherche (FNR). Besides conducting high-quality research, the tasks associated with this position include the co-supervision of a Ph.D. student and the dissemination of research results. The ACRYPT project is led by Prof. Alex Biryukov and expected to start in summer 2013.

Candidates must hold a Ph.D. degree (or be in the final stages of a Ph.D. program) in cryptography or a closely related discipline. Applications from researchers with experience in embedded systems security, network security, privacy/anonymity, or mobile/wireless security will also be considered. Preference will be given to candidates with a strong publication record including papers in top-tier crypto/security conference proceedings or journals. Candidates with an interest to conduct leading-edge research in one of the following areas are particularly encouraged to apply:

- Design and analysis of symmetric cryptographic primitives
- Efficient implementation of cryptosystems in hardware and/or software
- Physical attacks (SPA, DPA, fault attacks, etc.) and countermeasures

The position is offered on basis of a fixed-term contract for a duration of three years, which includes a probation period of six months. The monthly salary is roughly 3,600 € net (i.e. after deduction of taxes and social security contributions). Interested candidates are invited to submit their application by email to *lacs.acrypt(at)gmail.com*. The application material should contain a cover letter explaining the candidate\'s motivation and research interests, a detailed CV (including photo), a list of publications, copies of diploma certificates, and names and contact detai

*13:11* [Job][Update]
GCHQ Sponsored PhD Studentship , *Queen’s University Belfast, Centre for Secure Information Technologies (CSIT), UK*
The Government Communications Headquarters (GCHQ) in Cheltenham has agreed in principle to sponsor a PhD/Doctoral Studentship at CSIT, Queens University Belfast in the area of Novel Application of Advanced Machine Learning Techniques for use in Side Channel Analysis Attacks. This GCHQ-sponsored PhD studentship provides funding for 3.5 years and commences on 31 September 2013 with a proposed end date of March/April 2017. GCHQ will cover the costs of university fees and will provide an annual stipend to the student corresponding to the National Minimum Stipend (currently £13,590 per annum) plus an additional sum of £7,000 per annum (both tax free). For comparison this is **equivalent to approx. £26,555 annual salary**. A further £5k of funding will also be available per annum for travel to conferences, collaborative partners, and GCHQ visits.

The studentship is **only open to UK nationals** and the successful candidate will be required to spend in the region of 2 - 4 weeks per year at GCHQ headquarters in Cheltenham. To be considered for this studentship, candidates must **therefore be prepared to undergo GCHQ\\\'s security clearance procedures**.

*13:11* [Job][New]
GCHQ Sponsored PhD Studentship , *Queen’s University Belfast, Centre for Secure Information Technologies (CSIT)*
The Government Communications Headquarters (GCHQ) in Cheltenham has agreed in principle to sponsor a PhD/Doctoral Studentship at CSIT, Queens University Belfast in the area of Novel Application of Advanced Machine Learning Techniques for use in Side Channel Analysis Attacks. This GCHQ-sponsored PhD studentship provides funding for 3.5 years and commences on 31 September 2013 with a proposed end date of March/April 2017. GCHQ will cover the costs of university fees and will provide an annual stipend to the student corresponding to the National Minimum Stipend (currently £13,590 per annum) plus an additional sum of £7,000 per annum (both tax free). For comparison this is **equivalent to approx. £26,555 annual salary**. A further £5k of funding will also be available per annum for travel to conferences, collaborative partners, and GCHQ visits.

The studentship is **only open to UK nationals** and the successful candidate will be required to spend in the region of 2 - 4 weeks per year at GCHQ headquarters in Cheltenham. To be considered for this studentship, candidates must **therefore be prepared to undergo GCHQ\'s security clearance procedures**.