International Association
for Cryptologic Research

The proceedings of Asiacrypt 2013 are now available online. The IACR retains copyright for the "camera-ready" versions of papers submitted by authors for IACR proceedings. These versions are made available to the general public in the IACR archive approximately two years after publication. IACR members can access more recent IACR publications via Springer using this page.

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et al. (STOC 1988) proved that, nevertheless, every language having a multi-prover interactive proof also has a zero-knowledge multi-prover interactive proof, unconditionally. Their work led to, among many other things, a line of work studying zero knowledge without intractability assumptions. In this line of work, Kilian, Petrank, and Tardos (STOC 1997) defined and constructed zero-knowledge probabilistically checkable proofs (PCPs).

While PCPs with quasilinear-size proof length, but without zero knowledge, are known, no such result is known for zero knowledge PCPs. In this work, we show how to construct ``2-round'' PCPs that are zero knowledge and of length \tilde{O}(K) where K is the number of queries made by a malicious polynomial time verifier. Previous solutions required PCPs of length at least K^6 to maintain zero knowledge. In this model, which we call *duplex PCP* (DPCP), the verifier first receives an oracle string from the prover, then replies with a message, and then receives another oracle string from the prover; a malicious verifier can make up to K queries in total to both oracles.

Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but instead rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure --- which many central constructions can be shown to possess, including [BFLS91,ALMSS98,BS08] --- we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.

At Crypto 2015, Blondeau, Peyrin and Wang proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight blockcipher with a SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction.

We notice that there are good linear hulls for bit-oriented block cipher Simon corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced Simon block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced Simon. We also involve some key guessing technique and further extend the basic attacks to more rounds.

Our known-key attacks can reach as many as 29/32/38/48/63-rounds of Simon32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher Simon.

It is a well-known result that homomorphic encryption is not secure against adaptive chosen ciphertext attacks~(CCA2) because of its malleability property. Very recently, however, Gong et al. proposed a construction asserted to be a CCA2-secure additive homomorphic encryption (AHE) scheme; in their construction, the adversary is not able to obtain a correct answer when querying the decryption oracle on a ciphertext obtained by modifying the challenge ciphertext (Theoretical Computer Science, 2016). Because their construction is very similar to Paillier's AHE, it appeared to support an additive homomorphic property, though they did not specify an evaluation algorithm for the scheme in their paper.

In this paper, we present a simple CCA2 attack on their construction by re-randomizing the challenge ciphertext. Furthermore, we look into an additive homomorphic property of their construction. To do this, we first consider a typical candidate for an addition algorithm on ciphertexts, as provided for previous AHE constructions, and establish that it does not function correctly. Subsequently, we provide plausible evidence for the hardness of achieving an additive homomorphic property with their construction. According to our analysis, it seems hard to preserve additive homomorphic property of their construction without any modification.

In addition, as a minor contribution, we point out a flaw in the decryption algorithm of their construction and present a rectified algorithm for correct decryption.

Private functional encryption guarantees that not only the information in ciphertexts is hidden but also the circuits in decryption tokens are protected. A notable use case of this notion is query privacy in searchable encryption. Prior privacy models in the literature were fine-tuned for specific functionalities (namely, identity-based encryption and inner-product encryption), did not model correlations between ciphertexts and decryption tokens, or fell under strong uninstantiability results. We develop a new indistinguishability-based privacy notion that overcomes these limitations and give constructions supporting different circuit classes and meeting varying degrees of security. Obfuscation is a common building block that these constructions share, albeit the obfuscators necessary for each construction are based on different assumptions. Our feasibility results go beyond previous constructions in a number of ways. In particular, a keyword search scheme that we base on point obfuscators tolerates arbitrary and possibly low-entropy correlations between encrypted data and queried keywords, even under (mildly restricted) adaptive token-extraction queries. Our more elaborate keyword search scheme achieves the strongest notion of privacy that we put forth (with no restrictions), but relies on stronger forms of obfuscation. We also develop a composable and distributionally secure inner-product obfuscator and use it to build an inner-product encryption scheme that achieves an unprecedented level of privacy. This, in particular, positively answers a question left open by Boneh, Raghunathan and Segev (ASIACRYPT 2013) concerning the extension and realization of enhanced security for hyperplane membership.

A Universal Circuit (UC) is a circuit that can simulate any circuit of a maximum size, given its description as input. In this work, we look back at Valiant's universal circuit construction from Valiant (STOC 1976). Although it yields asymptotically optimal UC, and has implications for important problems in cryptography such as ''private function evaluation'' (PFE) and ''cryptographic program obfuscation'', somewhat surprisingly, no implementations of the construction exist. We provide a more approachable description, improve its constant factors, and put forth the first complete implementation. We observe that our improved implementation of Valiant's UC performs better than estimated and in fact, is almost always smaller than UC construction of Kolesnikov and Schneider (FC 2008). The UC circuits generated by our implementation can be used for benchmarking MPC protocols, and provide a point of comparison for any future PFE. We also observe, for the first time, that the same construction can be adapted to yield size optimized \emph{universal arithmetic circuit} (UAC).

Reputation systems are crucial for distributed applications in which users have to be made accountable for their actions, such as e-commerce websites. However, existing systems often disclose the identity of the raters, which might deter honest users from posting reviews, out of fear of retaliation from the ratees. While many privacy-preserving reputation systems have been proposed, none of them was at the same time truly decentralized, trustless, and suitable for real world usage in, for example, e-commerce applications. After discussing the weaknesses and shortcoming of existing solutions, we will present our own blockchain-based trustless reputation system, and analyze its correctness and the security guarantees it promises.

We study the quantum query complexity of finding a collision for a function $f$ whose outputs are chosen according to a distribution with min-entropy $k$. We prove that $\Omega(2^{k/9})$ quantum queries are necessary to find a collision for function $f$. This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).

Event date: 1 June to 3 June 2016
Submission deadline: 25 March 2016
Notification: 15 April 2016

We present a set of new, efficient, universally composable two-party protocols for evaluating reactive arithmetic circuits modulo n, where n is a safe RSA modulus of unknown factorization. Our protocols are based on a homomorphic encryption scheme with message space $Z_n$, zero-knowledge proofs of existence, and a novel "mixed" trapdoor commitment scheme. Our protocols are proven secure against adaptive corruptions (assuming secure erasures) under standard assumptions in the CRS model (without random oracles). Our protocols appear to be the most efficient ones that satisfy these security requirements. In contrast to prior protocols, we provide facilities that allow for the use of our protocols as building blocks of higher-level protocols. An additional contribution of this paper is a universally composable construction of the variant of the Dodis-Yampolskiy oblivious pseudorandom function in a group of order n as originally proposed by Jarecki and Liu.

Exciting new capabilities of modern trusted hardware technologies allow for the execution of arbitrary code within environments completely isolated from the rest of the system and provide cryptographic mechanisms for securely reporting on these executions to remote parties.

Rigorously proving security of protocols that rely on this type of hardware faces two obstacles. The first is to develop models appropriate for the induced trust assumptions (e.g., what is the correct notion of a party when the peer one wishes to communicate with is a specific instance of an an outsourced program). The second is to develop scalable analysis methods, as the inherent stateful nature of the platforms precludes the application of existing modular analysis techniques that require high degrees of independence between the components.

We give the first steps in this direction by studying three cryptographic tools which have been commonly associated with this new generation of trusted hardware solutions. Specifically, we provide formal security definitions, generic constructions and security analysis for attested computation, key-exchange for attestation and secure outsourced computation. Our approach is incremental: each of the concepts relies on the previous ones according to an approach that is quasi-modular. For example we show how to build a secure outsourced computation scheme from an arbitrary attestation protocol combined together with a key-exchange and an encryption scheme.

While threshold signature schemes have been presented before, there has never been an optimal threshold signature algorithm for DSA. Due to the properties of DSA, it is far more difficult to create a threshold scheme for it than for other signature algorithms. In this paper, we present a breakthrough scheme that provides a threshold DSA algorithm that is efficient and optimal. We also present a compelling application to use our scheme: securing Bitcoin wallets. Bitcoin thefts are on the rise, and threshold DSA is necessary to secure Bitcoin wallets. Our scheme is the first general threshold DSA scheme that does not require an honest majority and is useful for securing Bitcoin wallets.

As big data collection and analysis becomes prevalent in today’s computing environments there is a growing need for techniques to ensure security of the collected data. To make matters worse, due to its large volume and velocity, big data is commonly stored on distributed or shared computing resources not fully controlled by the data owner. Thus, tools are needed to ensure both the confidentiality of the stored data and the integrity of the analytics results even in untrusted environments. In this chapter, we present several cryptographic approaches for securing big data and discuss the appropriate use scenarios for each.

We begin with the problem of securing big data storage. We first address the problem of secure block storage for big data allowing data owners to store and retrieve their data from an untrusted server. We present techniques that allow a data owner to both control access to their data and ensure that none of their data is modified or lost while in storage. However, in most big data applications, it is not sufficient to simply store and retrieve one’s data and a search functionality is necessary to allow one to select only the relevant data. Thus, we present several techniques for searchable encryption allowing database- style queries over encrypted data. We review the performance, functionality, and security provided by each of these schemes and describe appropriate use-cases.

However, the volume of big data often makes it infeasible for an analyst to retrieve all relevant data. Instead, it is desirable to be able to perform analytics directly on the stored data without compromising the confidentiality of the data or the integrity of the computation results. We describe several recent cryptographic breakthroughs that make such processing possible for varying classes of analytics. We review the performance and security characteristics of each of these schemes and summarize how they can be used to protect big data analytics especially when deployed in a cloud setting.

We hope that the exposition in this chapter will raise awareness of the latest types of tools and protections available for securing big data. We believe better understanding and closer collaboration between the data science and cryptography communities will be critical to enabling the future of big data processing.

Functional encryption is a new public key paradigm that solves, in a non-interactive way, most of the security challenges raised by cloud computing. A recent paper by Abdalla, Bourse, De Caro, and Pointcheval shows a functional encryption scheme for evaluations of inner products whose security can be proven under simple assumptions. Inner product evaluation is a simple, but quite powerful functionality, that suffices for many concrete applications. We analyze the different security notions for functional encryption for inner product evaluation and propose a new generic construction that achieves security against adaptive adversaries. We show 3 instantiations based on the ElGamal encryption (plain DDH assumption), Paillier/BCP encryption (DCR assumption), and Regev encryption (LWE assumption). All of them have different advantages and drawbacks, but with acceptable trade-offs, and rely on standard assumptions.

The SimpleMatrix encryption scheme as proposed by Tao et al. \cite{TD13} is one of the very few existing approaches to create a secure and efficient encryption scheme on the basis of multivariate polynomials. However, in its basic version, decryption failures occur with non-negligible probability. Although this problem has been addressed in several papers \cite{DP14,TX15}, a general solution to it is still missing.\\ In this paper we propose an improved version of the SimpleMatrix scheme, which eliminates decryption failures completely and therefore solves the biggest problem of the SimpleMatrix encryption scheme. Additionally, we propose a second version of the scheme, which reduces the blow-up factor between plain and ciphertext size to a value arbitrary close to 1.

The chair of Embedded Security at Horst Görtz Institute for IT-Security (HGI) at Ruhr-University Bochum (Germany) has openings for Ph.D. positions. We are looking for outstanding candidates with strong background in Electrical/Computer Engineering, and/or Cryptography.

The vacancy is within the Nano-Scale Side-Channel Analysis project funded by DFG, the German Research Foundation. The available Ph.D. position is fully funded for three years.

The focus of the project is on practical as well as theoretical side-channel analysis of CMOS ASIC cryptographic devices. Applicants are required to have completed (or be close to completing) a Master or Diploma with excellent grades in Computer/Electrical Engineering, Computer Science, or closely related areas. In addition to the usual computer and electrical engineering background, the candidate is expected to be able to deal with hardware designs, e.g., VHDL/verilog, which is essential for the project.

Please send your application via e-mail as a single pdf containing a CV, copies of transcripts and certificates, and (if possible) names of references. Review of the applications will start immediately until the position has been filled.

Send your applications to emsec+apply (at) rub (dot) de

Starting date: earliest possible

Founded in 2001, the Horst Görtz Institute at Ruhr-University Bochum is a leading interdisciplinary research center dedicated to research and education covering all aspects of IT security, with an excellent record of research in cryptography. The Horst Görtz Institute has 15 professors and over 80 PhD students.

Closing date for applications: 15 February 2016

Contact: Amir Moradi, amir (dot) moradi (at) rub (dot) de

In this paper, by considering the constraints of Advanced Metering Infrastructure (AMI) systems, we propose an authenticated key exchange protocol and an authenticated message broadcasting protocol. The proposed protocols are based on two well-known protocols, Okamoto and Schnorr, and inherit their security features. For providing the security of the system against physical attacks, we utilize the Physical Unclonable Function (PUF) technology in communication parties. Thus, there is no need to store the secrets in the smart meters which can easily be corrupted. We show that the proposed authenticated key exchange protocol meets all the security requirements such as secure key generation, backward and forward secrecy and explicit authentication. Also, it is shown that the authenticated message broadcasting protocol is secure against corrupted smart meters. The proposed schemes are practical and efficient for providing a secure communication between parties. We believe that our proposed protocols are the best fit for an AMI system.

cMix is a cryptographic protocol for mix networks that uses precomputations of a group-homomorphic encryption function to avoid all real-time public-key operations by the senders, mix nodes, and receivers. Like other mix network protocols, cMix can enable an anonymity service that accepts inputs from senders and delivers them to an output buffer, in a way that the outputs are unlinkable to the inputs. cMix’s high performance scalable architecture, which results from its unique pre-computation approach, makes it suitable for smartphone-tosmartphone use while maintaining full anonymity sets independently per round.

Each sender establishes a shared key separately with each of the mix nodes, which is used as a seed to a cryptographic pseudorandom number generator to generate a sequence of message keys. Each sender encrypts its input to cMix with modular multiplication by message keys. cMix works by replacing the message keys, which are not known in the pre-computation, in real time with a precomputed random value.

Our presentation includes a detailed specification of cMix and simulation-based security arguments. We also give performance analysis, both modeled and measured, of our working prototype currently running in the cloud.

cMix is the core technology underlying our larger PrivaTegrity system that allows smart devices to carry out a variety of applications anonymously (including sending and receiving chat messages), with little extra bandwidth or battery usage. This paper focuses on cMix.

The applied cryptography group at Horst Görtz Institute for IT-Security (HGI) at Ruhr-University Bochum has openings for Ph.D. positions. We are looking for outstanding candidates with strong background in Computer Science, Mathematics or Engineering.

Our research focus is on practice-oriented provable security. Topics of interest may include (but are not limited to):

• Provable security of cryptographic implementations
• Randomness generation
• Cryptographic protocols (e.g. MPC, cryptocurrencies)

Starting date: earliest possible

Send your documents to sebastian (dot) faust (at) rub (dot) de

Applicants are required to have completed (or be close to completing) a Master or Diploma with excellent grades in Computer Science, Mathematics, or closely related areas. Additional knowledge in related disciplines such as, e.g., complexity theory or IT security is welcome.

Please send your application to Sebastian Faust via e-mail. Applications should contain a CV, a 1-page letter of motivation, copies of transcripts and certificates, and (if possible) names of references. Review of applications will start immediately until the position has been filled.

Founded in 2001, the Horst-Görtz Institute at Ruhr-University Bochum is a leading interdisciplinary research center dedicated to research and education covering all aspects of IT security, with an excellent record of research in cryptography. The Horst-Görtz Institute has 15 professors and over 80 PhD students.

Contact: Sebastian Faust, sebastian (dot) faust (at) rub (dot) de

Closing date for applications: 15 February 2016

• Conduct research on advanced ethical hacking, penetration testing, reverse engineering.
• Conduct assessment on network infrastructure, web and mobile security.
• Assisting in IT security enforcement and enhancement.
• Design secure application testing approaches, integrate quality assurance testings with security functionalities.
• Candidate with strong programming background will also be involved in security tool/signature development.
• Design and implement preventive security controls, application code review and analysis, code scanning and testing tools, web application scanning and penetration tests.
• Manage vendor and service provider on security tools and technologies project engagement and delivery.

Requirements:

• Bachelor’s degree or above in Computer Science, Electrical Engineering or other relevant disciplines with a minimum of 5 years of experience in security assessment. Candidates with less experience will also be considered for the Engineer level.
• Experience in financial industry is preferred but not mandatory.
• Demonstrate wide working knowledge of application security.
• Experience in application development life cycle, application testing and code scanning, with exposure in penetration test, finding exploits, vulnerabilities, unauthorized access, or other malicious activities in computer systems

Closing date for applications: 15 January 2016

Contact: charlenechoo (at) astri.org

More information: http://www.astri.org