International Association
for Cryptologic Research

We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses.

As an introduction to this viewpoint, we first present a general reduction from reconstruction with known queries to PAC learning. Then, we directly address the problem of $\epsilon$-approximate database reconstruction ($\epsilon$-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error $\epsilon$, and is independent of the size of the database, or the number $N$ of possible values of data items. This already goes significantly beyond the state of the art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharit\'{e} et al. (IEEE S&P 2018).

We also study the new problem of $\epsilon$-approximate order reconstruction ($\epsilon$-AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as ${\mathcal{O}}(\epsilon^{-1} \log \epsilon^{-1})$ uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints.

We then show that when an auxiliary distribution is available, $\epsilon$-AOR can be enhanced to achieve $\epsilon$-ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction.

Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries. We illustrate this with both concrete attacks for prefix queries and with a general lower bound for all query classes.

The main objective of the Internet of Things is to interconnect everything around us to obtain information which was unavailable to us before, thus enabling us to make better decisions. This interconnection of things involves security issues for any Internet of Things key technology. Here we focus on elliptic curve cryptography (ECC) for embedded devices, which offers a high degree of security, compared to other encryption mechanisms. However, ECC also has security issues, such as Side-Channel Attacks (SCA), which are a growing threat in the implementation of cryptographic devices. This paper analyze the state-of-the-art of several proposals of algorithmic countermeasures to prevent passive SCA on ECC defined over prime fields. This work evaluates the trade-offs between security and the performance of side-channel attack countermeasures for scalar multiplication algorithms without pre-computation, i.e. for variable base point. Although a number of results are required to study the state-of-the-art of side-channel attack in elliptic curve cryptosystems, the interest of this work is to present explicit solutions that may be used for the future implementation of security mechanisms suitable for embedded devices applied to Internet of Things. In addition security problems for the countermeasures are also analyzed.

The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters $q=n^2$ and noise level $\sigma = n^{1.5}/(\sqrt{2\pi}\log_{2}^{2}n)$, the asymptotic complexity is $2^{0.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.

Persistent fault analysis (PFA) was proposed at CHES 2018 as a novel fault analysis technique. It was shown to completely defeat standard redundancy based countermeasure against fault analysis. In this work, we investigate the security of masking schemes against PFA. We show that with only one fault injection, masking countermeasures can be broken at any masking order. The study is performed on publicly available implementations of masking.

The design of modern stream ciphers is strongly influenced by the fact that Time-Memory-Data tradeoff attacks (TMD-TO attacks) reduce their effective key length to $\mathit{SL}/2$, where $\mathit{SL}$ denotes the inner state length. The classical solution, employed, e.g., by eSTREAM portfolio members Trivium and Grain v1, is to design the cipher in accordance with the Large-State-Small-Key construction, which implies that $\mathit{SL}$ is at least twice as large as the session key length $\mathit{KL}$.

In the last years, a new line of research looking for alternative stream cipher constructions guaranteeing a higher TMD-TO resistance with smaller inner state lengths has emerged. So far, this has led to three generic constructions: the LIZARD construction, having a provable TMD-TO resistance of $2\cdot \mathit{SL}/3$; the Continuous-Key-Use construction, underlying the stream cipher proposals Sprout, Plantlet, and Fruit; and the Continuous-IV-Use construction, very recently proposed by Hamann, Krause, and Meier. Meanwhile, it could be shown that the Continuous-Key-Use construction is vulnerable against certain nontrivial distinguishing attacks.

In this paper, we present a formal framework for proving security lower bounds on the resistance of generic stream cipher constructions against TMD-TO attacks and analyze two of the constructions mentioned above. First, we derive a tight security lower bound of approximately $\min\{\mathit{KL},\mathit{SL}/2\}$ on the resistance of the Large-State-Small-Key construction. This shows that the feature $\mathit{KL}\le \mathit{SL}/2$ does not open the door for new nontrivial TMD-TO attacks against Trivium and Grain v1 which are more dangerous than the known ones. Second, we prove a maximal security bound on the TMD-TO resistance of the Continuous-IV-Use construction, which shows that designing concrete instantiations of ultra-lightweight Continuous-IV-Use stream ciphers is a hopeful direction of future research.

We introduce the notion of two-factor signatures (2FS), a generalization of a two-out-of-two threshold signature scheme in which one of the parties is a hardware token which can store a high-entropy secret, and the other party is a human who knows a low-entropy password. The security (unforgeability) property of 2FS requires that an external adversary corrupting either party (the token or the computer the human is using) cannot forge a signature. This primitive is useful in contexts like hardware cryptocurrency wallets in which a signature conveys the authorization of a transaction. By the above security property, a hardware wallet implementing a two-factor signature scheme is secure against attacks mounted by a malicious hardware vendor; in contrast, all currently used wallet systems break under such an attack (and as such are not secure under our definition). We construct efficient provably-secure 2FS schemes which produce either Schnorr signature (assuming the DLOG assumption), or EC-DSA signatures (assuming security of EC-DSA and the CDH assumption) in the Random Oracle Model, and evaluate the performance of implementations of them. Our EC-DSA based 2FS scheme can directly replace currently used hardware wallets for Bitcoin and other major cryptocurrencies to enable security against malicious hardware vendors.

While financially advantageous, outsourcing key steps such as testing to potentially untrusted Outsourced Semiconductor Assembly and Test (OSAT) companies may pose a risk of compromising on-chip assets. Obfuscation of scan chains is a technique that hides the actual scan data from the untrusted testers; logic inserted between the scan cells, driven by a secret key, hide the transformation functions between the scan- in stimulus (scan-out response) and the delivered scan pattern (captured response). In this paper, we propose ScanSAT: an attack that transforms a scan obfuscated circuit to its logic- locked version and applies a variant of the Boolean satisfiability (SAT) based attack, thereby extracting the secret key. Our empirical results demonstrate that ScanSAT can easily break naive scan obfuscation techniques using only three or fewer attack iterations even for large key sizes and in the presence of scan compression.

Relay attacks are nowadays well known and most designers of secure authentication protocols are aware of them. At present, the main methods to prevent these attacks are based on the so-called distance bounding technique which consists in measuring the round-trip time of the exchanged authentication messages between the prover and the verifier to estimate an upper bound on the distance between these entities. Based on this bound, the verifier checks if the prover is sufficiently close by to rule out an unauthorized entity. Recently, a new work has proposed an authentication protocol that surprisingly uses the side-channel leakage to prevent relay attacks. In this paper, we exhibit some practical and security issues of this protocol and provide a new one that fixes all of them. Then, we argue the resistance of our proposal against both side-channel and relay attacks under some realistic assumptions. Our experimental results show the efficiency of our protocol in terms of false acceptance and false rejection rates.

Logic locking has been proposed as a strong protection of intellectual property (IP) against security threats in the IC supply chain especially when the fabrication facility is untrusted. Various techniques have proposed circuit configurations which do not allow the untrusted fab to decipher the true functionality and/or produce usable versions of the chip without having access to the locking key. These techniques rely on using additional locking circuitry which injects incorrect behavior into the digital functionality when the key is incorrect. However, much of this conventional research focuses on locking individual modules (such as adders, ALUs etc.). While locking these modules is useful, the true test for any locking scheme should consider their impact on the application running on a processor with such modules. A locked module within a processor may or may not have a substantial impact at the application level thereby allowing the attacker (untrusted foundry or unauthorized user) to still get useful work out of the system despite not having access to the key details. In this work, we show that even when state of the art locking schemes are used to lock the modules within a processor, a large class of workloads derived from machine learning (ML) applications (which are increasingly becoming the most relevant ones) continue to function correctly. This has huge implications to the effectiveness of the current locking techniques. The main reason for this behavior is the inherent error resiliency of such applications. To counter this threat, we propose a novel secure and effective logic locking scheme, called Strong Anti-SAT (SAS), to lock the entire processor and make sure that the ML applications undergo significant accuracy loss when any wrong key is applied. We provide two types of SAS, namely SAS-A and SAS-B. Experiments show that, for both types of SAS, 1) the application-level accuracy loss is significant (for ML applications) given any wrong key, 2) the attacker needs extremely long time to find a correct key, and 3) the hardware overhead is very small. Lastly, even though our techniques target machine learning type application workloads, the impact on conventional workloads will also be similar. Due to the inherent error resilience of ML, locking ML workloads is a harder problem to tackle.

Group signature scheme provides group members a way to sign messages without revealing their identities. Anonymity and traceability are two essential properties in a group signature system. However, these two security properties hold based on the assumption that all the signing keys are perfectly secret and leakage-free. On the another hand, on account of the physical imperfection of cryptosystems in practice, malicious attackers can learn fraction of secret state (including secret keys and intermediate randomness) of the cryptosystem via side-channel attacks, and thus breaking the security of whole system.

To address this issue, Ono et al. introduced a new security model of group signature, which captures randomness exposure attacks. They proved that their proposed construction satisfies the security require-ments of group signature scheme. Nevertheless, their scheme is only provably secure against randomness exposure and supposes the secret keys remains leakage-free. In this work, we focus on the security model of leakage-resilient group signature based on bounded leakage setting and propose three new black-box constructions of leakage-resilient group signature secure under the proposed security models.

Open Position for Research Fellow in National University of Singapore

“NUS-Singtel Cyber Security R&D Lab” (http://nus-singtel.nus.edu.sg/) is a 5 years joint project with about SGD 43 mil (approximately USD 31 mil) of funds contributed by Singapore Telecommunications Limited (SingTel), National University of Singapore (NUS), and National Research Foundation (NRF) of Singapore. The R&D Lab will conduct research in four broad areas of cyber security having strategic relevance to Singtel’s business: (1) Predictive Security Analytics; (2) Network, Data and Cloud Security; (3) Internet-of-Things and Industrial Control Systems; (4) Future-Ready Cyber Security Systems.

NUS-SingTel Lab currently has one research fellow position with competitive pay. It is available to (fresh) PhD graduates in computer science/engineering from Singapore or overseas.

The Research Fellow will be responsible for working closely with the Principal Investigator and lab members on a new 3-year research project which just started in June 2018. He/she should possess experience or interest in at least some of the following research areas:

• Key management, Authentication, Authorization and Access control

• Trusted computing (e.g. TPM, Intel SGX)

• Post-quantum cryptography

Job requirements:

• A PhD degree in a relevant area (Computer Science/Engineer, mathematics, etc);

• Good publication record in cyber security and crypto area

• Publication in Rank 1 Cyber Security or Crypto Conference, or AsiaCrypt, ESORICS, ACSAC, TCC, Euro S&P, etc;

• Good communication skills, self-motivated and good team players;

• Some experience in programming is a plus;

• Willing to perform practical research which may eventually lead to products

To apply for the above position, please send a copy of your recent CV to \"comxj at nus.edu.sg\" with an email subject “Application for RF”.

Closing date for applications: 1 June 2019

Contact: Dr Xu,

comxj at nus.edu.sg

More information: https://www.nus-singtel.nus.edu.sg/

Singapore University of Technology and Design (SUTD) is a young university which was established in collaboration with MIT. iTrust is a Cyber Security Research Center which has the world\'s best facilities in cyber-physical systems (CPS) including testbeds for Secure Water Treatment (SWaT), Water Distribution (WADI), Electric Power and Intelligent Control (EPIC), and IoT. (See more info at https://itrust.sutd.edu.sg/research/testbeds/.)

I am looking for PhD interns with interest in cyber-physical system security (IoT, power grid, water, transportation, and autonomous vehicle etc.). The attachment will be at least 3 months. Allowance will be provided for local expenses.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Only short-listed candidates will be contacted for interview.

Closing date for applications: 31 March 2019

Contact: Prof. Jianying Zhou

More information: http://jianying.space/

Temasek Laboratories at National University of Singapore, Singapore is seeking highly motivated professionals in conducting research in the area of lattice-based cryptography.

Applicants are expected to have a PhD degree in Mathematics/Computer Science/Engineering and a strong background in algebra and number theory in Bachelor degree and higher degree courses.

A preferred candidate is to have experience in lattice-based cryptography and is expected to be proficient in C/C++ language, Magma Software, SAGEMATH Software, a team worker and able to conduct independent research.

Closing date for applications: 15 March 2019

Contact: Dr Tan Chik How, Principal Research Scientist, tsltch (at) nus.edu.sg

The IMDEA Software Institute invites applications for tenure-track (Assistant Professor) faculty positions. We are primarily interested in recruiting excellent candidates in the areas of Data Science, including machine learning; Security and Privacy; Cyber-Physical Systems; Software Engineering; and Systems, including parallel and distributed systems, embedded systems, hybrid systems, heterogeneous architectures, etc. Exceptional candidates in other areas within the general research areas of the Institute will also be considered. Tenured-level (Associate and Full Professor) applications are also welcome.

The primary mission of the IMDEA Software Institute is to perform research of excellence at the highest international level in software development technologies. It is one of the highest ranked institutions worldwide in its main topic areas.

Information about the Institute\'s current faculty and research can be found at http://www.software.imdea.org .

Closing date for applications: 6 February 2019

Contact: Applications should be completed at:

https://careers.imdea.org/software/

Please include reference FAC-1-2019 at the beginning of the form. For full consideration, complete applications must be received by February 6, 2018, although applications will continue to be accepted until the positions are filled. Pending final approval, we expect to fill two positions.

More information: http://www.software.imdea.org

CWI is looking for candidates to initiate and develop new research directions in Secure Software Systems, addressing major challenges in software systems relating to security and privacy.

The challenges concern the modelling, analysis, and design of software systems that satisfy a range of security and privacy requirements related to, but not confined to, secure information flow, static and dynamic security guarantees, security testing, intrusion detection, differential privacy, security games, authentication, authorization, anonymous communication, and cryptography.

We are looking for researchers with excellent track records in computer science, with a focus on privacy and security in software systems and their scientific foundations. The tenure-track candidates are expected to develop a research program that addresses current societal demands on secure software systems, whereas senior candidates are expected to develop and lead a new group in this area. The candidates are expected to utilise synergies with other CWI research groups, like the cryptology group of prof. Ronald Cramer.

For more detailed descriptions of the individual positions and the required profiles, we refer to the link below.

Applicants should send:

• a motivation letter;

• a curriculum vitae with a list of publications;

• a copy of their thesis or of their three most prominent publications;

• the names of at least three prominent scientists who can provide letters of recommendation;

• a research statement and a well-founded, innovative research plan for a period of 5 years, including plans on how to acquire additional funding and a challenging outlook for the future, which takes into account the international research landscape.

The candidates are asked to indicate in their application which position has their preference. We especially invite qualified women to apply.

Closing date for applications: 11 February 2019

Contact: Angelique Schilder (apply (at) cwi.nl)

More information: https://www.cwi.nl/jobs/vacancies/tenure-track-and-senior-researcher-positions-in-secure-software-systems-in-amsterdam

Ph.D. and Postdoc positions are available in the new research group in cryptology and data security, established by Christian Cachin, at the Institute of Computer Science, University of Bern.

Our research addresses all aspects of security in distributed systems, especially cryptographic protocols, consistency, consensus, and cloud-computing security. We are particularly interested in blockchains, distributed ledger technology, cryptocurrencies, and their security and economics.

Candidates should have a strong background in computer science or mathematics. They should like conceptual, rigorous thinking for working theoretically, or be interested in building concrete systems for working practically. Demonstrated expertise in blockchain technology, cryptography, or distributed computing is a plus.

Positions are available from Spring 2019 and come with a competitive salary. The selection process runs until suitable candidates have been found. The University of Bern conducts excellent research and lives up its vision that \'Knowledge generates value\'. The city of Bern lies in the center of Switzerland and offers some of the highest quality of life worldwide.

Applicants should hold a master degree (for Ph.D. positions) or a Ph.D. (for postdoc positions), with expertise in the relevant research topics.

Applications should be sent by email, with subject line *Application for Postdoc* or *Application for Ph.D.*, as one single PDF file, addressed directly to Prof. Christian Cachin by email.

For more information, please contact Christian Cachin ( https://cachin.com/cc/ ).

Closing date for applications: 30 March 2019

Contact: Christian Cachin, cachin (at) inf.unibe.ch

More information: https://cachin.com/cc/positions.html

A little bit about us…(Seattle Washington).

We\'re in near ‘stealth’ mode and we\'re a well-financed, financial technology start-up located in Seattle. We\'re growing (currently 13 employees) and need a senior level Security Software Engineer to help us deliver our game changing platform. We’re moving past the old way of thinking and are creating a seamless universal platform to bring the exchange of funds up to the speed of the Internet.

What you’ll be doing:

Be our security SME.

Design, implement, and optimize core cryptographic libraries and secure systems (protocols and mechanisms).

Perform technical security assessments, code audits and design reviews.

Develop technical solutions to help mitigate security vulnerabilities.

Conduct research to identify new attack avenues and product enhancements.

What you likely bring to us:

You have start-up experience and you really want to work on v1. Master’s degree in Computer Science, Mathematics, or a related field.

Experience implementing cryptographic primitives/algorithms and cryptographic protocols.

Experience with any of the following is a plus: Go, Rust, C, C++. Significant experience building secure applications and strong knowledge of authentication protocols and applied cryptography. Must be able to identify and defend against protocol/network-level attacks.

Strong experience with security-oriented system design with applied cryptography at the forefront.

What we offer:

Competitive start-up salary.

Full benefits package and equity.

Fun place to work with smart people!

Collaborative environment and a small team, make a big impact immediately.

Closing date for applications: 1 June 2019

Contact: Karl Augustine, Director of Recruiting, kaugust (at) transparentinc.co, 111 S. Jackson St., Seattle WA 98104

More information: https://jobs.lever.co/transparentinc

A little bit about us…(Seattle Washington).

We\'re in near ‘stealth’ mode and we\'re a well-financed, financial technology start-up located in Seattle. We\'re growing (currently 13 employees) and need a senior level Security Software Engineer to help us deliver our game changing platform. We’re moving past the old way of thinking and are creating a seamless universal platform to bring the exchange of funds up to the speed of the Internet.

What you’ll be doing:

Be our security SME.

Design, implement, and optimize core cryptographic libraries and secure systems (protocols and mechanisms).

Perform technical security assessments, code audits and design reviews.

Develop technical solutions to help mitigate security vulnerabilities.

Conduct research to identify new attack avenues and product enhancements.

What you likely bring to us:

You have start-up experience and you really want to work on v1. Master’s degree in Computer Science, Mathematics, or a related field.

Experience implementing cryptographic primitives/algorithms and cryptographic protocols.

Experience with any of the following is a plus: Go, Rust, C, C++. Significant experience building secure applications and strong knowledge of authentication protocols and applied cryptography. Must be able to identify and defend against protocol/network-level attacks.

Strong experience with security-oriented system design with applied cryptography at the forefront.

What we offer:

Competitive start-up salary.

Full benefits package and equity.

Fun place to work with smart people!

Collaborative environment and a small team, make a big impact immediately.

Closing date for applications: 1 June 2019

Contact: Karl Augustine, Director of Recruiting, kaugust (at) transparentinc.co, 111 S. Jackson St., Seattle WA 98104

More information: https://jobs.lever.co/transparentinc

Group signatures allow users of a group to sign messages anonymously in the name of the group, while incorporating a tracing mechanism to revoke anonymity and identify the signer of any message. Since its introduction by Chaum and van Heyst (EUROCRYPT 1991), numerous proposals have been put forward, yielding various improvements on security, efficiency and functionality. However, a drawback of traditional group signatures is that the opening authority is given too much power, i.e., he can indiscriminately revoke anonymity and there is no mechanism to keep him accountable. To overcome this problem, Kohlweiss and Miers (PoPET 2015) introduced the notion of accountable tracing signatures ($\mathsf{ATS}$) - an enhanced group signature variant in which the opening authority is kept accountable for his actions. Kohlweiss and Miers demonstrated a generic construction of $\mathsf{ATS}$ and put forward a concrete instantiation based on number-theoretic assumptions. To the best of our knowledge, no other $\mathsf{ATS}$ scheme has been known, and the problem of instantiating $\mathsf{ATS}$ under post-quantum assumptions, e.g., lattices, remains open to date.

~~In this work, we provide the first lattice-based accountable tracing signature scheme. The scheme satisfies the security requirements suggested by Kohlweiss and Miers, assuming the hardness of the Ring Short Integer Solution ($\mathsf{RSIS}$) and the Ring Learning With Errors ($\mathsf{RLWE}$) problems. At the heart of our construction are a lattice-based key-oblivious encryption scheme and a zero-knowledge argument system allowing to prove that a given ciphertext is a valid $\mathsf{RLWE}$ encryption under some hidden yet certified key. These technical building blocks may be of independent interest, e.g., they can be useful for the design of other lattice-based privacy-preserving protocols.

In this work, we propose new predicate encryption schemes for zero inner-product encryption (ZIPE) and non-zero inner-product encryption (NIPE) predicates from prime-order bilinear pairings, which are both attribute and function private in the public-key setting.

Our ZIPE scheme is adaptively attribute private under the standard Matrix DDH assumption for unbounded collusions. It is additionally computationally function private under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with superlogarithmic min-entropy. Existing (statistically) function private ZIPE schemes due to Boneh et al. [Crypto’13, Asiacrypt’13] necessarily require predicate distributions with significantly larger min-entropy in the public-key setting.

Our NIPE scheme is adaptively attribute private under the standard Matrix DDH assumption, albeit for bounded collusions. It is also computationally function private under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with super-logarithmic min-entropy. To the best of our knowledge, existing NIPE schemes from bilinear pairings were neither attribute private nor function private.

Our constructions are inspired by the linear FE constructions of Agrawal et al. [Crypto’16] and the simulation secure ZIPE of Wee [TCC’17]. In our ZIPE scheme, we show a novel way of embedding two different hard problem instances in a single secret key - one for unbounded collusion-resistance and the other for function privacy. With respect to NIPE, we introduce new techniques for simultaneously achieving attribute and function privacy. We also show natural generalizations of our ZIPE and NIPE constructions to a wider class of subspace membership, subspace non-membership and hidden-vector encryption predicates.