Skip to content

Transitivity: can't nest equiv, needed if equiv is part of an assumption #357

Closed

Description

@tobiasBora

In order to prove equivalence between definitions, I want to prove that A ~ D assuming that B ~ C. However, the transitivity rules does not seem to support this use-case: if I do:

lemma LeftOrRightImpliesMorRandom:
equiv [LibEncryptMessage.encrypt ~ LibEncryptRandom.encrypt : equiv [LibEncryptFirst.encryptOneOfTwo ~ LibEncryptSecond.encryptOneOfTwo : true ==> res{1} = res{2}] /\ m{1} = m{2}  ==> ={res}]. (* ={res} is a shortcut for res{1} = res{2} *)
    proof.
      transitivity LibEncryptMessageUsingSubroutine(LibEncryptFirst).encrypt
        (m{1} = m{2} ==> ={res})
        (m{1} = m{2} /\ equiv [LibEncryptFirst.encryptOneOfTwo ~ LibEncryptSecond.encryptOneOfTwo : true ==> ={res}] ==> ={res}).

then I get an error:

anomaly: EcPV.MemoryClash

Am I missing something? Or can I somehow define an equivalence with respect to another memory than &1 and &2?

Full compilable MWE:

require import Real Bool DBool Int Distr.

type key.
type msg.
type cip.
op [lossless] gen: key distr. (* generates axiom gen_ll*)
op enc: key -> msg -> cip.
op dec: key -> cip -> msg.
op [lossless] randomMessage: msg distr.

(*
  Technically we don't need types (we can just omit them), but this will be useful later when defining hybrids.
  (to exchange a library with the other.)
*)
module type ENC_ONE_OF_TWO = {
  proc encryptOneOfTwo (mLeft: msg, mRight: msg) : cip
}.

module LibEncryptFirst : ENC_ONE_OF_TWO = {
  (* Called eavesdrop in the example *)
  proc encryptOneOfTwo (mLeft: msg, mRight: msg) : cip = {
    var k: key;
    var c: cip;
    k <$ gen;
    c <- enc k mLeft;
    return c;
  }
}.

module LibEncryptSecond : ENC_ONE_OF_TWO = {
  (* Called eavesdrop in the example *)
  proc encryptOneOfTwo (mLeft: msg, mRight: msg) : cip = {
    var k: key;
    var c: cip;
    k <$ gen;
    c <- enc k mRight;
    return c;
  }
}.

module LibEncryptMessage = {
  (* Called eavesdrop in the example *)
  proc encrypt (m: msg) : cip = {
    var k: key;
    var c: cip;
    k <$ gen;
    c <- enc k m;
    return c;
  }
}.

module LibEncryptRandom = {
  (* Called eavesdrop in the example *)
  proc encrypt (m: msg) : cip = {
    var k: key;
    var c: cip;
    k <$ gen;
    m <$ randomMessage;
    c <- enc k m;
    return c;
  }
}.

(* We define now hybrids *)


print ENC_ONE_OF_TWO.

module LibEncryptMessageUsingSubroutine (EncLibraryOneOfTwo: ENC_ONE_OF_TWO) = {
  (* Called eavesdrop in the example *)
  proc encrypt (m: msg) : cip = {
    var mRandom: msg;
    var cipher: cip;
    mRandom <$ randomMessage;
    cipher <@ EncLibraryOneOfTwo.encryptOneOfTwo (m, mRandom);
    return cipher;
  }
}.


lemma LeftOrRightImpliesMorRandom:
equiv [LibEncryptMessage.encrypt ~ LibEncryptRandom.encrypt : equiv [LibEncryptFirst.encryptOneOfTwo ~ LibEncryptSecond.encryptOneOfTwo : true ==> res{1} = res{2}] /\ m{1} = m{2}  ==> ={res}]. (* ={res} is a shortcut for res{1} = res{2} *)
    proof.
      transitivity LibEncryptMessageUsingSubroutine(LibEncryptFirst).encrypt
    (m{1} = m{2} ==> ={res})
    (m{1} = m{2} /\ equiv [LibEncryptFirst.encryptOneOfTwo ~ LibEncryptSecond.encryptOneOfTwo : true ==> ={res}] ==> ={res}).

Activity

  1. tobiasBora commented on Mar 20, 2023

    @tobiasBora
    Author

    Actually, François Dupressoir (thanks!) made me realize that I don't need to nest equiv, I can prove instead:

    lemma LeftOrRightImpliesMorRandom:
    equiv [LibEncryptFirst.encryptOneOfTwo ~ LibEncryptSecond.encryptOneOfTwo : true ==> res{1} = res{2}]  => equiv [LibEncryptMessage.encrypt ~ LibEncryptRandom.encrypt : m{1} = m{2}  ==> ={res}].
    

    But I'm not sure, maybe other use cases could benefit from nested equiv statements.

  2. fdupress commented on Mar 20, 2023

    @fdupress
    Member

    The anomaly is a bug by itself, regardless of whether we want to support nested equivs.

    Regarding that point, there is nothing that could be done using nested equivs that could not be done using implications of equivs: running a pWhile programme cannot create new modules or change the semantics of existing modules.

  3. chdoc commented on Mar 30, 2023

    @chdoc
    Contributor

    In that case, maybe a proper error message is all that is required? Something along the lines of:
    "Nested equiv judgments are not supported. Please use implications between equiv judgments instead." (When writing down nested judgments, not when trying to use transitivity)

  4. oskgo commented on Feb 5, 2026

    @oskgo
    Contributor

    Fixed by #789

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions