Repository navigation
Closed
Description
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}).
Metadata
Metadata
Assignees
Labels
No labels
Activity
tobiasBora commentedon Mar 20, 2023
Actually, François Dupressoir (thanks!) made me realize that I don't need to nest equiv, I can prove instead:
But I'm not sure, maybe other use cases could benefit from nested equiv statements.
fdupress commentedon Mar 20, 2023
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 ofequivs: running a pWhile programme cannot create new modules or change the semantics of existing modules.chdoc commentedon Mar 30, 2023
In that case, maybe a proper error message is all that is required? Something along the lines of:
"Nested
equivjudgments are not supported. Please use implications betweenequivjudgments instead." (When writing down nested judgments, not when trying to usetransitivity)oskgo commentedon Feb 5, 2026
Fixed by #789