IACR News Central

It has been shown that, for appropriate parameters, solving the $\mathsf{SIS}$ problem in the average case is at least as hard as approximating certain lattice problems in the worst case %on any $n$-dimensional lattice to within polynomial factor $\beta\cdot\widetilde{O}(\sqrt n)$, where typically $\beta=O(\sqrt{n\log n})$ such that random $\mathsf{SIS}$ instances admit a solution. In this work, we show that $\beta=O(1)$, i.e., $\beta$ is essentially upper-bounded by a constant. This directly gives us a poly-time exhaustive search algorithm for solving the $\mathsf{SIS}$ problem (resulting in approximating certain worst-case lattice problems to within $\widetilde{O}(\sqrt n)$ factor). Although the exhaustive search algorithm is rather inefficient for typical setting of parameters, our result indicates that lattice-based cryptography is not secure, at least in an asymptotical sense. Our work is based on an observation of the lower/upper bounds on the smoothing parameter for lattices.

We present nQUIC, a variant of QUIC-TLS that uses the Noise protocol framework for its key exchange and basis of its packet protector with no semantic transport changes. nQUIC is designed for deployment in systems and for applications that assert trust in raw public keys rather than PKI-based certificate chains. It uses a fixed key exchange algorithm, compromising agility for implementation and verification ease. nQUIC provides mandatory server and optional client authentication, resistance to Key Compromise Impersonation attacks, and forward and future secrecy of traffic key derivation, which makes it favorable to QUIC-TLS for long-lived QUIC connections in comparable applications. We developed two interoperable prototype implementations written in Go and Rust. Experimental results show that nQUIC finishes its handshake in a comparable amount of time as QUIC-TLS.

Group signatures allow members of a group to anonymously produce signatures on behalf of the group. They are an important building block for privacy-enhancing applications, e.g., enabling user data to be collected in authenticated form while preserving the user’s privacy. The linkability between the signatures thereby plays a crucial role for balancing utility and privacy: knowing the correlation of events significantly increases the utility of the data but also severely harms the user’s privacy. Therefore group signatures are unlinkable per default, but either support linking or identity escrow through a dedicated central party or offer user-controlled linkability. However, both approaches have significant limitations. The former relies on a fully trusted entity and reveals too much information, and the latter requires exact knowledge of the needed linkability at the moment when the signatures are created. However, often the exact purpose of the data might not be clear at the point of data collection. In fact, data collectors tend to gather large amounts of data at first, but will need linkability only for selected, small subsets of the data. We introduce a new type of group signatures that provide a more flexible and privacy-friendly access to such selective linkability. When created, all signatures are fully unlinkable. Only when strictly needed or desired, should the required pieces be made linkable with the help of a central entity. For privacy, this linkability is established in an oblivious and non-transitive manner. We formally define the requirements for this new type of group signatures and provide an efficient instantiation that provably satisfies these requirements under discrete-logarithm based assumptions.

Non-malleable asymmetric encryption schemes which prove plaintext knowledge are sufficient for secrecy in some domains. For example, ballot secrecy in voting. In these domains, some applications derive encryption schemes by coupling malleable ciphertexts with proofs of plaintext knowledge, without evidence that the sufficient condition (for secrecy) is satisfied nor an independent security proof (of secrecy). Consequently, it is unknown whether these applications satisfy desirable secrecy properties. In this article, we propose a generic construction for such a coupling and show that our construction produces non-malleable encryption schemes which prove plaintext knowledge. Furthermore, we show how our results can be used to prove ballot secrecy of voting systems. Accordingly, we facilitate the development of applications satisfying their security objectives.

Automatic tools have played an important role in designing new cryptographic primitives and evaluating the security of ciphers. Simple Theorem Prover constraint solver (STP) has been used to search for differential/linear trails of ciphers. This paper proposes general STP-based models searching for differential and linear trails with the optimal probability and correlation for S-box based ciphers. In order to get trails with the best probability or correlation for ciphers with arbitrary S-box, we give an efficient algorithm to describe probability or correlation of S-Box. Based on the algorithm we present a search model for optimal differential and linear trails, which is efficient for ciphers with S-Boxes whose DDTs/LATs contain entities not equal to the power of two. Meanwhile, the STP-based model for single-key impossible differentials considering key schedule is proposed, which traces the propagation of values from plaintext to ciphertext instead of propagations of differences. And we found that there is no 5-round AES-128 single-key truncated impossible differential considering key schedule, where input and output differences have only one active byte respectively. Finally, our proposed models are utilized to search for trails of bit-wise ciphers GIFT-128, DES, DESL and ICEBERG and word-wise ciphers ARIA, SM4 and SKINNY-128. As a result, improved results are presented in terms of the number of rounds or probabilities/correlations.

In 2018, Shi et al. 's showed that Kaushik et al.'s quantum signature scheme is defective. It suffers from the forgery attack. They further proposed an improvement, trying to avoid the attack. However, after examining we found their improved quantum signature is deniable, because the verifier can impersonate the signer to sign a message. After that, when a dispute occurs, he can argue that the signature was not signed by him. It was from the signer. To overcome the drawback, in this paper, we raise an improvement to make it publicly verifiable and hence more suitable to be applied in real life. After cryptanalysis, we confirm that our improvement not only resist the forgery attack but also is undeniable.

Subspace Labs is building the future of decentralized cloud-based services. The subspace protocol and ecosystem enables developers to easily build web and mobile apps that give end users full ownership and control over their data. We are venture backed and have received a National Science Foundation (NSF) research grant to fund this position. We are seeking a Cryptographer who has familiarity with the blockchain space and existing decentralized protocols to help us develop and implement a new set of cryptographic primitives while ensuring the protocol is secure across a public network of untrusted nodes.

Requirements

• An MS or Ph.D. in cryptography or computer security

• Proficiency in at least one of the following languages: C,Python, Rust or Javascript. Proficiency in NodeJS and Typescript is a plus.

• Previous work and contribution to open-source projects, especially those dealing with blockchains or decentralized protocols.

• Experience with Proof-of-Space, Proof-of-Storage and Proof-of-Time cryptographic primitives

• Experience with the OpenPGP protocol, specifically OpenPGP-JS

• Experience with a canonical signature scheme such as BLS

• Local to the San Francisco Bay Area or willing to relocate

• Must be based in the United States for grant compliance purposes.

Responsibilities

• Develop and implement a hybrid proof-of-space that allows for both blockchain consensus and validation of storage pledges

• Select and implement a lightweight proof-of-replication, possibly based on Verifiable Delay Functions (VDFs)

• Take over primary responsibility for the Subspace Credit Leger, a modular component of the Subspace Protocol that is an early implementation of a Proof of Space-Time blockchain

• Optimize the existing usage of OpenPGP JS, explore replacement with another cryptosystem, and implement a canonical signature scheme for immutable records.

• Conduct a full security analysis of the protocol before developing and implementing necessary countermeasures

Closing date for applications: 31 January 2019

Contact: Jeremiah Wagstaff

Cofounder & CEO

jeremiah (at) subspace.network

More information: https://www.subspace.network

Nazarbayev University is seeking highly-qualified faculty at all ranks to join its rapidly growing Mathematics Department in the School of Science and Technology. All areas of mathematics will be considered but preference will be given to applied mathematics and statistics (broadly interpreted).

Successful candidates should hold a PhD in mathematics, statistics or in a related field and have excellent English-language communication skills and experience with Western higher education. Applicants for associate and full professor positions should have considerable experience in supervising students at the graduate level, possess strong teaching skills and experience, and a demonstrated rank-appropriate research accomplishment and service. Applicants for assistant professor level should demonstrate a potential for excellence in teaching, research, and service.

Position responsibilities include: teaching undergraduate and graduate level of courses (2-2 teaching load), supervision of graduate students, curricular and program development, ongoing engagement in professional and research activities, general program guidance and leadership, and other activities related to the intellectual and cultural environment of the university.

Nazarbayev University offers an attractive benefits package, including:

• competitive compensation
• free housing based on family size and rank
• relocation allowance
• no-cost medical insurance, with global coverage
• educational allowance for children
• air tickets to home country, twice per year

Closing date for applications: 31 March 2019

Contact: Applicants should send a detailed CV, teaching and research statements, and list of publications to sst.cv (at) nu.edu.kz. Review of applications will begin immediately but full consideration will be given to applications submitted no later than February 28th, 2019. Successful appointments are expected to begin on August 1st, 2019.

More information: http://sst.nu.edu.kz

Excellent Chinese students wishing to do a PhD degree in cyber security are invited to apply for PhD positions in the University of York, UK. PhD projects may be in the following broad areas of cyber security:

• applied cryptography, especially the design and implementation of cryptographic schemes and protocols with the aim of preserving user privacy and increasing user security, and
• usable security and privacy, i.e. security and privacy enhancing technologies that are designed to be usable by humans.

The exact project title and brief is to be discussed and finalised with the supervisor.

The scholarship is for Chinese students only and includes both a fee waiver and a living stipend. More information about the scholarship is available at: www.york.ac.uk/study/postgraduate-research/funding/china-scholarships

The final application deadline is 15 February 2019.

Potential candidates are encouraged to contact the supervisor Dr. Siamak F. Shahandashti in the first instance and as soon as possible by email at siamak.shahandashti (at) york.ac.uk and provide their CV, latest academic transcript, and one indicative piece of their research work (e.g. paper, thesis, report) for an initial assessment and discussion of PhD topic. Agreement on the PhD topic and proposal will be required for the final application.

Further information about the supervisor can be found through his homepage: www.cs.york.ac.uk/~siamak

York is a prestigious university in the UK and the Department of Computer Science is ranked top 10 in the UK in terms of research quality. More information about the university can be found here: www.york.ac.uk/about

Closing date for applications: 15 February 2019

Contact: Dr. Siamak F. Shahandashti | siamak.shahandashti (at) york.ac.uk | www.cs.york.ac.uk/~siamak

More information: https://www.york.ac.uk/study/postgraduate-research/funding/china-scholarships

Excellent students wishing to do a PhD degree in cyber security are invited to apply for PhD positions in the University of York, UK. PhD projects may be in the following broad areas of cyber security:

• applied cryptography, especially the design and implementation of cryptographic schemes and protocols with the aim of preserving user privacy and increasing user security, and
• usable security and privacy, i.e. security and privacy enhancing technologies that are designed to be usable by humans.

The exact project title and brief is to be discussed and finalised with the supervisor.

The scholarship is for non-UK/EU students only and includes both a fee waiver and a living stipend. More information about the scholarship is available at: www.york.ac.uk/study/postgraduate-research/funding/international/ygrs

The final application deadline is 31 January 2019.

Potential candidates are encouraged to contact the supervisor Dr. Siamak F. Shahandashti in the first instance and as soon as possible by email at siamak.shahandashti (at) york.ac.uk and provide their CV, latest academic transcript, and one indicative piece of their research work (e.g. paper, thesis, report) for an initial assessment and discussion of PhD topic. Agreement on the PhD topic and proposal will be required for the final application.

Further information about the supervisor can be found through his homepage: www.cs.york.ac.uk/~siamak

York is a prestigious university in the UK and the Department of Computer Science is ranked top 10 in the UK in terms of research quality. More information about the university can be found here: www.york.ac.uk/about

Closing date for applications: 31 January 2019

Contact: Dr. Siamak F. Shahandashti | siamak.shahandashti (at) york.ac.uk | www.cs.york.ac.uk/~siamak

More information: https://www.york.ac.uk/study/postgraduate-research/funding/international/ygrs

The Faculty of Mathematics, Informatics and Mechanics at University of Warsaw (MIM UW) invites applications for positions of an assistant professor (“adiunkt” in Polish) in Computer Science, starting on 1st October 2019.

MIM UW is one of the strongest computer science faculties in Europe. It is known for talented students (e.g., two wins and 13 times in top ten at the ACM International Collegiate Programming Contest) and strong research teams, especially in theoretical aspects of computer science like algorithms, logic and automata, cryptography (e.g., 8 ERC grants in these fields, 4 of them running at the moment). For an overview of research areas represented in the Faculty, see http://www.mimuw.edu.pl/en/dziedziny-badan

Requirements:

- PhD degree in computer science or mathematics

- Strong publication record in international computer science journals or conferences

- Teaching experience

- Mobility record (participation in conferences, research visits, postdoc positions, etc.)

In the current call, the position is offered in two variants:

1. standard \"tenure-track\" position, with teaching load of 210 hrs/year

2. a more \"postdoc-like\" position, for 2 or 4 years, with reduced teaching load (120hrs/year) -- only for candidates at most 5 years after obtaining PhD.

Deadline for applications: 31st January 2019.

More details, including application procedure can be found under the following links:

1. https://www.mimuw.edu.pl/rozne/konkursy-pliki/2019/praca-adiunkt-31-01-2019-en.pdf

2. https://www.mimuw.edu.pl/rozne/konkursy-pliki/2019/praca-adiunkt-s-eilenberg-31-01-2019-en.pdf

For more information about the procedure, requirements, conditions, etc. please contact a vice-director of Institute of Informatics, Lukasz Kowalik (kowalik (at) mimuw.edu.pl).

Closing date for applications: 31 January 2019

Within the scope of the Spanish \"Juan de la Cierva\" postdoctoral programme, the Research group on Cryptology and Information Security (GiCSI) of the Spanish National Research Council is seeking highly motivated professionals in conducting research in the area of blockchain-based protocols, security protocols and cryptographic privacy-enhancing technologies.

There are two types of Juan de la Cierva grants:

1. Juan de la Cierva Training Grants (Juan de la Cierva-Formación) are aimed at candidates that have been awarded their PhD between 01/01/2017 and 31/12/2018. These grants are aimed to complete their postdoctoral research training in Spanish R&D centers other than those in which they carried out their predoctoral training.

2. Juan de la Cierva Incorporation Grants (Juan de la Cierva-Incorporación) are aimed at those who were awarded their PhD between 01/01/2014 and 31/12/2016. These grants are intended to strengthen the grantee’s acquired skills during a first stage of postdoctoral training.

For more information about deadlines and other details, please refer to http://www.ciencia.gob.es/portal/site/MICINN/menuitem.dbc68b34d11ccbd5d52ffeb801432ea0/?vgnextoid=73d917cd13e77610VgnVCM1000001d04140aRCRD.

Interested candidates are encouraged to contact us as soon as possible.

Closing date for applications: 31 January 2019

Contact: David Arroyo, Tenured Scientist at the Spanish National Research Council (CSIC)

http://www.researcherid.com/rid/A-5167-2010

https://scholar.google.es/citations?user=IORMgpcAAAAJ&hl=es

We have several open positions for PhD/PostDoc at School of Computer Science, Guangzhou University, which is located in Guangzhou, China. Our attractive openings are suitable for PhD candidates and PostDoc researchers who seek to work in the field of information security. The research topics include but not limited to: Security and Privacy in Artificial Intelligence, Blockchain, cloud computing security, big data security, IoT security, and public-key cryptography.

PostDoc researchers will be offered competitive salary package plus other benefits, which is around 50,000 USD per year (salary and bonus before tax) and 30,000 USD research funding.

PhD candidates will be provided full research scholarship, allowances, free single dorm room, and round-trip tickets (Once a year).

Interested candidates please send your CV, reference letters, and copies of certificates to Prof. Jin Li. PostDocs please add your publication list.

More information about Prof. Jin Li:

http://www.scholat.com/jinli71

https://scholar.google.com/citations?user=7GDV2vUAAAAJ&hl=en&oi=ao

Closing date for applications: 30 July 2019

Closing date for applications: 30 July 2019

Contact: Prof. Jin Li:

E-mail: jinli71 (at) gmail.com

Integrated in Gemalto Zero Footprint Security (ZFS) Team, he/she will study and develop software protection techniques related to White Box Cryptography in the Mobile ecosystem Android and iOS.

A week in the life of a Cryptography Software Engineer:

•Create and develop new IP in the domain

•Respect milestones

•Ensure good quality of delivered software

•Keep knowledge of state of the art in the domain

Knowledge, Skills and Experience:

•Bachelor/Masters in Computer Science/Engineering or equivalent technical domain

•Experience in cryptography in particular White Box Cryptography

•Design, develop and test using C/C++ for execution on Linux, Mac OSX and Windows

•Document research, specifications and design results clearly, with an emphasis on explaining why decisions were made

•Flair for Mathematics topics

•Good to have experience in Android and/or iOS security

•Good to have experience in side channel attacks

•Not afraid by technical challenge

•Be driven and self-motivated

•Communicate clearly and respectfully with local and remote team members

•Collaborate with the team to meet and exceed the team goals

•Display attention to detail

•Find novel solutions to identified needs

•Focus on customer needs

•Learn rapidly advancing technologies

•Embrace changing needs and priorities

•Travelling might be required

Closing date for applications: 1 March 2019

Contact: For interested applicants, please submit your resume to se-asia.recruit (at) gemalto.com with the following information:

Subject/Email Title: IACR: [applicable position title]: [your name]

More information: https://www.linkedin.com/jobs/view/1017741340/

We are looking for a bright post-doctoral researcher focusing in theoretical cryptography and more precisely verifiable delegation of computation to work on a collaborative project on cloud-assisted computing.

The position is fully funded for 2 years. The post-doc will be hired at the department of Computer Science and Engineering at Chalmers and will be working under the supervision of Prof. Katerina Mitrokotsa. The preferred starting date is in April 2019.

To Apply use the online form at: https://goo.gl/HqgGqM

Closing date for applications: 26 January 2019

Contact: Katerina Mitrokotsa, Associate Professor, Chalmers University of Technology, Department of Computer Science and Engineering, Gothenburg, Sweden, aikmitr (at) chalmer.se

More information: http://www.chalmers.se/en/about-chalmers/Working-at-Chalmers/Vacancies/Pages/default.aspx?rmpage=job&rmjob=6985

Event date: 23 September to 27 September 2019
Submission deadline: 8 February 2019
Notification: 15 March 2019

Event date: 3 June to 7 June 2019
Submission deadline: 29 April 2019

Event date: 8 July 2019
Submission deadline: 28 January 2019
Notification: 8 April 2019

Event date: 26 August to 30 August 2019

In this paper, we compute hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys by carrying out cryptanalytic attacks against digital signatures contained in public blockchains and Internet-wide scans. The ECDSA signature algorithm requires the generation of a per-message secret nonce. This nonce must be generated perfectly uniformly, or else an attacker can exploit the nonce biases to compute the long-term signing key. We use a lattice-based algorithm for solving the hidden number problem to efficiently compute private ECDSA keys that were used with biased signature nonces due to multiple apparent implementation vulnerabilities.

The 2019 Levchin Prize has been awarded to:

• Eric Rescorla, for sustained contributions to the standardization of security protocols, most recently in the development and standardization of TLS 1.3; and
• Mihir Bellare, for outstanding contributions to the design and analysis of real-world cryptography, including the development of the random oracle model, modes-of-operation, HMAC, and formal models of key exchange.

The Levchin Prize was established in 2015 by internet entrepreneur, Max Levchin. The prize honors significant contributions to real-world cryptography and celebrates recent advances that have had a major impact on the practice of cryptography and its use in real-world systems. Up to two awards will be given every year and each carries a cash prize of $10,000.

This year's prize was awarded at the Real World Crypto symposium in San Jose, California, USA.

More information about the Levchin Prize and the awardees can be found at levchinprize.com

Secure block cipher design is a complex discipline which combines mathematics, engineering, and computer science. In order to develop cryptographers who are grounded in all three disciplines, it is necessary to undertake synergistic research as early as possible in technical curricula, particularly at the undergraduate university level. In this work, students are presented with a new block cipher, which is designed to offer moderate security while providing engineering and analysis challenges suitable for the senior undergraduate level. The BIG (Block) (Instructional, Generic) cipher is analyzed for vulnerability to linear cryptanalysis. Further, the cipher is implemented using the Nios II microprocessor and two configurations of memory-mapped hardware accelerators, in the Cyclone V FPGA on the Terasic DE1 System-on-chip (SoC). Three distinct implementations are realized: 1) Purely software (optimized for latency), 2) Purely hardware (optimized for area), and 3) A hardware-software codesign (optimized for throughput-to-area ratio). All three implementations are evaluated in terms of latency (encryption and decryption), throughput (Mbps), area (ALMs), and throughput-to-area (TP/A) ratio (Mbps/ALM); all metrics account for a fully functional Nios II, 8 kilobytes of on-chip RAM, Avalon interconnect, benchmark timer, and any hardware accelerators. In terms of security, we demonstrate recovery of a relationship among 12 key bits using as few as 16,000 plaintext/ciphertext pairs in a 6-round reduced round attack and reveal a diffusion rate of only 43.3 percent after 12 rounds. The implementation results show that the hardware-software codesign achieves a 67x speed-up and 37x increase in TP/A ratio over the software implementation, and 5x speed-up and 5x increase in TP/A ratio compared to the hardware implementation.

CryptoNote protocol proved to be very popular among cryptocurrency startups. We propose several features to extend the basic protocol. Among them are Hybrid Mining (a different mining scheme preventing a straightforward 51% attack), Slow Emission (an emission curve better suited for the real-world adoption), Return Addresses (transaction-specic addresses anonymously linking transactions to their originators), Tiny Addresses (short numerical addresses easy to remember and relay). For breivity, we call these features CryptoNote+.

Multi-client functional encryption (MCFE) is a more flexible variant of functional encryption whose functional decryption involves multiple ciphertexts from different parties. Each party holds a different secret key $\mathsf{sk}_i$ and can independently and adaptively be corrupted by the adversary. We present two compilers for MCFE schemes for the inner-product functionality, both of which support encryption labels. Our first compiler transforms any scheme with a special key-derivation property into a decentralized scheme, as defined by Chotard et al. (ASIACRYPT 2018), thus allowing for a simple distributed way of generating functional decryption keys without a trusted party. Our second compiler allows to lift a unnatural restriction present in existing (decentralized) MCFE schemes,which requires the adversary to ask for a ciphertext from each party. We apply our compilers to the works of Abdalla et al. (CRYPTO 2018) and Chotard et al. (ASIACRYPT 2018) to obtain schemes with hitherto unachieved properties. From Abdalla et al., we obtain instantiations of DMCFE schemes in the standard model (from DDH, Paillier, or LWE) but without labels. From Chotard et al., we obtain a DMCFE scheme with labels still in the random oracle model, but without pairings.

In recent years, Mixed Integer Linear Programming (MILP) has been widely used in cryptanalysis of symmetric-key primitives. For differential and linear cryptanalysis, MILP can be used to solve the two problems: calculation of the minimum number of differential/linear active S-boxes, and search for the best differential/linear characteristics. There are already numerous papers published in this area which either find differential characteristics with good probabilities or ones with small numbers of active S-boxes. However, the efficiency is not satisfactory enough for many symmetric-key primitives. In this paper, we will greatly improve the efficiency of the search algorithms for both the two problems based on MILP. Solving the problems of the calculation of the minimum number of differential/linear active S-boxes and the search for the best differential/linear characteristics can be equivalent to solving an MILP model whose feasible region is the set of all possible differential/linear characteristics. However, searching the whole feasible region is inefficient and high-probability differential/linear characteristics are likely to appear on the smaller feasible region with a low number of active S-boxes at some round. Inspired by the idea of divide-and-conquer approach, we divide the whole feasible region into smaller ones and separately search them. We apply our method to 5 lightweight block ciphers: PRESENT, GIFT-64, RECTANGLE, LBLOCK and TWINE. For each cipher, we obtain better results than the best-known ones. For the calculation of the minimum number of differential active S-boxes, we can reach 31-round PRESENT, 28-round GIFT-64 and 17-round RECTANGLE respectively. For the search for the best differential characteristics, we can reach 23, 14, 15, 21 and 17 rounds for the five ciphers respectively. Based on the duality between the differential cryptanalysis and the linear cryptanalysis, we leave the case for linear cryptanalysis in our future work.

Robustly reusable Fuzzy Extractor (rrFE) considers reusability and robustness simultaneously. We present two approaches to the generic construction of rrFE. Both of approaches make use of a secure sketch and universal hash functions. The first approach also employs a special pseudo-random function (PRF), namely unique-input key-shift (ui-ks) secure PRF, and the second uses a key-shift secure auxiliary-input authenticated encryption (AIAE). The ui-ks security of PRF (resp. key-shift security of AIAE), together with the homomorphic properties of secure sketch and universal hash function, guarantees the reusability and robustness of rrFE. Meanwhile, we show two instantiations of the two approaches respectively. The first instantiation results in the first rrFE from the LWE assumption, while the second instantiation results in the first rrFE from the DDH assumption over non-pairing groups.

We introduce CHURP (CHUrn-Robust Proactive secret sharing). CHURP enables secure secret-sharing in dynamic settings, where the committee of nodes storing a secret changes over time. Designed for blockchains, CHURP has lower communication complexity than previous schemes: $O(n)$ on-chain and $O(n^2)$ off-chain in the optimistic case of no node failures.

CHURP includes several technical innovations: An efficient new proactivization scheme of independent interest, a technique (using asymmetric bivariate polynomials) for efficiently changing secret-sharing thresholds, and a hedge against setup failures in an efficient polynomial commitment scheme. We also introduce a general new technique for inexpensive off-chain communication across the peer-to-peer networks of permissionless blockchains.

We formally prove the security of CHURP, report on an implementation, and present performance measurements.

Message franking enables cryptographically verifiable reporting of abusive content in end-to-end encrypted messaging. Grubbs, Lu, and Ristenpart recently formalized the needed underlying primitive, what they call compactly committing authenticated encryption (AE), and analyzed the security of a number of approaches. But all known secure schemes are still slow compared to the fastest standard AE schemes. For this reason Facebook Messenger uses AES-GCM for franking of attachments such as images or videos. We show how to break Facebook’s attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. The core problem stems from use of fast but non-committing AE, and so we build the fastest compactly committing AE schemes to date. To do so we introduce a new primitive, called encryptment, which captures the essential properties needed. We prove that, unfortunately, schemes with performance profile similar to AES-GCM won’t work. Instead, we show how to efficiently transform Merkle-Damgärd-style hash functions into secure encryptments, and how to efficiently build compactly committing AE from encryptment. Ultimately our main construction allows franking using just a single computation of SHA-256 or SHA-3. Encryptment proves useful for a variety of other applications, such as remotely keyed AE and concealments, and our results imply the first single-pass schemes in these settings as well.

NTRU lattices are a class of polynomial rings which allow for compact and efficient representations of the lattice basis, thereby offering very good performance characteristics for the asymmetric algorithms that use them. Signature algorithms based on NTRU lattices have fast signature generation and verification, and relatively small signatures, public keys and private keys.

A few lattice-based cryptographic schemes entail, generally during the key generation, solving the NTRU equation: $$ f G - g F = q \mod x^n + 1 $$ Here $f$ and $g$ are fixed, the goal is to compute solutions $F$ and $G$ to the equation, and all the polynomials are in $\mathbb{Z}[x]/(x^n + 1)$. The existing methods for solving this equation are quite cumbersome: their time and space complexities are at least cubic and quadratic in the dimension $n$, and for typical parameters they therefore require several megabytes of RAM and take more than a second on a typical laptop, precluding onboard key generation in embedded systems such as smart cards.

In this work, we present two new algorithms for solving the NTRU equation. Both algorithms make a repeated use of the field norm in tower of fields; it allows them to be faster and more compact than existing algorithms by factors $\tilde O(n)$. For lattice-based schemes considered in practice, this reduces both the computation time and RAM usage by factors at least 100, making key pair generation within range of smart card abilities.

Distributed credit networks, such as Ripple and Stellar, are becoming popular as an alternative means for financial transactions. However, the current designs do not preserve user privacy or are not truly decentralized. In this paper, we explore the creation of a distributed credit network that preserves user and transaction privacy and unlinkability. We propose BlAnC, a novel, fully decentralized blockchain-based credit network where credit transfer between a sender-receiver pair happens on demand. In BlAnC, multiple concurrent transactions can occur seamlessly, and malicious network actors that do not follow the protocols and/or disrupt operations can be identified efficiently. We perform security analysis of our proposed protocols in the universal composability framework to demonstrate its strength, and discuss how our network handles operational dynamics. We also present preliminary experiments and scalability analyses.