## In this issue

1. [2024/556] Menhir: An Oblivious Database with Protection ...
2. [2024/557] Permutation-Based Hash Chains with Application to ...
3. [2024/769] Time-Based Cryptography From Weaker Assumptions: ...
4. [2024/776] Instance-Hiding Interactive Proofs
5. [2024/777] Measure-Rewind-Extract: Tighter Proofs of One-Way ...
6. [2024/778] Ideal-to-isogeny algorithm using 2-dimensional ...
7. [2024/779] Elliptic Curve Cryptography for the masses: Simple ...
8. [2024/780] Information-theoretic Multi-server Private ...
9. [2024/781] Doubly-Efficient Batch Verification in Statistical ...
10. [2024/782] Relating Code Equivalence to Other Isomorphism Problems
11. [2024/783] Differential Cryptanalysis on Quantum Computers
12. [2024/784] Universal Blockchain Assets
13. [2024/785] SmartBean: Transparent, Concretely Efficient, ...
14. [2024/786] Modelling Ciphers with Overdefined Systems of ...
15. [2024/787] A new attack against search-LWE using Diophantine ...
16. [2024/788] A Fault-Resistant NTT by Polynomial Evaluation and ...
17. [2024/789] FairSec: Fair and Maliciously Secure Circuit-PSI ...
18. [2024/790] Physical Ring Signature
19. [2024/791] Minimize the Randomness in Rasta-Like Designs: How ...
20. [2024/792] Stickel's Key Agreement Algebraic Variation
21. [2024/793] Hide-and-Seek and the Non-Resignability of the BUFF ...
22. [2024/794] Detecting Rogue Decryption in (Threshold) ...
23. [2024/795] New Limits of Provable Security and Applications to ...
24. [2024/796] Weak Consistency mode in Key Transparency: OPTIKS
25. [2024/797] Nonadaptive One-Way to Hiding Implies Adaptive ...
26. [2024/798] Incompressible Functional Encryption
27. [2024/799] Symmetric Signcryption and E2EE Group Messaging in ...
28. [2024/800] A Note on Zero-Knowledge for NP and One-Way Functions
29. [2024/801] Algebraic Structure of the Iterates of $\chi$
30. [2024/802] On Maximum Size Simultaneous Linear Approximations ...
31. [2024/803] Can We Beat Three Halves Lower Bound?: ...
32. [2024/804] Analysis on Sliced Garbling via Algebraic Approach
33. [2024/805] DiTRU: A Resurrection of NTRU over Dihedral Group
34. [2024/806] Resettable Statistical Zero-Knowledge for NP
35. [2024/807] Optimal Consensus in the Presence of Overlapping ...
36. [2024/808] Arma: Byzantine Fault Tolerant Consensus with ...
37. [2024/809] Reducing Overdefined Systems of Polynomial ...
38. [2024/810] The Perils of Limited Key Reuse: Adaptive and ...
39. [2024/811] Traceable Secret Sharing Based on the Chinese ...
40. [2024/812] Relations among new CCA security notions for ...
41. [2024/813] How to Redact the Bitcoin Backbone Protocol
42. [2024/814] Succinct Homomorphic Secret Sharing
43. [2024/815] Faster verifications and smaller signatures: Trade- ...
44. [2024/816] Zero-knowledge IOPs Approaching Witness Length
45. [2024/817] DVA: Dangerous Variations of ALTEQ
46. [2024/818] The Brave New World of Global Generic Groups and ...
47. [2024/819] A new stand-alone MAC construct called SMAC
48. [2024/820] Rate-1 Arithmetic Garbling from Homomorphic Secret- ...
49. [2024/821] A General Framework for Lattice-Based ABE Using ...
50. [2024/822] Early Stopping Byzantine Agreement in ...
51. [2024/823] Batched Distributed Point Function from Sparse LPN ...
52. [2024/824] Improved Meet-LWE Attack via Ternary Trees

## 2024/556

* Title: Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage
* Authors: Leonie Reichert, Gowri R Chandran, Phillipp Schoppmann, Thomas Schneider, Björn Scheuermann
* [Permalink](https://eprint.iacr.org/2024/556)
* [Download](https://eprint.iacr.org/2024/556.pdf)

### Abstract

Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of information leaks, access patterns and volume patterns, allow for database reconstruction attacks.

In this paper, we present Menhir, an oblivious TEE database that hides access patterns with ORAM guarantees and volume patterns through differential privacy. The database allows range and point queries with SQL-like WHERE-clauses. It builds on the state-of-the-art oblivious AVL tree construction Oblix (S&P'18), which by itself does not protect against volume leakage. We show how volume leakage can be exploited in range queries and improve the construction to mitigate this type of attack. We prove the correctness and obliviousness of Menhir. Our evaluation shows that our approach is feasible and scales well with the number of rows and columns in the database.

## 2024/557

* Title: Permutation-Based Hash Chains with Application to Password Hashing
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/557)
* [Download](https://eprint.iacr.org/2024/557.pdf)

### Abstract

Hash chain based password systems are a useful way to guarantee authentication with one-time passwords. The core idea is specified in RFC 1760 as S/Key. At CCS 2017, Kogan et al. introduced T/Key, an improved password system where one-time passwords are only valid for a limited time period. They proved security of their construction in the random oracle model under a basic modeling of the adversary. In this work, we make various advances in the analysis and instantiation of hash chain based password systems. Firstly, we describe a slight generalization called U/Key that allows for more flexibility in the instantiation and analysis, and we develop a security model that refines the adversarial strength into offline and online complexity, that can be used beyond the random oracle model, and that allows to argue multi-user security directly. Secondly, we derive a new security proof of U/Key in the random oracle model, as well as dedicated and tighter security proofs of U/Key instantiated with a sponge construction and a truncated permutation. These dedicated security proofs, in turn, solve a problem of understanding the preimage resistance of a cascaded evaluation of the sponge construction. When applied to T/Key, these results improve significantly over the earlier results: whereas the originally suggested instantiation using SHA-256 uses a compression function that maps 768 bits into 256 bits, with a truncated permutation construction one can generically achieve 128 bits of security already with a permutation of size 256 bits.

## 2024/769

* Title: Time-Based Cryptography From Weaker Assumptions: Randomness Beacons, Delay Functions and More
* Authors: Damiano Abram, Lawrence Roy, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/769)
* [Download](https://eprint.iacr.org/2024/769.pdf)

### Abstract

The assumption that certain computations inherently require some sequential time has established itself as a powerful tool for cryptography. It allows for security and liveness guarantees in distributed protocols that are impossible to achieve with classical hardness assumptions. Unfortunately, many constructions from the realm of time-based cryptography are based on new and poorly understood hardness assumptions, which tend not to stand the test of time (cf.. Leurent et al. 2023, Peikert & Tang 2023).
In this work, we make progress on several fronts. We formally define the concept of a delay function and present a construction thereof from minimal assumptions. We show that these functions, in combination with classical cryptographic objects that satisfy certain efficiency criteria, would allow for constructing delay encryption, which is otherwise only known to exist based on a new hardness assumption about isogenies. We formally define randomness beacons as they are used in the context of blockchains, and we show that (linearly homomorphic) time-lock puzzles allow for efficiently constructing them.
Our work puts time-based cryptography on a firmer theoretical footing, provides new constructions from simpler assumptions, and opens new avenues for constructing delay encryption.

## 2024/776

* Title: Instance-Hiding Interactive Proofs
* Authors: Changrui Mu, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/776)
* [Download](https://eprint.iacr.org/2024/776.pdf)

### Abstract

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties, and may be seen as a generalization of the influential concept of Randomized Encodings [Ishai et al. FOCS 00, Applebaum et al. FOCS 04, Agrawal et al. ICALP 15], and as a counterpart to Zero-Knowledge proofs [Goldwasser et al. STOC 89].

We investigate the properties and power of such instance-hiding proofs, and show the following:
1. Any language with an IHIP is contained in AM/poly and coAM/poly.
2. If an average-case hard language has an IHIP, then One-Way Functions exist.
3. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof.
4. IHIP's are closed under composition with any efficiently computable function.