International Association
for Cryptologic Research

Singular Spectrum Analysis (SSA) is a powerful data decomposition/recomposition technique that can be used to reduce the noise in time series. Compared to existing solutions aiming at similar purposes, such as frequency-based filtering, it benefits from easier-to-exploit intuitions, applicability in contexts where low sampling rates make standard frequency analyses challenging, and the (theoretical) possibility to separate a signal source from a noisy source even if both run at the same frequency. In this paper, we first describe how to apply SSA in the context of side-channel analysis, and then validate its interest in three different scenarios. Namely, we consider unprotected software, masked software, and unprotected hardware block cipher implementations. Our experiments confirm significant noise reductions in all three cases, leading to success rates improved accordingly. They also put forward the stronger impact of SSA in more challenging scenarios, e.g. masked implementations (because the impact of noise increases exponentially with the number of shares in this case), or noisy hardware implementations (because of the established connection between the amount of noise and the attacks' success rate in this case). Since noise is a fundamental ingredient for most countermeasures against side-channel attacks, we conclude SSA can be an important element in the toolbox of evaluation laboratories, in order to efficiently preprocess their measurements in a black box manner.

The Fiat-Shamir (FS) transformation (Fiat and Shamir, Crypto '86) is a popular paradigm for constructing very efficient non-interactive zero-knowledge (NIZK) arguments and signature schemes using a hash function, starting from any three-move interactive protocol satisfying certain properties. Despite its wide-spread applicability both in theory and in practice, the known positive results for proving security of the FS paradigm are in the random oracle model, i.e., they assume that the hash function is modelled as an external random function accessible to all parties. On the other hand, a sequence of negative results shows that for certain classes of interactive protocols, the FS transform cannot be instantiated in the standard model.

We initiate the study of complementary positive results, namely, studying classes of interactive protocols where the FS transform *does* have standard-model instantiations. In particular, we show that for a class of "highly sound" protocols that we define, instantiating the FS transform via a $q$-wise independent hash function yields NIZK arguments and secure signature schemes. In the case of NIZK, we obtain a weaker "$q$-bounded" zero-knowledge flavor where the simulator works for all adversaries asking an a-priori bounded number of queries $q$; in the case of signatures, we obtain the weaker notion of random-message unforgeability against $q$-bounded random message attacks.

Our main idea is that when the protocol is highly sound, then instead of using random-oracle programming, one can use complexity leveraging. The question is whether such highly sound protocols exist and if so, which protocols lie in this class. We answer this question in the affirmative in the common reference string (CRS) model and under strong assumptions. Namely, assuming indistinguishability obfuscation and puncturable pseudorandom functions we construct a compiler that transforms any 3-move interactive protocol with instance-independent commitments and simulators (a property satisfied by the Lapidot-Shamir protocol, Crypto '90) into a compiled protocol in the CRS model that is highly sound. We also present a second compiler, in order to be able to start from a larger class of protocols, which only requires instance-independent commitments (a property for example satisfied by the classical protocol for quadratic residuosity due to Blum, Crypto '81). For the second compiler we require dual-mode commitments.

We hope that our work inspires more research on classes of (efficient) 3-move protocols where Fiat-Shamir is (efficiently) instantiable.

Université Libre de Bruxelles, Computer Science Department
Post-doc Position in Cloud Security

Applications are invited for a two-years Post-Doc position to work on the analysis and the design of secure protocols for cloud environments.

Candidates are expected to publish papers in well-known security related conferences and journals and should:

• Hold a PhD degree in Computer Science, Mathematics or related fields
• Have solid background on computer security and cryptography
• Have a good publication record
• Demonstrate an excellent level of spoken and written English. Knowledge of French is a plus.

Due to the particular nature of the funding, the position is only available for a non-Belgian citizen in a situation of international mobility, i.e. the candidate should not have spent more than 24 months in Belgium over the last 3 years.

Applications must include:

• a curriculum vitae, including a list of publications
• copies of diplomas
• two (or more) references

Closing date for applications: 10 April 2016

Contact: Applications can be send by email to Prof. Olivier Markowitch, olivier.markowitch (at) ulb.ac.be

More information: http://qualsec.ulb.ac.be/research/post-doc/

We study two open problems proposed by Wagner in his seminal work on the generalized birthday problem. First, with the use of multicollisions, we improve Wagner's $3$-tree algorithm. The new 3-tree only slightly outperforms Wagner's 3-tree, however, in some applications this suffices, and as a proof of concept, we apply the new algorithm to slightly reduce the security of two CAESAR proposals. Next, with the use of multiple collisions based on Hellman's table, we give improvements to the best known time-memory tradeoffs for the k-tree. As a result, we obtain the a new tradeoff curve T^2 \cdot M^{\lg k -1} = k \cdot N. For instance, when k=4, the tradeoff has the form T^2 M = 4 \cdot N.

Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2^164.15. This attack is more than 2^49 times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0.

Oblivious transfer is a fundamental building block for multiparty computation protocols. In this paper, we present a generally realizable framework for fully-simulatable $t$-out-of-$n$ oblivious transfer ($\mbox{OT}^{n}_{t}$) with security against non-adaptive malicious adversaries in the plain mode. Our construction relies on a single cryptographic primitive which is a variant of smooth projective hashing (SPH). A direct consequence of our work is that the existence of protocols for $\mbox{OT}^{n}_{t}$ is reduced to the existence of this SPH variant. Before this paper, the only known reductions provided half-simulatable security and every known efficient protocol involved at least two distinct cryptographic primitives. We show how to instantiate this new SPH variant under not only the decisional Diffie-Hellman assumption, the decisional $N$-th residuosity assumption and the decisional quadratic residuosity assumption as currently existing SPH constructions, but also the learning with errors problem. Our framework only needs $4$ communication rounds, which implies that it is more round-efficient than known protocols holding identical features.

We present two practical frameworks for $h$-out-of-$n$ oblivious transfer ($OT^{n}_{h}$). The first one is secure against covert adversaries who are not always willing to cheat at any price. The security is proven under the ideal/real simulation paradigm (call such security fully simulatable security). The second one is secure against malicious adversaries who are always willing to cheat. It provides fully simulatable security and privacy respectively for the sender and the receiver (call such security one-sided simulatable security). The two frameworks can be implemented from the decisional Diffie-Hellman (DDH) assumption, the decisional $N$-th residuosity assumption, the decisional quadratic residuosity assumption and so on.

The DDH-based instantiation of our first framework costs the minimum communication rounds and the minimum computational overhead, compared with existing practical protocols for oblivious transfer with fully simulatable security against covert adversaries or malicious adversaries.

Though our second framework is not efficient, compared with existing practical protocols with one-sided simulatable security against malicious adversaries. However, it first provides a way to deal with general $OT^{n}_{h}$ on this security level. What is more, its DDH-based instantiation is more efficient than the existing practical protocols for oblivious transfer with fully simulatable security against malicious adversaries.

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of information security and cryptography. The position is for five years at the Department of Computer Science and Engineering. The PhD student will join Katerina Mitrokotsa’s group and will be funded by a project funded by the Swedish research council focusing on security and privacy issues in resource constrained devices.

The PhD student is expected to have a MSc degree or equivalent, and strong background in mathematics and/or theoretical computer science, with some background in cryptography.

The position is fully funded for five years. The call for expressions of interest will remain open until a suitable candidate is appointed.

For any inquiries or to apply for the position, submit a full research curriculum-vitae (cv), names of two references, and a research statement to Prof. Katerina Mitrokotsa (aikmitr@ chalmers.se) clearly indicating the position sought.

Successful candidates will help to design and evaluate cryptographically reliable and privacy-preserving authentication protocols.

Closing date for applications: 31 March 2016

Contact: Katerina Mitrokotsa
Associate Professor
Chalmers University of Technology
Department of Computer Science and Engineering
Göteborg, Sweden

Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. All accepted applicants will receive competitive scholarships including tuition waiver, housing, monthly stipend, computer, travel support, etc.

• For more information about our group and projects, visit

  https://crypto.ku.edu.tr

• For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit

  https://gsse.ku.edu.tr/en/academics/computer-science-and-engineering/program-overview/

  Note that we do NOT accept Ph.D./M.Sc. applications via email. All applications must be completed online with all the required documents.

  For Ph.D. applicants from China and Hong Kong, we have the prestigious Fung scholarship:

  https://crypto.ku.edu.tr/fung_phd_scholarship_for_china_hong_kong

• For summer internship opportunities (at both undergraduate and graduate level), visit

  http://kusrp.ku.edu.tr

• For postdoctoral researcher positions, contact Asst. Prof. Alptekin Küpçü directly, including full CV, sample publications, a research proposal, and 3 reference letters sent directly by the referees.

  http://home.ku.edu.tr/~akupcu

Late applications will be accepted, though early applications will be given precedence.

Closing date for applications: 12 June 2016

Contact: gsse (at) ku.edu.tr

https://gsse.ku.edu.tr/phd-computer-science-and-engineering

More information: https://gsse.ku.edu.tr/en/academics/computer-science-and-engineering/program-overview/

Applications are open for a PhD position in the field of privacy enhancing technologies with the Security Group of IMDEA Software Institute (http://software.imdea.org/). The successful applicant can start from April 2016.

Candidates should either have graduated in Computer Science, Engineering, Mathematics or a related MSc course. A good engineering mathematics background and a strong interest in Security and Privacy is necessary. Inquisitiveness, commitment, and a critical attitude is expected. The working language at the institute is English, and candidates can be of any nationality.

The successful applicant will work under the supervision of Dr. Carmela Troncoso on the design and evaluation of privacy-preserving systems. The project will tackle the definition of privacy metrics, the development of techniques to compute them and their integration in the design and engineering of privacy enhancing technologies.

The IMDEA Software Institute is based in Madrid, Spain. The typical duration of a PhD grant at the IMDEA Software Institute is between 3 and 5 years and salaries are internationally competitive, including attractive conditions such as access to an excellent public healthcare system.

Applicants interested in the position should send an email to Carmela Troncoso and submit the application documents at https://careers.imdea.org/software/. Review of applications starts immediately until the position is filled. The application requires:

• Curriculum Vitae
• Motivation letter describing at least one research question you would like to work on
• Names (and e-mail) of 3 persons that can provide references about you and your work

For any question send Carmela Troncoso an email

Closing date for applications: 31 July 2016

Contact: Informal enquiries can be sent to Carmela Troncoso at carmela.troncoso AT imdea.org

More information: https://software.imdea.org/~carmela.troncoso/openpositions.html

In this paper we propose a new algorithm for solving the Learning With Errors (LWE) problem based on the steps of the famous Blum-Kalai-Wasserman (BKW) algorithm. The new idea is to introduce an additional procedure of mapping subvectors into codewords of a lattice code, thereby increasing the amount of positions that can be cancelled in each BKW step. The procedure introduces an additional noise term, but it is shown that by using a sequence of lattice codes with different rates the noise can be kept small. Developed theory shows that the new approach compares favorably to previous methods. It performs particularly well for the binary-LWE case, i.e., when the secret vector is sampled from $(0,1)^*$.

We address the problem of speeding up group computations in cryptography using a single untrusted computational resource. We analyze the security of an efficient protocol for securely outsourcing multi-exponentiations proposed at ESORICS 2014. We show that this scheme does not achieve the claimed security guarantees and we present several practical polynomial-time attacks on the delegation protocol which allows the untrusted helper to recover part (or the whole) of the device secret inputs. We then provide simple constructions for outsourcing group exponentiations in different settings (e.g. public/secret, fixed/variable bases and public/secret exponents). Finally, we prove that our attacks on the ESORICS 2014 protocol are unavoidable if one wants to use a single untrusted computational resource and to limit the computational cost of the limited device to a constant number of (generic) group operations. In particular, we show that our constructions are actually optimal.

Authenticated Key Exchange (AKE) protocols have been widely deployed in many real-world applications for securing communication channels. In this paper, we make the following contributions. First, we revisit the security modelling of leakage-resilient AKE protocols, and show that the existing models either impose some unnatural restrictions or do not sufficiently capture leakage attacks in reality. We then introduce a new strong yet meaningful security model, named challenge-dependent leakage-resilient eCK (CLR-eCK) model, to capture challenge-dependent leakage attacks on both long-term secret key and ephemeral secret key (i.e., randomness). Second, we propose a general framework for constructing one-round CLR-eCK-secure AKE protocols based on smooth projective hash functions (SPHFs). This framework ensures the session key is private and authentic even if the adversary learns a large fraction of both long-term secret key and ephemeral secret key, and hence provides stronger security guarantee than existing AKE protocols which become insecure if the adversary can perform leakage attacks during the execution of a session. Finally, we also present a practical instantiation of the general framework based on the Decisional Diffie-Hellman assumption without random oracle. Our result shows that the instantiation is efficient in terms of the communication and computation overhead and captures more general leakage attacks.

We show how to construct efficient, unconditionally secure non-malleable codes for bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most $n^{\delta}$ bits, where $n$ is the total number of bits in a codeword and $0 \leq \delta < 1$ a constant. Notably, this tampering class includes $\mathsf{NC}^0$.

We provide a formal treatment of backdoored pseudorandom generators (PRGs). Here a saboteur chooses a PRG instance for which she knows a trapdoor that allows prediction of future (and possibly past) generator outputs. This topic was formally studied by Vazirani and Vazirani, but only in a limited form and not in the context of subverting cryptographic protocols. The latter has become increasingly important due to revelations about NIST's backdoored Dual EC PRG and new results about its practical exploitability using a trapdoor.

We show that backdoored PRGs are equivalent to public-key encryption schemes with pseudorandom ciphertexts. We use this equivalence to build backdoored PRGs that avoid a well known drawback of the Dual EC PRG, namely biases in outputs that an attacker can exploit without the trapdoor. Our results also yield a number of new constructions and an explanatory framework for why there are no reported observations in the wild of backdoored PRGs using only symmetric primitives.

We also investigate folklore suggestions for countermeasures to backdoored PRGs, which we call {\em immunizers}. We show that simply hashing PRG outputs is not an effective immunizer against an attacker that knows the hash function in use. Salting the hash, however, does yield a secure immunizer, a fact we prove using a surprisingly subtle proof in the random oracle model. We also give a proof in the standard model under the assumption that the hash function is a universal computational extractor (a recent notion introduced by Bellare, Tung, and Keelveedhi).

The Dept. of Computer Science at University College London welcomes applications for a postdoctoral researcher in cryptography position. The post is under the supervision of Prof. Jens Groth with a flexible starting date and an initial duration until September 2017. Candidates must have (or be about to receive) a PhD.

University College London is one of Europe\'s highest ranked universities. The department is ranked as the best in computer science in the UK and recognized by the EPSRC and GCHQ as an Academic Centre of Excellence in Cyber Security Research. We are located at UCL\'s main campus in the centre of London.

Closing date for applications: 8 April 2016

Contact: Informal enquiries can be sent to Jens Groth at j.groth AT ucl.ac.uk

More information: http://www.cs.ucl.ac.uk/staff/J.Groth/openings.html

Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. All accepted applicants will receive competitive scholarships including tuition waiver, housing, monthly stipend, computer, travel support, etc.

• For more information about our group and projects, visit https://crypto.ku.edu.tr
• For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit https://gsse.ku.edu.tr/phd-computer-science-and-engineering
  
  Note that we do NOT accept Ph.D./M.Sc. applications via email. All applications must be completed online with all the required documents.
  
  For applicants from China and Hong Kong, we have the prestigious Fung scholarship https://crypto.ku.edu.tr/fung_phd_scholarship_for_china_hong_kong
• For summer internship opportunities (at both undergraduate and graduate level), visit http://kusrp.ku.edu.tr
• For postdoctoral researcher positions, contact Asst. Prof. Alptekin Küpçü direcly, including full CV, sample publications, and a research proposal. http://home.ku.edu.tr/~akupcu

Late applications will be accepted, though early applications will be given precedence.

Closing date for applications: 1 June 2016

Contact: gsse (at) ku.edu.tr
https://gsse.ku.edu.tr/phd-computer-science-and-engineering

More information: https://gsse.ku.edu.tr/phd-computer-science-and-engineering

The Physical Analysis and Cryptographic Engineering (PACE), Temasek Laboratories @ Nanyang Technological University, Singapore invites strong applications from highly motivated to fulfill research scientist position, in the area of hardware security. Candidates should have already completed, or be close to completing a PhD degree in mathematics, computer science, electrical engineering, or related disciplines, with strong track record in R&D (publications in international journals and conferences.)

The candidate will perform the research on hardware design/analysis of cryptosystems in FPGA/ASIC/Microcontrollers, with prime focus on PKC/PQC. The underlying work will involve design, analysis and lab. testing in equal parts.

The initial contract will be one year with strong possibilities of further extensions. Supported by government research fundings, we concentrate on cutting-edge research, candidates are expected to have good publication record, especially those with conferences/workshops of IACR. Besides an active group to work with, we also offer globally competitive salaries, including basic monthly salary and performance-based bonus, besides other allowances.

Only shortlisted candidates will be contacted for interview.

Contact: Shivam Bhasin, Co Principal Investigator. Email: sbhasin (at) ntu.edu.sg

Closing date for applications: 30 June 2016

An aggregate signature scheme is the aggregation of multiple signatures into a single compact signature of short string that can convince to any arbitrary verifier participating in the scheme. The aggregate signature scheme is very useful for real-world cryptographic applications such as secure routing, database outsourcing, etc. where the signatures on several distinct messages generated by many distinct users requires to be compact. In this paper, we presented an aggregate signature scheme using Certificateless Public Key Cryptography(CL-PKC). The scheme is provably secure with strongest security and shortest length. We have proven the scheme is existentially unforgeable under adaptive chosen message attack, assuming the hardness of computational Diffie-Hellman(CDH) Problem.

Our new Access Control Encryption is an implementation of CP-ABE, when used as part of a key delivery mechanism for an encrypted Data Base. It focuses on improving performance. In ACE the access policies are any predicates over the set of object attributes. Efficiency gains are most pronounced when the DNF representations of policies are compact. In ACE, within the life span of the keys, each user has to perform very few ABE decryptions, regardless of the number of policies accessible to her. Keys to most objects are then computed using only symmetric key decryptions. ACE is not the first to utilize symmetric key cryptography to reduce the number of CP-ABE operations, when access policies form a multi-level partially ordered set. However, in addition to this significant saving, ACE also takes advantage of overlaps among policies on clauses of the policies, thus further reducing computational complexity. Let R denote the number of user roles, N be the number of object access policies, k the ratio between the cost of CP-ABE encryption and symmetric key encryption complexities (for 10 attributes k&#8776;10&#8310;), and N=cR. The gain factor of ACE vs. a competing hybrid system is &#951;=kc/(k+c). Usually c>>1, but in some systems it may happen that c<1. ACE is composed of two sub systems encrypting the same messages: A CP-ABE and a symmetric key encryption system. We prove that ACE is secure under a new Uniform Security Game that we propose and justify, assuming that its building blocks, namely CP-ABE and block ciphers are secure. We require that CP-ABE be secure under the Selective Set Model, and that the block cipher be secure under Multi-User CPA, which we define. We present Policy Encryption (PE) that can replace CP-ABE as a component of ACE. In many cases, PE is more efficient than CP-ABE. However PE does not prevent collusions. Instead it limits collusions. PE is useful in those cases where owners can compartmentalize objects and subjects, so that within each compartment the owners can tolerate collusions. PE prevents inter compartmental collusions. PE has also the following appealing properties: It relies on older hence more reliable intractability assumption, the Computational Diffie-Hellman assumption, whereas CP-ABE relies on the newer Bilinear Diffie-Hellman assumption. PE uses off-the shelf standard crypto building blocks with one small modification, with proven security. For a small number of compartments PE is much faster than CP-ABE. PE and CP-ABE can coexist in the same system, where ABE is used in high security compartments. We apply ACE to a practical financial example, the Consolidate Audit Trail (CAT), which is expected to become the largest repository of financial data in the world.