IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
27 March 2021
Daniel R. L. Brown
An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where $\textbf{M}$ is a field multiplication and $\textbf{S}$ is a field squaring. This is approximately $(3.55\textbf{M} + 4.07\textbf{S})$/bit, with $1\textbf{S}$/bit for input decompression and $1\textbf{S}$/bit for output normalization. Optimizing speed by allowing uncompressed input points leads to an estimate $(3.38\textbf{M}+2.95\textbf{S})$/bit.
To mitigate some side-channel attacks, the secret scalar is only used to copy curve points from one array to another: the field operations used are fixed and independent of the secret scalar. The method is likely vulnerable to cache-timing attacks, nonetheless.
25 March 2021
Qingdao, China, 11 August - 14 August 2021
Submission deadline: 20 May 2021
Notification: 30 July 2021
The Test-of-Time award for Eurocrypt 2006 is awarded to "A provable-security treatment of the key-wrap problem" (Phillip Rogaway and Thomas Shrimpton), for placing the important real world primitive of key-wrapping on a solid theoretic foundation.
The Test-of-Time award for Crypto 2006 is awarded to "New proofs for NMAC and HMAC: Security without collision-resistance" (Mihir Bellare), for proving that the security of the widely deployed HMAC construction does not depend on the collision resistance of the underlying hash function.
The Test-of-Time award for Asiacrypt 2006 is awarded to "Simulation-sound NIZK proofs for a practical language and constant size group signatures" (Jens Groth), for constructing asymptotically optimal NIZK proofs and group signatures without using random oracles, and paving the way to practical constructions.
For more information, see https://www.iacr.org/testoftime.
Imperial College London
As part of a wider effort on Blockchain Security and Finance research, we are offering funded Ph.D. positions related to the field of Decentralized Finance for stellar candidates.
We offer a striving research group with:- Over 15 combined years of full-time research experience in the blockchain domain.
- Very consistent publications in highly competitive venues. So far, in the year 2021 alone: 2x IEEE Symposium on Security & Privacy (Oakland), 2x Financial Cryptography and Datasecurity (FC) and 1x IEEE EuroS&P paper.
- Hands-on supervision and collaboration among senior and junior Ph.D. students.
- Interdisciplinary challenges covering information security, cryptography, game theoretic incentives, economics, finance, systems, etc.
- Practical, real-world applicable research.
- Regular Zoom/Slack/iPad calls/chats/whiteboard sessions.
- Fun group events, such as game evenings etc.
Your profile ideally matches with the following:
- You enjoy to communicate transparently and openly, e.g. through regular/daily Zoom calls and slack.
- You are self-motivated, outcome drive and productive, especially during the current pandemic.
- You have a strong analytical background coupled with a solid ability to write clean and simple code.
- You prefer simplicity over complexity. You first strive towards a quick and non-perfect solution, and don't prematurely optimise something that shouldn't exist.
- While you may not yet like writing, you want to learn being able to write the perfect English text.
- You want to produce world-leading research, which you'd like to get challenged by reviewers from only the best conferences.
Closing date for applications:
Contact: arthur@gervais.cc
More information: https://scholar.google.com/citations?hl=en&user=jLr_xi4AAAAJ&view_op=list_works&sortby=pubdate
Graz University of Technology, Graz, Austria
In order to complement our team, we are looking for a fulltime PhD researcher in Post-Quantum Cryptography.
Responsibilities:
The PhD researcher will be working on the implementation and side-channel security aspects of post-quantum cryptography within the “Cyroptografic Engineering” group within the “Secure Systems” area at IAIK.
The PhD candidate will have to start by May/June 2021.
Required Qualifications:
• MSc degree (or close to completion) in computer science, information and computer engineering, software development, mathematics, or a related field.
• Research experience from MSc/BSc projects.
• Outstanding candidates with BSc degree and publications in related research area are also welcome.
• Experience with cryptography, programming, and digital circuit design (ASIC or FPGA) design
How to apply:
Applications, curriculum vitae and other documents should preferably be uploaded here https://free.formcloud.de/formcycle/form/provide/7780/. Please select „7050 – PhD 2021 – crypteng" as a reference number. The application deadline is April 20th 2021.
Closing date for applications:
Contact: For more detailed information please conctact Sujoy Sinha Roy - sujoy.sinharoy@iaik.tugraz.at.
More information: https://www.tugraz.at/index.php?id=50397
Department of Computer Science, The University of Manchester, UK
The Department of Computer Science at the University of Manchester (UK) wishes to appoint a Senior Lecturer in Systems Security. The new appointment will complement existing world-class research in software security and automated reasoning.
Applicants should be computer scientists with a strong interest and track record in a relevant area of systems security, for example, cryptography, operating systems and virtualization, distributed systems security, authentication, authorization, and accountability. We also encourage applicants with a strong interest and track record in code and data integrity, malware analysis, integrity, trustworthiness, privacy, and anonymity. You will be a member of the Formal Methods Group with access to expertise in program analysis and reasoning methods. We are particularly interested in developing collaborations involving several groups within the department and wider University. For example, an exciting opportunity exists to work closely with the well-known advanced processor technologies group to study applications in massively parallel software and the IoT. Thus, experience and interest in collaborative research are particularly welcome.
You should hold a relevant Ph.D. or equivalent, have an excellent international publication record in top security conferences (e.g., ACM CCS, IEEE S&P, NDSS, USENIX Security). The applicants should show the capability of developing a portfolio of funded research activities in a multidisciplinary environment and have a solid commitment to excellence in teaching.
Closing date for applications:
Contact:
Enquiries about the vacancy, shortlisting and interviews: Dr. Lucas Cordeiro (lucas.cordeiro@manchester.ac.uk) or Dr. Giles Reger (giles.reger@manchester.ac.uk).
General enquiries: hrservices@manchester.ac.uk
More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?isPreview=Yes&jobid=19901
22 March 2021
Jiaxin Pan, Magnus Ringerud
Shweta Agrawal, Damien Stehle, Anshu Yadav
1. Threshold Signatures. For round optimal threshold signatures, we improve the only known construction by Boneh et al. [CRYPTO'18] as follows:
a. Efficiency. We reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease signature bit-lengths from $\widetilde{O}(\lambda^3)$ to $\widetilde{O}(\lambda)$.
b. Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing queries are made. We improve this in two ways: in the ROM, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline pre-processing phase.
2. Blind Signatures. For blind signatures, we improve the state of art lattice-based construction by Hauck et al.[CRYPTO'20] as follows:
a. Round Complexity. We improve the round complexity from three to two -- this is optimal.
b. Efficiency. Again, we reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of signatures and $\lambda$ is the security parameter.
c. Number of Signing Queries. Unlike the scheme from Hauck et al., our construction enjoys a proof that is not restricted to a polylogarithmic number of signatures. Using lattice hardness assumptions over rings, we obtain signatures of bit-lengths bounded as $\widetilde{O}(\lambda)$. In contrast, the signature bit-length in the scheme from Hauck et al. is $\Omega(\lambda^3 + Q_S \cdot \lambda)$.
Concretely, we can obtain blind/threshold signatures of size $\approx 3$ KB using a variant of Dilithium-G with $\approx 128$ bit-security, for adversaries limited to getting $256$ signatures. In contrast, parameters provided by Hauck et al. lead to blind signatures of $\approx 7.73$ MB, for adversaries limited to getting 7 signatures, while concrete parameters are not provided for the construction of threshold signatures by Boneh et al.
Cholun Kim
Yunwen Liu, Zhongfeng Niu, Siwei Sun, Chao Li, Lei Hu
Fabrice Benhamouda, Aayush Jain, Ilan Komargodski, Huijia Lin
We give a construction of mrNISC that achieves standard simulation security, as classical multi-round MPC protocols achieve. Our construction relies on the Learning With Errors (LWE) assumption with polynomial modulus, and on the existence of a pseudorandom function (PRF) in $\mathsf{NC}^1$. We achieve semi-malicious security in the plain model and malicious security by further relying on trusted setup (which is unavoidable for mrNISC). In comparison, the only previously known constructions of mrNISC were either using bilinear maps or using strong primitives such as program obfuscation.
We use our mrNISC to obtain new Multi-Key FHE (MKFHE) schemes with threshold decryption:
$\bullet$ In the CRS model, we obtain threshold MKFHE for $\mathsf{NC}^1$ based on LWE with only $\textit{polynomial}$ modulus and PRFs in $\mathsf{NC}^1$, whereas all previous constructions rely on LWE with super-polynomial modulus-to-noise ratio.
$\bullet$ In the plain model, we obtain threshold levelled MKFHE for $\mathsf{P}$ based on LWE with $\textit{polynomial}$ modulus, PRF in $\mathsf{NC}^1$, and NTRU, and another scheme for constant number of parties from LWE with sub-exponential modulus-to-noise ratio. The only known prior construction of threshold MKFHE (Ananth et al., TCC 2020) in the plain model restricts the set of parties who can compute together at the onset.
Nguyen Thoi Minh Quan
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
Rafael Dowsley, Caleb Horst, Anderson C A Nascimento
Akshaya Mani, Ian Goldberg
Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service attacks). This suggests that a simple solution such as throttling traffic flow at the Tor exits may permit early detection of these attacks.
However, naively monitoring and throttling traffic at the Tor exits can endanger the privacy of the network's users. Indeed, many recent works have proposed private measurement systems that support safe aggregation of exit statistics. However, these systems do not permit identification of "unlinkable" connections that are part of a high-volume attack. Doing so could allow Tor to take proper remedial actions, such as dropping the attack traffic, but care must be taken to protect privacy.
We present ZXAD (pronounced "zed-zad"), the first zero-knowledge based private Tor exit abuse detection system. ZXAD detects large-volume traffic attacks without revealing any information, apart from the fact that some user is conveying a high volume of traffic through Tor. We formally prove the correctness and security of ZXAD. We also measure two proof-of-concept implementations of our zero-knowledge proofs and show that ZXAD operates with low bandwidth and processing overheads.
Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, Mridul Nandi
We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In particular, it provides birthday security for hashing $5$ inputs using three $2n$-to-$n$ compression calls, instead of only $4$ inputs in prior constructions.
Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where $t$ message blocks are hashed using only $3t/4$ calls to the $2n$-to-$n$ compression functions; a $25\%$ saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using $3$ (resp. $2$) parallel execution units; saving a factor of $4$ (resp. $2$) over the traditional MD-hashing, where parallelism does not help to process one message.
We also get a novel variant of a Merkle tree, where $t$ message blocks can be processed using $0.75(t-1)$ compression function calls and depth $0.86 \log_2 t$, thereby saving $25\%$ in the number of calls and $14\%$ in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree.
For the aggressive variant, we reduce the proof length to a $29\%$ overhead compared to Merkle trees ($1.29\log_2 t$ vs $\log_2 t$), but the verification time is now 14\% faster ($0.86\log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid $t$-block message.
Laia Amorós, Annamaria Iezzi, Kristin Lauter, Chloe Martindale, Jana Sotáková
Ahmet Sinak
Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla
We then construct incrementally verifiable computation (IVC) from folding schemes by using a "verifier circuit" that at each recursive step folds an entire R1CS instance representing computation (including a copy of the verifier circuit) at its prior step into a running relaxed R1CS instance. A distinctive aspect of our approach to IVC is that it achieves the smallest verifier circuit (a key metric to minimize in IVC) in the literature: the circuit is constant-sized and its size is dominated by two group scalar multiplications. We then show that the running relaxed R1CS instance can be proven in zero-knowledge with a succinct proof using a variant of an existing zkSNARK.
Putting these together, we obtain Nova, a new zero-knowledge proof system for incremental computations, where for an $N$-sized computation with $C$-sized steps, the prover runs in $O_\lambda(N)$ time to produce $O_\lambda(\log{C})$-sized proofs that can be verified in $O_\lambda(C)$ time. Nova does not require a trusted setup nor performs FFTs, so it can be efficiently instantiated with any cycles of elliptic curves where DLOG is hard. Furthermore, at each step, the prover time is dominated by two $\approx$$C$-sized multiexponentiations. Finally, Nova can achieve $O_\lambda(\log{C})$ verification time at the cost of employing a pairing-friendly elliptic curve where SXDH is hard.