International Association
for Cryptologic Research

In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the fully homomorphic encryption scheme with non-zero isotropic octonions. I improve the previous scheme by adopting the non-zero isotropic octonions so that the “m and -m attack” is not useful because in proposed scheme many ciphertexts exist where the plaintext m is not zero and the norm is zero. The improved scheme is based on multivariate algebraic equations with high degree or too many variables while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. The improved scheme is against the Gröbner basis attack.

Several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the rings used in those cryptosystems. The same structures are also used in the leading proposals for post-quantum lattice-based cryptography, including the classic NTRU cryptosystem and typical Ring-LWE-based cryptosystems.

This paper proposes NTRU Prime, which tweaks NTRU to use rings without these structures; proposes Streamlined NTRU Prime, which optimizes NTRU Prime from an implementation perspective; finds high-security post-quantum parameters for Streamlined NTRU Prime; and optimizes a constant-time implementation of those parameters. The performance results are surprisingly competitive with the best previous speeds for lattice-based cryptography.

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that supports the revocation of user's private keys to manage the dynamic credentials of users in a system. Many different RHIBE schemes were proposed previously, but they are not efficient in terms of the private key size and the update key size since the depth of a hierarchical identity is included as a multiplicative factor.

In this paper, we propose efficient RHIBE schemes with shorter private keys and update keys and small public parameters by removing this multiplicative factor. To achieve our goals, we first present a new HIBE scheme with the different generation of private keys such that a private key can be simply derived from a short intermediate private key. Next, we show that two efficient RHIBE schemes can be built by combining our HIBE scheme, an IBE scheme, and a tree based broadcast encryption scheme in a modular way.

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of short-vector lattice problems). In our protocol, the prover and the verifier do not need to interact at all: The verifier sets up a public key ahead of time, and this key can be used by any prover to prove arbitrary statements in a completely adaptive manner. Verification is done using a secret verification key, and soundness relies on this key not being known to the prover. Our protocol further allows to prove statements about computations of arbitrary RAM machines.

Previous works either relied on knowledge assumptions, or could only offer non-adaptive two-message protocols (where the first message could not be re-used), and required either obfuscation-based assumptions or super-polynomial hardness assumptions.

We show that our techniques can also be applied to construct a new type of (non-adaptive) 2-message delegation protocols for batch NP statements. Specifically, we can simultaneously prove the membership of multiple instances in a given NP language, with communication complexity proportional to the length of a single witness.

We introduce a new technique, component-based garbled circuits, for increasing the efficiency of secure two-party computation in the offline/online semi-honest setting. We observe that real-world functions are generally constructed in a modular way, comprising many standard components such as arithmetic operations and other common tasks. Our technique allows circuits for these common tasks to be garbled and shared during an offline phase; once the function to compute is specified, these pre-shared components can be chained together to create a larger garbled circuit. We stress that we do not assume that the function is known during the offline phase — only that it uses some common, predictable components.

Improving on the above technique, we give a second method of chaining, which we call single communication multiple connections chaining, which allows blocks of consecutive wires holding multi-bit pieces of data to be connected between components with only a single transmitted wire label. This means that connecting components requires minimal communication.

Finally, we give an implementation, CompGC, of these techniques and measure the efficiency gains for various examples. We find that our techniques result in roughly an order of magnitude performance improvement over standard garbled circuit-based secure two-party computation.

Ciphertext-policy attribute-based encryption (CP-ABE) is regarded as a promising cryptographic tool for encrypted access control in public cloud storage systems. However, a problem for CP-ABE schemes is that there is no way to change access policy on ciphertext once it is generated. This shortcoming makes us cannot conveniently use CP-ABE as traditional 1-to-1 public key encryption when the access policy needs to be changed. In this paper, we propose a dynamic policy update algorithm for CP-ABE. The policy update algorithm not only has the ability to remove attributes from an access policy but also is able to add newly issued attributes to an access policy. When the access policy of a ciphertext changes, user private key will always be fixed and thus private channels to update user keys are eliminated. Moreover, our policy update algorithm does not rely on predefined attributes, such as timestamp and user ID, and does not produce new public parameters as well. The update algorithm can be independently executed by the creator of a ciphertext and the update times for the ciphertext are unlimited. We construct such a scheme and show its usage in a practical scenario. The performance analysis shows an excellent result: The communication, computation, and storage costs of our policy update are only relevant to the number of attributes in access policy.

In the rich literature of secure multi-party computation (MPC), several important results rely on “protocol transformations,” whereby protocols from one model of MPC are transformed to protocols from another model. Motivated by the goal of simplifying and unifying results in the area of MPC, we formalize a general notion of black-box protocol transformations that captures previous transformations from the literature as special cases, and present several new transformations. We motivate our study of protocol transformations by presenting the following applications.

• Simplifying feasibility results: – Easily rederive a result in Goldreich’s book (2004), on MPC with full security in the presence of an honest majority, from an earlier result in the book, on MPC that offers “security with abort.” – Rederive the classical result of Rabin and Ben-Or (1989) by applying a transformation to the simpler protocols of Ben-Or et al. or Chaum et al. (1988). • Efficiency improvements: – The first “constant-rate ”MPC protocol for a constant number of parties that offers full information-theoretic security with an optimal threshold, improving over the protocol of Rabin and Ben-Or; – A fully secure MPC protocol with optimal threshold that improves over a previous protocol of Ben-Sasson et al. (2012) in the case of “deep and narrow” computations; – A fully secure MPC protocol with near-optimal threshold that improves over a previous protocol of Damgård et al. (2010) by improving the dependence on the security parameter from linear to polylogarithmic; – An efficient new transformation from passive-secure two-party computation in the OT-hybrid and OLE-hybrid model to zero-knowledge proofs, improving over a recent similar transformation of Hazay and Venkitasubramaniam (2016).

Finally, we prove the impossibility of two simple types of black-box protocol transformations, including an unconditional variant of a previous negative result of Rosulek (2012) that relied on the existence of one-way functions.

The Open Smart Grid Protocol (OSGP) is a widely used industry standard for exchanging sensitive data between devices inside of smart grids. For message confidentiality, OSGP implements a customised form of the RC4 stream cipher. In this work, we show how already known weaknesses of RC4 can be exploited to successfully attack the OSGP implementation as well. The attack modification is able to effectively derive the secret OSGP encryption and decryption key, given that an attacker can accumulate the cipher streams of approximately 90,000 messages. The possession of this key allows the attacker to decrypt all data intercepted on the OSGP smart grid and thereby obtain privacy critical information of its participants.

Event date: 15 June 2016

Event date: 29 August to 2 September 2016

We have two new Research Fellow positions in the Secure Systems group within the Department of Computer Science. Surrey is a GCHQ recognised Academic Centre of Excellence for cybersecurity. One position is part of a newly funded EPSRC interdisciplinary project entitled “Improving customer experience while ensuring data privacy for intelligent mobility” and the other is expanding the group’s expertise in verification and trusted computing. Both projects will involve research collaborations with other academic organisations and industry. We would be pleased to hear from potential applicants.

Job Titles:

Research Fellow in Security: https://jobs.surrey.ac.uk/vacancy.aspx?ref=032316

Research Fellow in Secure Systems: https://jobs.surrey.ac.uk/vacancy.aspx?ref=032116

Closing date for applications: 13 June 2016

Contact: Helen Treharne, Reader in Secure Systems

More information: https://jobs.surrey.ac.uk/Vacancies.aspx

The Faculty of Information Technology is looking for candidates to fill several positions as a Lecturer / Senior Lecturer – Cyber Security. As a successful candidate, you must have a demonstrated record of high-quality research in the cyber security area and the capability to establish and lead a high quality research team in this area, as well as demonstrated capacity to perform high-quality teaching in the Computer Science or Software Engineering areas. Your application should clearly show how this is the case.

Your research expertise in one of the following research areas is pivotal to the success of this role:

- security of advanced networking infrastructures (VNF, SDN, etc.)

- cross-layer security (from physical layer up to applications, including meta-data)

- secure roots of trust and trust management for IoT, critical infrastructures, virtualization

- interdisciplinary cyber security

- resilience of IT-based infrastructures

- IoT with cyber security focus (automation, robotics, sensors/actuators, etc.)

- software security

- mobile security, Android, iOS

- forensics, cyber-crime, forensic readiness.

If you have an excellent record of scholarly, high quality, high impact publications in refereed journals and conferences in areas of cyber security, we urge you to apply.

IMPORTANT: It is essential for your application to include a letter answering your suitability according to the key selection criteria (Please refer to \"How to apply for Monash Jobs\"). In addition, it would be helpful if your CV contains, for each high quality, high impact publication, a brief indication of its impact (in terms of citations) and of the quality of the venue. For the latter, please refer to the CORE conference and journal rankings www.core.edu.au/index.php

For the former, please refer to Google Scholar, Scopus, or Thomson Reuters.

This role is a full-time or part-time position; flexible working arrangements can be negotiated.

Closing date for applications: 29 May 2016

Contact: Associate Professor Carsten Rudolph

More information: http://www.jobs-monash.jxt.net.au/academic-jobs/lecturer-senior-lecturer-cyber-secruity/625850

Post Quantum Secure Multi-Party computation

INRIA is participating in the European H2020 PQCRYPTO project, http://pqcrypto.eu.org , whose aim is to recommend cryptographic primitives still secure after the potential advent of the quantum computer.

INRIA team Grace is involved in the topic\"advanced applications\", like searchable encryption, homomorphic encryption, secure multi-party computation, and has to deliver recommendations.

Besides the EU project PQCRYPTO, Grace wants to invest and put efforts in the topic of information theoretically secure multi-party computation (MPC).

Also, Grace would like to investigate how multi-party computation is useful in the context of blockchains.

Mission

The mission is to support project-team Grace in his growing involvement in (information theoretically) secure multi-party computation.

While the team masters mathematical and algorithmic aspects underlying secret sharing schemes relevant to information theoretically secure MPC (coding theory, algebraic function fields over finite fields), the team\'s knowledge of the MPC security models (simulation, universal composition) needs to be strenghtened. In particular, it is not clear how a powerful quantum adversary may affect these models.

The second part of the mission would be to help distinguishing between general purpose MPC and decidated MPC, for main applications.

The position may be extended for a second year.

Job description

Within H2020 PQCRYPTO, the applicant will be in charge, with the team leader and European researchers, of delivering the final recommendations. He will help the project participants to elaborate a plan and guidelines for these recommendations. He will also interfere with specialists in quantum computing, to assess the security models of MPC schemes in presence of a quantum adversary.

Profile

The candidate should have the done a PhD thesis in the topic of MPC computation, and know well the security models underlying the topic, with all their subtleties.

Closing date for applications: 31 May 2016

Contact: Daniel Augot

batiment Alan Turing

1 rue d\'Estienne d\'Orves

campus de l\'Ecole polytechnique

Palaiseau

France

More information: http://bit.ly/24HTRc6

Event date: 1 September to 7 September 2016

Event date: 27 November to 4 December 2016

Event date: 7 November to 9 November 2016
Submission deadline: 15 July 2016
Notification: 8 September 2016

Event date: 30 November to 2 December 2016
Submission deadline: 26 August 2016
Notification: 21 October 2016

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called \emph{permissionless setting}---anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92).

The analysis of the blockchain consensus protocol (a.k.a. Nakamoto consensus) has been a notoriously difficult task. Prior works that analyze it either make the simplifying assumption that network channels are fully synchronous (i.e. messages are instantly delivered without delays) (Garay et al, Eurocrypt'15) or only consider specific attacks (Nakamoto'08; Sampolinsky and Zohar, FinancialCrypt'15); additionally, as far as we know, none of them deal with players joining or leaving the protocol.

In this work we prove that the blockchain consensus mechanism satisfies a strong forms of *consistency* and *liveness* in an asynchronous network with adversarial delays that are a-priori bounded, within a formal model allowing for adaptive corruption and spawning of new players, assuming that the computational puzzle is modeled as a random oracle. (We complement this result by showing a simple attack against the blockchain protocol in a fully asynchronous setting, showing that the “puzzle-hardness” needs to be appropriately set as a function of the maximum network delay; this attack applies even for static corruption.)

As an independent contribution, we define an abstract notion of a blockchain protocol and identify appropriate security properties of such protocols; we prove that Nakamoto's blockchain protocol satisfies them and that these properties are sufficient for typical applications; we hope that this abstraction may simplify further applications of blockchains.

We show how to encrypt a relational database in such a way that it can efficiently support a large class of SQL queries. Our construction is based solely on structured encryption and does not make use of any property-preserving encryption (PPE) schemes such as deterministic and order-preserving encryption. As such, our approach leaks considerably less than PPE-based solutions which have recently been shown to reveal a lot of information in certain settings (Naveed et al., CCS '15). Our construction achieves asymptotically optimal query complexity under very natural conditions on the database and queries.

Since hundreds of certificate authorities (CAs) can issue browser-trusted certificates, it can be difficult for domain owners to detect certificates that have been fraudulently issued for their domain. Certificate Transparency (CT) is a recent standard by the Internet Engineering Task Force (IETF) that aims to construct public logs of all certificates issued by CAs, making it easier for domain owners to monitor for fraudulently issued certificates. To avoid relying on trusted log servers, CT includes mechanisms by which monitors and auditors can check whether logs are behaving honestly or not; these mechanisms are primarily based on Merkle tree hashing and authentication proofs. Given that CT is now being deployed, it is important to verify that it achieves its security goals.

In this work, we define four security properties of logging schemes such as CT that can be assured via cryptographic means, and show that CT does achieve these security properties. We consider two classes of security goals: those involving security against a malicious logger attempting to present different views of the log to different parties or at different points in time, and those involving security against malicious monitors who attempt to frame an honest log for failing to include a certificate in the log. We show that Certificate Transparency satisfies these security properties under various assumptions on Merkle trees all of which reduce to collision resistance of the underlying hash function (and in one case with the additional assumption of unforgeable signatures).