Paper 2023/295

Randomized Half-Ideal Cipher on Groups with applications to UC (a)PAKE

Bruno Freitas Dos Santos, University of California, Irvine
Yanqi Gu, University of California, Irvine
Stanislaw Jarecki, University of California, Irvine

An Ideal Cipher (IC) is a cipher where each key defines a random permutation on the domain. Ideal Cipher on a group has many attractive applications, e.g., the Encrypted Key Exchange (EKE) protocol for Password Authenticated Key Exchange (PAKE) [10], or asymmetric PAKE (aPAKE) [40, 36]. However, known constructions for IC on a group domain all have drawbacks, including key leakage from timing information [15], requiring 4 hash-onto-group operations if IC is an 8-round Feistel [27], and limiting the domain to half the group [12] or using variable-time encoding [56, 48] if IC is implemented via (quasi-) bijections from groups to bitstrings [40]. We propose an IC relaxation called a (Randomized) Half-Ideal Cipher (HIC), and we show that HIC on a group can be realized by a modified 2-round Feistel (m2F), at a cost of 1 hash-onto-group operation, which beats existing IC constructions in versatility and computational cost. HIC weakens IC properties by letting part of the ciphertext be non-random, but we exemplify that it can be used as a drop-in replacement for IC by showing that EKE [10] and aPAKE of [40] realize respectively UC PAKE and UC aPAKE even if they use HIC instead of IC. The m2F construction can also serve as IC domain extension, because m2F constructs HIC on domain D from an RO-indiferrentiable hash onto D and an IC on 2κ-bit strings, for κ a security parameter. One application of such extender is a modular lattice-based UC PAKE using EKE instantiated with HIC and anonymous lattice-based KEM.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
ideal cipherauthenticated key exchangepassword authenticated key exchangePAKEaPAKE
Contact author(s)
s brunofreitas @ pm me
yanqig1 @ uci edu
stanislawjarecki @ gmail com
2023-02-28: last of 2 revisions
2023-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bruno Freitas Dos Santos and Yanqi Gu and Stanislaw Jarecki},
      title = {Randomized Half-Ideal Cipher on Groups with applications to UC (a)PAKE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/295},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.