International Association
for Cryptologic Research

The Laboratory of Computer Networks and Architecture at the University of São Paulo is currently hiring researchers with background in cryptography for a 2-year post-doc position. The project is the result of a partnership with Intel (see http://www.fapesp.br/en/9719 for the CFP), and is focused on the analysis and design of hardware-friendly post-quantum cryptographic algorithms.

The main requirements for the application are (1) a solid background in cryptography, preferably (but not necessarily) with post-quantum primitives, (2) good design/programming skills, preferably (but not necessarily) in programming languages such as C and/or hardware description languages such as VHDL, (3) a track record of strong R&D capability, with relevant publications on top conferences/journals, and (4) be able to work with little supervision and to work well with other researchers, as well as have good presentation and communication skills in English (ability to speak Portuguese is considered a plus, but it is not mandatory). The candidates are expected to work closely with the industry partners in the project (mainly researchers from Intel) and produce valuable research material in time and with the required quality.

The application requires: an academic curriculum vitae, a motivation letter, and the contact information of at least 2 people that can provide reference about the candidate’s work. Applicants that have already completed or that are close to complete their PhDs are both welcome.

The post-doc fellowship is granted by FAPESP, following the rules that can be found at http://www.fapesp.br/en/5427. Applications will be reviewed as soon as they are received, and only selected candidates will be contacted for interview. The process will remain open until the positions are filled or up to October 1st, 2016.

Closing date for applications: 1 October 2016

Contact: Prof. Marcos A. Simplicio Jr -- msimplicio (at) larc.usp.br

More information: http://www.larc.usp.br/en/content/security-group/

In this paper we attack a $2n$-bit double length hash function proposed by Lee et al. This proposal is a blockcipher-based hash function with hash rate $2/3$. The designers claimed that it could achieve ideal collision resistance and gave a security proof. However, we find a collision attack with complexity of $\Omega(2^{3n/4})$ and a preimage attack with complexity of $\Omega(2^{n})$. Our result shows this construction is much worse than an ideal $2n$-bit hash function.

We propose an efficient hardware architecture design & implementation of Advanced Encryption Standard (AES). The AES algorithm defined by the National Institute of Standard and Technology (NIST) of United States has been widely accepted. The cryptographic algorithms can be implemented with software or built with pure hardware. However Field Programmable Gate Arrays (FPGA) implementation offers quicker solution and can be easily upgraded to incorporate any protocol changes. This contribution investigates the AES encryption cryptosystem with regard to FPGA and Very High Speed Integrated Circuit Hardware Description language (VHDL). Optimized and Synthesizable VHDL code is developed for the implementation of 128- bit data encryption process. AES encryption is designed and implemented in FPGA, which is shown to be more efficient than published approaches. Xilinx ISE 12.3i software is used for simulation. Each program is tested with some of the sample vectors provided by NIST and output results are perfect with minimal delay. The throughput reaches the value of 1609Mbit/sec for encryption process with Device XC6vlx240t of Xilinx Virtex Family.

Event date: 8 October to 9 October 2016
Submission deadline: 2 September 2016
Notification: 23 September 2016

The unbalanced oil and vinegar signature scheme (UOV) is one of signature schemes whose public key is a set of multivariate quadratic forms. Recently, a new variant of UOV called Cubic UOV was proposed at Inscrypt 2015. It was claimed that the cubic UOV was more efficient than the original UOV and its security was enough. However, an equivalent secret key of the cubic UOV can be recovered easily. In this note, we describe how to recover it.

In IMACC 2015 and Inscrypt 2015, Zhang and Tan proposed new vinegar-like variants of multivariate signature schemes. While their aims were to enhance the security of broken schemes, the security is much less than expected. In this note, we describe how to recover a public key of the original scheme.

The security of order-revealing encryption (ORE) has been unclear since its invention. Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions.

This work shows that more plaintext information can be extracted from ORE ciphertexts than was previously thought. We identify two issues: First, we show that when multiple columns of correlated data are encrypted with ORE, attacks can use the encrypted columns together to reveal more information than prior attacks could extract from the columns individually. Second, we apply known attacks, and develop new attacks, to show that the \emph{leakage} of concrete ORE schemes on non-uniform data leads to more accurate plaintext recovery than is suggested by the security theorems which only dealt with uniform inputs.

In 2009, Gentry proposed the first Fully Homomorphic Encryption (FHE) scheme, an extremely powerful cryptographic primitive that enables to perform computations, i.e., to evaluate circuits, on encrypted data without decrypting them first. This has many applications, in particular in cloud computing.

In all currently known FHE schemes, encryptions are associated to some (non-negative integer) noise level, and at each evaluation of an AND gate, the noise level increases. This is problematic because decryption can only work if the noise level stays below some maximum level $L$ at every gate of the circuit. To ensure that property, it is possible to perform an operation called _bootstrapping_ to reduce the noise level. However, bootstrapping is time-consuming and has been identified as a critical operation. This motivates a new problem in discrete optimization, that of choosing where in the circuit to perform bootstrapping operations so as to control the noise level; the goal is to minimize the number of bootstrappings in circuits.

In this paper, we formally define the _bootstrap problem_, we design a polynomial-time $L$-approximation algorithm using a novel method of rounding of a linear program, and we show a matching hardness result: $(L-\epsilon)$-inapproximability for any $\epsilon>0$.

Constrained pseudorandom functions (CPRF) are a fundamental extension of the notion of traditional pseudorandom functions (PRF). A CPRF enables a master PRF key holder to issue constrained keys corresponding to specific constraint predicates over the input domain. A constrained key can be used to evaluate the PRF only on those inputs which are accepted by the associated constraint predicate. However, the PRF outputs on the rest of the inputs still remain computationally indistinguishable from uniformly random values. A constrained verifiable pseudorandom function (CVPRF) enhances a CPRF with a non-interactive public verification mechanism for checking the correctness of PRF evaluations. A delegatable constrained pseudorandom function (DCPRF) is another extension which augments a CPRF to empower constrained key holders to delegate further constrained keys that allow PRF evaluations on inputs accepted by more restricted constraint predicates compared to ones embedded in their own constrained keys. Until recently, all the proposed constructions of CPRF’s and their extensions(i) either could handle only bounded length inputs, (ii) or were based on risky knowledge-type assumptions. In EUROCRYPT 2016, Deshpande et al. have presented a CPRF construction supporting inputs of unconstrained polynomial length based on indistinguishability obfuscation and injective pseudorandom generators, which they have claimed to be selectively secure. In this paper, we first identify a flaw in their security argument and resolve this by carefully modifying their construction and suitably redesigning the security proof. Our alteration does not involve any additional heavy duty cryptographic tools. Next, employing only standard public key encryption (PKE), we extend our CPRF construction, presenting the first ever CVPRF and DCPRF constructions that can handle inputs of unbounded polynomial length. Finally, we apply our ideas to demonstrate the first known attribute-based signature (ABS) scheme for general signing policies supporting signing attributes of arbitrary polynomial length.

We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition. Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower energy and/or hardware cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks.

Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a good measure for the cost of evaluating the iMHF on an ASIC. If n denotes the number of nodes of a DAG (or equivalently, the number of operations --- typically hash function calls --- of the underlying iMHF), its pebbling complexity must be close to n^2 for the iMHF to be memory-hard. We show that the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit can be attacked with complexity O(n^{1.75}); the data-independent phase of Pomelo (a finalist of the password hashing competition) and Lyra2 (also a finalist) can be attacked with complexity O(n^{1.83}) and O(n^{1.67}), respectively.

For our attacks we use and extend the technique developed by [Alwen-Blocki'16], who show that the pebbling complexity of a DAG can be upper bounded in terms of its depth-robustness.

Event date: 19 October to 21 October 2016
Submission deadline: 4 September 2016
Notification: 18 September 2016

As lattice cryptography becomes more widely used in practice, there is an increasing need for further cryptanalytic effort and higher-confidence security estimates for its underlying computational problems. Of particular interest is a class of problems used in many recent implementations, namely, Learning With Errors (LWE), its more efficient ring-based variant Ring-LWE, and their ``deterministic error'' counterparts Learning With Rounding (LWR) and Ring-LWR.

To facilitate such analysis, in this work we give a broad collection of challenges for concrete Ring-LWE and Ring-LWR instantiations over cyclotomics rings. The challenges cover a wide variety of instantiations, involving two-power and non-two-power cyclotomics; moduli of various sizes and arithmetic forms; small and large numbers of samples; and error distributions satisfying the bounds from worst-case hardness theorems related to ideal lattices, along with narrower errors that still appear to yield hard instantiations. Each challenge comes with a qualitative hardness estimate ranging from ``toy'' to ``very hard,'' which we determine by estimating the Hermite factor needed to solve it via lattice attacks.

A central issue in the creation of challenges for LWE-like problems is that dishonestly generated instances can be much harder to solve than properly generated ones, or even impossible. To address this, we devise and implement a simple, non-interactive, publicly verifiable protocol which gives reasonably convincing evidence that the challenges are properly distributed, or at least not much harder than claimed.

We construct efficient protocols for several tasks related to private matching of $k$-mers (sets of $k$ length strings). These are based upon the evaluation of functionalities in the levelled homomorphic encryption scheme YASHE which supports addition and multiplication as SIMD operations. We analyse the correctness and security properties of these protocols as well their resource costs in terms of the underlying task parameters.

Hierarchical identity-based broadcast encryption (HIBBE) organizes the users in a tree-like structure in which they can delegate the decryption ability to their subordinates. In addition, the trusted third party (TTP) can reduce its burden because the users' secret keys can be generated in a distributed mechanism by users' supervisors. HIBBE enables encrypting a message for any arbitrary set of receivers, and only the chosen users and their supervisors are able to decrypt. To preserving the anonymity of the intended receivers, in this paper, for the first time, we propose an anonymous HIBBE scheme. The proposed scheme is constructed based on composite order bilinear maps. We formally define the anonymity against chosen identity vector set and chosen plaintext attack (Anon-CIVS-CPA), and prove that the proposed scheme provides this property. Performance evaluation shows the practical and deployable aspects of our proposed scheme. With the advantage of HIBBE, we enable hierarchical identity-based signature (HIBS) schemes to sign a message for a set of designated verifiers. This resulted in proposing a generic construction for the novel notion of hierarchical identity-based multi-designated verifiable signature (HIB-MDVS). We formally define HIB-MDVS's security against existential forgery under chosen message attack (EF-CMA), prove that the resulting HIB-MDVS is unforgeable, and finally show that it provides the anonymity of the intended verifiers.

Strong designated verifier signatures make the message authenticated only to a designated person called the designated verifier while privacy of the signer's identity is preserved. This primitive is useful in scenarios that authenticity, signer ambiguity and signer's privacy are required simultaneously such as electronic voting and tendering. To have quantum-attack-resistant strong designated verifier signatures as recommended in National Institute of Standards and Technology internal report (NISTIR 8105, dated April 2016), a provably secure code-based construction was proposed by Koochak Shooshtari et al. in 2016. In this paper, we show that this code-based candidate for strong designated verifier signatures does not have signer ambiguity or non-transferability, the main feature of strong designated verifier signatures. In addition, it is shown that it is not strongly unforgeable if a designated verifier transfers a signature to a third party. Then, a new proposal for strong designated verifier signatures based on coding theory is presented, and its security which includes strong unforgeability, signer ambiguity and privacy of the signer's identity properties is proved under Goppa Parameterized Bounded Decoding and the Goppa Code Distinguishing assumptions in the random oracle model.

This work presents the construction of intelligent algorithmic mechanism based on multidimensional view of intelligent reasoning, threat analytics, cryptographic solutions and secure multiparty computation. It is basically an attempt of the cross fertilization of distributed AI, algorithmic game theory and cryptography. The mechanism evaluates innate and adaptive system immunity in terms of collective, machine, collaborative, business and security intelligence. It also shows the complexity analysis of the mechanism and experimental results on three test cases: (a) intrusion detection, (b) adaptively secure broadcast and (c) health security. Keywords: Algorithmic mechanism, Intelligent reasoning, Threat analytics, Security intelligence, Intrusion detection.

We give one- and two-dimensional scalar multiplication algorithms for Jacobians of genus~2 curves that operate by projecting to Kummer surfaces, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper "signed" output back on the Jacobian. This extends the work of Lopez and Dahab, Okeya and Sakurai, and Brier and Joye to genus 2, and also to two-dimensional scalar multiplication. The technique is especially interesting in genus 2, because Kummer surfaces can outperform comparable elliptic curve systems.

In this paper we study the feasibility of using homomorphic tallying in the Estonian Internet voting system. The paper analyzes the security benefits provided by homomorphic tallying, the costs introduced and the required changes to the voting system. We find that homomorphic tallying has several security benefits, such as improved ballot secrecy, public verifiability of the vote tallying server and the possibility for observers to recalculate the tally without compromising ballot secrecy. The use of modern elliptic curve cryptography allows homomorphic tallying to be implemented without a significant loss of performance.

Event date: 3 April to 7 April 2017
Submission deadline: 1 January 2017
Notification: 1 February 2017

Homomorphic encryption allows to make specific operations on private data which stays encrypted. While applications such as cloud computing require to have a practical solution, the encryption scheme must be secure. In this article, we detail and analyze in-depth the homomorphic encryption scheme proposed by Zhou and Wornell. From the analysis of the encryption scheme, we are able to mount three attacks. The first attack enables to recover a secret plaintext message broadcasted to multiple users. The second attack performs a chosen ciphertext key recovery attack and it was implemented and verified. The last attack is a related chosen plaintext decryption attack.