Dual Form Signatures: An Approach for Proving Security from Static Assumptions, by Michael Gerbush and Allison Lewko and Adam O\'Neill and Brent Waters
In this paper, we introduce the abstraction of Dual Form Signatures as a useful framework for proving security (existential unforgeability) from static assumptions for schemes with special structure that are used as a basis of other cryptographic protocols and applications. We demonstrate the power of this framework by proving security under static assumptions for close variants of pre-existing schemes:
\\item the LRSW-based Camenisch-Lysyanskaya signature scheme
\\item the identity-based sequential aggregate signatures of Boldyreva, Gentry, O\'Neill, and Yum.
The Camenisch-Lysyanskaya signature scheme was previously proven only under the interactive LRSW assumption, and our result can be viewed as a static replacement for the LRSW assumption. The scheme of Boldyreva, Gentry, O\'Neill, and Yum was also previously proven only under an interactive assumption that was shown to hold in the generic group model. The structure of the public key signature scheme underlying the BGOY aggregate signatures is quite distinctive, and our work presents the first security analysis of this kind of structure under static assumptions.
We view our work as enhancing our understanding of the security of these signatures, and also as an important step towards obtaining proofs under the weakest possible assumptions.
Finally, we believe our work also provides a new path for proving security of signatures with embedded structure. Examples of these include:
attribute-based signatures, quoteable signatures, and signing group elements.
Post-Doc, Technical University Denmark, Copenhagen
Postdoc within the area of Symmetric Cryptography
Applications are invited for an 18 month (with a possible extension of 6 months) Postdoc position at the Danish-Chinese Center for Applications of Algebraic Geometry in Coding and Cryptology. The center is located at the Department of Mathematics at the Technical University of Denmark. The position is available from July 2012 or earliest thereafter.
The candidate should have a PhD degree or academic qualifications equivalent to the PhD level, and should have a strong background in symmetric cryptography. This is usually demonstrated by having publications in well established journals and/or conferences.
As it is essential for the project to establish research connections with China, applicants are expected to be willing to actively establish these connections. This ideally includes one or several visits to the East China Normal University.
Salary and terms of employment
The appointment will be based on the collective agreement with the Confederation of Professional Associations. The allowance will be agreed with the relevant union.
The period of employment is 18 months.
Further information about the project may be reached by contacting Associate Professor Gregor Leander, tel. (+45) 4525 3055, g.leander (at) mat.dtu.dk
We must have your online application no later than 31 May 2012. See http://www.mat.dtu.dk/English/Om_instituttet/Matjob/JobOversigt.aspx?guid=3ba4aac2-107e-4958-886a-daa25bb444e4 for details.
Research Fellow, Nanyang Technological University, Singapore
Physical Analysis and Cryptographic Engineering (PACE) Labs at Nanyang Technological University are seeking 2 Research Scientists in the area of side-channel and fault attacks. The newly founded lab is dedicated to all aspects of side-channel and fault attacks and offers brand-new facilities, a very diverse international research environment, and the opportunity to undertake independent research.
Candidates shall hold, or expect to obtain, a Ph.D. in Computer Sciences, Electrical Engineering, Mathematics or a related field. A solid background in one or several areas of Information Theory, Digital Signal Processing, Statistics, Mutual Information Analysis, DEMA attacks, fault attacks, practical measurements, lightweight implementations (software and/or hardware) would be considered an advantage.
Starting date is in May 2012 and funding is available for 3 years, thus the contract will be for up to 3 years (depending on the successful candidates\' ability to start working in Singapore).
Salaries are competitive and are determined according to the successful applicants\' accomplishments, experience and qualifications.
Interested applicants with a strong publication record in the fields of side-channel and/or fault attacks are encouraged to submit their application including:
1) cover letter,
2) detailed CV,
3) filled personal particulars form*, and
4) names/contact emails of 2 references
to Prof. Axel Poschmann aposchmann (at) ntu.edu.sg.
Review of applications starts immediately and will continue until positions are filled.
* accesible via http://www.spms.ntu.edu.sg/MAS/Document/Graduate/Personal%20particulars%20form_research%20staff.doc
Logic Minimization Techniques with Applications to Cryptology
Abstract A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the nonlinearity of a circuit—as measured by the number of nonlinear gates it contains—is reduced. The second step reduces the number of gates in the linear components of the already reduced circuit. The technique can be applied to arbitrary combinational logic problems, and often yields improvements even after optimization by standard methods has been performed. In this paper we show the results of our technique when applied to the S-box of the Advanced Encryption Standard (FIPS in Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001). We also show that, in the second step, one is faced with an NP-hard problem, the Shortest Linear Program (SLP) problem, which is to minimize the number of linear operations necessary to compute a set of linear forms. In addition to showing that SLP is NP-hard, we show that a special case of the corresponding decision problem is Max SNP-complete, implying limits to its approximability. Previous algorithms for minimizing the number of gates in linear components produced cancellation-free straight-line programs, i.e., programs in which there is no cancellation of variables in GF(2). We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to nontrivial inputs. The straight-line programs produced by our techniques are not always cancellation-free. We have experimentally verified that, for randomly chosen linear transformations, they are significantly smaller than the circuits produced by previous algorithms.
- Content Type Journal Article
- Pages 1-33
- DOI 10.1007/s00145-012-9124-7
- Joan Boyar, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark
- Philip Matthews, Aarhus University, Aarhus, Denmark
- René Peralta, Information Technology Laboratory, NIST, Gaithersburg, MD, USA
From: Thu, 03 May 2012 07:37:37 GMT
- Journal Journal of Cryptology
- Online ISSN 1432-1378
- Print ISSN 0933-2790