International Association for Cryptologic Research

# IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

25 March 2017
ePrint Report Pseudorandomness of Ring-LWE for Any Ring and Modulus Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to the decision version of (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.
ePrint Report Threshold Fully Homomorphic Encryption Aayush Jain, Peter M. R. Rasmussen, Amit Sahai
We formally define and give the first construction of (leveled) threshold fully homomorphic encryption for any access structure induced by a monotone boolean formula and in particular for the threshold access structure. Our construction is based on the learning with errors assumption and can be instantiated with any existing homomorphic encryption scheme that satisfies fairly general conditions, such as Gentry, Sahai, Waters (CRYPTO 2013) and Brakerski, Gentry, Vaikuntanathan (ITCS 2012).

From threshold homomorphic encryption, we construct function secret sharing and distributed pseudorandom functions for the aforementioned access structures. No such constructions were known prior to this work.
21 March 2017
Job Posting PhD student Karlsruhe Institute of Technology, Germany
We are looking for a PhD student in theoretical cryptography. The research focus will be the development and analysis of classical and new cryptographic building blocks (such as public-key encryption and obfuscation).

The research will take place in the cryptography and security group at KIT. The research position will be multi-year and fully funded, with a starting date as soon as possible (negotiable). There is no closing date; applications will be considered until the position is filled.

For more information about the position, contact Dennis (dot) Hofheinz (at) kit (dot) edu. Your application should include a CV, and a letter of motivation.

Closing date for applications:

Job Posting Postdoc Karlsruhe Institute of Technology, Germany
We are looking for a postdoctoral researcher in theoretical cryptography. The research focus will be the development and analysis of classical and new cryptographic building blocks (such as public-key encryption or obfuscation).

The research will take place in the cryptography and security group at KIT. The research position will be multi-year and fully funded, with a starting date as soon as possible (negotiable). There is no closing date; applications will be considered until the position is filled.

For more information about the position, contact Dennis (dot) Hofheinz (at) kit (dot) edu. Your application should include a CV, and at least two references.

Closing date for applications:

Event date: 24 October to 27 October 2017
Job Posting PhD Student Aarhus University, Denmark
The Cryptography and Security group of Aarhus University is looking for PhD students interested in working in the area of cryptographic protocols (secure two/multi party computation, zero-knowledge, ORAM, etc.) under the supervision of Associate Professor Claudio Orlandi. The PhD position is financed by a \"Sapere Aude\" starting grant (Danish Council for Independent Research).

Applicants who have completed (or are about to complete) a master in computer science, computer engineering, or math are welcome to apply by contacting me.

All applications will be processed by the Graduate School of Science and Technology of Aarhus University (follow the link for more information). The next deadlines for application is May 1st, (earliest start on August 1st).

Closing date for applications: 1 May 2017

Contact: Claudio Orlandi, Associate Professor

orlandi (at) cs.au.dk

Fixed Term Contract 2 years (CDD), full-time 40 hrs/week Start day: July 2017 or later upon agreement.

The successful candidate will join the CryptoLUX group led by Prof. Alex Biryukov. He or she will contribute to a research project on future directions in symmetric cryptography in the areas of:

• Lightweight block ciphers and hash functions
• Side-channel attacks on symmetric cryptosystems and countermeasures
• Design and security analysis of blockchain technologies
• Proof-of-work schemes for use in digital currencies or denial-of-service prevention

The University offers a two-year employment contract which may be extended up to five years.

Closing date for applications: 30 April 2017

Contact: Alex Biryukov

The Department of Computer Science at the University of Surrey invites applications for two posts of Lecturer/Senior Lecturer (Assistant Professor/Associate Professor) in Secure Systems.

Further details and instructions for applying are at https://jobs.surrey.ac.uk/vacancy.aspx?ref=083116-R

Salary range: ?39324 to ?57674

We aim to attract outstanding candidates to the Secure Systems group who have strong visions for research, a growing international research profile, a passion for teaching, and who value collaborative research and working in a team.

The first post is in the area of ‘security through hardware and applied cryptography’, an area that we are growing, with the recent appointment of Professor Liqun Chen.

The second post is in ‘secure systems and applications’, to enhance or complement one or more of the following areas: trusted computing, security through hardware, verification, data privacy, cyber-physical and internet of things security, cloud or mobile security, machine learning and data analytics applied to security, human factors, formal methods and applied cryptography.

Applicants to both posts should have a PhD in a relevant subject or equivalent professional experience. An ability to produce high quality outputs is also required. The appointed candidates will be expected to contribute to all aspects of the Department’s activities.

We are looking for individuals academics that can inspire students through their curiosity for leading-edge aspects of technology. The Department runs a GCHQ-certified MSc in Information Security, which is the flagship programme of the Secure Systems group.

The University and the Department specifically are committed to building a culturally diverse organisation and strongly encourages applications from female and minority candidates. The Department shares the Athena SWAN ideals with respect to the equality and diversity agenda.

Closing date for applications: 2 May 2017

Contact: Professor Steve Schneider

Director of Surrey Centre for Cyber Security

University of Surrey, Guildford, Surrey GU2 7XH, UK

s.schneider (at) surrey.ac.uk

+44 1483 689637

Job Posting PhD student Karlsruhe Institute of Technology, Germany

We are looking for a PhD student in theoretical cryptography. The research focus should be the development and analysis of classical and new cryptographic building blocks (such as public-key encryption and obfuscation).

The research will take place in the cryptography and security group at KIT. The research position will be multi-year and fully funded, with a starting date as soon as possible (negotiable). There is no closing date; applications will be considered until the position is filled.

For more information about the position, contact Dennis (dot) Hofheinz (at) kit (dot) edu. Your application should include a CV, and a letter of motivation.

Closing date for applications:

Job Posting Postdoc Karlsruhe Institute of Technology, Germany

We are looking for a postdoctoral researcher in theoretical cryptography. The research focus should be the development and analysis of classical and new cryptographic building blocks (such as public-key encryption and obfuscation).

The research will take place in the cryptography and security group at KIT. The research position will be multi-year and fully funded, with a starting date as soon as possible (negotiable). There is no closing date; applications will be considered until the position is filled.

For more information about the position, contact Dennis (dot) Hofheinz (at) kit (dot) edu. Your application should include a CV, and at least two references.

Closing date for applications:

The Security and Privacy Group* at Birmingham seeks applications for a new permanent Lecturer post in cyber security.

Candidates are expected to have established research careers, demonstrating sustained excellent publication record and some ability to attract research funding. We encourage candidates whose research complements and extends the current capabilities of the group**, but are particularly interested in those working in the areas of systems security, malware analysis and/or reverse engineering.

The deadline for applications is 2 April 2017. Further details and instructions for applying are at

• http://www.jobs.ac.uk/job/AXS707/lecturer-in-computer-security/

The School of Computer Science is ranked in the top 10 UK computer science departments for the number of world-leading publications in terms of originality, significance and rigour by the Research Excellence Framework 2014, conducted by the UK government. The University has identified computer security and privacy as an area for investment. The group is a GCHQ/EPSRC Academic Centre of Excellence in Cyber Security Research, one of 13 such centres in the UK. Informal enquiries about these posts are welcome, and can be addressed to any member of the group and/or to Professor Mark Ryan, m.d.ryan[at]cs.bham.ac.uk.

* Members of the group are: Rami Bahsoon, Ian Batten, Tom Chothia, David Galindo, Flavio Garcia, David Oswald, Dave Parker, Eike Ritter, Mark Ryan, Erik Tews.

** The current research focus of the group includes: applied cryptography, formal verification, automotive security, embedded devices and IoT security (including ICS), wireless security, cloud security, electronic voting, and security and privacy for society.

Closing date for applications: 2 April 2017

20 March 2017
The analysis of real-world protocols, in particular key exchange protocols and protocols building on these protocols, is a very complex, error-prone, and tedious task. Besides the complexity of the protocols itself, one important reason for this is that the security of the protocols has to be reduced to the security of the underlying cryptographic primitives for every protocol time and again.

We would therefore like to get rid of reduction proofs for real-world key exchange protocols as much as possible and in many cases altogether, also for higher-level protocols which use the exchanged keys. So far some first steps have been taken in this direction. But existing work is still quite limited, and, for example, does not support Diffie-Hellman (DH) key exchange, a prevalent cryptographic primitive for real-world protocols.

In this paper, building on work by K{\"u}sters and Tuengerthal, we provide an ideal functionality in the universal composability setting which supports several common cryptographic primitives, including DH key exchange. This functionality helps to avoid reduction proofs in the analysis of real-world protocols and often eliminates them completely. We also propose a new general ideal key exchange functionality which allows higher-level protocols to use exchanged keys in an ideal way. As a proof of concept, we apply our framework to three practical DH key exchange protocols, namely ISO 9798-3, SIGMA, and OPTLS.
ePrint Report New Limits for AES Known-Key Distinguishers Lorenzo Grassi, Christian Rechberger
Known-key distinguishers have been introduced to better understand the security of block ciphers in situations where the key can not be considered to be secret.

AES is often considered as a target of such analyses, simply because AES or its building blocks are used in many settings that go beyond classical encryption. The most recent known-key model of Gilbert (proposed at Asiacrypt 2014) allows to consider two 4-round distinguishers combined in an inside-out fashion (8 core rounds), and to extend it by one round in each direction (two extension rounds). The resulting 10-round distinguisher has a time complexity of $2^{64}$. In that work, arguments were put forward suggesting that two extension rounds seems to be the limit in the known-key model, and that likely only a distinguisher that exploits the balance property can be extended in such way.

In this paper we disprove both these conjectures and arrive at the following results. We firstly show that the technique proposed by Gilbert can also be used to extend a known-key distinguisher based on truncated differential trails. This allows to improve all the known-key distinguishers currently present in literature for AES up to 10 rounds of AES. In particular, we are able to set up a 9-round known-key distinguisher for AES with a time complexity of $2^{23}$ and a 10-round known-key distinguisher with a time complexity of $2^{50}$. Secondly we are also able to show that more than two extension rounds are possible. As a result of this, we describe the first known-key distinguishers on 12 rounds of AES, by extending an 8-round known-key distinguisher by two rounds in each direction (four extension rounds). The time complexity is $2^{82}$.

We conclude with a discussion on why it seems not feasible to set up similar distinguishers on 14 rounds exploiting the same strategy.
ePrint Report Towards Easy Key Enumeration Changhai Ou, Degang Sun, Zhu Wang, Xinping Zhou, Juan Ai
Key enumeration solutions are post-processing schemes for the output sequences of side channel distinguishers, the application of which are prevented by very large key candidate space and computation power requirements. The attacker may spend several days or months to enumerate a huge key candidate space (i.e. $2^{40}$). In this paper, we aim at pre-processing and reducing the key candidate space by deleting impossible key candidates before enumeration. A new distinguisher named Group Collision Attack (GCA) is given. Moreover, we introduce key verification into key recovery and a new divide and conquer strategy named Key Grouping Enumeration (KGE) is proposed. KGE divides the huge key space into several groups and uses GCA to delete impossible key combinations and output possible ones in each group. KGE then recombines the remaining key candidates in each group using verification. The number of remaining key candidates becomes much more smaller through these two impossible key candidate deletion steps with a small amount of computation. Thus, the attacker can use KGE as a pre-processing tool of key enumeration and enumerate the key more easily and fast in a much smaller candidate space.
We conduct a reduction-based security analysis of the Extensible Authentication Protocol (EAP), a widely used three-party authentication framework. EAP is often found in enterprise networks where it allows a client and an authenticator to establish a shared key with the help of a mutually trusted server. Considered as a three-party authenticated key exchange protocol, we show that the general EAP construction achieves a security notion we call 3P-AKE$^w$. %under the assumption that it employs \emph{channel binding}. %Channel binding ensures that the session key derived by the client and the authenticator is cryptographically bound to them. The 3P-AKE$^w$ security notion captures the idea of \emph{weak forward secrecy} and is a simplified three-party version of the well-known eCK model in the two-pass variant. Our analysis is modular and reflects the compositional nature of EAP.

Additionally, we show that the security of EAP can easily be upgraded to provide \emph{full} forward secrecy simply by adding a subsequent key-confirmation step between the client and the authenticator. In practice this key-confirmation step is often carried out in the form of a 2P-AKE protocol which uses EAP to bootstrap its authentication. A concrete example is the extremely common IEEE~802.11 protocol used in WLANs. In enterprise settings EAP is often used in conjunction with IEEE~802.11 in order to allow the wireless client to authenticate itself to a wireless access point (the authenticator) through some centrally administrated server. Building on our modular results for EAP, we get as our second major result the first reduction-based security result for IEEE~802.11 combined with EAP.
Masking with random values is an effective countermeasure against side-channel attacks. For cryptographic algorithms combining arithmetic and Boolean masking, it is necessary to switch from arithmetic to Boolean masking and vice versa. Following a recent approach by Hutter and Tunstall, we describe a high-order Boolean to arithmetic conversion algorithm whose complexity is independent of the register size k. Our new algorithm is proven secure in the Ishai, Sahai and Wagner (ISW) framework for private circuits. In practice, for small orders, our new countermeasure is one order of magnitude faster than previous work. We also describe a 3rd-order attack against the 3rd-order Hutter-Tunstall algorithm, and a constant, 4th-order attack against the t-th order Hutter-Tunstall algorithms, for any t>=4.
ePrint Report A Lattice-Based Universal Thresholdizer for Cryptographic Systems Dan Boneh, Rosario Gennaro, Steven Goldfeder, Sam Kim
We develop a general approach to thresholdizing a large class of (non-threshold) cryptographic schemes. We show how to add threshold functionality to CCA-secure public-key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. To do so, we introduce a general tool, called a universal thresholdizer, from which many threshold systems are possible. The tool builds upon a lattice-based fully-homomorphic encryption (FHE) system. Applying the tool to a (non-threshold) lattice-based signature, gives the first single-round threshold signature from the learning with errors problem (LWE). Applying the tool to a (non-threshold) lattice-base CCA-secure PKE, gives a single-round lattice-based threshold CCA-secure PKE.
Recent works (Lin, EUROCRYPT'16, ePrint'16; Lin and Vaikunthanathan, FOCS'16; Ananth and Sahai, EUROCRYPT'17) establish a tight connection between constructions of indistinguishability obfuscation from $L$-linear maps and pseudo-random generators (PRGs) with output locality $L$. This approach appears however not to be suitable to obtain instantiations from bilinear maps, as no polynomial-stretch PRG with locality lower than 5 exists.

This paper presents new candidate constructions of indistinguishability obfuscation from (i) $L$-linear maps for any $L \ge 2$, and (ii) PRGs with block-wise locality $L$. A PRG has block-wise locality $L$ if every output bit depends on at most $L$ (disjoint) input blocks, each consisting of up to $\log \lambda$ input bits. In particular, we give:

A construction of a general-purpose indistinguishability obfuscator from $L$-linear maps and a subexponentially-secure PRG with block-wise locality $L$ and polynomial stretch.

A construction of general-purpose functional encryption from $L$-linear maps and any slightly super-polynomially secure PRG with block-wise locality $L$ and polynomial stretch.

All our constructions are based on the SXDH assumption on $L$-linear maps and subexponential Learning With Errors (LWE) assumption. In the special case of $L = 2$, our constructions can be alternatively based on bilinear maps with the Matrix Diffie-Hellman assumption and the 3-party Decision Diffie Hellman assumption, without assuming LWE. Concurrently, we initiate the study of candidate PRGs with block-wise locality $L\ge 2$ based on Goldreich's local functions, and their security. In particular, lower bounds on the locality of PRGs do not apply to block-wise locality for any $L \ge 2$, and the security of instantiations with block-wise locality $L \ge 3$ is backed by similar validation as constructions with (conventional) locality $5$. We complement this with hardness amplification techniques that weaken the pseudorandomness requirement on our candidates to qualitatively weaker requirements.
ePrint Report Proof of Luck: an Efficient Blockchain Consensus Protocol Mitar Milutinovic, Warren He, Howard Wu, Maxinder Kanwal
In the paper, we present designs for multiple blockchain consensus primitives and a novel blockchain system, all based on the use of trusted execution environments (TEEs), such as Intel SGX-enabled CPUs. First, we show how using TEEs for existing proof of work schemes can make mining equitably distributed by preventing the use of ASICs. Next, we extend the design with proof of time and proof of ownership consensus primitives to make mining energy- and time-efficient. Further improving on these designs, we present a blockchain using a proof of luck consensus protocol. Our proof of luck blockchain uses a TEE platform's random number generation to choose a consensus leader, which offers low-latency transaction validation, deterministic confirmation time, negligible energy consumption, and equitably distributed mining. Lastly, we discuss a potential protection against up to a constant number of compromised TEEs.
ePrint Report IPcore implementation susceptibility: A case study of Low latency ciphers Dillibabu Shanmugam, Ravikumar Selvam, Suganya Annadurai
Security evaluation of third-party cryptographic IP (Intellectual Property) cores is often ignored due to several reasons including, lack of awareness about its adversity, lack of trust validation methodology otherwise view security as a byproduct. Particularly, the validation of low latency cipher IP core on Internet of Things (IoT) devices is crucial as they may otherwise become vulnerable for information theft. In this paper, we share an (Un)intentional way of cipher implementation as IP core(hard) become susceptible against side channel attack and show how the susceptible implementation can be experimentally exploited to reveal secret key in FPGA using power analysis. In this paper our contributions are: First, we present Look-Up Table (LUT) based unrolled implementation of PRINCE block cipher with place and route constraints in FPGA. Second, using power analysis attack we recover 128-bit key of PRINCE with complexity of 2^9. Finally, we conclude the paper with the experimental results.
ePrint Report Efficient Multivariate Ring Signature Schemes Mohamed Saied Emam Mohamed, Albrecht Petzoldt
Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of more advanced schemes, such as schemes for oblivious transfer and signature schemes with special properties. While, in the last years, a number of multivariate ring signature schemes have been proposed, all of these have weaknesses in terms of security or efficiency. In this paper we propose a simple and efficient technique to extend arbitrary multivariate signature schemes to ring signature schemes and illustrate it using the example of Rainbow. The resulting scheme provides perfect anonymity for the signer (as member of a group), as well as shorter ring signatures than all previously proposed post-quantum ring signature schemes.
ePrint Report An Analysis of FV Parameters Impact Towards its Hardware Acceleration Joël Cathébras, Alexandre Carbon, Renaud Sirdey, Nicolas Ventroux
The development of cloud computing services is restrained by privacy concerns. Centralized medical services for instance, require a guarantee of confidentiality when using outsourced computation platforms. Fully Homomorphic Encryption is an intuitive solution to address such issue, but until 2009, existing schemes were only able to evaluate a reduced number of operations (Partially Homomorphic Encryption). In 2009, C. Gentry proposed a blueprint to construct FHE schemes from SHE schemes. However, it was not practical due to the huge data size overhead and the exponential noise growth of the initial SHE. Since then, major improvements have been made over SHE schemes and their noise management, and resulting schemes, like BGV and FV, allow to foresee small applications.

Besides scheme improvements, new practical approaches were proposed to bring homomorphic encryption closer to practice. The $IV$-based stream cipher trans-ciphering approach brought by Canteaut et al. in 2015 reduces the on-line latency of the trans-ciphering process to a simple homomorphic addition. The homomorphic evaluation of stream ciphers, that produces the trans-ciphering keystream, could be computed in an off-line phase, resulting in an almost transparent trans-ciphering process from the user point of view. This approach combined with hardware accelerations could bring homomorphic encryption closer to practice.

This paper deals the choice of FV parameters for efficient implementation of this scheme in the light of related works' common approaches. At first sight, using large polynomial degree to reduce the coefficients size seemed to be advantageous, but further observations contradict it. Large polynomial degrees imply larger ciphertexts and more complex implementations, but smaller ones imply more primes to find for CRT polynomial representation. The result of this preliminary work for the choice of an adequate hardware target motivates the choice of small degree polynomials rather than small coefficients for the FV scheme.
Cross-VM attacks have emerged as a major threat on commercial clouds. These attacks commonly exploit hardware level leakages on shared physical servers. A co-located machine can readily feel the presence of a co-located instance with a heavy computational load through performance degradation due to contention on shared resources. Shared cache architectures such as the last level cache (LLC) have become a popular leakage source to mount cross-VM attack. By exploiting LLC leakages, researchers have already shown that it is possible to recover fine grain information such as cryptographic keys from popular software libraries. This makes it essential to verify implementations that handle sensitive data across the many versions and numerous target platforms, a task too complicated, error prone and costly to be handled by human beings.

Here we propose a machine learning based technique to classify applications according to their cache access profiles. We show that with minimal and simple manual processing steps feature vectors can be used to train models using support vector machines to classify the applications with a high degree of success. The profiling and training steps are completely automated and do not require any inspection or study of the code to be classified. In native execution, we achieve a successful classification rate as high as 98\% (L1 cache) and 78\% (LLC) over 40 benchmark applications in the Phoronix suite with mild training. In the cross-VM setting on the noisy Amazon EC2 the success rate drops to 60\% for a suite of 25 applications. With this initial study we demonstrate that it is possible to train meaningful models to successfully predict applications running in co-located instances.
ePrint Report Model-counting Approaches For Nonlinear Numerical Constraints Mateus Borges, Quoc-Sang Phan, Antonio Filieri, Corina S. P\u{a}s\u{a}reanu
Model counting is of central importance in quantitative reasoning about systems. Examples include computing the probability that a system successfully accomplishes its task without errors, and measuring the number of bits leaked by a system to an adversary in Shannon entropy. Most previous work in those areas demonstrated their analysis on programs with linear constraints, in which cases model counting is polynomial time. Model counting for nonlinear constraints is notoriously hard, and thus programs with nonlinear constraints are not well-studied. This paper surveys state-of-the-art techniques and tools for model counting with respect to SMT constraints, modulo the bitvector theory, since this theory is decidable, and it can express nonlinear constraints that arise from the analysis of computer programs. We integrate these techniques within the Symbolic Pathfinder platform and evaluate them on difficult nonlinear constraints generated from the analysis of cryptographic functions.
15 March 2017
Design of JPEG Anti-Forensics Scheme(s) for evaluation of existing JPEG forensic schemes--

Explosive growth in the numbers of forged images has created a situation where authenticity of every image is a suspect. Also it is not humanly possible to examine each suspect image manually by experts. Thus researchers are coming up with methods to verify the authenticity of an image without any human intervention. New schemes for verification of suspect images are getting published every other day without any formal analysis of their performance. Most of these schemes employ fancy image processing techniques and their reliability is proven against standard image processing operations that can be performed using off the shelf software like Adobe Photoshop. A proper evaluation of these forensics schemes is need of the hour and we want to design anti-forensics scheme meant for JPEG compression.

Closing date for applications: 23 March 2017

14 March 2017
ePrint Report Key Recovery: Inert and Public Colin Boyd, Xavier Boyen, Christopher Carr, Thomas Haines
We propose a public key infrastructure framework, inspired by modern distributed cryptocurrencies, that allows for tunable key escrow, where the availability of key escrow is only provided under strict conditions and enforced through cryptographic measures. We argue that any key escrow scheme designed for the global scale must be both inert --- requiring considerable effort to recover a key --- and public --- everybody should be aware of all key recovery attempts. To this end, one of the contributions of this work is an abstract design of a proofof-work scheme that demonstrates the ability to recover a private key for some generic public key scheme. Our framework represents a new direction for key escrow, seeking an acceptable compromise between the demands for control of cryptography on the Internet and the fundamental rights of privacy, which we seek to align by drawing parallels to the physical world.
ePrint Report Full accounting for verifiable outsourcing Riad S. Wahby, Ye Ji, Andrew J. Blumberg, abhi shelat, Justin Thaler, Michael Walfish, Thomas Wies
Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when these costs are cheaper than not outsourcing. Yet, prover costs are generally ignored. The only exception is Verifiable ASICs (VA), wherein the prover is a custom chip; however, the only prior VA system ignores the cost of precomputation.

This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe’s base is an interactive proof geared to data parallel computation. Giraffe makes this protocol asymptotically optimal for the prover, which is of independent interest. Giraffe also develops a design template that produces hardware designs automatically for a wide range of parameters, introduces hardware primitives molded to the protocol’s data flows, and incorporates program analyses that expand applicability. Giraffe wins even when outsourcing several tens of sub-computations, scales to 500x larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.
ePrint Report Forkable Strings are Rare Alexander Russell, Cristopher Moore, Aggelos Kiayias, Saad Quader
A fundamental combinatorial notion related to the dynamics of the Ouroboros proof-of-stake blockchain protocol (https://eprint.iacr.org/2016/889) is that of a forkable string. The original description and analysis of the protocol established that the probability that a string of length $n$ is forkable, when drawn from a binomial distribution with parameter $(1 - \epsilon)/2$, is $\exp(-\Omega(\sqrt{n}))$. In this note we improve this estimate to $\exp(-\Omega(n))$.
Event date: 31 March 2017